Standard LR parsers are efficient but brittle. They demand unambiguous grammars and a fixed lookahead, failing immediately upon encountering a shift-reduce or reduce-reduce conflict. But many useful grammars, especially for natural languages or complex domain-specific languages, are inherently ambiguous. Generalized LR (GLR) parsing extends LR techniques to handle these non-deterministic and ambiguous grammars without modification.

Instead of giving up at a conflict, a GLR parser explores all possibilities in parallel. It effectively clones its parsing process for each valid action. If a standard LR parser's journey is a single path, a GLR parser's is a branching, and sometimes reconverging, exploration of a landscape of potential parses.

The core innovation enabling this parallel exploration is the Graph-Structured Stack (GSS). Unlike the linear stack of a conventional LR parser, the GSS is a directed acyclic graph. Each node in the graph represents a parser state, and edges represent transitions. When the parser encounters a conflict, it doesn't halt; it splits the stack.

Stack splitting happens at points of non-determinism. For a shift-reduce conflict, one path performs the shift, pushing a new state onto its virtual stack top. Another path performs the reduction, popping states and pushing the result of the reduction. This creates two independent 'heads' processing the input. Critically, if two different parsing paths reach the same state after processing the same input, their stack tops are merged. This prevents the number of active parsers from growing exponentially and is key to GLR's practical efficiency. This merging transforms the collection of separate stacks into a single, cohesive graph structure.

Since a GLR parser can follow multiple valid parse paths, the output for an ambiguous sentence isn't a single parse tree. It's a collection of all possible parse trees. Storing these trees separately would be highly redundant and inefficient. Instead, GLR parsers produce a compact representation called a Shared Packed Parse Forest (SPPF).

An SPPF is a graph that merges common subtrees from different parse trees. Ambiguities are represented by 'packed nodes,' which contain multiple ways a particular substring can be derived. For example, if the input x * y + z can be parsed as (x * y) + z or x * (y + z), the SPPF will have a single root node representing the full expression. This root will point to packed nodes that represent the two different groupings, but both groupings will reuse the same terminal nodes for x, y, z, *, and +. This sharing makes the representation exponentially more compact than a list of individual trees.

The elegance of GLR comes with a performance trade-off. In the worst-case scenario of a highly ambiguous grammar, GLR's time complexity is cubic, or $O(n^3)$, where $n$ is the length of the input. This is on par with other general parsing algorithms like Earley or CYK. However, the true power of GLR is that for the deterministic, unambiguous subsets of a grammar, its performance is linear, $O(n)$, just like a standard LR parser. This hybrid performance makes it ideal for grammars that are 'mostly' deterministic but have specific, known areas of ambiguity.

This adaptability has made GLR a key feature in modern parser generators. Tools like Bison can be configured to use a GLR engine when the provided grammar is not LALR(1). This allows developers to write more natural and intuitive grammars, leaving the mechanical handling of ambiguity to the parser generator. The programmer can then either use the first valid parse tree found or iterate through the SPPF to apply semantic disambiguation rules.

GLR parsing represents a pragmatic and powerful bridge between the efficiency of deterministic parsing and the flexibility required for real-world languages. By embracing ambiguity instead of rejecting it, GLR enables the creation of more robust and expressive language processing tools.