Table-Driven Parser

A table-driven parser is a parser whose control logic is encoded in a precomputed table rather than in a hand-written program. The parser operates as a generic engine that interprets the table, making it a virtual machine for parsing. LL and LR parsers are the canonical table-driven approaches: an LL parser uses a table indexed by non-terminal and lookahead terminal; an LR parser uses a table indexed by state and symbol.

The advantage of table-driven parsers is mechanical verifiability. Because the parsing logic is generated automatically from a formal grammar, the parser can be proved correct relative to the grammar. The disadvantage is rigidity. Table-driven parsers struggle with context-sensitive constructs, semantic predicates, and ad hoc disambiguation rules that hand-written recursive descent parsers handle naturally.

Table-driven parsing treats grammar as specification and parser as implementation. This separation of concerns is elegant but fragile: real languages are rarely pure context-free, and the gap between formal grammar and actual syntax is where table-driven parsers accumulate their most painful complexity.