GLL parser

GLL parser
ClassParsing, context-free
Data structureString
Worst-case performance
  • for LL(1) grammars
  • for ambiguous context-free grammars

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

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

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

References

  1. ^ 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.
  2. ^ 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.
  3. ^ Cappers, Bram (2014-08-11). Exploring and visualizing GLL parsing (PDF) (Thesis). Retrieved 2026-06-21.
  4. ^ 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.
  5. ^ 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.
  6. ^ 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

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.