GLL parser
Parsing algorithm for context-free languages
From Wikipedia, the free encyclopedia
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]
- for LL(1) grammars
- for ambiguous context-free grammars
| GLL parser | |
|---|---|
| Class | Parsing, context-free |
| Data structure | String |
| Worst-case performance |
|
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]