Lesson 3.6 — Generalized LR: graph-structured stacks and shared packed parse forests

Techniques: Tomita's GLR algorithm with a graph-structured stack (GSS) and a shared packed parse forest (SPPF) (Tomita 1985/1991; Rekers 1992); right-nulled GLR (RNGLR) and binary RNGLR (BRNGLR) (Scott and Johnstone 2006; Scott, Johnstone and Economopoulos 2007); used by Bison %glr-parser, Elkhound and tree-sitter · Pebble implements: nothing; the optional lab G1 is a Tomita GLR parser that returns an SPPF · Lab: labs/ch03-lr-toolkit/glr/ (SPEC R9, contract parseGLR; lr glr) · Prerequisites: Lessons 3.1–3.5; parse-tree counting (Lesson 2.1) · Time: 4 hours

A conflict means the table offers two actions. Everything so far removed one of them. GLR keeps both: it runs every action, splitting the parse stack; stacks that die are dropped, stacks that reach the same state at the same position merge. The stacks form a graph (the GSS), and the trees they build share subtrees and pack alternatives (the SPPF), so an input with exponentially many parse trees is still parsed in polynomial time and space. On a deterministic grammar GLR behaves exactly like the LR parser it is built from; on an ambiguous one it returns all parses and leaves the choice to you.

1. Problem and motivation

Input: an LR table with conflicts (any method; LALR is common) for an arbitrary context-free grammar, and \(w\). Output: whether \(w \in L(G)\), and a compact representation of all its parse trees.

Tomita's GLR with a GSS and an SPPF

Lang's 1974 paper [Lan74] observed that a nondeterministic LR parser can be simulated by sharing stacks; Tomita made it practical for natural-language parsing in 1985 [Tom85, Tom91]: a graph-structured stack whose nodes are (state, input position) pairs, and a shared packed parse forest in which equal subtrees are one node and alternative derivations of the same span are packed under one node. Rekers' thesis [Rek92] cleaned up the forest construction and handled the \(\varepsilon\) cases carefully; it underlies the ASF+SDF/SGLR tools. In compilers, GLR is the escape hatch for grammars that are ambiguous or not LR(k) by nature: C and C++ declarations vs expressions (Elkhound, McPeak's C++ front end [MN04]), and incremental editor parsing (tree-sitter, which forks its stack on conflicts declared in the grammar [TS-docs]). Bison's %glr-parser [BISON-Manual] offers it with %dprec and %merge to choose among parses.

RNGLR and BRNGLR

Tomita's first algorithm only handles grammars without \(\varepsilon\)-productions; his version with \(\varepsilon\) fails to terminate or loses parses on hidden left recursion (\(A \Rightarrow^{+} \beta A \gamma\) with \(\beta \Rightarrow^{+} \varepsilon\)), a problem Nozohoor-Farshi first fixed [NF91]. Scott and Johnstone's right-nulled GLR (RNGLR) [SJ06] fixes it cleanly with a modified table: a reduction \(A \to \alpha\beta\) is also performed in the state after \(\alpha\) when \(\beta \Rightarrow^{*} \varepsilon\) ("right-nullable"), with the \(\varepsilon\)-part's forest precomputed, so no reduction ever needs to wait for an \(\varepsilon\)-reduction at the same position. Their binary RNGLR (BRNGLR) [SJE07] splits long reductions into steps of two symbols and brings the worst case from \(O(n^{p+1})\) down to \(O(n^3)\), the bound of CYK and Earley (Ch 4).

2. Definitions and algorithms

The input is \(w = t_1 \cdots t_n\) and \(t_{n+1} = \$\). The table may have conflicts; each cell is a set of actions.

Definition 3.6.1 (Graph-structured stack)

A GSS is a directed acyclic graph whose nodes are pairs \((s, i)\) of an LR state \(s\) and a level \(i \in \{0, \dots, n\}\) (the number of tokens consumed), with at most one node per pair. The root is \((q_0, 0)\). An edge \((s, i) \to (s', j)\) with \(j \le i\) is labelled by the forest node of the grammar symbol that took the parser from \(s'\) to \(s\), deriving \(t_{j+1} \cdots t_i\). The frontier \(U_i\) is the set of nodes at level \(i\). Every path from a frontier node to the root spells, in reverse, the symbols of one ordinary LR stack.

Definition 3.6.2 (Shared packed parse forest)

An SPPF for \(w\) has symbol nodes \((X, j, i)\) — \(X\) derives \(t_{j+1} \cdots t_i\), unique per triple — and, below each nonterminal symbol node, packed nodes \((A \to X_1 \cdots X_m;\ c_1, \dots, c_m)\) whose children \(c_k = (X_k, j_{k-1}, j_k)\) satisfy \(j_0 = j\), \(j_m = i\). A symbol node with several packed nodes is a local ambiguity. The trees represented by \((X, j, i)\) are: one leaf if \(X\) is a terminal; otherwise, for each packed node, every combination of one tree per child. \(\#(X, j, i)\) denotes their number.

Definition 3.6.3 (Right-nullable reductions [SJ06])

An item \([A \to \alpha \bullet \beta]\) with \(\beta \Rightarrow^{*} \varepsilon\) and \(\alpha \neq \varepsilon\) (or \(A \to \varepsilon\) with \(\alpha = \beta = \varepsilon\)) is right-nullable. The RN table adds, for each such item in a state \(I\) and each lookahead \(a\) in its lookahead set, the action reduce \((A, \lvert\alpha\rvert)\): pop \(\lvert\alpha\rvert\) edges and attach a precomputed \(\varepsilon\)-SPPF for \(\beta\).

Tomita's GLR with a GSS and an SPPF

Algorithm 3.6.4 (Tomita's GLR, ε-free grammars)

• Input: an LR table with action sets (any method), \(w\).
• Output: accept with the root \((S, 0, n)\) of an SPPF of all parse trees of \(w\), or reject at the first level where every stack died.
• Precondition: no \(\varepsilon\)-productions, no cycles \(A \Rightarrow^{+} A\) (otherwise infinitely many trees).
• Postcondition: Theorem 3.6.7: accepts iff \(w \in L(G)\); the SPPF represents exactly the parse trees of \(w\).
• Invariant: at the start of level \(i\), \(U_i\) contains a node \((s, i)\) for every state \(s\) reachable by a viable prefix \(\gamma\) with \(\gamma \Rightarrow^{*} t_1 \cdots t_i\) that the table can reach by shifting \(t_i\); after the reducer, \(U_i\) is closed under all reductions on lookahead \(t_{i+1}\).

Reference solution: solutions/labs/ch03-lr-toolkit/glr/GLR.cpp; oracle lr.glr_parse.

function GLR(ACTION, GOTO, w):
    U0 ← {(q0, 0)}
    for i = 0 .. n:                                  # t(n+1) = $
        a ← t(i+1)
        # reducer: saturate U_i under reductions on lookahead a
        work ← [(v, none) for v in U_i];  done ← ∅
        while work ≠ ∅:
            (v, via) ← pop work
            for each reduce A → X1…Xm in ACTION[state(v), a]:
                for each path v ← … of m edges (using the edge 'via' if given):
                    if (v, A → X1…Xm, path) ∈ done: continue;  add it to done
                    u_base ← last node of the path;  labels ← edge labels, left to right
                    node ← SymbolNode(A, level(u_base), i);  add Packed(A → X1…Xm, labels) to node
                    s' ← GOTO[state(u_base), A]
                    if (s', i) ∉ U_i:  create it with edge → u_base labelled node; push ((s', i), none)
                    elif no edge (s', i) → u_base labelled node:
                        add that edge; push ((s', i), that edge)          # re-reduce through it
        if i = n: accept iff some node of U_n has accept on $ and SymbolNode(S, 0, n) exists
        # shifter
        leaf ← SymbolNode(a, i, i + 1);  U_{i+1} ← ∅
        for each v in U_i, each shift s in ACTION[state(v), a]:
            add edge (s, i + 1) → v labelled leaf        # creating (s, i+1) if needed
        if U_{i+1} = ∅: reject at position i

Algorithm 3.6.5 (Counting and enumerating the trees of an SPPF)

• Input: an SPPF of an acyclic grammar and a symbol node.
• Output: \(\#(X, j, i)\) (or the trees themselves).
• Precondition: the SPPF is acyclic (no cycles \(A \Rightarrow^{+} A\) in \(G\)).
• Postcondition: Definition 3.6.2's count.
• Invariant: memoized values are final.

function Count(node):                                  # memoized
    if node is a terminal leaf: return 1
    return Σ over packed nodes p of node:  Π over children c of p: Count(c)

Provided in the lab as lr::countTrees (labs/ch03-lr-toolkit/provided/Print.cpp).

RNGLR and BRNGLR

Algorithm 3.6.6 (RNGLR, the changes to Algorithm 3.6.4 [SJ06])

• Input: the RN table (Definition 3.6.3) with action sets; \(w\).
• Output: as Algorithm 3.6.4, for every context-free grammar (\(\varepsilon\)-productions and hidden left recursion allowed; cyclic grammars produce cyclic forests).
• Precondition: the \(\varepsilon\)-SPPF of every nullable suffix \(\beta\) has been built once, before parsing.
• Postcondition: accepts iff \(w \in L(G)\).
• Invariant: every reduction pops at least one edge except the reductions of length 0, which are performed only when the node that enables them is created (never later), so no reduction at level \(i\) is ever missed or repeated.

changes to GLR:
  • reduce (A, m) with m = |α| pops m edges (m may be less than |αβ|), and the new
    packed node gets children labels(path) followed by the ε-SPPF of β
  • when a node (s, i) is created (by a shift or a reduction), queue its reductions of
    length 0 immediately, and queue reductions of length ≥ 1 only through the new edge
  • BRNGLR: a reduction of length m ≥ 3 is split into m − 1 binary steps through
    intermediate "memo" GSS nodes, so each step walks paths of length ≤ 2

3. Worked example

The flat expression grammar tests/ch02/Inputs/expr-ambiguous.grammar with its LALR table (Lesson 3.5 §3: conflicts in I8 and I9 on + and *), input id + id * id (two trees).

Tomita's GLR with a GSS and an SPPF on the example

One row per level (oracle glr_parse; a reduction is written state \(\xrightarrow{p}\) base → goto):

level \(i\)	lookahead	frontier \(U_i\) before reducing	reductions performed	\(U_i\) after	shifts
0	id	{0}	–	{0}	0 → 2
1	+	{2}	2 \(\xrightarrow{4}\) 0 → 3	{2, 3}	3 → 5
2	id	{5}	–	{5}	5 → 2
3	*	{2}	2 \(\xrightarrow{4}\) 5 → 8; then 8 \(\xrightarrow{1}\) 0 → 3 (the reduce half of the conflict in I8)	{2, 3, 8}	3 → 6 and 8 → 6 (both stacks shift *: node (6, 4) gets two edges)
4	id	{6}	–	{6}	6 → 2
5	$	{2}	2 \(\xrightarrow{4}\) 6 → 9; 9 \(\xrightarrow{2}\) 0 → 3 (via the edge to (3, 3)); 9 \(\xrightarrow{2}\) 5 → 8 (via the edge to (8, 3)); 8 \(\xrightarrow{1}\) 0 → 3	{2, 3, 8, 9}	accept in (3, 5)

At level 3 the stack splits: one path has reduced \(E + E\) and will shift * from I3 (tree \((\mathit{id} + \mathit{id}) * \mathit{id}\)), the other keeps \(E + E\) open and shifts * from I8 (tree \(\mathit{id} + (\mathit{id} * \mathit{id})\)). They merge at node (6, 4). At level 5, both paths reduce to \(E\) over \([0, 5]\) and reach the same GSS node (3, 5) through the same base (0, 0): the second reduction adds no edge, only a second packed node. The final GSS (the nodes of state 2, entered by shifting id and left only by reducing \(E \to \mathit{id}\), are omitted):

flowchart RL
  n35(["3 @5"]) -->|"E[0,5]"| n00(["0 @0"])
  n95(["9 @5"]) -->|"E[4,5]"| n64(["6 @4"])
  n85(["8 @5"]) -->|"E[2,5]"| n52(["5 @2"])
  n64 -->|"*[3,4]"| n33(["3 @3"])
  n64 -->|"*[3,4]"| n83(["8 @3"])
  n33 -->|"E[0,3]"| n00
  n83 -->|"E[2,3]"| n52
  n52 -->|"+[1,2]"| n31(["3 @1"])
  n31 -->|"E[0,1]"| n00

The SPPF (symbol nodes with their packed nodes; production numbers in parentheses):

symbol node	packed nodes
E[0,5]	(1) E[0,1] +[1,2] E[2,5] · (2) E[0,3] *[3,4] E[4,5]
E[0,3]	(1) E[0,1] +[1,2] E[2,3]
E[2,5]	(2) E[2,3] *[3,4] E[4,5]
E[0,1], E[2,3], E[4,5]	(4) id

\(\#E[0,5] = 1 \cdot 1 \cdot 1 + 1 \cdot 1 \cdot 1 = 2\) (Algorithm 3.6.5). With 12 operands the oracle and the lab count \(C_{11} = 58\,786\) trees in a forest of fewer than 200 nodes (ch03.GLR.SharingKeepsTheForestPolynomial).

RNGLR and BRNGLR on the example

Take \(S \to A\,S\,b \mid x\), \(A \to \varepsilon\): hidden left recursion (\(S \Rightarrow A\,S\,b \Rightarrow S\,b\)), \(L = x\,b^{*}\), one tree per sentence. Its LR(0) automaton has I0 \(= \{S' \to \bullet S,\ S \to \bullet A\,S\,b,\ S \to \bullet x,\ A \to \bullet\}\) and I1 \(= \mathrm{GOTO}(I0, A) = \{S \to A \bullet S\,b\}\) plus the same closure — and \(\mathrm{GOTO}(\mathrm{I1}, A) = \mathrm{I1}\) again; I2 \(= \{S \to A\,S \bullet b\}\) and I3 \(= \{S \to A\,S\,b \bullet\}\) follow on \(S\) and \(b\). On lookahead \(x\) both states shift \(x\) and reduce \(A \to \varepsilon\).

level-0 step	what happens	GSS at level 0
1	reduce \(A \to \varepsilon\) from (I0, 0)	new node (I1, 0), edge to (I0, 0) labelled A[0,0]
2	reduce \(A \to \varepsilon\) from (I1, 0)	GOTO(I1, A) = I1: the node exists, so only a self-loop edge (I1, 0) → (I1, 0) labelled A[0,0]
3	(a parser that makes a new stack instead of reusing (I1, 0) repeats step 2 forever)	—
4	shift \(x\) from (I0, 0) and (I1, 0)	level 1

With node sharing the GSS is finite but cyclic at level 0. At level 2, reducing \(S \to A\,S\,b\) walks the path b-edge, S-edge, A-edge from \((I3, 2)\); the A-edge is either the self-loop (base (I1, 0): one more nesting level) or the edge to (I0, 0) (base I0: outermost), so x b b is accepted with the single tree \(S \to A\,(S \to A\,(S \to x)\,b)\,b\), and the one \(\varepsilon\)-node A[0,0] is shared by every nesting level.

What RNGLR adds: in general, an \(\varepsilon\)-reduction can add an edge at level \(i\) after another node of level \(i\) was processed, and a reduction path from that node may need to traverse the new edge somewhere in its middle; Tomita's rule "re-reduce from the new edge's source" then misses parses, and naive stack copying loops (Bison, box below). RNGLR's RN table performs every reduction \(A \to \alpha\beta\) with nullable \(\beta\) as soon as \(\alpha\) is on the stack, attaching the precomputed \(\varepsilon\)-SPPF for \(\beta\), so that no reduction ever has to pass through an \(\varepsilon\)-edge created at the current level [SJ06]. For this grammar no item has a nullable non-empty suffix, the RN table equals the LR(0) table, and node sharing alone suffices; BRNGLR would perform the length-3 reduction \(S \to A\,S\,b\) as two binary steps.

Try it

lr glr tests/ch02/Inputs/expr-ambiguous.grammar id + id '*' id prints the tree count and the forest in the format above (after you do lab G1, or with -DPEBBLE_USE_SOLUTION=glr); ./course drill shift-reduce-trace --difficulty hard shows the deterministic path that precedence would pick.

Bison's GLR parser picks among parses with %dprec

Reproduce (bison 3.8.2, clang 23.1.2; any OS):

cat > dprec.y <<'EOF'
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define YYSTYPE char *
int yylex(void);
void yyerror(const char *s) { printf("error: %s\n", s); }
static char *node(char *a, const char *op, char *b) {
  char *s = malloc(strlen(a) + strlen(b) + 4);
  sprintf(s, "(%s%s%s)", a, op, b);
  return s;
}
%}
%glr-parser
%expect 4
%%
top: e              { printf("%s\n", $1); } ;
e: e '+' e          { $$ = node($1, "+", $3); } %dprec 2
 | e '*' e          { $$ = node($1, "*", $3); } %dprec 1
 | 'n'              { $$ = "n"; }
 ;
%%
static const char *in;
int yylex(void) { return *in ? *in++ : 0; }
int main(int argc, char **argv) { in = argv[1]; return yyparse(); }
EOF
bison -o dprec.c dprec.y
clang-23 -w -o dprec dprec.c
for w in n+n*n n*n+n n+n+n; do printf '%-6s ' $w; ./dprec $w; done

Output (complete):

n+n*n  (n+(n*n))
n*n+n  ((n*n)+n)
n+n+n  error: syntax is ambiguous

What to notice: the same four conflicts as §3, kept by %glr-parser (and acknowledged by %expect 4). For n+n*n the two parses differ at the root (rule 1 vs rule 2) and %dprec picks the higher one, so * binds tighter. For n+n+n both parses use rule 1 at the root: %dprec cannot decide, and Bison reports the ambiguity at runtime — the local ambiguity E[0,5] of §3 surfacing to the user. Associativity needs %merge or precedence declarations [BISON-Manual].

4. Invariants and correctness

Tomita's GLR with a GSS and an SPPF

Theorem 3.6.7 (GLR is correct for ε-free acyclic grammars [Tom91, Rek92])

For a grammar without \(\varepsilon\)-productions and cycles, and any LR(0)-based table (LR(0), SLR, LALR or canonical LR(1) with all conflicts kept), Algorithm 3.6.4 accepts \(w\) iff \(w \in L(G)\), and the trees represented by \((S, 0, n)\) are exactly the parse trees of \(w\).

Proof sketch (full proofs: [Rek92, ch. 1], and for the RNGLR generalization [SJ06, §4])

Simulation. Consider the nondeterministic LR parser that, in each configuration, may take any action of the cell. Its runs on \(w\) correspond one-to-one to rightmost derivations of \(w\) — every reduction it performs is valid for its stack (the items argument of Theorem 3.1.19 without the determinism step), and conversely every rightmost derivation is realized by the run that always picks the action the derivation needs (Lemma 3.2.11's argument, which only needs the needed actions to be present, not uniqueness). Sharing. Every stack of the nondeterministic parser after consuming \(t_1 \cdots t_i\) and saturating reductions is a path from some node of \(U_i\) to the root, and every such path is such a stack: shifting creates exactly the one-step extensions; a reduction pops a path and pushes one edge; merging nodes with equal (state, level) is sound because the future of a stack depends only on its top state and position (the LR table is consulted with the top state only). The reducer's worklist, with the "re-reduce through a new edge" rule, performs every reduction on every path exactly once: since there are no \(\varepsilon\)-rules, every edge leaving a level-\(i\) node goes to a lower level, so a path using a new edge must start at that edge's source. Forest. Each performed reduction adds one packed node to \((A, j, i)\) with the edge labels as children; by induction on \(i\) the symbol node \((X, j, i)\) represents exactly the derivations \(X \Rightarrow^{*} t_{j+1} \cdots t_i\) used by some run, and the root represents one tree per accepting run, i.e. per rightmost derivation, i.e. per parse tree.

Proposition 3.6.8 (Tomita's GLR is polynomial; the forest can hold exponentially many trees)

With \(p\) the length of the longest right side, Algorithm 3.6.4 runs in \(O(n^{p+1})\) time and the SPPF has \(O(n^{p+1})\) size; \(\#(S, 0, n)\) can be exponential in \(n\) (Catalan numbers for the flat expression grammar).

Proof

There are at most \(\lvert Q \rvert (n+1)\) GSS nodes, so at most \(\lvert Q \rvert^2 (n+1)^2\) edges: an edge's label is determined by its two nodes, because every transition into an LR state is on the same symbol (the state's accessing symbol) and the span is given by the two levels. A reduction of length \(m \le p\) from a node at level \(i\) follows paths whose \(m\) edges end at levels \(i \ge j_1 \ge \cdots \ge j_m\); there are \(O((\lvert Q\rvert\, n)^m)\) such paths per starting node, so \(O(n^{p})\) reductions per level and \(O(n^{p+1})\) in total; each adds at most one packed node with \(\le p\) children. For the flat grammar, the number of trees of \(\mathit{id}(+\mathit{id})^{k}\) is the Catalan number \(C_k = \frac{1}{k+1}\binom{2k}{k} = \Theta(4^k / k^{3/2})\) (count the root operator's position, as in Lesson 2.1), while the forest has \(O(k^2)\) symbol nodes.

RNGLR and BRNGLR

Theorem 3.6.9 (RNGLR is correct for all context-free grammars; BRNGLR is cubic [SJ06, SJE07])

RNGLR accepts exactly \(L(G)\) for every context-free grammar, and builds an SPPF representing all parse trees (a cyclic one if \(G\) has cycles); BRNGLR runs in \(O(n^3)\) time.

Proof sketch (full proofs: [SJ06, §4–5], [SJE07, §4])

The only place Algorithm 3.6.4 used \(\varepsilon\)-freedom is "a path through a new edge starts at the edge's source". With \(\varepsilon\)-reductions, new edges can appear from a level-\(i\) node to another level-\(i\) node, and a path through such an edge may start at another node, possibly created earlier — Tomita's \(\varepsilon\) version misses those or loops. Right-nulled reductions remove every reduction whose remaining right side is nullable from the end of a path: the reduction happens at the moment the non-nullable prefix is complete, so an \(\varepsilon\)-edge is never the first edge of a reduction path, and "reduce through the new edge only" becomes correct again. Scott and Johnstone prove that the RN table's extra reductions are exactly those the \(\varepsilon\)-closure would eventually perform. BRNGLR's binary splitting bounds the path length walked per step by 2, so each level costs \(O(n^2)\) and the parse \(O(n^3)\).

When it breaks. Tomita's algorithm on \(\varepsilon\)-rules with hidden left recursion loops or loses parses — and Bison's GLR, which does not implement RNGLR, loops on exactly that grammar (real-world box below). On cyclic grammars (\(A \Rightarrow^{+} A\)) the SPPF is cyclic and represents infinitely many trees; counting (Algorithm 3.6.5) is then undefined, and the lab excludes such grammars.

5. Complexity

Variables: \(n\) input length; \(p\) longest right side; \(\lvert Q \rvert\) LR states.

Technique	Time (worst)	Time (typical)	Space	Variables
Tomita GLR	\(O(n^{p+1})\) (Proposition 3.6.8)	linear on nearly deterministic grammars: one stack most of the time	GSS \(O(\lvert Q\rvert n)\) nodes; SPPF \(O(n^{p+1})\)	as above
RNGLR	\(O(n^{p+1})\)	as Tomita	as Tomita + \(\varepsilon\)-SPPFs	as above
BRNGLR	\(O(n^3)\)	as Tomita	\(O(n^3)\)	as above

Pathological input: \(\mathit{id}(+\mathit{id})^{k}\) in the flat grammar forces a split at every operator: the reducer does \(\Theta(k^2)\) reductions per level near the end and the forest has \(\Theta(k^2)\) symbol nodes, for \(C_k\) trees. At scale: the typical cost of GLR is that of the deterministic LR parser plus the ambiguous regions: McPeak and Necula's Elkhound switches between a plain LR loop and the GSS for exactly this reason, and report performance competitive with Bison's LALR parsers on deterministic input [MN04].

6. Variants and refinements

Tomita's GLR with a GSS and an SPPF

• Deterministic core + GLR on demand (Elkhound [MN04], Bison): run the plain LR loop while there is one stack and one action, switch to the GSS at a conflict — trade-off: near-LR speed, more complex code.
• Disambiguation filters (%dprec, %merge in Bison; dynamic precedence in tree-sitter; Klint–Visser filters in SDF) — trade-off: choose one tree early (smaller output) vs keep the forest (complete, but the consumer must choose).
• Error-tolerant GLR (tree-sitter): when all stacks die, recover by skipping or inserting while comparing costs across stacks — trade-off: always a tree, sometimes a surprising one (Lesson 3.7).

RNGLR and BRNGLR

• Nozohoor-Farshi's correction [NF91]: repeat \(\varepsilon\)-reductions until a fixed point — trade-off: correct, but more reductions than RNGLR.
• GLL (Scott and Johnstone 2010, Ch 4): the top-down analogue with a graph-structured call stack — trade-off: easier to hand-write and debug, same cubic bound with binarized SPPFs.

7. In real compilers

Tomita's GLR with a GSS and an SPPF

• Bison (3.8.2) data/skeletons/glr.c — yyglrShift, yyglrReduce, yysplitStack, yyprocessOneStack, and on ambiguity yyresolveValue, yymergeOptionSets, yyreportAmbiguity [BISON-src].
• tree-sitter (0.27.0) lib/src/parser.c — ts_parser__advance forks the stack (lib/src/stack.c) when a state has several actions that the grammar declared as conflicts, ts_parser__condense_stack merges and prunes versions, and ts_parser__select_tree compares alternatives using dynamic precedence and error cost [TS-parser].
• Elkhound (McPeak and Necula, CC 2004) — a GLR generator with a deterministic LR core, used for Elsa, a C++ front end [MN04].

tree-sitter forks on a declared conflict and chooses by dynamic precedence

Reproduce (tree-sitter-cli 0.27.0 via npm, Node 22; needs network for npx the first time):

export RUST_BACKTRACE=0 NO_COLOR=1
cat > grammar.js <<'EOF'
module.exports = grammar({
  name: 'decl',
  rules: {
    stmt: $ => choice($.declaration, $.expression_statement),
    declaration: $ => seq($.identifier, '*', $.identifier, ';'),
    expression_statement: $ => seq($.expr, ';'),
    expr: $ => choice($.identifier, prec.left(seq($.expr, '*', $.expr))),
    identifier: $ => /[a-z]+/,
  }
});
EOF
npx --yes tree-sitter-cli@0.27.0 generate 2>&1 | sed -n '3,18p'
sed -i "s/  rules: {/  conflicts: \$ => [[\$.declaration, \$.expr]],\n  rules: {/" grammar.js
sed -i "s/declaration: \$ => seq(\(.*\)),$/declaration: \$ => prec.dynamic(1, seq(\1)),/" grammar.js
grep -E "conflicts|declaration:" grammar.js
npx --yes tree-sitter-cli@0.27.0 generate
printf 'a * b;' > one.txt; printf 'a * b * c;' > two.txt
npx --yes tree-sitter-cli@0.27.0 parse one.txt two.txt 2>/dev/null

Output (complete):

Caused by:
    Unresolved conflict for symbol sequence:

      identifier  •  '*'  …

    Possible interpretations:

      1:  (declaration  identifier  •  '*'  identifier  ';')
      2:  (expr  identifier)  •  '*'  …

    Possible resolutions:

      1:  Specify a higher precedence in `declaration` than in the other rules.
      2:  Specify a higher precedence in `expr` than in the other rules.
      3:  Specify a left or right associativity in `expr`
      4:  Add a conflict for these rules: `declaration`, `expr`
  conflicts: $ => [[$.declaration, $.expr]],
    declaration: $ => prec.dynamic(1, seq($.identifier, '*', $.identifier, ';')),
(stmt [0, 0] - [0, 6]
  (declaration [0, 0] - [0, 6]
    (identifier [0, 0] - [0, 1])
    (identifier [0, 4] - [0, 5])))
(stmt [0, 0] - [0, 10]
  (expression_statement [0, 0] - [0, 10]
    (expr [0, 0] - [0, 9]
      (expr [0, 0] - [0, 5]
        (expr [0, 0] - [0, 1]
          (identifier [0, 0] - [0, 1]))
        (expr [0, 4] - [0, 5]
          (identifier [0, 4] - [0, 5])))
      (expr [0, 8] - [0, 9]
        (identifier [0, 8] - [0, 9])))))

What to notice: without the declaration, tree-sitter's LR(1) builder reports the C-style a * b; ambiguity as a shift/reduce-like conflict (reduce identifier to expr, or shift * for a declaration) and offers precedence or a GLR conflicts entry. With the entry, the generated parser forks at that state: for a * b; both stacks survive to the end and dynamic precedence 1 selects the declaration; for a * b * c; the declaration stack dies at the second * and only the expression remains — Algorithm 3.6.4's frontier shrinking back to one node [TS-docs].

RNGLR and BRNGLR

• Scott and Johnstone's tools (the RNGLR/BRNGLR reference implementations, later ART) are research systems; among mainstream generators, none implements RNGLR, which is why ε-heavy grammars can defeat them (box below).
• SGLR (Spoofax/SDF, Rekers' algorithm with Visser's scannerless extensions) handles \(\varepsilon\) and hidden left recursion with Rekers' \(\varepsilon\) treatment [Rek92].

Bison's GLR parser does not terminate on hidden left recursion

Reproduce (bison 3.8.2, clang 23.1.2; any OS):

cat > hidden.y <<'EOF'
%{
#include <stdio.h>
int yylex(void);
void yyerror(const char *s) { printf("error: %s\n", s); }
%}
%glr-parser
%expect 2
%%
top: s             { printf("accepted\n"); } ;
s: a s 'b' | 'x' ;
a: %empty ;
%%
static const char *in;
int yylex(void) { return *in ? *in++ : 0; }
int main(int argc, char **argv) { in = argv[1]; return yyparse(); }
EOF
bison -o hidden.c hidden.y
clang-23 -w -o hidden hidden.c
for w in bx x xbb; do printf '%-4s ' $w; timeout 10 ./hidden $w; echo "(exit status $?)"; done

Output (complete):

bx   error: syntax error
(exit status 1)
x    (exit status 124)
xbb  (exit status 124)

What to notice: the grammar is unambiguous (\(L = x\,b^{*}\), one tree per sentence) and not cyclic, yet on every sentence Bison's GLR parser runs until timeout kills it (status 124): each \(\varepsilon\)-reduction of a at position 0 creates another stack that can reduce a again — the non-termination that Nozohoor-Farshi and RNGLR fix (§1). An input that dies at the first token (bx) is rejected at once.

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Tomita GLR (GSS + SPPF)	All ε-free acyclic CFGs; all parses	\(O(n^{p+1})\) · LR speed on deterministic regions	Returns every parse; ambiguity must be resolved (dprec/merge/dynamic precedence)	Moderate: GSS, path enumeration, forest	Bison %glr-parser, Elkhound, tree-sitter
RNGLR / BRNGLR	All CFGs; BRNGLR cubic	\(O(n^{p+1})\) / \(O(n^3)\) · research implementations	Same forests, correct with ε and hidden left recursion	High: RN tables, ε-SPPFs, binarization	Scott–Johnstone tools, SGLR-style systems

Choose GLR when the grammar is naturally ambiguous or not LR(1) and you would rather keep it readable (C/C++ declarations, natural-language-like DSLs, incremental editor grammars), and when you can afford to resolve ambiguity after parsing. Choose RNGLR/BRNGLR when the grammar has \(\varepsilon\)-rules in left-recursive positions or you need the cubic bound; for deterministic languages, stay with LALR/IELR and precedence.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch03.yaml)	Drill	Flashcard tag	Exercises
Tomita GLR	glr-tree-count, rnglr-why	none: the GLR trace is a combination of shift-reduce-trace per stack; the lab's G1 tests and lr glr give unlimited practice	glr	G1 ★
RNGLR / BRNGLR	rnglr-why, brnglr-bound	none (theory; the hidden-left-recursion box is the exercise)	rnglr	—

A forest is not a tree

GLR tells you that the input is ambiguous, not which reading the programmer meant. Bison's %dprec decides only when the alternatives differ at their topmost rule (the n+n+n case above fails): for operators, precedence declarations (Lesson 3.5) are the right tool, and GLR is for ambiguities that only semantics can settle.

References

See the chapter references.