We use cookies on this site. By browsing our site you agree to our use of cookies. Close this message Find out more

Home > Computer Science home > Research > CSLE > GLL parsing
More in this section CSLE

GLL parsing


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


Comment on this page

Did you find the information you were looking for? Is there a broken link or content that needs updating? Let us know so we can improve the page.

Note: If you need further information or have a question that cannot be satisfied by this page, please call our switchboard on +44 (0)1784 434455.

This window will close when you submit your comment.

Add Your Feedback