# Pushdown Automata in Parsing

Pushdown automata are like finite automata, but also work with stack

- next state is given by:
- current state
- current input symbol read
- top of the stack

- within each step the automaton can pop a symbol or push a symbol onto stack

We have seen a pushdown automaton for top-down parsing in Interpreting LL Parsing Table

Why pushdown automata?

- parsing requires stack

Equivalence of expressive power:

regular expressions | non-deterministic FA |
---|---|

deterministic context-free grammars | deterministic pushdown automata |

context-free grammars | non-deterministic pushdown automata |

Non-deterministic and deterministic finite state automata are equally expressive

Non-deterministic pushdown automata are **more expressive** than non-deterministic ones

- we
**cannot**determinize pushdown automata in general

Deterministic automata can be used to construct efficient one-pass parsing algorithms

- typically sufficient for parsing programming languages
- for parsing mathematical formulas and natural languages, general grammars are more suitable (Earley Parser)