GLL: Generalised LL

Recursive Descent (RD) parsers are popular because their control flow follows the structure of the grammar and hence they are easy to write and to debug. However, the class of grammars which admit RD parsers is very limited. Backtracking techniques may be used to extend this class, but can have explosive run-times and cannot deal with grammars with left recursion. Tomita-style RNGLR parsers are fully general but are based on LR techniques and do not have the direct relationship with the grammar that an RD parser has. We develop the fully general GLL parsing technique which is recursive descent-like, and has the property that the parse follows closely the structure of the grammar rules, but uses RNGLR-like machinery to handle non-determinism. The resulting recognisers run in worst-case cubic time and can be built even for left recursive grammars.

— Scott and Johnstone, 2010

Implementations

Haskel

• gll-combinators
  • code
  • paper: GLL Parsing with Flexible Combinators, 2018
• fungll-combinators
  • code
  • paper: Purely functional GLL parsing, 2020
• Happy-GLL
  • paper: Happy-GLL: modular, reusable and complete top-down parsers for parameterized nonterminals, 2023

Scala

• gll-combinators
  • code
  • paper: Preliminary Proceedings of the Ninth Workshop on Language Descriptions Tools and Applications LDTA, 2009
• Iguana
  • code
  • paper: Faster, Practical GLL Parsing, 2015
  • web

Java

• A Reference GLL Implementation
  • code
  • paper: A Reference GLL Implementation, 2023

Go

• GoGLL

Rust

• gll