Shift, reduce, accept: building an LR parser from a grammar
The V8 page shows a hand-written parser. Most language tools instead generate their parser from a grammar: Bison, yacc, and the parsers inside PostgreSQL, Bash and GCC's old C front end. This page builds an SLR parser in front of us from any grammar we type: FIRST and FOLLOW sets, LR(0) item sets, the parsing table, and a step-by-step parse that grows its tree. Then we open real Bison and see the same machine in C.
The construction follows the Dragon Book (2nd ed., Sections 4.4.2 and 4.6). For the expression grammar it reproduces the book's twelve states, SLR table (Fig. 4.37) and moves for id * id + id (Fig. 4.38) exactly; we checked that before publishing. The Bison boxes are real files and real output from GNU Bison 3.8.2.
Why parse bottom-up
A top-down parser, like V8's, guesses which rule to use from the next token and calls a function per rule. An LR parser waits: it shifts tokens onto a stack until the top of the stack matches the right-hand side of a rule, then reduces it to the rule's left-hand side. It finishes when the whole input has been reduced to the start symbol. Read backwards, the sequence of reductions is a rightmost derivation.
The hard part is knowing when to reduce. The answer is a finite automaton over "items", compiled into a table of ACTION and GOTO entries. That compilation is what a parser generator does, and it is what we watch below.
What it is. Our SLR(1) parser generator and driver: FIRST and FOLLOW, LR(0) items, the ACTION and GOTO table, and the parse. It drives every frame below.
Checked against. Every cell of Dragon Book Fig. 4.37 and every move of Fig. 4.38, the conflicts on the classic grammars, and GNU Bison 3.8.2's own conflict reports (verify/check-dragon-book.js).
Not covered. LALR(1) and canonical LR(1) tables (the Bison section shows real LALR output), error recovery, precedence declarations, and grammars written without spaces between symbols.
One rule per line: A -> x y | z. Symbols are separated by spaces. Anything never on a left-hand side is a terminal. Use ε for an empty alternative. The first rule's left side is the start symbol.
Augment the grammar, then compute FIRST and FOLLOW
We add a new start rule S' → S so that "reduce to S'" can only mean "accept". FIRST(X) is the set of terminals that can begin a string derived from X. FOLLOW(A) is the set of terminals that can appear immediately after A in some sentential form. SLR uses FOLLOW to decide where to place reduce actions.
LR(0) items, CLOSURE and GOTO
An item is a rule with a dot showing how much of it we have seen: E → E · + T means "we have an E and expect + T next". A state is a set of items. CLOSURE adds, for every nonterminal right after a dot, all of its rules with the dot at the start. GOTO(I, X) moves the dot over X in every item of I that allows it, then takes the closure. Starting from CLOSURE({S' → · S}) and applying GOTO until no new state appears gives the canonical collection.
Bold items are the kernel; the rest came from CLOSURE. Purple items have the dot at the end, which means a reduction is possible. Click a transition to see its target state.
The SLR parsing table
The rules are short. For an item A → α · a β with terminal a, ACTION[i, a] = shift to GOTO(i, a). For a complete item A → α ·, ACTION[i, b] = reduce by that rule for every b in FOLLOW(A). For S' → S ·, ACTION[i, $] = accept. GOTO entries come straight from the automaton. If any cell gets two actions, the grammar is not SLR(1), and the cell turns red.
sn = shift and go to state n · rn = reduce by rule n · acc = accept · blank = syntax error · right of the bar: GOTO
Run the parser on an input
The driver is the same for every LR parser (Dragon Book Algorithm 4.44): look at the state on top of the stack and the next input token, do what ACTION says, and on a reduce pop one entry per symbol of the rule, then push GOTO of the newly exposed state. The tree below is built from the reductions.
Inside a Bison-generated parser
We gave Bison the expression grammar and compiled the result with GCC. Bison builds LALR(1) tables rather than SLR. For this grammar they make the same parsing decisions, but Bison numbers states differently and adds one state for shifting the end-of-file token. The driver is the C function yyparse, and it is our Step button written with labels and goto.
Compare Bison's trace with ours. Bison reduces before reading the next token ("Reducing stack by rule 6" appears before "Reading a token"). That is a default reduction: when a state's only sensible action is one reduction, yypact says so and yydefault skips the lookahead. Our SLR driver always reads the lookahead first. The tables are also compressed into yypact, yytable and yycheck instead of a full two-dimensional array.
Conflicts: the dangling else, and where SLR is too weak
The dangling else. In if c1 then if c2 then s1 else s2, which if owns the else? The grammar allows both, so there is a state where the parser could either shift else or reduce the inner if. Load the "Dangling else" preset in the lab and find the red cell. Bison reports the same conflict and shows both derivations; by default it shifts, attaching else to the nearest if. Declaring precedence silences it.
SLR is not always enough. The classic Dragon Book grammar for C-style assignments (S → L = R | R, L → * R | id, R → L) is unambiguous, yet SLR gets a shift/reduce conflict on =: = is in FOLLOW(R), because of *R = …, even in the state where reducing L to R can never be followed by =. Load the "SLR fails" preset to see it. LALR computes lookaheads per state instead of per nonterminal, so Bison builds this grammar without any conflict.
Predict, then check
Exercises
- Add a right-associative power operator
P → F ^ P | Fand changeT → T * P | P. Predict the new number of states, then check in the lab. Parseid ^ id ^ idand confirm the tree groups to the right. - Dragon Book Exercise 4.6.2: build the SLR sets of items and table for
S → S S + | S S * | a. Is the grammar SLR? Verify with the lab, then withbison -v. - Install Bison (
sudo apt install bisonon Ubuntu or WSL), save the grammar from Frame 5, and runbison -v expr.y && gcc expr.c -o expr && ./expr. Match each line of the trace to a row of our SLR table. - Write a grammar with a reduce/reduce conflict, for example two nonterminals that both derive
idin the same context. Find the red cell in the lab and explain which reduction Bison picks (hint: the rule that appears first). - Open PostgreSQL's
gram.yand find its%left/%rightprecedence declarations. Which conflicts do they exist to resolve?
Exam-style questions, with model answers
Five questions in the style of a CSE420 exam. Every answer was produced or checked with this page's engine or real Bison. Write our answer on paper first, then open the model answer and mark ourselves honestly. The marks follow the usual pattern of university theory exams; they are not copied from any real paper.
S → S S + | S S * | a: augment it, construct the canonical collection of LR(0) items, and build the SLR parsing table. Is the grammar SLR(1)? (Dragon Book exercise 4.6.2.)Augmented: 0 S' → S, 1 S → S S +, 2 S → S S *, 3 S → a. FOLLOW(S) = { $, a, +, * }.
I0: S' → ·S S → ·S S + S → ·S S * S → ·a I1: S' → S· S → S ·S + S → S ·S * S → ·S S + S → ·S S * S → ·a I2: S → a· I3: S → S S ·+ S → S S ·* S → S ·S + S → S ·S * S → ·S S + S → ·S S * S → ·a I4: S → S S +· I5: S → S S *·
| State | + | * | a | $ | S |
|---|---|---|---|---|---|
| 0 | s2 | 1 | |||
| 1 | s2 | acc | 3 | ||
| 2 | r3 | r3 | r3 | r3 | |
| 3 | s4 | s5 | s2 | 3 | |
| 4 | r1 | r1 | r1 | r1 | |
| 5 | r2 | r2 | r2 | r2 |
Yes, it is SLR(1): no cell has two actions. (Generated by this page's engine; paste the grammar into the lab to see it.)
Marking: 1 for augmenting and numbering, 2 for the six item sets, 2 for the table, 1 for the conclusion.
a a + a *.| Stack | Input | Action |
|---|---|---|
| 0 | a a + a * $ | shift 2 |
| 0 a2 | a + a * $ | reduce S → a, goto 1 |
| 0 S1 | a + a * $ | shift 2 |
| 0 S1 a2 | + a * $ | reduce S → a, goto 3 |
| 0 S1 S3 | + a * $ | shift 4 |
| 0 S1 S3 +4 | a * $ | reduce S → S S +, goto 1 |
| 0 S1 | a * $ | shift 2 |
| 0 S1 a2 | * $ | reduce S → a, goto 3 |
| 0 S1 S3 | * $ | shift 5 |
| 0 S1 S3 *5 | $ | reduce S → S S *, goto 1 |
| 0 S1 | $ | accept |
Marking: 4 for the moves, 1 for showing the GOTO after each reduce.
S → A a | b A c | d c | b d a and A → d, compute FIRST and FOLLOW of S and A, and show that the grammar is not SLR(1).FIRST(S) = { b, d }, FIRST(A) = { d }. FOLLOW(S) = { $ }, FOLLOW(A) = { a, c }.
The state reached on d from I0 contains S → d · c and A → d ·. SLR puts "reduce A → d" on every token in FOLLOW(A), including c, which collides with the shift on c. Likewise, after b d the state holds S → b d · a and A → d ·, with a conflict on a. So there are two shift/reduce conflicts.
The grammar is still LALR(1): in the first state the only valid lookahead for A → d · is a, and in the second it is c, so per-state lookaheads separate the actions.
Marking: 2 for the sets, 2 for locating and explaining a conflict.
S → if E then S | if E then S else S | other. How does yacc/Bison resolve it by default, and how can the grammar author state the choice explicitly?After if E then if E then S, with else as the next token, the parser can either reduce the inner if E then S (so the else belongs to the outer if) or shift else (so it belongs to the inner one). Both choices give a valid parse, so the grammar is ambiguous and the table cell has two actions.
Bison reports "1 shift/reduce conflict" and resolves it by shifting, which matches each else with the nearest unmatched if, the rule in C and Java. To say this explicitly, declare %nonassoc THEN and then %nonassoc ELSE: ELSE gets higher precedence than the rule ending in THEN, so the conflict is resolved as a shift without a warning. The alternative is rewriting the grammar with matched and unmatched statements.
Marking: 2 for the two derivations, 1 for the default, 1 for a precedence fix.
S → L = R | R, L → * R | id, R → L have an SLR conflict, even though it is unambiguous? Why does LALR(1) not have it?In the state reached on L from the start, the items are S → L · = R and R → L ·. SLR reduces R → L on every token in FOLLOW(R). Because of S → L = R and L → * R, = is in FOLLOW(R), so the cell for = holds both "shift" and "reduce": a shift/reduce conflict.
But in this state, reducing to R can only finish a whole statement S → R, so the only valid lookahead is $. LALR(1) computes lookaheads per state, so it reduces only on $. Bison builds this grammar without warnings; its state 4 says '=' shift and $default reduce using rule 5 (R).
Marking: 2 for locating the conflict via FOLLOW(R), 2 for the per-state lookahead explanation.
Everything this page cites, by depth
The Bison skeleton is © the Free Software Foundation, GPL-3.0 with the Bison exception, quoted for study. All Bison outputs were produced with GNU Bison 3.8.2.