Draft:GLL parser
 | Review waiting, please be patient.
This may take 4 months or more, since drafts are reviewed in no specific order. There are 4,478 pending submissions waiting for review.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Reviewer tools
|
| Class | Parsing, context-free |
|---|---|
| Data structure | String |
| Worst-case performance |
|
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.[1] While the theory behind "generalising" deterministic parsers had already been developed by Bernard Lang in 1974,[2] it wasn't until 2010 that a fully generalized LL recognizer was put into practice.[1]
Algorithm
[edit]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.[3]
Similarly to GLR, the resulting parse forest is usually represented in a shared packed parse forest (SPPF).[4] However, newer, simpler methods have been developed as well.[5]
Advantages
[edit]Due to being based on recursive descent parsers, the source code for a GLL parser will usually closely match the grammar it parses.[1] Compared to GLR, GLL parsers are generally easier to implement and, due to their top-down nature, can generate better error messages.[6]
See also
[edit]References
[edit]- ^ a b c Scott, Elizabeth; Johnstone, Adrian (2010-09-17). "GLL Parsing". Electronic Notes in Theoretical Computer Science. 253 (7): 177–189. doi:10.1016/j.entcs.2010.08.041. ISSN 1571-0661.
- ^ Lang, Bernard (1974). Deterministic techniques for efficient non-deterministic parsers. International Colloquium on Automata, Languages, and Programming. Springer. pp. 255--269. doi:10.1007/978-3-662-21545-6_18. ISBN 978-3-662-21545-6.
- ^ Cappers, Bram (2014-08-11). Exploring and visualizing GLL parsing (PDF) (Thesis). Retrieved 2026-06-21.
- ^ Scott, Elizabeth; Johnstone, Adrian (2013-10-01). "GLL parse-tree generation". Science of Computer Programming. 78 (10): 1828–1844. doi:10.1016/j.scico.2012.03.005. ISSN 0167-6423.
- ^ Scott, Elizabeth; Johnstone, Adrian; van Binsbergen, L. Thomas (2019-04-15). "Derivation representation using binary subtree sets". Science of Computer Programming. 175: 63–84. doi:10.1016/j.scico.2019.01.008. ISSN 0167-6423.
- ^ Afroozeh, Ali; Izmaylova, Anastasia (2015-10-15), One parser to rule them all, Association for Computing Machinery, pp. 151–170, doi:10.1145/2814228.2814242, ISBN 9781450336888