GLL parser

GLL parser
Class	Parsing, context-free
Data structure	String
Worst-case performance	$O(n)$ for LL(1) grammars $O(n^{3})$ 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. While the theory behind "generalising" deterministic parsers had already been developed by Bernard Lang in 1974, it wasn't until 1999 that a GLL parser was implemented, although no proof of correctness was given at the time. The algorithm was later rediscovered by Scott et al. who developed a GLL parser starting from a recursive descent parser.