Pushdown Automata in Parsing

Why pushdown automata

  • pushdown automata are like finite automata, but also work with stack
  • parsing requires stack

Equivalence of expressive power:

regular expressions non-deterministic FA
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 correspond to efficient one-pass parsing algorithms

  • typically sufficient for parsing programming languages

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

There are more general deterministic pushdown automata

  • one example are LR(1) parsers