GLR parser

From Wikipedia, the free encyclopedia

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.

Oops something went wrong: