GLL parser
Parsing algorithm for context-free languages
A GLL parser (Generalized Left to right, Leftmost derivation) is a parser based on a modification of LL parsers to recognize languages described by any context-free grammar. While the theory behind "generalising" deterministic parsers had already been developed by Bernard Lang in 1974, it wasn't until 1999 that a GLL parser was implemented, although no proof of correctness was given at the time. The algorithm was later rediscovered by Scott et al. who developed a GLL parser starting from a recursive descent parser.
01Algorithm
Most implementations of GLL parsers use a recursive descent parser as their base and replace the normal stack with a graph-structured stack, similar to the GLR algorithm. Whereas recursive descent parsers usually make implicit use of the function-call-stack, a GLL parser will have to manage its stack explicitly. This means that for a recursive descent parser to be turned into a GLL parser, a few smaller transformations have to be made first.
Similarly to GLR, the resulting parse forest is usually represented in a shared packed parse forest (SPPF). However, newer, simpler methods have been developed as well.
02Advantages
Due to being based on recursive descent parsers, the source code for a GLL parser will usually closely match the grammar it parses. Compared to GLR, GLL parsers are generally easier to implement and, due to their top-down nature, can generate better error messages.
Sources and credits
This article is adapted from the Wikipedia article “GLL parser”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.