GLR Parser

A GLR parser (Generalized LR parser) is a variant of the LR parser that can handle ambiguous and nondeterministic context-free grammars by exploring multiple parse paths in parallel rather than committing to a single deterministic sequence. Developed by Masaru Tomita in the 1980s, the Tomita algorithm maintains a graph-structured stack that represents all possible parser states simultaneously, discarding paths that lead to syntax errors and retaining those that produce valid derivations. GLR parsing bridges the gap between the efficiency of deterministic LR parsing and the expressive power of general context-free parsing, making it suitable for natural language processing and programming languages with syntactic ambiguities that cannot be resolved by lookahead alone. Modern implementations, including the GLR mode of Bison, use Tomita's core insight to scale generalized parsing to industrial grammars.