Chomsky hierarchy
Grammar  Languages  Automaton  Complexity 

Type0  Recursively enumerable  Turing machine  undecidable 
Type0  Recursive  
Type1  Contextsensitive  Linearbounded nondeterministic Turing machine  exponential 
Type2  nondetermnisitic CFG  Nondeterministic pushdown automaton  polynomial 
Type2  deterministic CFG  Deterministic pushdown automaton  
Type3  Regular expressions  Finite state automaton  linear 
Note : CFG  contextfree grammars; REG  regular expressions; CSG  contextsensitive grammars; DFA  deterministic finite automaton;
Chomsky initially identified 4 types in his hierarchy, but then we discovered correspondence between language hierarchies and computational complexity. So we can refine initial categorization with more classes, for example mildly contextsensitive.
Side note: diagram of the world of computability and complexity, complexity zoology: active inclusion diagram, complexity zoo, computational complexity theory at SEP.
Regular expressions can’t specify, for example:
 Palindromes
 Strings with an equal number of 0’s and 1’s
 Matched parentheses
 Properly formed arithmetic expressions
REG is not enough for a general programming language ( PL ), CSG is too much (it is exponential), so the default choice for PL is CFG. BNF is used to formally specify PL (which is nondeterministic CFG), but I would say that deterministic CFG is preferred for parsing, for example, PEG.
Side note: What’s the Difference Between BNF, EBNF, ABNF?, On the Expressive Power of Programming Languages by Shriram Krishnamurthi.
Tasks
Nondeterministic CFG algorithms useful for natural language processing, but they tend to be slower (and nondeterministic, obviously). For PL parsing deterministic CFG seems to be more practical  they can be less expressive, but faster and much simpler to implement. This is the key idea of PEG parser, it is deterministic by construction and not left recursive (but it is always possible to rewrite from leftrecursive form to right recursive).
Typical tasks for programs working with deterministic CFG are:
 Identify if a given sentence is a member of language or not, for example, validate the email
 Generate valid sentences for a given language, for example, generate fake emails
 Parse given sentence, for example, generate AST for compiler/interpreter or highlight syntax
Current research:
 Parallel parsing algorithms  mainly for nondeterministic CFG
 Streaming parsers  to parse input from a socket
 Error recovery, for better error messages or to be able to highlight syntax in presence of an error
 Incremental parsing, for example, to be able to do syntax highlighting in IDE on each keystroke. See treesitter
Algorithms
Parser users tend to separate themselves into bottomup and topdown tribes. Topdown users value the readability of recursive descent (
RD
) implementations ofLL
parsing along with the ease of semantic action incorporation. Bottomup users value the extended parsing power ofLR
parsers, in particular the admissibility of left recursive grammars, althoughLR
parsers cannot cope with hidden left recursion and evenLR(0)
parse tables can be exponential in the size of the grammar, while anLL
parser is linear in the size of the grammar.
List of algorithms (based on this page):

CYK
(Cocke–Younger–Kasami) algorithm bottomup, dynamic programming, chart parser
 supports any contextfree grammar in Chomsky Normal Form
O(n^3)
 online demo 1, online demo 2, list of partofspeech tags

Earley
parser (Jay Earley, 1968): dynamic programming, chart parser
 supports any contextfree grammar
O(n^3)
Earley
gave an outline of a method for turning his recognizers into parsers, but it turns out that this method is incorrect. Tomita’sGLR
parser returns a shared packed parse forest (SPPF) representation of all derivations of a given string from a given CFG but is worstcase unbounded polynomial order. – SPPFStyle Parsing From Earley Recognisers
LL
lefttoright, leftmost derivation (topdown), “recursive descent”

LL(k)
(Lewis and Stearns, 1968)
k
tokens of lookahead  very expensive (when introduced)


LL(1)
 exactly one token lookahead
 much more efficient
 uses
FIRST()
andFOLLOW()
to build parse tables  online demo 1, online demo 2

Efficient LL(k)
(Terence Parr, 1990)
k
tokens of lookahead 
k
is gradually increased w/ backtracking as a failback  basis of original
ANTLR

In terms of recognition strength,
LL
techniques are widely held to be inferior toLR
parsers. The fact that anyLR(k)
grammar can be rewritten to beLR(1)
, whereasLL(k)
is stronger thanLL(1)
, appears to giveLR
techniques the additional benefit of not requiring ktoken lookahead and its associated ovehead. In this paper, we suggest thatLL(k)
is actually superior toLR(1)
when translation, rather than acceptance, is the goal. Further, a practical method of generating efficientLL(k)
parsers is presented. This practical approach is based on the fact that most parsing decisions in a typicalLL(k)
grammar can be made without comparing ktuples and often do not even require the full k tokens of look ahead. We denote such"optimized" LL(k)
parsers

GLL
GeneralisedLL
(Bernard Lang, 1974 & Scott and Johnstone, 2010)
LL
analogue toGLR
 maintains multiple parsing descriptors on a stack

Recursive Descent (RD) parsers are popular because their control flow follows the structure of the grammarand hence they are easy to write and to debug. However, the class of grammars which admit RD parsersis very limited. Backtracking techniques may be used to extend this class, but can have explosive runtimes and cannot deal with grammars with left recursion. Tomitastyle
RNGLR
parsers are fully generalbut are based onLR
techniques and do not have the direct relationship with the grammar that an RD parser has. We develop the fully generalGLL
parsing technique which is recursive descentlike, and has the property that the parse follows closely the structure of the grammar rules, but usesRNGLR
like machinery to handle nondeterminism. The resulting recognisers run in worstcase cubic time and can be built evenfor left recursive grammars.

LL(*)
(Terence Parr and Kathleen Fisher, 2011)
LL
analogue toLAR(m)
 regular lookaheads w/ cyclic DFAs
 basis of original
ANTLR 3
(?)

Despite the power of Parser Expression Grammars (
PEG
s) andGLR
, parsing is not a solved problem. Adding nondeterminism (parser speculation) to traditionalLL
andLR
parsers can lead to unexpected parsetime behavior and introduces practical issues with error handling, singlestep debugging, and sideeffecting embedded grammar actions. This paper introduces theLL(*)
parsing strategy and an associated grammar analysis algorithm that constructsLL(*)
parsing decisions from ANTLR grammars. At parsetime,decisions gracefully throttle up from conventional fixed k≥1 lookahead to arbitrary lookahead and, finally, fail over to backtracking depending on the complexity of the parsing decision and the input symbols.LL(*)
parsing strength reaches into the contextsensitive languages, in some cases beyond whatGLR
andPEG
s can express. By statically removing as much speculation as possible,LL(*)
provides the expressivity ofPEG
s while retainingLL
’s good error handling and unrestricted grammar actions.

ALL(*)
AdaptiveLL(*)
(Parsing: The Power of Dynamic Analysis” Terence Parr, Sam Harwell, and Kathleen Fisher 2014) parallel regular lookaheads
 dynamic; adapts to input sentences
 simulates augmented recursive transition networks (ATNs)
 basis of
ANTLR 4
Despite the advances made by modern parsing strategies suchas
PEG
,LL(*)
,GLR
, andGLL
, parsing is not a solved problem. Existing approaches suffer from a number of weaknesses, including difficulties supporting sideeffecting embedded actions, slow and/or unpredictable performance, and counterintuitive matching strategies. This paper introduces theALL(*)
parsing strategy that combines the simplicity, efficiency, andpredictability of conventional topdownLL(k)
parsers with the power of aGLR
like mechanism to make parsing decisions. The critical innovation is to move grammar analysis to parsetime, which letsALL(*)
handle any nonleftrecursive contextfree grammar.ALL(*)
is O(n4) in theory but consistently performs linearly on grammars used in practice, outperform in ggeneral strategies such asGLL
andGLR
by orders of magnitude. ANTLR 4 generatesALL(*)
parsers and supports directleftrecursion through grammar rewriting.
A new parsing method called
LLLR
parsing is defined and a method for producingLLLR
parsersis described. AnLLLR
parser uses anLL
parser as its backbone and parses as much of itsinput string usingLL
parsing as possible. To resolveLL
conflicts it triggers small embeddedLR
parsers. An embeddedLR
parser starts parsing the remaining input and once theLL
conflict is resolved, theLR
parser produces the left parse of the substring it has just parsed and passes the control back to the backboneLL
parser. TheLLLR(k)
parser can be constructed for anyLR(k)
grammar. It produces the left parse of the input string without any backtracking and, if used for a syntaxdirected translation, it evaluates semantic actions using the topdown strategy just like the canonicalLL(k)
parser. AnLLLR(k)
parser is appropriate for grammars where theLL(k)
conflicting nonterminals either appear relatively close to the bottom of the derivation trees or produce short substrings. In such cases anLLLR
parser can perform a significantly better error recovery than anLR
parser since the most part of the input string is parsed with the backboneLL
parser.LLLR
parsing is similar toLL(∗)
parsing except that it (a) usesLR(k)
parsers insteadof finite automata to resolve theLL(k)
conflicts and (b) does not perform any backtracking.
LR
lefttoright, rightmost derivation (“bottomup”), “shift/reduce”
 Canonical
LR
(Don Knuth, 1965) allows duplicated states
 fewer conflicts; much larger parse tables
 online demo

SLR
(Frank DeRemer) simple
LR
:LR(0)
states and their transitions 
FOLLOW()
used to compute lookaheads  online demo
 simple

LALR
(Frank DeRemer, 1969) similar to
SLR
but w/ smaller lookaheads  equivalently, a simplified version of canonical
LR
 more complicated lookahead calculation
 basis of yacc/bison
 recursive ascent (Thomas Penello, 1986)
 online demo
 similar to

GLR
(Masaru Tomita, 1984) generalized
LR(k)
: returns all valid parses  spawns parallel parsing processes on conflicts
 graphstructured stack (
GSS
)  more efficient than Earley
 generalized

LAR(m)
(Practical arbitrary lookahead LR parsing, Bermudez and Schimpf, 1990) regular lookaheads w/ cyclic DFAs

GLR*
(GLR*  An Efficient Noiseskipping Parsing Algorithm For Context Free Grammars Alon Lavie and Masaru Tomita, 1993) 
SGLR
ScannerlessGLR
(Scannerless generalizedLR parsing, Eelco Visser, 1999)
Current deterministic parsing techniques have a number of problems. These include the limitations of parser generators for deterministic languages and the complex interface between scanner and parser. Scannerless parsing is a parsing technique in which lexical and contextfree syntax are integrated into one grammar and are all handled by a single contextfree analysis phase. This approach has a number of advantages including discarding of the scanner and lexical disambiguation by means of the context in which a lexical token occurs. Scannerless parsing generates a number of interesting problems as well. Integrated grammars do not fit the requirements of the conventional deterministic parsing techniques. A plain contextfree grammar formalism leads to unwieldy grammars, if all lexical information is included. Lexical disambiguation needs to be reformulated for use in contextfree parsing. The
scannerless generalizedLR
parsing approach presented in this paper solves these problems. Grammar normalization is used to support an expressive grammar formalism without complicating the underlying machinery. Follow restrictions are used to express longest match lexical disambiguation. Reject productions are used to express the prefer keywords rule for lexical disambiguation. TheSLR(1)
parser generation algorithm is adapted to implement disambiguation by general priority and associativity declarations and to interpret follow restrictions.GeneralizedLR
parsing is used to provide dynamic lookahead and to support parsing of arbitrary contextfree grammars including ambiguous ones. An adaptation of theGLR
algorithm supports the interpretation of grammars with reject productions.

RIGLR
Reduction Incorporated GeneralizedLR
(Elizabeth Scott and Adrian Johnstone. Generalised bottom up parsers with reduced stack activity, 2005)
We describe a generalized bottom up parser in which nonembedded recursive rules are handled directly by the underlying automaton, thus limiting stack activity to the activation of rules displaying embedded recursion. Our strategy is motivated by Aycock and Horspool’s approach, but uses a different automaton construction and leads to parsers that are correct for all contextfree grammars, including those with hidden left recursion. The automaton features edges which directly connnect states containing reduction actions with their associated goto state: hence we call the approach reduction incorporated generalized LR parsing. Our parser constructs shared packed parse forests in a style similar to that of Tomita parsers. We give formal proofs of the correctness of our algorithm, and compare it with Tomita’s algorithm in terms of the space and time requirements of the running parsers and the size of the parsers’ tables.

RNGLR
Right nulledGLR
parsers (Elizabeth Scott and Adrian Johnstone. Right nulled GLR parsers, 2006)
The right nulled generalized
LR
parsing algorithm is a new generalization ofLR
parsing which provides an elegant correction to, and extension of, Tomita’sGLR
methods whereby we extend the notion of a reduction in a shiftreduce parser to include right nulled items. The result is a parsing technique which runs in linear time onLR(1)
grammars and whose performance degrades gracefully to a polynomial bound in the presence of nonLR(1)
rules. Compared to otherGLR
based techniques, our algorithm is simpler and faster.

BRNGLR
Binary Right Nulled GLR (BRNGLR: a cubic Tomitastyle GLR parsing algorithm, Elizabeth Scott, Adrian Johnstone, Rob Economopoulos, 2007)
Tomitastyle generalised
LR
(GLR
) algorithms extend the standardLR
algorithm to nondeterministic grammars by performing all possible choices of action. Cubic complexity is achieved if all rules are of length at most two. In this paper we shall show how to achieve cubic time bounds for all grammars by binarising the search performed whilst executing reduce actions in aGLR
style parser. We call the resulting algorithm Binary Right NulledGLR
(BRNGLR
) parsing. The binarisation process generates runtime behaviour that is related to that shown by a parser which preprocesses its grammar or parse table into a binary form, but without the increase in table size and with a reduced runtime space overhead. BRNGLR parsers have worstcase cubic run time on all grammars, linear behaviour onLR(1)
grammars and produce, in worstcase cubic time, a cubic size binary SPPF representation of all the derivations of a given sentence.
A major research goal for compilers and environments is the automatic derivation of tools from formal speciﬁcations. However, the formal model of the language is often inadequate; in particular,
LR(k)
grammars are unable to describe the natural syntax of many languages, such as C++ and Fortran, which are inherently nondeterministic. Designers of batch compilers work around such limitations by combining generated components with ad hoc techniques (for instance, performingpartial type andscope analysis in tandem with parsing). Unfortunately, thecomplexity of incremental systems precludes the use of batch solutions. The inability to generate incremental tools for important languages inhibits the widespread use of languagerich interactive environments. We address this problem by extending the language model itself, introducing a program representation based on parse DAGs that is suitable for both batch and incremental analysis. Ambiguities unresolved by one stage are retained in this representation until further stages can complete the analysis, even if the resolution depends on further actions by the user. Representing ambiguity explicitly increases the number and variety of languages that can be analyzed incrementally using existing methods.

MSGLR
ModularSGLR
(A Modular SGLR Parsing Architecture for Systematic Performance Optimization, Denkers, Jasper et al., 2018)
SGLR
parsing is an approach that enables parsing of contextfree languages by means of declarative, concise and maintainable syntax definition. Existing implementations suffer from performance issues and their architectures are often highly coupled without clear separation between their components. This work introduces a modularSGLR
architecture with several variants implemented for its components to systematically benchmark and improve performance. This work evaluates these variants both independently and combined using artificial and real world programming languages grammars. The architecture is implemented in Java as JSGLR2, the successor of the original parser in Spoofax, interpreting parse tables generated by SDF3. The improvements combined result into a parsing and imploding time speedup from 3x on Java to 10x on GreenMarl with respect to the previous JSGLR implementation.
We present the Incremental Scannerless Generalized
LR
(ISGLR
) parsing algorithm, which combines the benefits ofIncremental GeneralizedLR
(IGLR
) parsing and Scannerless Generalized LR (SGLR
) parsing. TheISGLR
parser canreuse parse trees from unchanged regions in the input andthus only needs to parse changed regions. We also presentincremental techniques for imploding the parse tree to anAbstract Syntax Tree (AST) and syntax highlighting. Scannerless parsing relies heavily on nondeterminism duringparsing, negatively impacting the incrementality ofISGLR
parsing. We evaluated theISGLR
parsing algorithm usingfile histories from Git, achieving a speedup of up to 25 timesover nonincrementalSGLR
PEG

TDPL
orTS
(The tmg recognition schema, Alexander Birman, 1970) 
PEG
: parsing expression grammar (Parsing Expression Grammars: A recognitionbased Syntactic Foundation, Bryan Ford, 2004) similar to CFGbased grammars, but alternation is inherently ordered
 often implemented with “packrat” parsers that memoize partial results
For decades we have been using Chomsky’s generative system of grammars,particularly contextfreegrammars(CFGs)and regular expressions(REs),to express the syntax of programming languages and protocols. The power of generative grammars to express ambiguity is crucial to their original purpose of modelling natural languages, but this very power makes it unnecessarily difficult both to express and to parse machineoriented languages using CFGs. Parsing Expression Grammars(
PEG
s) provide an alternative recognitionbased formal foundation for describing machineoriented syntax,which solves the ambiguity problem by not introducing ambiguity in the first place Where CFG sexpress nondeterministic choice between alternatives,PEG
s instead use prioritized choice.PEG
s address frequently felt expressiveness limitations of CFGs and REs, simplifying syntax definitions and making it unnecessary to separate their lexical and hierarchical components. A lineartime parser can be built for any PEG , avoiding both the complexity and fickleness ofLR
parsers and the inefficiency of generalized CFG parsing.While PEGs provide a rich set of operators for constructing grammars, they are reducible to two minimal recognition schemas developed around 1970,TS/TDPL
andgTS/GTDPL
, which are here proven equivalent ineffective recognition power.
A recursive descent parser is built from a set of mutuallyrecursive functions, where each function directly implements one of thenonterminals of a grammar. A
packrat
parser uses memoization to reduce the time complexity for recursive descent parsing fromexponential to linear in the length of the input. Recursive descent parsers are extremely simple to write, but suffer from two significantproblems: (i) leftrecursive grammars cause the parser to get stuck in infinite recursion, and (ii) it can be difficult or impossible to optimally recover the parse state and continue parsing after a syntax error. Both problems are solved by thepika
parser, a novel reformulation ofpackrat
parsing as a dynamic programming algorithm, which requires parsing the input in reverse: bottomup andright to left, rather than topdown and left to right. This reversed parsing order enablespika
parsers to handle grammars that use eitherdirect or indirect left recursion to achieve left associativity, simplifying grammar writing, and also enables optimal recovery fromsyntax errors, which is a crucial property for IDEs and compilers.Pika
parsing maintains the lineartime performance characteristics ofpackrat
parsing as a function of input length. Thepika
parser
was benchmarked against the widelyused Parboiled2 and ANTLR4 parsing libraries, and the pikaparser
performed significantly better than the otherparsers
for an expression grammar, althoughfor a complex grammar implementing the Java language specification, a large constant performance impact was incurred per input character for thepika
parser, which allowed Parboiled2 and ANTLR4 to perform significantly better than thepika
parser for this grammar (in spite of ANTLR4’s parsing time scaling between quadratically and cubically in the length of the input with the Java grammar). Therefore, if performance is important,pika
parsing is best applied to simple to moderatesized grammars, or to very large inputs, if other parsing alternatives do not scale linearly in the length of the input. Several new insights into precedence, associativity, and left recursion are presented.
PS
If you want to know more history of BNF and REG see Guy Steele talk.
If you want to understand the terminology, like LR, LL, backtracking, etc. see this course.
If you want to learn more about dynamic programming read this.
Algorithms used in realworld applications: wikipedia article on parser generators.
Visualizing algorithms:
About ambiguity:
 The Usability of Ambiguity Detection Methods for ContextFree Grammars
 Ambiguity Detection for ContextFreeGrammars in Eli
More reading:
Discussion (1)
A great review of parsing literature! Love it.