Implement an LR(1) Parser Table by Hand for a Small Grammar

LR(1) Tables Encode Shift-Reduce Parsing

Yacc and Bison generate LR parsers from grammars. An LR(1) table maps (state, lookahead) to shift, reduce, accept, or error actions. GCC's old Java parser and many language specs use LR because it handles left recursion and large grammars mechanically.

Building the Table by Hand

For a small grammar, compute item sets: dotted productions like E -> E . + T. Closure adds items implied by nonterminals after the dot. GOTO maps states on nonterminals; ACTION maps states on terminals. Conflicts (shift/reduce) reveal grammar ambiguity.

cCopy
Loading…

• Shift pushes terminal and new state
• Reduce pops RHS, pushes LHS, GOTO
• Accept when S' -> S . and lookahead is $
• LR(1) lookahead resolves many LR(0) conflicts

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will construct an LR(1) parser table by hand for a small expression grammar. This exercise asks you to compute item sets, fill ACTION and GOTO tables, and trace parse steps on sample input.