Parser Table

A parser table is the data structure at the heart of every table-driven parser — LL, LR, and LALR alike. It encodes, for every possible combination of parser state and input token, the single action the parser should take: shift (push the token and advance), reduce (pop the stack and apply a grammar production), accept (signal success), or error (reject the input). In an LR parser, the table has two parts: an action table indexed by state and terminal, and a goto table indexed by state and non-terminal. The construction of these tables from a context-free grammar is the central algorithmic challenge of parser generation. The table's size and structure directly determine the parser's speed and memory footprint. When grammar ambiguity or insufficient lookahead causes the same state-token pair to map to multiple valid actions, the result is a shift-reduce or reduce-reduce conflict — a signal that the grammar exceeds the parser class's expressive power and must be refactored or the parser upgraded.