LR(1) parser

Basic idea

Canonical LR(1): each state remembers an exact 1-token lookahead, so it accepts every deterministic CFG. Tables are large; LALR(1) is the practical compromise that merges equivalent LR(1) states.

Key formulas

• Parse time: $O(n)$
• LR(1) item: $[A \to \alpha \cdot \beta, a]$ where $a$ is the lookahead.
• Strictly more powerful than SLR(1) / LALR(1); accepts all deterministic CFLs.

Siblings

• Earley parser
• LL1 parser
• LR(0) parser
• Parsing Expression Grammer (PEG) parser
• SLR(1) parser