Skip to content

Parsers timeline

timeline 1961 1961 1964 1964 1965 1965 1968 1968 1969 1969 1970 1970 1971 1971 1984 1984 1990 1990 1993 1993 1999 1999 2004 2004 2005 2005 2006 2006 2007 2007 2009 2009 2010 2010 2011 2011 2014 2014 2016 2016 2018 2018 2019 2019 2020 2020 2022 2022 CYK CYK Earley Earley CYK->Earley Brzozowski Derivative Brzozowski Derivative Regular-expression derivatives Regular-expression derivatives Brzozowski Derivative->Regular-expression derivatives LR LR LR->Earley LALR LALR LR->LALR GLR GLR LR->GLR LLLR LLLR LR->LLLR Earley->GLR Yakker Yakker Earley->Yakker SEVM SEVM Earley->SEVM LL(k) LL(k) Efficient LL(k) Efficient LL(k) LL(k)->Efficient LL(k) GLL GLL LL(k)->GLL LL(k)->LLLR SLR SLR LALR->SLR LAR(m) LAR(m) LALR->LAR(m) TDPL TDPL PEG PEG TDPL->PEG GLR* GLR* GLR->GLR* SGLR SGLR GLR->SGLR RIGLR RIGLR GLR->RIGLR GLR->GLL IGLR IGLR GLR->IGLR LL(*) LL(*) Efficient LL(k)->LL(*) LAR(m)->LL(*) MSGLR MSGLR SGLR->MSGLR ISGLR ISGLR SGLR->ISGLR Tratt's PEG Tratt's PEG PEG->Tratt's PEG Pika Pika PEG->Pika PEGLL PEGLL PEG->PEGLL RNGLR RNGLR RIGLR->RNGLR BRNGLR BRNGLR RNGLR->BRNGLR Parsing with Derivatives Parsing with Derivatives Regular-expression derivatives->Parsing with Derivatives GLL->PEGLL IGLR->ISGLR ALL(*) ALL(*) LL(*)->ALL(*) Parsing with Zippers Parsing with Zippers Parsing with Derivatives->Parsing with Zippers

Algorithms

List of algorithms (based on this page):

LL

left-to-right, leftmost derivation (top-down), “recursive descent”

  • LL(k)
    • k tokens of lookahead
    • very expensive (when introduced)
  • LL(1)
    • exactly one token lookahead
    • much more efficient
    • uses FIRST() and FOLLOW() to build parse tables
  • Efficient LL(k)
    • k tokens of lookahead
    • k is gradually increased w/ backtracking as a fallback
    • basis of original ANTLR
  • GLL: Generalised LL
    • LL analogue to GLR
    • maintains multiple parsing descriptors on a stack
  • LL(*)
    • LL analogue to LAR(m)
    • regular lookaheads w/ cyclic DFAs
    • basis of ANTLR 3
  • ALL(*): Adaptive LL(*)
    • parallel regular lookaheads
    • dynamic; adapts to input sentences
    • simulates augmented recursive transition networks (ATNs)
    • basis of ANTLR 4
  • LLLR: a Combination of LL and LR

LR

left-to-right, rightmost derivation (“bottom-up”), “shift/reduce”

PEG

  • PEG: parsing expression grammar
    • similar to CFG-based grammars, but alternation is inherently ordered
    • often implemented with “packrat” parsers that memoize partial results
    • recursive descent with backtracking
  • PEGLL: PEG + GLL

Parsing with derivatives