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)