Parsing Expression Grammar (PEG) encodes a recursivedescent parser with limited backtracking. Its properties are useful in many applications. In its appearance, PEG is almost identical to a grammar in the Extended Backus-Naur Form (EBNF), but may define a different language. Recent research formulated some conditions under which PEG is equivalent to its interpretation as EBNF. However, PEG has a useful feature, namely syntactic predicate, that is alien to EBNF. The equivalence results apply thus only to PEG without predicates. The paper considers PEG with predicates. Not being able to investigate equivalence, the paper turns to the limited backtracking that is the main source of difficulty in understanding PEG. It is shown that the limitation of backtracking has no effect under conditions similar to those for PEG without predicates. There is, in general, no mechanical way to check these conditions, but they can be often checked by inspection. The paper outlines an experimental tool to facilitate such inspection.
Parsing Expression Grammars (PEGs) have been introduced by Ford in [
In addition to circumventing the LL(1) restriction, PEG can be used to define parsers that do not require a separate ”scanner” or ”tokenizer”. All this makes it useful, but PEG is not well understood as a language definition tool. Literature contains many examples of surprising behavior.
In its appearance, PEG is almost identical to a grammar in the Extended Backus-Naur Form (EBNF). Few minor typographical changes convert EBNF to PEG. As EBNF is familiar to most, one expects that the identically-looking PEG defines the same language. This is often the case, but the confusion comes when it is not.
In [
In a pioneering work [
PEG has one feature that does not have a counterpart in EBNF: the syntactic
predicate. All results about the equivalence of PEG and EBNF must be thus
restricted to PEG without predicates. And this is the case for all results from
[
This paper is an attempt to better understand PEG even in the presence of
predicates. Because one can no longer investigate the equivalence of PEG and
EBNF, we concentrate on the main source of confusion: the limited backtracking.
We find that limited backtracking has no effect on choice expressions that can
be identified as ”disjoint”. The conditions for disjointness are similar to those
from [
We start by recalling, in Section 2, the definition of Parsing Expression Grammar and its formal semantics. In Section 3, we discuss limited backtracking and disjoint expressions. Section 4 introduces the PEG Analyzer with the help of three examples. The results obtained in Section 3 require a modification to the relation Follow known from the classical literature. This modification involves a rather tedious treatment not relevant for the main subject, so it is presented separately in Section 5. Finally, Section 6 contains few comments. 2
We start with a simplified Parsing Expression Grammar G over alphabet . The grammar is a set of rules of the form A = e where A belongs to a set N of symbols distinct from the letters of and e is an expression. Each expression is one of these: "
(”empty”), a ∈ (”terminal”), A ∈ N (”nonterminal”), ! e
(”predicate”),
e1e2 (”sequence”),
e1| e2 (”choice”),
where each of e1; e2; e is an expression. The set of all expressions is in the
following denoted by E. There is exactly one rule A = e for each A ∈ N . The
expression e appearing in this rule is denoted by e(A). The predicate operator
binds stronger than sequence and sequence stronger than choice.
1 This work is in Portuguese. An extended English version is available in [
The expressions represent parsing procedures, and rules represent named parsing procedures. In general, parsing procedure is applied to an input string from ∗ and tries to recognize an initial portion of that string. If it succeeds, it returns ”success” and usually consumes the recognized portion. Otherwise, it returns ”failure” and does not consume anything. The actions of different procedures are specified in Figure 1.
" a A ! e
Call e1. If it succeeded, call e2 and return success if e2 succeeded.
If e1 or e2 failed, backtrack: reset the input as it was before the invocation of e1 and return failure.
Call e1. Return success if it succeeded. Otherwise call expression e2 and return success if e2 succeeded or failure if it failed.
We note the limited backtracking: once e1 in e1| e2 succeeded, e2 will never be tried. The backtracking done by the sequence expression may only roll back e1| e2 as a whole.
The actions of parsing procedures can be formally defined using ”natural
semantics” introduced in [
The PEG parser may end up in an infinite recursion, the well-known nemesis
of top-down parsers. Formally, it means that there is no proof according to the
rules of Figure 2. It has been demonstrated that if the grammar G is free from
left-recursion, then for every e ∈ E and x ∈ ∗ there exists a proof of [e] x PEG
fail or [e] x PEG y for some y ∈ ∗. This has been shown in [
For e ∈ E, we denote by L(e) the set of words x ∈ ∗ such that [e] xy PEG y for some y ∈ ∗. This is the language accepted by e. Note that, in general, x ∈ L(e) does not mean [e] xy PEG y for each y.
["] x PEG x
[e] xy PEG y [! e] xy PEG fail [a] ax PEG x (empty) (not1) [e(A)] xy PEG Y
[A] xy PEG Y [e] x PEG fail [! e] x PEG x
(rule) (not2) (letter1)
b ̸= a [b] ax PEG fail
(letter2) [e1] xyz PEG yz [e2] yz PEG Z [e1e2] xyz PEG Z
(seq1) [e1] xy PEG y [e1| e2] xy PEG y (choice1) [e1] xy PEG fail [e2] xy PEG Y
[e1| e2] xy PEG Y where Y denotes y or fail and Z denotes z or fail . [a] " PEG fail [e1] x PEG fail [e1e2] x PEG fail (letter3)
(seq2) (choice2)
We define the EBNF interpretation of G as the language LE (e) accepted by expression e ∈ E. It is defined recursively as
LE (") = {"}; LE (a) = {a}; LE (A) = LE (e(A));
LE (! e) = {"}; LE (e1e2) = LE (e1)LE (e2);
LE (e1| e2) = LE (e1) ∪ LE (e2):
By defining LE (! e) = {"}, we extended the interpretation to PEG with
predicates. This is not what one can expect looking at the grammar, just an
approximation. The following result from [
L(e) ⊆ LE (e) for any e ∈ E :
The opposite of (1) does not, in general hold. This is, to some extent, due to the different interpretation of predicates, but the main cause is limited backtracking. 3
We say that choice e = e1| e2 is strictly disjoint if
L(e1) ∗ ∩ L(e2) ∗ = ∅: Such choice is not affected by the limitation of backtracking. Indeed, suppose that e is applied to some string s and e1 succeeds. This means s ∈ L(e1) ∗. (1) (2) After this, any attempt to backtrack must result in a failure. It would mean applying e2 to s, and a success would mean s ∈ L(e2) ∗, which is excluded by (2). So, not attempting it does not make any difference.
The choice aa|a is not disjoint in the sense of (2). However, it is not affected by partial backtracking when it appears in some contexts, for example, in (aa|a)b. A success of aa means that input has the form aa ∗, so backtracking to a is useless as it will later result in a failure by not finding b.
We are going to look at limited backtracking in the context of our grammar G successfully parsing a complete input string. Thus, we assume that G has a unique start symbol S ∈ N with the corresponding rule S = e # where e is an expression and # is a unique end-of-text marker that appears only in this rule. We say that a string w ∈ ∗ is accepted by S to mean that [S] w PEG ".
For an expression e ∈ E, we define Tail(e) to be the set of strings y such that [e] xy PEG y appears as partial result in the proof of [S] w PEG " for some w. We say that the choice e = e1| e2 is disjoint (in the context of G) if
L(e1) ∗ ∩ L(e2) Tail(e) = ∅:
LE (e1) ∗ ∩ LE (e2)LE (Follow(e)) ∗ = ∅:
Using known methods one can compute the sets of symbols that appear as first in strings from LE (e1) ∗ respectively LE (e2)LE (Follow(e)) ∗. Condition (5) is then obviously satisfied if these sets are disjoint. This is the familiar LL(1) condition.
The same argument as before shows that such choice is not affected by the limitation of backtracking. If e is applied to some string s in a proof [S] w PEG " and e1 succeeds, we have s ∈ L(e1) ∗. An attempt to backtrack would mean applying e2 to s, and a success would mean s ∈ L(e2) Tail(e), which is excluded by (3).
A mechanical checking of (3) is in general impossible because of complexity of L(e) and Tail(e), and because it may involve checking emptiness of intersection of context-free languages - known to be undecidable. However, it can be often checked using approximation.
With (1), we can approximate L(e1) and L(e2) by LE (e1) respectively LE (e2). This gives a stronger condition: (3) (4) (5)
LE (e1) ∗ ∩ LE (e2) Tail(e) = ∅:
It was shown in [
To approximate Tail(e), we need to modify the relation Follow known from the classical literature. The modification is described in Section 5, where it is shown (Proposition 1) that with the modified relation, we have Tail(e) ⊆ LE (Follow(e)) ∗ where LE (Follow(e)) = ∪x∈Follow(e)LE (x). This gives an even stronger condition:
As suggested in [
The grammar G considered up to now is a simplified version of full PEG. This latter allows expressions such as e1| e2| : : : | en, e1e2 : : : en, e∗, e+, and e? . The expression E = e1| e2| : : : | en is a syntactic sugar for E = e1| E1, E1 = e2| E2, : : : , En = en so (3) must hold for all of E; E1; : : : ; En−1. One can verify that this is true if
L(ei) ∗ ∩ L(ej ) Tail(E) = ∅ for 1 ≤ i < j < n: (6) The expressions E = e∗, E = e+, and E = e? constitute syntactic sugar for, respectively E = eE=", E = eE=e, and E = e=" so (3) must hold for each of them. One can verify that this is true if
L(e) ∗ ∩ Tail(E) = ∅: (7)
The rules for computing Follow(e) given in the Section 5 can be similarly extended to the full PEG.
The terminals in full PEG are not necessary single letters, and may be multiletter quoted strings. Instead of sets of ”first letters” used in the test for LL(1), one has to compute sets of ”first terminals” and check their disjointness. 4
Giving up all hope for an automatic verification of (3), the author created an
experimental tool, the PEG Analyzer, that combines the LL(1) check with
heuristics. It takes a grammar, tests all choice expressions for LL(1) using (5), and
presents for inspection those that did not pass the test. To facilitate
inspection, it gradually expands the involved expressions by replacing them with their
definitions, somewhat in the spirit of what was suggested in [
To give some idea of the Analyzer, we apply it to the grammar shown in Figure 3. The grammar defines the syntax of a simple calculator.
When Analyzer is applied to this grammar, it indicates that the choice between the first two alternatives of Factor does not satisfy LL(1), and opens a window shown in Figure 4. It is an invitation to verify (3) for e1 = Digits? Fraction, e2 = Digits, and Tail(Factor).
The first two lines show these two expressions. The second is, in fact, a
pseudo-expression, with pseudo-expression Tail(Factor) representing the tail.
The third line tells that both expressions have [
The subsequent lines show the two expressions in more detail. Thus, the first
expression stands for two alternative expressions, Digits Fraction and Fraction.
Since this latter does not start with [
In the second expression, Tail(Factor) is replaced by the approximation
LE (Follow(Factor)) ∗ in the form of pseudo-expression. Again, Digits is
expanded to [
Verifying (3) means checking if any string represented by e1 can be a prefix of any string in L(e2) Tail(Factor). One can easily see that Digits in the first expression is always followed by a dot, while in the second it can be only followed by AddOp, MultOp, or Rparen, none of which is a dot. The condition (3) is thus satisfied. The second example illustrates treatment of predicates. The grammar in Figure 5 is a fragment of larger grammar that uses identifiers, with some of them being reserved as ”keywords”. Only one keyword, "print" is shown. Its definition is followed by ! Letter to make sure it is not recognized as a prefix of an identifier. The definition of Identifier is preceded by ! Keyword to ensure that keyword is not recognized as an identifier.
Statement = (Keyword Number | Identifier Number) ";" #
Keyword = "print" !Letter
Identifier = !Keyword Letter+
Letter = [a-z]
Number = [
The Analyzer applied to this grammar indicates that the choice in Statement does not satisfy LL(1), and opens the window shown in Figure 6. To check LL(1), the Analyzer approximated L("print"! Letter) with LE("print") and L(! Keyword Letter+) with LE(Letter+):
L("print"! Letter) ⊆ LE("print"!Letter) = LE("print") ;
L(! Keyword Letter+) ⊆ LE(! Keyword Letter+) = LE(Letter+) : It found their first terminals to be, respectively, "print" and [a-z]. As they are not disjoint, the choice does not satisfy LL(1) and is signaled as such. But, this is a false alarm. One can easily see that
L("print" ! Letter ...) ∩ L(! Keyword Letter+ ...) = ∅ showing that the expression satisfies (3).
Statement.1.1 = Keyword Number Statement.1.2 = Identifier Number Tail(Statement.1)
"print" <==> [a-z] Keyword Number "print" !Letter Number
<==> Identifier Number Tail(Statement.1) Identifier Number ";" ... !Keyword Letter+ Number ";" ...
Fig. 6. Presentation of a non-LL(1) case 4.3
Suppose now that in the calculator from Example 1, we want sometimes to skip the multiplication sign and write, for example 2(.3+4) instead of 2*(.3+4). To achieve this, we replace the definition of MultOp by MultOp = "*"? | "/".
The Analyzer applied to the modified grammar shows now two cases not
satisfying LL(1). The first produces the window shown in Figure 7. It says that
[
Digits.1 = [
<==> Tail(Digits) MultOp Factor ...
Factor ...
Digits? Fraction ...
Digits Fraction ...
[
Digits ...
[
How does this happen and what does it mean? A look at the grammar shows
that the offending [
In this example, the grammar interpreted as EBNF has an ambiguity, and PEG just selects one of the possible parses.
The second case not satisfying LL(1) is the same as for the original grammar: the choice between the first two alternatives of Factor, and is reported exactly as shown in Figure 4. However, MultOp in MultOp Factor that appears in the tail of Factor may be omitted. And Factor has an alternative that begins with a dot. Thus, Digits in Digits Tail(Factor] can be followed by a dot and (3) is not satisfied. It means that, for example, 2.34 will be treated by PEG as a single Factor, and not as shorthand for 2*.34.
Here the grammar interpreted as EBNF has another ambiguity and PEG chooses one possible parse. In both cases, we may accept the PEG’s choice because it corresponds to the perception of a human reader.
We define a number of relations R ⊆ E×E, writing e′ ∈ R(e) to mean (e; e′) ∈ R. • Derivess(e) is the set of all e′ ∈ E such that [e′] x′y PEG y can be derived from [e] xy PEG y using one inference rule.
Thus, e′ ∈ Derivess(e) if and only if: – e′ = A ∈ N where e(A) = e, – e′ = e e2 for some e2 such that " ∈ L(e2), – e′ = e1 e for some e1, – e′ = e| e2 for some e2, – e′ = e1| e for some e1. • Derivesf (e) is the set of all e′ ∈ E such that [e′] xy PEG fail can be derived from [e] xy PEG y using one inference rule.
Thus, e′ ∈ Derivesf (e) if and only if: – e′ =! e, – e′ = e e2 for some e2. • Deriveff (e) is the set of all e′ ∈ E such that [e′] x PEG fail can be derived from [e] x PEG fail using one inference rule.
Thus, e′ ∈ Deriveff (e) if and only if: – e′ = A ∈ N where e(A) = e, – e′ = e1 e for some e1, – e′ = e e2 for some e2, – e′ = e| e2 for some e2, – e′ = e1| e for some e1 that can fail. • Nexts(e) is the set of all e′ ∈ E such that " ∈= L(e′) and there exists e e′ ∈ E. • Nextf (e) = {"} for all e such that there exists ! e ∈ E or e| e2 ∈ E for some e2. Define Follow = Derives∗s × Nexts ∪ Derives∗s × Derivesf × Derivef∗f × Nextf . Proposition 1. For each partial result [e] xy PEG y in the proof of [S] w PEG " holds y ⊆ LE (Follow(e)) ∗ where LE (Follow(e)) = ∪e′∈Follow(e) LE (e′). Proof. Consider any partial result [E1] xy PEG y in the proof of [S] w PEG ". It is the first in a chain of n ≥ 1 partial results derived successively using the rules of Figure 2 and other partial results. The chain ends with final result [S] w PEG " derived from [En #] xn # PEG ". In this chain, the first j ≥ 1 partial results are of the form [Ei] xiy PEG y. By definition of Derivess, we have Ei ∈ Derives∗s(E1) for 1 ≤ i ≤ j. The first partial result in a different form must be one of these: (b) [! Ej ] xj y PEG fail . (a) [Ej e2] xj uv PEG v where y = uv, u ̸= ", and [e2] uv PEG v. (c) [Ej e2] xj y PEG fail where [e2] xj y PEG fail . form must be one of these: (d) [! Ej+k] uv PEG uv. (e) [Ej+k| e2] uv PEG v where [e2] uv PEG v, LE (Follow(E1)) ∗.
In case (a) we have e2 ∈ Nexts(Ej ), so e2 ∈ (Derives∗s × Nextf )(E1) ⊆ Follow(E1). We have also y = uv where u ∈ L(e2) ⊆ LE (e2) ⊆ LE (Follow(E1)), so y ∈
In cases (b) and (c), we have partial result [Ej+1] x PEG fail . According to the definition of Derivesf , we have Ej+1 ∈ Derivesf (Ej ). It is first in the chain of k ≥ 1 partial results in the form [Ei] x PEG fail derived successively using the rules of Figure 2 and other partial results. By definition of Deriveff , we have Ei ∈ Derivef∗f (Ej ) for j + 1 ≤ i ≤ j + k. The first partial result in a different where uv = x. We only know that the original y is a suffix of uv, but is very (d)-(e), we have Nextf (Ej+k) = {"}, so unlikely to be the same as v. We can only approximate it as y ∈ ∗. In each of {"} = (Derives∗s × Derivesf × Derivef∗f × Nextf )(E1) ⊆ Follow(E1): We have " ∈ LE (Follow(E1)), so y ∈ LE (Follow(E1)) ∗. ⊔⊓ Note that the very rough approximation of Tail(e) by ∗, changing (5) into a strict disjointness, applies to e that appears in a partial proof resulting in a failure (which is eventually needed to prove [S] w PEG "). 6
The fact that EBNF does not have predicates spoils the useful correspondence with PEG. The basic conditions for absence of effects of limited backtracking remain in principle unchanged, but there is no way of talking about equivalence.
There is no way to just include the recognition-oriented predicates as part of the construction-oriented EBNF. But one may consider some more natural extensions to EBNF that could serve the same purpose as predicates in defining useful grammars.
The example of PEG Analyzer shows that disjointness can often be checked by inspection. The tool as described here is quite primitive. One can improve it by letting the user interactively choose specific parts of expressions for detailed
The subject for further research is a careful analysis of what happens in the inspection. case of non-disjoint choice.