Part of "Parsing" series
- An overview of parsing algorithms
- Notes on parsing theory, part 1
- Notes on parsing theory, part 2
Parser users tend to separate themselves into bottom-up and top-down tribes. Top-down users value the readability of recursive descent (
RD) implementations of
LLparsing along with the ease of semantic action incorporation. Bottom-up users value the extended parsing power of
LRparsers, in particular the admissibility of left recursive grammars, although
LRparsers cannot cope with hidden left recursion and even
LR(0)parse tables can be exponential in the size of the grammar, while an
LLparser is linear in the size of the grammar.
– GLL Parsing
A chart parser is a type of parser suited to parsing ambiguous grammars . Chart parsers avoid exponential blowup in parsing time arising from the nondeterminism of a grammar by reducing duplication of work through the use of memoization. Top-down chart parsers (such as packrat parsers) use memoized recursion, whereas bottom-up chart parsers more specifically use dynamic programming (Section 1.7). The
Earleyparser is a top-down chart parser, and is mainly used for parsing natural language in computational linguistics . It can parse any context-free grammar, including left-recursive grammars. The
Earleyparser executes in cubic time in the general case, quadratic time for unambiguous grammars, and linear time for all
Earleyparser may be converted from top-down memoized recursive form into bottom-up dynamic programming form  Parsing with pictures is a chart parsing algorithm that provides an alternative approach to parsing context-free languages. The authors claim that this method is simpler and easier to understand than standard parsers using derivations or pushdown automata . This parsing method unifies
LRparsers, and demonstrates that
Earleyparsing is the most fundamental Chomskyan context-free parsing algorithm, from which all others derive.
– Pika parsing: reformulating packrat parsing as a dynamic programmingalgorithm solves the left recursion and error recovery problems
List of algorithms (based on this page):
Earleyparser (Jay Earley, 1968):
- dynamic programming, chart parser
- supports any context-free grammar
Earleygave an outline of a method for turning his recognizers into parsers but it turns out that this method is incorrect. Tomita’s
GLRparser returns a shared packed parse forest (SPPF) representation of all derivations of a given string from a given CFG but is worst-case unbounded polynomial order.
– SPPF-Style Parsing From Earley Recognisers
left-to-right, leftmost derivation (top-down), “recursive descent”
LL(k)(Lewis and Stearns, 1968)
ktokens of lookahead
- very expensive (when introduced)
Efficient LL(k)(Terence Parr, 1990)
ktokens of lookahead
kis gradually increased w/ backtracking as a failback
- basis of original
In terms of recognition strength,
LLtechniques are widely held to be inferior to
LRparsers. The fact that any
LR(k)grammar can be rewritten to be
LL(k)is stronger than
LL(1), appears to give
LRtechniques the additional benefit of not requiring k-token lookahead and its associated overhead. In this paper, we suggest that
LL(k)is actually superior to
LR(1)when translation, rather than acceptance, is the goal. Further, a practical method of generating efficient
LL(k)parsers is presented. This practical approach is based on the fact that most parsing decisions in a typical
LL(k)grammar can be made without comparing k-tuples and often do not even require the full k tokens of look ahead. We denote such
LL(Bernard Lang, 1974 & Scott and Johnstone, 2010)
- maintains multiple parsing descriptors on a stack
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
RNGLRparsers are fully general but are based on
LRtechniques and do not have the direct relationship with the grammar that an RD parser has. We develop the fully general
GLLparsing 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.
LL(*)(Terence Parr and Kathleen Fisher, 2011)
- regular lookaheads w/ cyclic DFAs
- basis of
Despite the power of Parser Expression Grammars (
GLR, parsing is not a solved problem. Adding nondeterminism (parser speculation) to traditional
LRparsers can lead to unexpected parse-time behavior and introduces practical issues with error handling, single-step debugging, and side-effecting embedded grammar actions. This paper introduces the
LL(*)parsing strategy and an associated grammar analysis algorithm that constructs
LL(*)parsing decisions from ANTLR grammars. At parse-time, 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 context-sensitive languages, in some cases beyond what
PEGs can express. By statically removing as much speculation as possible,
LL(*)provides the expressivity of
PEGs while retaining
LL’s good error handling and unrestricted grammar actions.
LL(*)(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
Despite the advances made by modern parsing strategies such as
GLL, parsing is not a solved problem. Existing approaches suffer from a number of weaknesses, including difficulties supporting side-effecting embedded actions, slow and/or unpredictable performance, and counter-intuitive matching strategies. This paper introduces the
ALL(*)parsing strategy that combines the simplicity, efficiency, and predictability of conventional top-down
LL(k)parsers with the power of a
GLR-like mechanism to make parsing decisions. The critical innovation is to move grammar analysis to parse-time, which lets
ALL(*)handle any non-left-recursive context-free grammar.
ALL(*)is O(n4) in theory but consistently performs linearly on grammars used in practice, outperform in general strategies such as
GLRby orders of magnitude. ANTLR 4 generates
ALL(*)parsers and supports direct left-recursion through grammar rewriting.
A new parsing method called
LLLRparsing is defined and a method for producing
LLLRparsers is described. An
LLLRparser uses an
LLparser as its backbone and parses as much of its input string using
LLparsing as possible. To resolve
LLconflicts it triggers small embedded
LRparsers. An embedded
LRparser starts parsing the remaining input and once the
LLconflict is resolved, the
LRparser produces the left parse of the substring it has just parsed and passes the control back to the backbone
LLLR(k)parser can be constructed for any
LR(k)grammar. It produces the left parse of the input string without any backtracking and, if used for a syntax-directed translation, it evaluates semantic actions using the top-down strategy just like the canonical
LLLR(k)parser is appropriate for grammars where the
LL(k)conflicting nonterminals either appear relatively close to the bottom of the derivation trees or produce short substrings. In such cases an
LLLRparser can perform a significantly better error recovery than an
LRparser since the most part of the input string is parsed with the backbone
LLLRparsing is similar to
LL(∗)parsing except that it (a) uses
LR(k)parsers instead of finite automata to resolve the
LL(k)conflicts and (b) does not perform any backtracking.
left-to-right, rightmost derivation (“bottom-up”), “shift/reduce”
LR(Don Knuth, 1965)
- allows duplicated states
- fewer conflicts; much larger parse tables
- online demo
LR(0)states and their transitions
FOLLOW()used to compute lookaheads
- online demo
LALR(Frank DeRemer, 1969)
GLR(Masaru Tomita, 1984)
LR(k): returns all valid parses
- spawns parallel parsing processes on conflicts
- graph-structured stack (
- more efficient than Earley
LAR(m)(Practical arbitrary lookahead LR parsing, Bermudez and Schimpf, 1990)
- regular lookaheads w/ cyclic DFAs
GLR*(GLR* - An Efficient Noise-skipping Parsing Algorithm For Context Free Grammars Alon Lavie and Masaru Tomita, 1993)
GLR(Scannerless generalized-LR 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 context-free syntax are integrated into one grammar and are all handled by a single context-free 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 context-free grammar formalism leads to unwieldy grammars, if all lexical information is included. Lexical disambiguation needs to be reformulated for use in context-free parsing. The
scannerless generalized-LRparsing 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. The
SLR(1)parser generation algorithm is adapted to implement disambiguation by general priority and associativity declarations and to interpret follow restrictions.
Generalized-LRparsing is used to provide dynamic lookahead and to support parsing of arbitrary context-free grammars including ambiguous ones. An adaptation of the
GLRalgorithm supports the interpretation of grammars with reject productions.
RIGLRReduction Incorporated Generalized
LR(Elizabeth Scott and Adrian Johnstone. Generalised bottom up parsers with reduced stack activity, 2005)
We describe a generalized bottom up parser in which non-embedded 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 context-free 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.
GLRparsers (Elizabeth Scott and Adrian Johnstone. Right nulled GLR parsers, 2006)
The right nulled generalized
LRparsing algorithm is a new generalization of
LRparsing which provides an elegant correction to, and extension of, Tomita’s
GLRmethods whereby we extend the notion of a reduction in a shift-reduce parser to include right nulled items. The result is a parsing technique which runs in linear time on
LR(1)grammars and whose performance degrades gracefully to a polynomial bound in the presence of non
LR(1)rules. Compared to other
GLR-based techniques, our algorithm is simpler and faster.
BRNGLRBinary Right Nulled GLR (BRNGLR: a cubic Tomita-style GLR parsing algorithm, Elizabeth Scott, Adrian Johnstone, Rob Economopoulos, 2007)
GLR) algorithms extend the standard
LRalgorithm to non-deterministic 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 a
GLR-style parser. We call the resulting algorithm Binary Right Nulled
BRNGLR) parsing. The binarisation process generates run-time behaviour that is related to that shown by a parser which pre-processes its grammar or parse table into a binary form, but without the increase in table size and with a reduced run-time space overhead. BRNGLR parsers have worst-case cubic run time on all grammars, linear behaviour on
LR(1)grammars and produce, in worst-case 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 non-deterministic. Designers of batch compilers work around such limitations by combining generated components with ad hoc techniques (for instance, performing partial type and scope analysis in tandem with parsing). Unfortunately, the complexity of incremental systems precludes the use of batch solutions. The inability to generate incremental tools for important languages inhibits the widespread use of language-rich 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.
SGLR(A Modular SGLR Parsing Architecture for Systematic Performance Optimization, Denkers, Jasper et al., 2018)
SGLRparsing is an approach that enables parsing of context-free 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 modular
SGLRarchitecture 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
ISGLR) parsing algorithm, which combines the benefits of Incremental Generalized
IGLR) parsing and Scanner-less Generalized LR (
SGLR) parsing. The
ISGLRparser can reuse parse trees from unchanged regions in the input and thus only needs to parse changed regions. We also present incremental techniques for imploding the parse tree to an Abstract Syntax Tree (AST) and syntax highlighting. Scannerless parsing relies heavily on non-determinism during parsing, negatively impacting the incrementality of
ISGLRparsing. We evaluated the
ISGLRparsing algorithm using file histories from Git, achieving a speedup of up to 25 times over non-incremental
TS(The tmg recognition schema, Alexander Birman, 1970)
PEG: parsing expression grammar (Parsing Expression Grammars: A recognition-based Syntactic Foundation, Bryan Ford, 2004)
- similar to CFG-based grammars, but alternation is inherently ordered
- often implemented with “packrat” parsers that memoize partial results
- recursive descent with backtracking
For decades we have been using Chomsky’s generative system of grammars, particularly context-free grammars(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 modeling natural languages, but this very power makes it unnecessarily difficult both to express and to parse machine-oriented languages using CFGs. Parsing Expression Grammars(
PEGs) provide an alternative recognition-based formal foundation for describing machine-oriented syntax, which solves the ambiguity problem by not introducing ambiguity in the first place Where CFG express nondeterministic choice between alternatives,
PEGs instead use prioritized choice.
PEGs address frequently felt expressiveness limitations of CFGs and REs, simplifying syntax definitions and making it unnecessary to separate their lexical and hierarchical components. A linear-time parser can be built for any PEG, avoiding both the complexity and fickleness of
LRparsers 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,
gTS/GTDPL, which are here proven equivalent ineffective recognition power.
Abstract. Parsing Expression Grammars (
PEGs) are specifications of unambiguous recursive-descent style parsers. PEGs incorporate both lexing and parsing phases and have valuable properties, such as being closed under composition. In common with most recursive-descent systems, raw
PEGs cannot handle left-recursion; traditional approaches to left-recursion elimination lead to incorrect parses. In this paper, I show how the approach proposed for direct left-recursive Packrat parsing by Warth et al. can be adapted for ‘pure’
PEGs. I then demonstrate that this approach results in incorrect parses for some
PEGs, before outlining a restrictive subset of left-recursive
PEGs which can safely work with this algorithm. Finally I suggest an alteration to Warth et al.’s algorithm that can correctly parse a less restrictive subset of directly recursive
Packrat parsing is a linear-time implementation method of recursive descent parsers. The trick is a memoization mechanism, where all parsing results are memorized to avoid redundant parsing in cases of backtracking. An arising problem is extremely huge heap consumption in memoization, resulting in the fact that the cost of memoizationis likely to outweigh its benefits. In many cases, developers need to make a difficult choice to abandon packrat parsing despite the possible exponential time parsing. Elastic packrat parsing is developed in order to avoid such a difficult choice. The heap consumption is upper-bounded since memorized results are stored on a sliding window buffer. In addition, the buffer capacity is adjusted by tracing each of nonterminal backtracking activities at runtime. Elastic packrat parsing is implemented in a part of our Nez parser. We demonstrate that the elastic packrat parsing achieves stable and robust performance against a variety of inputs with different backtracking activities.
Pika(Pika parsing: reformulating packrat parsing as a dynamic programming algorithm solves the left recursion and error recovery problems, 2020)
A recursive descent parser is built from a set of mutually-recursive functions, where each function directly implements one of the nonterminals of a grammar. A
packratparser uses memoization to reduce the time complexity for recursive descent parsing from exponential to linear in the length of the input. Recursive descent parsers are extremely simple to write, but suffer from two significant problems: (i) left-recursive 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 the
pikaparser, a novel reformulation of
packratparsing as a dynamic programming algorithm, which requires parsing the input in reverse: bottom-up and right to left, rather than top-down and left to right. This reversed parsing order enables
pikaparsers to handle grammars that use either direct or indirect left recursion to achieve left associativity, simplifying grammar writing, and also enables optimal recovery from syntax errors, which is a crucial property for IDEs and compilers.
Pikaparsing maintains the linear-time performance characteristics of
packratparsing as a function of input length. The
parserwas benchmarked against the widely-used Parboiled2 and ANTLR4 parsing libraries, and the pika
parserperformed significantly better than the other
parsersfor an expression grammar, although for a complex grammar implementing the Java language specification, a large constant performance impact was incurred per input character for the
pikaparser, which allowed Parboiled2 and ANTLR4 to perform significantly better than the
pikaparser 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,
pikaparsing is best applied to simple to moderate-sized 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.
We show how one way of removing non-determinism from this formalism yields a formalism with the semantics of PEGs. We also prove, based on these new formalisms, how
LL(1)grammars define the same language whether interpreted as CFGs or as
PEGs, and also show how strong-
LL(k), right-linear, and LL-regular grammars have simple language-preserving translations from CFGs to
– On the relation between context-free grammars and parsing expression grammars
- Adaptable Parsing Expression Grammars (APEG), 2014
- Parsing Expression Grammars with Unordered Choices, 2017
We present the design and theory of a new parsing engine, YAKKER, capable of satisfying the many needs of modern programmers and modern data processing applications. In particular, our new parsing engine handles (1) full scannerless context-free grammars with (2) regular expressions as right-hand sides for defining nonterminals. YAKKER also includes (3) facilities for binding variables to intermediate parse results and (4) using such bindings within arbitrary constraints to control parsing. These facilities allow the kind of data-dependent parsing commonly needed in systems applications, particularly those that operate over binary data. In addition, (5) nonterminals may be parameterized by arbitrary values, which gives the system good modularity and abstraction properties in the presence of data-dependent parsing. Finally, (6) legacy parsing libraries, such as sophisticated libraries for dates and times, may be directly incorporated into parser specifications… We prove the correctness of our translation of data-dependent grammars into these new automata and then show how to implement the automata efficiently using a variation of Earley’s parsing algorithm.
We present a new, virtual machine based approach to parsing, heavily based on the original Earley parser. We show how to translate grammars into virtual machine instruction sequences that are then used by the parsing algorithm. Additionally, we introduce an optimization that merges shared rule prefixes to increase parsing performance. Finally, we present and evaluate an implementation of Scannerless Earley Virtual Machine
Parsing with derivatives
Might et al. (2011) introduced parsing with derivatives,which handles arbitrary context-free grammars while be-ing both easy to understand and simple to implement. De-spite much initial enthusiasm and a multitude of independentimplementations, its worst-case complexity has never beenproven to be better than exponential. In fact, high-level ar-guments claiming it is fundamentally exponential have beenadvanced and even accepted as part of the folklore. Perfor-mance ended up being sluggish in practice, and this slug-gishness was taken as informal evidence of exponentiality – On the Complexity and Performance of Parsing with Derivatives
- Derivatives of Regular Expressions, JANUSZ A. BRZOZOWSKI, 1964
- Regular-expression derivatives re-examined, 2009
- Parsing with Derivatives, 2011
- POSIX Regular Expression Parsing withDerivatives, 2014
- LL(1) Parsing with Derivatives and Zippers, 2019
- Derivative Grammars: A Symbolic Approach to Parsing with Derivatives, 2019
If you want to know more history of BNF and REG see Guy Steele talk.
If you want to learn more about dynamic programming read this.
Algorithms used in real-world applications: wikipedia article on parser generators.
- The Usability of Ambiguity Detection Methods for Context-Free Grammars
- Ambiguity Detection for Context-FreeGrammars in Eli