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

Topic Overview

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.

Your Task

Build the LR parse table for a small expression grammar by hand, encode it as ACTION/GOTO arrays, and drive it with the standard shift-reduce loop. For each input, print the reductions the parser performs: for a correct table, that sequence is the rightmost derivation in reverse.

Grammar

cCopy
Loading…

n stands for a number token.

Input

One expression per line; blank lines are ignored. Tokens: a run of digits is n; +, *, (, ) are themselves; spaces and tabs are ignored. Any other character is a token that has no ACTION entry anywhere, so it causes a rejection.

Output

One line per input, starting with the input line exactly as given:

cCopy
Loading…

• For an accepted input, list every reduction in the order performed, written E->E+T, E->T, T->T*F, T->F, F->(E), F->n, then ACCEPT.
• For a rejected input print only the rejection: K is the 1-based index of the token that has no ACTION entry (TOK is its text; a number prints as its digits), or at end if the end-of-input marker $ is what the parser could not handle.

You may build the canonical LR(1) collection, or the smaller LALR(1)/SLR(1) tables: for this grammar they accept the same inputs, perform the same reductions, and detect errors at the same token, so the output does not depend on your state numbering.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. ACTION[state][terminal] holding shift/reduce/accept/error, GOTO[state][nonterminal], and a stack of states.
2. On reduce by A → β: pop |β| states, then push GOTO[top][A].

Hidden tests cover nested parentheses, long chains of + and *, a single number, and errors in the middle (2 + * 3, (), 2 3) and at the end.