Parsing Expression Grammar (PEG) is extended to handle left recursion, and under speci ed conditions becomes a correct parser for left-recursive grammars in Backus-Naur Form (BNF).
The technique of parsing by recursive descent assigns to each grammatical construct a procedure that calls other procedures to process components of that construct. As grammars are usually de ned in a recursive way, these calls are recursive. This method encounters two problems: (1) Procedures corresponding to certain type of construct must chose which procedure to call next. (2) If the grammar contains left recursion, a procedure may call itself inde nitely.
Problem (1) has been traditionally solved by looking at the next input symbol(s), which works if the grammar satis es a condition known as LL(n). Another way is to try the alternatives one by one, backtracking in the input, until one succeeds (or all fail).
Making full search can require exponential time, so a possible option is limited
backtracking: never return after a partial success. This method has been used in
actual parsers [
Problem (2) is serious because of a strong tendency to present grammars in left-recursive form. Converting the grammar to right-recursive form is possible, but is tedious, error-prone, and obscures the spirit of the grammar.
The problem has been in the recent years solved by what can be called "recursive ascent". Each recursion must end up in a part of syntax tree that does not involve further recursion. It has been referred to as the "seed". After identifying the seed, one reconstructs the syntax tree upwards, in the process of "growing the seed". Extensions to PEG using this method have been described in [6, 8, 12, 15{17].
The paper tries to nd out under which conditions this process will work
correctly. The idea of "working correctly" needs an explanation. One of the most
common ways to de ne the syntax of a formal language is the Backus-Naur Form
(BNF) or its extended version EBNF. We treat here PEG as a parser for BNF
that implements recursive descent with limited backtracking. Because of limited
backtracking, PEG may miss some strings that belong to the language de ned
by BNF. The author has previously tried to answer the question under which
conditions PEG will accept exactly the language de ned by BNF (see [
We look here at a process inspired by Hill [
We consider an extremely simpli ed form of BNF grammar over alphabet . It 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 2 ("letter"), A 2 N ("nonterminal").
e1e2 ("sequence"), e1je2 ("choice"). where each of e1; e2 is an expression and " denotes empty word. The set of all expressions is in the following denoted by E. There is exactly one rule A = e for each A 2 N . The expression e appearing in this rule is denoted by e(A).
Each expression e 2 E has its language L(e) de ned formally by natural semantics shown in Figure 1. String x belongs to L(e) if and only if [e]x BNF x ! can be proved using the inference rules from Figure 1. Note that if a proof of [e]x B!NF x exists, one can prove [e]xy B!NF x for every y 2
(empty) ["]w B!NF " [e1]xw B!NF x [e2]w B!NF y [e1e2]xw B!NF xy [a]aw B!NF a
(seq) [e1]w B!NF x [e1je2]w B!NF x (choice1)
[e2]w B!NF x [e1je2]w B!NF x
(choice2) (letter) [e(A)]w B!NF x [A]w B!NF x (rule) [Aa]baac B!NF baa [AajB]baac B!NF baa [A]baac B!NF baa
[a]a B!NF a [Ac]baac B!NF baac [S]baac B!NF baac The proof can be represented in the inverted form shown in Figure 3. This seems more intuitive when speaking about "recursive descent". The diagram on the right is simpli ed to show only the expressions. It is the syntax tree of baac. [S]baac B!NF baac [Ac]baac B!NF baac
[c]c B!NF c [A]baac B!NF baa [AajB]baac B!NF baa [Aa]baac B!NF baa
[a]a B!NF a [A]baac B!NF ba [AajB]baac B!NF ba [AajB]baac B!NF b [A]baac B!NF b [a]aa B!NF a [AajB]baac B!NF b [B]baac B!NF b [b]baac B!NF b
Fig. 3. BNF tree and syntax tree [c]c B!NF c
S Ac
c
A
Aa a A
Aa a
A B b
For e 2 E de ne first(e) as follows: first(") = first(a) = ∅;
first(A) = fe(A)g; first(e1je2) = fe1; e2g; first(e1e2) = {fe1g if " 2= L(e1); fe1; e2g if " 2 L(e1): De ne further First to be the transitive closure of relation first. In the following, we write e r!st e′ to mean that e′ 2 first(e), and e Fi!rst e′ to mean that e′ 2 First(e).
An expression e is left-recursive if e Fi!rst e. Let R E be the set of all leftrecursive expressions. De ne relation Rec R R so that (e1; e2) 2 Rec means e1 Fi!rst e2 Fi!rst e1. It is an equivalence relation that de nes a partition of R into equivalence classes; we refer to them as recursion classes. The recursion class containing expression e is denoted by C(e) .
Let e be an expression belonging to recursion class C. If e = A 2 N or e = e1e2 with non-nullable e1, the expression e′ 2 first(e) must also belong to C. This is so because e′ is the only element in first(e), and we must have e r!st e′ Fi!rst e to achieve e Fi!rst e. In e = e1je2 or e = e1e2 with nullable e1, one of expressions e1 or e2 may be outside C. It is a seed of C, and e is an exit of C. For e = e1e2 in C, e2 is a leaf of C. The set of all seeds of C is denoted by Seed(C) and the set of all its leafs by Leaf(C).
As an example, the grammar used in Figure 2 has R = fA; Aajb; Aag. All these expressions belong to the same recursion class with exit Aajb, seed b and leaf a.
To simplify the discussion, we asume in the following that all exits have the form e1je2, that is, e1 2 R in e1e2 is not nullable. As the ordering of BNF choice expression does not in uence its language, we assume that e2 in e1je2 is always the seed. 3.2
Consider a node in the syntax tree and the leftmost branch emanating from it. It is a chain of nodes connected by r!st . If the branch contains any left-recursive expressions, expressions belonging to the same recursion class C must form an uninterrupted sequence. Indeed, if e1 and e2 appearing in the branch belong to C, we have e1 Fi!rst e Fi!rst e2 Fi!rst e1 for any e in between. Such sequence is a recursion sequence of class C. The same argument shows that the branch can contain at most one recursion sequence of a given class, and that sequences of different classes cannot be nested.
The last expression in the sequence must be an exit of C. One can easily see that each recursion class must have at least one exit. We assume in the following that this is the case.
Let e r!st e′ be two consecutive expressions in a recursion sequence. Let [e]w B!NF x and [e′]w BNF x′. Expression e can be one of these:
! { A = e′. Then x = x′ according to (rule). { e′je2. Then x = x′ according to (choice1). { e1je′. Then x = x′ according to (choice2).
{ e′e2. Then x = x′y where y 2 L(e2) according to (seq).
De ne adv(e; e′) = f"g in each of the rst three cases and adv(e; e′) = L(e2) in
the last. For a recursion sequence s = e[n]; e[n 1]; : : : ; e[
Given a BNF grammar, we de ne for each e 2 E a parsing procedure named [e]. The procedure may return "success" after possibly "consuming" some input, or "failure" without consuming anything. In the following, the result of calling [e] for input w is denoted by [e]w; it is either fail or the consumed string x (possibly ").
The action of parsing procedure [e] for e 2= R is the same as in PEG and is shown in Figure 4.
The procedure [e] for e 2 R is a "grower" for the recursion class C(e) and input string w. The grower has a "plant" [e′; w] for each expression e′ 2 C(e). The plant is a procedure with memory. The procedure emulates the action of parsing procedure [e′], but may use results from other plants instead of calls to parsing procedures. It computes a result as shown in Figure 5. The memory holds the result of procedure applied to w. It is denoted by ⟨e′; w⟩. The grower initializes all its plants with ⟨e′; w⟩ = fail, and then repeatedly calls all plants in some order. If the result is better than already held by the plant, it replaces the latter. (A string is better than fail, and longer string is better than shorter one.) The grower stops when it cannot improve any result. The result in [e; w] is then the result of parsing procedure [e].
In order to create a formal record of parsing process, we represent actions of parsing procedures and plants by inference rules shown in Figure 6. A rule with conclusion [e]w = X represents a call to [e] returning X. One with conclusion ⟨e; w⟩ = x represents setting new result x in ⟨e; w⟩. A premise [e′]w = X ["] [a] [A = e1] Call [e1] and return result.
Indicate success without consuming any input.
If the text ahead starts with a, consume a and return success.
Otherwise return failure.
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 [e2] and return success if [e2] succeeded or failure if it failed. represents call a to sub-procedure [e′] returning X; a premise ⟨e′; w⟩ = X represents result obtained from [e′; w]. With these conventions, parsing process is represented as a formal proof.
An example of such proof is shown in Figure 7. It represents parsing process for the string and grammar from example in Figure 3. Note that part of that tree was constructed by going down and part by going up. [(e1j e2); w] If ⟨e1; w⟩ ̸= fail, return ⟨e1; w⟩.
If ⟨e1; w⟩ = fail and there exists plant [e2; w], return ⟨e2; w⟩.
Otherwise call [e2], restore input to w, and return [e2]w.
We say that "parsing procedure [e] handles string w" to mean that the procedure applied to w terminates and returns either x 2 or fail. Proposition 1. Each parsing procedure [e] for e 2 E handles all w 2 .
Proof is found in the Appendix.
Proposition 2. For each result [e]w = x or ⟨e; w⟩ = x in a parse tree there exists a proof of [e]w B!NF x.
Proof is by induction on height of the subtree.
The conditions under which each BNF tree has a corresponding parse tree depend on the context in which certain expression may be used. We assume that the grammar has a start expression S and use as context the BNF proof for [S]u B!NF u for u 2 .
For e 2 E, we de ne Tail(e) as the set of all strings that may follow a string
matched by e in the proof of [S]u BNF u. More precisely, it is the set of strings z in
!
all results [e]xz BNF x that appear in that proof. A possible method for estimating
!
Tail(e) can be found in [
The ordering of choice expression is essential for rules (choice2.p), (choice2.g ), and(choice3.g ). But, the ordering does not affect the language de ned by BNF rules. Therefore, we can always rearrange the choice as is best for the parsing. Proposition 3. If the grammar satis es the following conditions (1)-(3) then for each proof of [S]u BNF u there exists parse tree with root [S]u = u. Moreover, ! for each subproof [e]w B!NF x of that proof exists parse tree with root [e]w = x or ⟨e; w⟩ = x.
For each e = e1je2 2 R; e2 2= C(e); For each e = e1je2; L(e1) For each e 2 R; Adv(e)
\ L(e2)Tail(e) = ∅; \ TailR(e) = ∅: (1) (2) (3) Proof is found in the Appendix. 5
We presented sufficient conditions under which the extended PEG is a correct parser for BNF grammars. Because we treat PEG as parser for BNF, it does not include syntactic predicates of classical PEG.
We chose here the scheme for handling left recursion inspired by [
Checking (2) in the presence of left recursion is not simple. Without left recursion, one can use approximation by pre xes, with LL(1) as the extreme case. The languages de ned by left recursion often have identical pre xes and differ only at the far end.
The chosen scheme required a rather severe restriction (1) to the grammar. It seems possible to replace it by a requirement that languages of different seeds of the same recursion class are disjoint, as well as languages of expressions in first 1(e) for e 2 R. This is the subject of further research, as well as attempts to analyze other schemes.
["]w = " (empty.p) [a]aw = a (letter1.p) [e1]xz = x [e2]z = y
[e1e2]xz = xy [e1]xz = x [e2]z = fail
[e1e2]xz = fail [e1]w = x [e1j e2]w = x (choice1.p)
⟨[ee;]ww⟩==XX (grow.p) [b]awb ̸== afail (letter2.p)
[a]" = fail (letter3.p) (seq1.p) A.1
Proof of Proposition 1 ⊔⊓ ⊔⊓ ⊔⊓ (Induction base:) Obviously, each procedure of rank 0 handles w. (Induction step:) Assume that each procedure of rank m or less handles all words of length n + 1 or less. Take any procedure [e] of rank m + 1.
If e 2= R, e can be one of these:
length n + 1 or less, so e1je2 handles w. { e1e2 with nullable e1. We have (e1) m and (e2) { A 2 N . We have (e(A)) = m; thus e(A) handles w, and so does A. m. Each of them handles words of length n + 1 or less, so e1e2 handles w. { e1e2 with non-nullable e1. We have (e1) = m, so e1 handles w. If it fails, so w, with length n or less. Thus, e2 handles w′, so e1e2 handles w. does e1e2. Otherwise it consumes x ̸= " and e2 is applied to the rest w′ of { e1je2. We have (e1) m and (e2) m. Each of them handles words of If e 2 R, the result of [e] is obtained by grower for the recursion class C(e) and input w. The grower stops when it cannot improve any result. Each improvement means consuming more of w. Since w is nite, the grower must eventually stop.
Thus, [e] handles w.
Lemma 3. Each parsing procedure handles word of length 0.
The proof is by induction on the length of w with Lemma 3 as induction base and Lemma 2 as induction step.
Lemma 2. If each parsing procedure handles all words of length n or less, each parsing procedure handles all words of length n + 1.
Proof. Let the rank of expression e, denoted (e), be de ned as follows: { (") = (a) = 0, and otherwise: { For e 2= R, highest (e′) for e′ 2 First(e) plus 1; { For e 2 R, highest (e′) for e′ 2 Seed(C(e)) [ Leaf(C(e)) plus 1. One can easily see that this de nition is not circular.
Assume that each procedure handles all words of length n or less, and consider a word w of length n + 1. We use induction on rank of e to show that each [e] handles w.
Proof. The proof is essentially the same as that of Lemma 2, with w replaced by ", and simpli ed case of e1e2 with non-nullable e1.
A.2
Suppose we are given a BNF proof of [S]u BNF u. We are going to show that each partial proof of that proof (and the nal proof) has the corresponding parse tree. In the following, we say "subtree [e]w BNF x" to mean the partial proof with ! result [e]w B!NF x. De ne the level of subtree [e]w B!NF x as follows: ! for components of e. { For e = " and e = a the level is 1. { For e 2= R, other than above, the level is 1 plus the highest level of subtrees { Each result with e 2 R belongs to some recursion sequence. All subtrees in that sequence have the same level, equal to 1 plus the highest level of subtrees for the seed and leafs of that recursion sequence.
The proof is by induction on the level. (Induction base:) The parse trees for subtrees on level 1 are ["]w = " respectively [a]az = a. They represent calls to parsing procedures ["] and [a]. (Induction step:) Assume that there exists parse tree for each subtree on level n or less. We show that there exists parse tree for each subtree on level n + 1. For a subtree [e]w BNF x on level n + 1 where e 2= R we construct parse tree from ! parse trees of subtrees. This is done in Lemma 4 and represents calls from [e] to its subprocedures.
The root of each subtree [e]w B!NF x on level n + 1 where e 2 R belongs to some recursion sequence (perhaps degenerated to length 1). We construct parse trees for all results in the sequence from parse trees for the leafs and the seed. This is done in Lemma 5 and represents work done by the grower. on e:
! exists parse tree for [e]w B!NF x.
Lemma 4. Assume there exists parse tree for each subtree of [e]w B!NF x. There Proof. The parse tree for [e]w BNF x is constructed in the way that depends [A]w = x is constructed from it using (rule.p). { A = e′. [A]w BNF x is derived from [e′]w B!NF x according to (rule).
!
As assumed, there exists parse tree [e′]w = x for [e′]w B!NF x. The parse tree { e1e2. [e1e2]xz B!NF xy is derived from [e1]xz B!NF x and [e2]z B!NF y according ⊔⊓ (seq1.p).
! As assumed, there exist parse trees [e1]xz = x and [e2]z = y. for [e1)]xz B!NF x and [e2]z BNF y. The parse tree [e1e2]xz = xy is built from them using { e1je2 with [e1je2]w B!NF x derived from [e1]w BNF x according to (choice1). ! As assumed, there exists parse tree [e1]w = x for [e1]w B!NF x. The parse tree [e1je2]w = x is constructed from it using (choice1.p). { e1je2 with [e1je2]w BNF x derived from [e2]w BNF x according to (choice2).
! ! As assumed, there exists parse tree [e2]w = x for [e2]w BNF x. [e2]w B!NF x ! means w 2 L(e2)Tail(e). As speci ed in Figure 4, parser calls the procedure [e1] on z. According to Proposition 1, the call returns either fail or pre x y of w. By Proposition 2, this latter would mean w 2 L(e1) constructed from [e1]w = fail and [e2]w = x using (choice2.p). tradicts (2). Therefore must be [e1]y = fail. The parse tree [e1je2]w = x is , which conthe subtree [e[n]]w BNF x[n].
! The proof is by induction on n.
Lemma 5. If there exist parse tree for each seed and each leaf of recursion
sequence e[k]; : : : ; e[
Proof. Suppose the grower is called to handle e for input w. We start by showing that after the n-th round of the grower, ⟨e[n]⟩ contains the root of parse tree for As the grower checks all plants on each round, it will call ⟨e[n]⟩ on round n. ing to (seq).
is constructed from it using (rule.g ).
The result [e[
!
(Induction base:) Expression e[
rst round, [e1; z] contains fail. As e2 is
the seed of the sequence, there exists parse tree with root [e2]w = x. The parse
tree for ⟨e[
The e′ here is e[n] with parse tree ⟨e′; w⟩ = x. The parse tree for ⟨e[n+1]; w⟩ { e1e2 with [e[n+1]]xz B!NF xy derived from [e1]xz B!NF x and [e2]z B!NF y accordThe e1 here is e[n] with parse tree ⟨e1; xz⟩ = x. As e2 is a leaf of the sequence, there exists parse tree with root [e2]z = y. The parse tree for [e[n+1]; w] is constructed using (seq1.g ). { e1je2. By (1), e2 2= C. The BNF result [e[n+1]]w BNF x is derived from or ! [e2]w B!NF x according to (choice2). is stored in ⟨e[n]; w⟩ in every turn.
⟨e[n+1]; w⟩ is constructed from it using (choice1.g ).
As e[n] is in C, it must be e1 with parse tree ⟨e1; w⟩ = x. The parse tree for Note that from (3) follows " 2= Adv(e). Thus, according to Lemma 1, a new result (3). Thus, the grower stops at e[k].
Suppose the grower does not stop after e[k] because it nds a better result for plant [e[k]; w]. If this better result is x′, we have by Lemma 1 x′ = ⟨e[k]; w⟩Adv(e[k]) which means Adv(e[k]) is a pre x of TailR(e), and contradicts The parse tree [e]w = x is constructed from ⟨e[k]; w⟩ = x using (grow.p). ⊔⊓