Parsing expression grammar

In computer science, a parsing expression grammar is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s.
Syntactically, PEGs also look similar to context-free grammars, but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser.
Unlike CFGs, PEGs cannot be ambiguous; a string has exactly one valid parse tree or none. It is conjectured that there exist context-free languages that cannot be recognized by a PEG, but this is not yet proven. PEGs are well-suited to parsing computer languages where multiple interpretation alternatives can be disambiguated locally, but are less likely to be useful for parsing natural languages where disambiguation may have to be global.

Definition

A parsing expression is a kind of pattern that each string may either match or not match. In case of a match, there is a unique prefix of the string which has been consumed by the parsing expression; this prefix is what one would usually think of as having matched the expression. However, whether a string matches a parsing expression may depend on parts of it which come after the consumed part. A parsing expression language is a set of all strings that match some specific parsing expression.
A parsing expression grammar is a collection of named parsing expressions, which may reference each other. The effect of one such reference in a parsing expression is as if the whole referenced parsing expression was given in place of the reference. A parsing expression grammar also has a designated starting expression; a string matches the grammar if it matches its starting expression.
An element of a string matched is called a terminal symbol, or terminal for short. Likewise the names assigned to parsing expressions are called nonterminal symbols, or nonterminals for short. These terms would be descriptive for generative grammars, but in the case of parsing expression grammars they are merely terminology, kept mostly because of being near ubiquitous in discussions of parsing algorithms.

Syntax

Both abstract and concrete syntaxes of parsing expressions are seen in the literature, and in this article. The abstract syntax is essentially a mathematical formula and primarily used in theoretical contexts, whereas concrete syntax parsing expressions could be used directly to control a parser. The primary concrete syntax is that defined by Ford, although many tools have their own dialect of this. Other tools can be closer to using a programming-language native encoding of abstract syntax parsing expressions as their concrete syntax.

Atomic parsing expressions

The two main kinds of parsing expressions not containing another parsing expression are individual terminal symbols and nonterminal symbols. In concrete syntax, terminals are placed inside quotes, whereas identifiers not in quotes denote nonterminals:

"terminal" Nonterminal 'another terminal'

In the abstract syntax there is no formalised distinction, instead each symbol is supposedly defined as either terminal or nonterminal, but a common convention is to use upper case for nonterminals and lower case for terminals.
The concrete syntax also has a number of forms for classes of terminals:

A . is a parsing expression matching any single terminal.
Brackets around a list of characters form a parsing expression matching one of the numerated characters. As in regular expressions, these classes may also include ranges written as a hyphen with the range endpoints before and after it.
Some dialects have further notation for predefined classes of characters, such as letters, digits, punctuation marks, or spaces; this is again similar to the situation in regular expressions.

In abstract syntax, such forms are usually formalised as nonterminals whose exact definition is elided for brevity; in Unicode, there are tens of thousands of characters that are letters. Conversely, theoretical discussions sometimes introduce atomic abstract syntax for concepts that can alternatively be expressed using composite parsing expressions. Examples of this include:

the empty string ε,
end of input E, and
failure .

In the concrete syntax, quoted and bracketed terminals have backslash escapes, so that "line feed or carriage return" may be written . The abstract syntax counterpart of a quoted terminal of length greater than one would be the sequence of those terminals; "bar" is the same as "b" "a" "r". The primary concrete syntax assigns no distinct meaning to terminals depending on whether they use single or double quotes, but some dialects treat one as case-sensitive and the other as case-insensitive.

Composite parsing expressions

Given any existing parsing expressions e, e₁, and e₂, a new parsing expression can be constructed using the following operators:

Sequence: e₁ e₂
Ordered choice: e₁ / e₂
Zero-or-more: e*
One-or-more: e+
Optional: e?
And-predicate: &e
Not-predicate: !e
Group:

Operator priorities are as follows, based on Table 1 in:

Operator	Priority
	5
e*, e+, e?	4
&e, !e	3
e₁ e₂	2
e₁ / e₂	1

Grammars

In the concrete syntax, a parsing expression grammar is simply a sequence of nonterminal definitions, each of which has the form

Identifier LEFTARROW Expression

The Identifier is the nonterminal being defined, and the Expression is the parsing expression it is defined as referencing. The LEFTARROW varies a bit between dialects, but is generally some left-pointing arrow or assignment symbol, such as <-, ←, :=, or =. One way to understand it is precisely as making an assignment or definition of the nonterminal. Another way to understand it is as a contrast to the right-pointing arrow → used in the rules of a context-free grammar; with parsing expressions the flow of information goes from expression to nonterminal, not nonterminal to expression.
As a mathematical object, a parsing expression grammar is a tuple, where is the set of nonterminal symbols, is the set of terminal symbols, is a function from to the set of parsing expressions on, and is the starting parsing expression. Some concrete syntax dialects give the starting expression explicitly, but the primary concrete syntax instead has the implicit rule that the first nonterminal defined is the starting expression.
It is worth noticing that the primary dialect of concrete syntax parsing expression grammars does not have an explicit definition terminator or separator between definitions, although it is customary to begin a new definition on a new line; the LEFTARROW of the next definition is sufficient for finding the boundary, if one adds the constraint that a nonterminal in an Expression must not be followed by a LEFTARROW. However, some dialects may allow an explicit terminator, or outright require it.

Example

This is a PEG that recognizes mathematical formulas that apply the basic five operations to non-negative integers.

Expr ← Sum
Sum ← Product *
Product ← Power *
Power ← Value ?
Value ← + /

In the above example, the terminal symbols are characters of text, represented by characters in single quotes, such as . The range is a shortcut for the ten characters from '0' to '9'. The nonterminal symbols are the ones that expand to other rules: Value, Power, Product, Sum, and Expr. Note that rules Sum and Product don't lead to desired left-associativity of these operations, and the Power rule results in desired right-associativity of exponent. Also note that a rule like would cause infinite recursion, so it cannot be used in practice even though it can be expressed in the grammar.

Semantics

The fundamental difference between context-free grammars and parsing expression grammars is that the PEG's choice operator is ordered. If the first alternative succeeds, the second alternative is ignored. Thus ordered choice is not commutative, unlike unordered choice as in context-free grammars. Ordered choice is analogous to soft cut operators available in some logic programming languages.
The consequence is that if a CFG is transliterated directly to a PEG, any ambiguity in the former is resolved by deterministically picking one parse tree from the possible parses. By carefully choosing the order in which the grammar alternatives are specified, a programmer has a great deal of control over which parse tree is selected.
Parsing expression grammars also add the and- and not- syntactic predicates. Because they can use an arbitrarily complex sub-expression to "look ahead" into the input string without actually consuming it, they provide a powerful syntactic lookahead and disambiguation facility, in particular when reordering the alternatives cannot specify the exact parse tree desired.