GLR parser

<p>A GLR parser (generalized left-to-right rightmost derivation parser) is an extension of an <a href="/facts/LR_parser/bpMod8K0">LR parser</a> algorithm to handle <a href="/facts/Deterministic_context-free_grammar/ahbfKnLc">non-deterministic</a> and <a href="/facts/Ambiguous_grammar/elcVDDL4">ambiguous grammars</a>. The theoretical foundation was provided in a 1974 paper by Bernard Lang (along with other general context-free parsers such as GLL). It describes a systematic way to produce such algorithms, and provides uniform results regarding correctness proofs, complexity with respect to grammar classes, and optimization techniques. The first actual implementation of GLR was described in a 1984 paper by <a href="/facts/Masaru_Tomita/q80rd8bB">Masaru Tomita</a>, it has also been referred to as a "parallel parser". Tomita presented five stages in his original work, though in practice it is the second stage that is recognized as the GLR parser.
</p><p>Though the algorithm has evolved since its original forms, the principles have remained intact. As shown by an earlier publication, Lang was primarily interested in more easily used and more flexible parsers for <a href="/facts/Extensible_programming/hDFSJ5Xp">extensible programming</a> languages. Tomita's goal was to parse <a href="/facts/Natural_language/B4gLS7Kd">natural language</a> text thoroughly and efficiently. Standard <a href="/facts/LR_parsers/bpMod8K0">LR parsers</a> cannot accommodate the nondeterministic and ambiguous nature of <a href="/facts/Natural_language/B4gLS7Kd">natural language</a>, and the GLR algorithm can.
</p>

GLR parser open-in-new

GLR parser