 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
A GLR parser (generalized left-to-right rightmost derivation parser) is an extension of an LR parser algorithm to handle non-deterministic and ambiguous grammars.[1] The theoretical foundation was provided in a 1974 paper[2] 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 Masaru Tomita, it has also been referred to as a "parallel parser". Tomita presented five stages in his original work,[3] though in practice it is the second stage that is recognized as the GLR parser.
Though the algorithm has evolved since its original forms, the principles have remained intact. As shown by an earlier publication,[4] Lang was primarily interested in more easily used and more flexible parsers for extensible programming languages. Tomita's goal was to parse natural language text thoroughly and efficiently. Standard LR parsers cannot accommodate the nondeterministic and ambiguous nature of natural language, and the GLR algorithm can.
- ^ Masaru Tomita (6 December 2012). Generalized LR Parsing. Springer Science & Business Media. ISBN 978-1-4615-4034-2.
- ^ Cite error: The named reference
Lang74was invoked but never defined (see the help page). - ^ Cite error: The named reference
Tomitawas invoked but never defined (see the help page). - ^ Cite error: The named reference
Lang71was invoked but never defined (see the help page).