LRparsers

LR parsers are a family of deterministic bottom-up parsers for context-free grammars. The LR acronym stands for Left-to-right input scanning and Rightmost derivation in reverse. They parse by reading the input tokens left to right and constructing a rightmost derivation of the input in reverse, using a pushdown automaton implemented as a parsing table and a stack of states. LR parsing is designed for grammars that are LR, meaning a deterministic parse is possible without backtracking.

In operation, the parser maintains two stacks: a stack of grammar symbols and a stack of parsing states. It repeatedly consults an action table using the current state and the next input token. Actions include shift (read a token and push a new state), reduce (apply a grammar production by popping symbols, pushing the left-hand side nonterminal, and performing a goto on the new top state), and accept when the start rule is reduced and input is consumed. If no action is defined, a syntax error is reported.

Variants of LR parsers differ in how much lookahead they use and how parsing tables are constructed. LR(0) uses no lookahead and often yields many conflicts. SLR(1) uses FOLLOW sets to decide reductions. Canonical LR(1) uses a dedicated lookahead for each item, offering the most expressive power but generating large tables. LALR(1) merges states with identical cores to reduce table size while retaining most of Canonical LR(1) power. The designation LR(k) refers to parsers that operate with k-token lookahead.

History and usage: LR parsing was advanced by Frank DeRemer in the 1960s and has become foundational in compiler design. Many modern parser generators, such as yacc and bison, produce LALR(1) parsers. LR parsers handle a wide range of programming language syntax, though some grammars require grammar rewriting or more general parsing approaches (e.g., GLR) when LR parsing is not feasible.