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

Another parser doesn't descend from the start symbol by prediction, it reads tokens and simultaneously identifies completed structures from the top of the stack.

Recursive descent parsers predict the next step from the start symbol. In contrast, LR parsers begin from the input: they shift tokens onto the stack until the right-hand side of a production rule appears at the top of the stack, then reduce it to its left-hand nonterminal. What they see is a "prefix that is feasible," and their goal is to reconstruct the reverse of the rightmost derivation.

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, the closure must include all productions that could begin with that nonterminal. 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, LALR, and canonical LR(1) use different methods to propagate or merge lookahead information, resulting in different table sizes and varying capabilities for handling grammars. 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. It's essential to verify that the number of conflicts 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

%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 are the semantic values of the right-hand symbol, while $$ is the result on the left. The position markers vary depending on tool configuration. 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;
• To track spelling versus expansion positions during macro expansion;
• To enable optimized nodes to map back to the original source structure.

Composite nodes and missing tokens require zero-length or 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 employ special error symbols, backtrack to an accepting state, and discard input until a synchronizing token is encountered. 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 you need deterministic, non-backtracking ordered choice: consider PEG, but be aware that its semantics for preference differ from traditional CFGs.

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.