GLR Parsing and the Graph-Structured Stack

A deterministic LR parser has one state on top of its stack and one action per lookahead token. When a grammar has a conflict, that single action is not available, and the usual answer is to rewrite the grammar or declare a precedence. GLR parsing takes the other route: when several actions are possible, it performs all of them and keeps track of every resulting parse.

The data structure that makes this possible is the graph-structured stack, and it is the whole idea. Once the stack is a DAG rather than a list, several parses can share their common prefixes, so those prefixes are stored once however many parses run through them, and the number of complete parses can be exponential without the structure growing to match.

One stack becomes a DAG

In a deterministic parser, the stack is a list of states, and a shift pushes a new top. In a GLR parser, a stack node may have several successors, so the structure is a directed acyclic graph whose nodes are states at a given input position. Each node points down to its predecessors, and a node reached by several parses lists several of them, so the paths through the graph are exactly the stacks of the individual parses.

When two parses reach the same state at the same position with the same remaining stack, they are the same parse head as far as the parser can tell, and their nodes are merged. That merge is what keeps the structure small: parses that have converged are indistinguishable and need not be tracked separately.

A reduction pops n states and pushes one, following every combination of predecessors. If a node has three predecessors, reducing by a production of length two means three pops, and each combination produces a node for the goto state. The parser iterates over the frontier of active nodes at each position rather than a single stack.

The frontier and the worklist

The algorithm maintains a set of active nodes for the current input position, plus a worklist of pending actions. For each node in the set and the current lookahead, the parser looks up every action in the table. Shifts create nodes at the next position. Reduces create new nodes at the current position and enqueue further actions.

The worklist terminates because each distinct (state, position, stack context) node is interned once, so a node that is already present is never processed a second time; shifts advance the position, and reduces only ever produce nodes that are interned or already exist. The total work is therefore bounded by the number of distinct nodes times the actions in their table rows, which for an unambiguous grammar matches deterministic LR, and for an ambiguous one grows with the shared structure rather than with the number of derivations.

/* Sketch of the per-position loop. Node lists are keyed by state. */
for (;;) {
    Action a = next_action(&work);           /* (node, lookahead) pair */
    if (a.kind == SHIFT) {
        Node *n = intern_node(a.state, a.len + 1, a.node);
        if (add_to_frontier(a.len + 1, n))   /* true if n is new */
            enqueue_actions(&work, n, lookahead_at(a.len + 1));
    } else if (a.kind == REDUCE) {
        for (Node *p = pop_paths(a.node, a.rhs_len); p; p = p->next_path) {
            Node *n = intern_node(goto_state(p->state, a.lhs), a.len, p);
            if (add_to_frontier(a.len, n))   /* worklist grows here, FIFO */
                enqueue_actions(&work, n, a.lookahead);
        }
    } else {
        break;                               /* error or accept */
    }
}

intern_node is the merge step: if a node with the same state, position, and predecessor already exists, return it rather than allocating a second. Without interning, the structure is a tree of parses and the exponential blow-up returns. With it, shared prefixes are shared, and the “is it new” answer from the frontier insert is what stops the worklist from revisiting a node.

Ambiguity packaged as a forest

When two reductions complete the same nonterminal over the same input span, the parser has two derivations of one phrase. Storing both as separate trees is what the intern step prevents. Instead the two nodes are recorded as alternative productions of a single forest node covering that span.

The result is a shared packed parse forest. Each leaf of the sharing is a node that covers an input range and a nonterminal, and each such node holds a set of production alternatives, each with its own sequence of child nodes for that alternative. The forest’s size is proportional to the number of distinct (nonterminal, span) pairs times the number of alternatives, which for typical grammars is polynomial in input length even when the number of parse trees is exponential.

A grammar with a genuinely ambiguous construct, such as a sequence of binary operators with no declared precedence, produces a forest with a node per span and two alternatives per node. The number of trees is Catalan in the number of operators, but the forest is quadratic, which is why GLR can report all parses without enumerating them.

Disambiguation after the fact

A GLR parser accepts ambiguous input and produces a forest. Turning that into a compiler’s output requires choosing, and there are three common strategies.

Precedence declarations can be applied during parsing, which makes the conflict resolve as in a deterministic parser and leaves the forest with one alternative where the declaration applies. This is cheapest and preserves determinism for the constructs that have it.

A disambiguation filter can run over the forest after parsing, applying rules such as “prefer the parse with fewer nodes” or “prefer the parse whose operator tree is left-associative”. The filter needs to be expressible over the forest, which for associativity rules means local rewrites.

The third strategy is to keep the ambiguity and let a later pass decide, which is what a parser for a language with a context-dependent construct must do. The forest is passed to semantic analysis, which resolves each ambiguous node once it knows the types involved. This is the most expensive option and the only correct one for constructs whose resolution is not syntactic.

Cost of merging and the non-merging variant

Interning nodes requires a hash lookup per node created, which adds a constant factor to every shift and reduce. For an unambiguous grammar the GLR parser then does the same number of actions as the deterministic one plus a hash per action, so it is a small multiple of the deterministic cost rather than a different order.

The alternative is not to merge, keeping one stack per parse. This is simpler to implement and is what a backtracking parser effectively does. It is also exponential in the worst case, which is the reason merging exists.

The merging has a subtle cost: two parses that reach the same state with the same stack context are merged, and if they had different semantic values, those values must both be kept. The parser therefore carries semantic value lists on nodes, or defers value construction to a pass over the forest. Deferring is the usual choice, since it keeps the parse loop free of semantic actions and lets the forest be built before any type-dependent decision is made.

Practical costs against LR and packrat

A deterministic LR parser’s table is fixed at build time and its runtime state is one stack. A GLR parser’s table is the same table with the conflicts left in, so the build is cheaper, but the runtime needs node allocation, hashing, and a frontier set.

Memory is the sharp difference. A node is allocated per reduce step rather than per input token, so the count is proportional to the number of parser actions and therefore to input length for a grammar whose parse is sparse. That is more than the deterministic parser’s single stack, but the growth is the same order.

For an ambiguous grammar the forest grows with the number of distinct span-and-nonterminal pairs that the parse reaches, which for a grammar ambiguous at every level is quadratic in the span count rather than linear. A grammar with no declared precedence and an unbounded chain of binary operators sits in that quadratic case, and the parser’s memory grows with it.

The comparison with packrat is instructive. Packrat memoises per (rule, position) and guarantees linear time at the cost of a table proportional to grammar size times input. GLR merges parses instead of memoising rule applications: for a conflict-free grammar it does the same work as a deterministic LR parser, and in the worst case, on a grammar with conflicts at every step, Tomita’s formulation runs in time cubic in the input length rather than exponential. Neither dominates; GLR handles ambiguity that must be preserved, packrat handles grammars that are ordered-choice by design.

Where GLR is the only workable option

Languages whose grammar is fixed by an external standard and cannot be rewritten are the primary case. If a standard publishes a grammar with a known ambiguity, an implementation must accept every string the grammar derives, and a deterministic parser resolves each conflict by a built-in rule, which fixes one tree where the standard may leave the choice to the implementation or to a later phase.

The second case is a language with a construct whose parse depends on semantic information, such as a cast versus a call distinguished by a type table. A GLR parser can keep both alternatives until the table answers, which is the only way to parse without a lexer hack. The mechanisms for feeding that information back into the token stream are covered in Context-Dependent Lexing.

The third case is tooling that must report ambiguity rather than resolve it: grammar analysers, language servers that highlight ambiguity, and parser generators that verify a grammar is unambiguous before generating a deterministic parser. For those, the forest is the product, not an intermediate.

For the deterministic baseline that GLR generalises, see LALR Table Construction and What the Conflicts Mean. For the ordered-choice alternative, see Packrat Parsing and the Linear-Time Guarantee.