Centre for Software Language Engineering, Royal Holloway, University of London


GLL parsers

GLL is a fully general recursive descent-like parsing technique which supports even left recursive grammars. It has worst-case cubic runtime order while also being close to linear on most 'real' grammars. GLL parsers produce a binarised shared packed parse forest, an efficient representation of all the derivation trees of the input string.

Similarly to recursive descent parsers, GLL parsers effectively traverse the grammar using the input string to guide the traversal. Of course, if the grammar is not LL(1) there may be several traversal threads, each of which has a pointer into the grammar and a pointer into the input string. A GLL parser pursues each of these threads. This is done efficiently by explicitly handling the function call and return activity associated with nonterminals in a traditional recursive descent parser using a Tomita style graph structured stack.

Multiple traversal threads are handled using process descriptors, making the algorithm parallel rather than backtracking in nature. Each time a traversal bifurcates, the current grammar and input pointers, together with the top of the current stack and associated portion of the derivation tree, are recorded in a descriptor for subsequent processing. More details can be found here.

Algorithm Sketch and Terminology.

Example - A Simple Grammar.

Example - A Highly Ambiguous Grammar.

The GLL recognition algorithm.

© Elizabeth Scott and Adrian Johnstone
   Centre for Software Language Engineering, Royal Holloway, University of London