GLR

GLR, short for Generalized LR parsing, is a parsing algorithm for context-free grammars that can handle grammars beyond the capabilities of standard LR parsers. It was introduced by Masaya Tomita in the 1980s. The central idea is to use a graph-structured stack that represents multiple possible parse stacks simultaneously, allowing the parser to explore several parse paths in parallel rather than backtracking serially.

The parser operates with standard LR-style shift and reduce actions. When the next action is nondeterministic, GLR forks into parallel parse paths that share common prefixes through the graph-structured stack. By merging equivalent states, it avoids exponential blowup in many practical grammars. As a result, GLR can parse any context-free grammar and can yield all valid parse trees for a given input, which makes it suitable for processing ambiguous languages.

In terms of performance, the worst-case time complexity is O(n^3) for general grammars, with memory usage tied to the number of parallel paths represented on the graph-structured stack. In practice, GLR performs well on many natural-language grammars and on some ambiguous programming-language grammars. The method has had a significant influence in parsing research and has informed the development of several experimental parsers in natural language processing, although deterministic LR/LALR parsers remain more common for many production compilers.