What are the relations between pushdown automata and parsers?

Question

For a CFG, there is a pushdown automaton; vice versa.

For a CFG, there is a parser; and I guess vice versa?

What are the relations between pushdown automata and parsers? Are they directly related? Can they be derived from each other?

What are the relations between pushdown automata and parser generators (e.g. Yacc)?

Thanks.

Answer 1

No, there are parsers for languages that are not context-free, in particular, context-sensitive languages.

Since non-deterministic pushdown automata are equivalent to CFGs and there exist parsers for context-sensitive languages, then no, NDPAs are not equivalent to parsers.

See the first paragraph above; the link refers to parser generators.

Answer 2

There is usually a pushdown automata at the core of every programming language parser, at least implicitly (e.g parsers based on recursive-descent do not have an explicitly-coded pushdown automaton). YACC is one tool for generating such parsers from grammar definitions. The pushdown automaton is used to verify that a given program is syntactically correct.

However, it should be noted that parsers for real programming languages do more than check syntax. For example, verifying the internal datatype consistency of expressions is outside the scope of what can be expressed (easily) with syntax alone. In that sense, parsers generally exceed pushdown automata.