6.3 LR Shift-Reduce and Syntax Trees: Reconstructing Structure from Prefixes on the Stack

Recursive descent predicts from the start symbol. An LR parser works from the input, using its state and lookahead to decide when to shift and when to reduce a handle on the stack to a nonterminal. Merely matching a production’s right-hand side is not enough to justify a reduction; the state table determines when it is valid. The parser maintains a viable prefix and constructs a rightmost derivation in reverse.

Learning Objectives

• Explain shift, reduce, accept, and error actions;
• Understand the purpose of LR items, closure, and goto;
• Distinguish between shift/reduce and reduce/reduce conflicts;
• Choose between CST, AST, or lossless tree, and preserve source code provenance.

1. Shift and Reduce

Grammar:

E → E + T | T
T → id

Step-by-step reduction process for input id + id:

Stack           Input          Action
               id + id $      shift id
id             + id $        reduce T → id
T              + id $        reduce E → T
E              + id $        shift +
E +            id $          shift id
E + id         $             reduce T → id
E + T          $             reduce E → E + T
E              $             accept

A real LR parser stack also maintains the automaton state. The ACTION table selects actions based on the top-of-stack state and the lookahead symbol. After a reduction, the GOTO table determines the next state based on the new top-of-stack state and the left-hand nonterminal of the rule.

2. LR Item Represents Progress in a Production

An item places a dot on the right side of a production:

E → E · + T

This indicates that E has been recognized, and the next expected symbol is + T. If the dot appears before a nonterminal, closure adds items whose left-hand side is that nonterminal, with the dot at the start of each right-hand side, and continues until no new items appear. After reading a grammar symbol, the goto operation advances the dot past that symbol and recomputes the closure.

A set of items forms a deterministic finite automaton (DFA): each state represents the current prefix of the grammar that has been recognized. LR(1) items additionally carry a lookahead token, which determines on which input tokens a reduction should occur after completing a production.

SLR uses each nonterminal’s global FOLLOW set for reduction lookaheads. Canonical LR(1) carries lookahead in each item and propagates it through closure using FIRST of the suffix followed by the existing lookahead. LALR typically merges states with the same LR(0) core and unions their lookaheads. Table sizes and supported grammar classes therefore differ. They cannot all be broadly considered the same "LR" construct.

3. Two Kinds of Conflicts

Shift/Reduce

A single table entry may either shift a lookahead token or reduce using a rule. A classic example is a dangling else: when encountering else, you can either reduce the if without an else clause, or shift it and combine it with the most recent if.

Reduce/Reduce

The same table entry may apply two different production rules for reduction, indicating that the current stack state can be interpreted in two distinct ways. This kind of conflict is generally harder to resolve using simple precedence rules.

Tools often allow developers to declare operator precedence and associativity to resolve expression conflicts. Inspect the actual conflicting states and productions, not just whether the conflict count matches expectations; silently suppressing new conflicts with a "shift always" rule can lead to unexpected changes in language behavior as the grammar evolves.

4. Bison-Style Semantic Actions

This is a grammar-and-action fragment, not a complete .y file. Enable %locations, declare tokens and semantic-value types, and provide the lexer, yyerror, and AST constructors before generating and compiling it. Only addition and multiplication productions are present; the subtraction and division declarations leave room for later extensions:

%left '+' '-'
%left '*' '/'

%%
expr:
      expr '+' expr { $$ = make_binary($1, PLUS, $3, @$); }
    | expr '*' expr { $$ = make_binary($1, STAR, $3, @$); }
    | '(' expr ')'  { $$ = with_span($2, @$); }
    | NUMBER        { $$ = make_number($1, @$); }
    ;

$1 and $3 refer to right-hand-side semantic values, and $$ is the result for the left-hand side. In Bison, @$ is the location of the rule’s result; its location type is configurable. Later precedence declarations bind more tightly, so multiplication outranks addition here, and %left resolves equal-precedence conflicts with left associativity. Failures, exceptions, and error recovery within semantic actions must adhere to the parser runtime's stack cleanup conventions; otherwise, node leaks may occur.

Priority declarations in the grammar are compact, but hierarchical nonterminals are generally more easily understood by a variety of parsers and readers. The choice should balance readability of language specifications with tooling diagnostics.

5. CST, AST, and Lossless Syntax Tree

Structure	Typically Preserves	Primary Use Cases
CST	Grammar nodes, punctuation, parentheses	Explains the parsing process
AST	Semantic expressions, declarations, statements	Type checking, IR generation
Lossless tree	All tokens, whitespace, comments, error nodes	Formatting, IDEs, refactoring

An AST can omit parenthetical nodes because the tree structure already encodes operator precedence. However, if a tool needs to preserve the user's original syntax, it must retain parentheses and trivia in other representations. There is no single syntax tree that is optimal for all consumers.

6. Source Locations Should Not Be Attached Only to Leaves

The span of a binary expression node typically extends from the start of the left operand to the end of the right operand; the operator token has its own span. This allows:

• To report the entire erroneous expression;
• To precisely highlight the operator;
• Track spelling and expansion locations during macro expansion;
• To enable optimized nodes to map back to the original source structure.

Synthesized nodes and missing tokens need zero-length or explicitly synthetic spans. Diagnostic rendering must recognize these cases to avoid generating inverted or out-of-bounds ranges.

7. LR Error Recovery Is Not Inherently Worse

LR parsers can use the special error symbol, pop the stack to a state that can shift it, and discard input until a synchronization token is reached. Modern implementations also support local recovery and generation of expected token sets.

The diagnostic quality of both LL and LR parsers primarily depends on the grammar, state information, recovery algorithms, and human design, so it's incorrect to generalize that "LL is good and LR is bad." While LR states are harder to map directly to user-level concepts, they also contain precise information about feasible prefixes.

8. How to Choose a Parsing Strategy

• When the grammar is predictable, and the team values hand-written control and custom diagnostics: use recursive descent or Pratt parsing.
• When working with mature LR grammars and needing to handle left recursion or broader grammar classes: use an LR parser generator.
• When ambiguity must be preserved or natural-language-style grammars are involved: use generalized algorithms like GLR or Earley.
• When ordered choice fits the language: consider PEG. It does not preserve multiple parses, but an alternative may fail and cause input to be retried with the next alternative. Packrat memoization avoids repeated parsing work; ordered choice differs from CFG alternatives.

Before selecting a parser, establish clear requirements for language semantics, error recovery, incremental updates, and toolchain compatibility, don’t just compare tables that list support for more grammar types.

Common Misconceptions

• LR parsers generate leftmost derivations from left to right: This actually constructs the reverse of a rightmost derivation.
• Any conflict indicates linguistic ambiguity: Conflicts may arise from state merging in a chosen LR variant, or they might be resolvable with a stronger lookahead.
• Priority declarations automatically conform to language semantics: Incorrect declaration order can consistently produce erroneous semantics.
• ASTs that drop punctuation allow all tools to reuse them: Source-code tools typically require lossless trees or token mappings.

Exercise

1. Manually trace the shift/reduce actions for id + id.
2. Define precedence and associativity rules for +, *, and right-associative ^.
3. Explain what parse trees result from the two shift/reduce choices in the grammar for dangling else.
4. Choose a tree structure for three consumer types (compiler, formatter, and IDE) and justify the trade-offs of each choice.

Summary

An LR parser encodes grammar prefixes into states and executes shifts and reductions on a state stack. Conflicts must be interpreted, not suppressed; semantic actions transform reduction results into ASTs or other tree structures. Whether choosing LL or LR, source location tracking and error recovery are core capabilities, not afterthoughts.

The next chapter will establish relationships between symbols and types on trees, then lower the high-level structure into a more analyzable and code-generating intermediate representation.

References

• Bison: operator precedence
• Bison: error recovery
• Bryan Ford: Parsing Expression Grammars