Recursive-descent parsers can not handle left recursion, and several solutions to this problem have been suggested. This paper presents yet another solution. The idea is to modify recursive-descent parser so that it reconstructs left-recursive portions of syntax tree bottom-up, by "recursive ascent". Recursive-descent parser is a collection of "parsing procedures" that correspond to diferent syntactic units and call each other recursively. Some of these procedures must choose what to call next, and the choice is made by looking at the input ahead, on depth-first basis. This process does not work if the grammar is left-recursive: the procedure may indefinitely call itself, facing the same input. One suggested solution [1] counts the number of recursive calls of each procedure and stops when it reaches a pre-set bound. The process is repeated with the bound starting with 1 and gradually increased. Another solution [2, 3] saves the input consumed by invocations of parsing procedures and tricks the parser to use the saved result instead of making recursive call. The third idea sees parsing as reconstruction of input's syntax tree. The classical process builds that tree top-down, but [4] suggests that portions of the tree involved in left recursion can be reconstructed starting from the bottom. We present here an approach based on this idea. To reconstruct portions of the tree bottom-up we use procedures that call each other recursively. These procedures can be regarded as new parsing procedures. We incorporate them into the recursive-descent parser, and the result is recursive-descent parser for a new grammar, referred to as the "dual grammar". The dual grammar is (normally) not left-recursive and defines the same language as the original one. After the necessary definitions in Section 2, Section 3 gives an example of recursive ascent, and shows that the procedures performing it can be seen as parsing procedures for new nonterminals. Section 4 incorporates these new non-terminals into the original grammar, thus obtaining the dual grammar. Two Propositions state the essential properties of that grammar. Section 5 discusses handling choice expressions, and Section 6 discusses the elements omitted to simplify the presentation. Section 7 contains some final remarks: relation to other solutions and unsolved problems. Proofs of the Propositions are given in the Appendix.
We consider a BNF-like grammar = (N, Σ, E, ℰ , ) with finite set N of non-terminals, finite set Σ of terminals, finite set E of expressions, function ℰ from non-terminals to expressions, and the start symbol .
An expression is one of these: • ∈ Σ ("terminal"), • ∈ N ("non-terminal"), • 1 . . . ("sequence"), • 1| . . . | ("choice"), where each of is an expression. The function ℰ is defined by a set of rules of the form → , where is the expression assigned by ℰ to non-terminal . We often write → to mean = ℰ ( ). To simplify the presentation, we did not include the empty string among expressions. In the following, expressions ∈ Σ and ∈ N will be viewed as special cases of choice expression with = 1.
Non-terminal → 1 . . . derives the string 1 . . . of symbols, while → 1| . . . | derives one of 1, . . . , . The derivation is repeated to obtain a string of terminals. This process is represented by syntax tree.
Figures 1 and 2 are examples of grammar , showing syntax trees of strings derived from the start symbol. The set of all strings derived from ∈ N is called the language of and is denoted by ℒ( ).
N = {Z,A,A1,B,B1,B2} Σ = {a,b,x,y} = Z Z → x A y A → A1 | a A1→ B a B → B1 | B2 | b B1→ A b B2→ B b
A a x
B B1
Z A A1
HH
y HH
a HH b For ∈ N and ∈ N ∪ Σ, define →first − to mean that parsing procedure for may call that for on the same input. We have thus:
ifrst • If → 1 . . . , →−
ifrst • If → 1| . . . | , →− 1.
for 1 ≤ ≤ .
Let →−First be the transitive closure of →first − . Non-terminal ∈ N is recursive if →− First . The set of all recursive non-terminals of is denoted by R. All non-terminals in Figure 1 except Z, and all non-terminals in Figure 2 are recursive.
N = {E,E1,F,F1} Σ = {a,b,x,z} = E E → E1 | F E1→ E + F F → F1 | a F1→ F * a
F
HH a E1 +
HH F a
F F1 *
HH a
Define relation between recursive 1, 2 ∈ R that holds if 1 →− First 1. This is an First 2 →− equivalence relation that partitions R into equivalence classes. We call them recursion classes. The recursion class of is denoted by C( ). All non-terminals in Figure 1 belong to the same class; the grammar of Figure 2 has two recursion classes: {E,E1} and {F,F1}.
In syntax tree, the leftmost path emanating from any node is a chain of nodes connected by →first − . Suppose 1 and 2 belonging to the same recursion class C appear on the same leftmost path. Any non-terminal between them must also belong to C, which follows from the fact that 1 →−First →−First 2 →−First 1. It means that members of C appearing on the same leftmost path must form an uninterrupted sequence. We call such sequence a recursion path of class C. The only recursion path in Figure 1 is the whole leftmost path from the first A without ifnal a. The syntax tree in Figure 2 has two recursion paths, one starting with E and another with F.
Let → 1 . . . be on a recursion path. The next item on the leftmost path is 1, and it
First . It follows that the last item on a recursion path must must belong to C( ) to ensure →− be → 1| . . . | where at least one of is not a member of C( ). Such is called an exit of C( ), and its alternatives outside C( ) are the seeds of C( ). In Figure 1, both A and B are exits, and the seeds are a and b. In Figure 2, E and F are exits of their respective classes, and the corresponding seeds are F and a.
A recursive that appears in expression for a non-terminal outside C( ), or is the start symbol, is an entry of its recursion class. It is the only non-terminal that can be first in a recursion path. The recursion class of Figure 1 has entry A, and recursion classes of Figure 2 have E and F as their respective entries.
To simplify presentation, we assume that each class has only one entry.
Recursive descent constructs the syntax tree implicitly, as the structure of its procedure calls. We assume that to serve any purpose, this tree has to be somehow registered. Thus, we assume that parsing procedures include "semantic actions" that actually build data structure representing the tree.
We suggest that parsing procedure for entry builds its syntax tree in a special way, illustrated below by parsing the string ’xabay’ from Figure 1. The parsing starts with procedure for non-recursive Z that, in the usual way, calls the procedures for ’x’, A, and ’y’. After consuming ’x’, Z applies A to ’abay’. The procedure for entry A is not the usual choice between A1 and a; instead, it reconstructs the subtree A as follows: 1. The recursion path from A must end with a seed. The seeds are a and b. Decide to try a. 2. Apply expression a to ’abay’. It consumes ’a’, leaving ’bay’. Use a as start of the tree. 3. The only possible parent of seed a in the syntax tree is its exit A. Add A on top of the tree, with a as child. 4. We have a tree for A, but decide to continue. 5. A appears only in B1→A b, so B1 is the only possible parent of A. 6. The tree for A is already constructed. Complete B1 by applying expression b to the remaining ’bay’. It consumes b, leaving ’ay’. Add B1 on top of the tree, with A,b as children. 7. B1 appears only in B→B1|B2|b, so B is the only possible parent of B1. 8. Add B on top of the tree, with B1 as child.
9. The possible parents of B are A1→B a and B2→B b. Decide for A1. 10. The tree for B is already constructed. Complete A1 by applying expression a to ’ay’. It consumes ’a’, leaving ’y’. Add A1 on top of the tree with B,a as children. 11. The only possible parent of A1 is A→A1. 12. Add A on top of the tree, with A1 as child. 13. We have a tree for A, and decide to stop. Return the tree of the consumed ’aba’ to Z, which continues to consume y and constructs the tree for ’xabay’.
In general, the procedure for entry chooses and executes one of procedures that correspond
to diferent seeds. In the example, the choice is made in step 1, and the selected procedure
consists of steps 2-13. The procedure for seed starts with constructing the tree for and
follows by executing a procedure that adds node for the containing exit ; then it proceeds to
grow the resulting tree towards . These are the steps 2 respectively 3-13 in our example. This
may be seen as parsing procedure that implements a new expression for :
→ 1 $1| . . . | $
(
We can see $ as a special case of procedure $ that adds a new node on top of previously constructed tree. This is the case in steps 6, 8, 10, and 12 of our example. The procedure then continues to build the tree, which is in each case done in the subsequent steps up to the step 13.
The way of adding on top of tree depends on as illustrated in Figure 3.
If → 12 . . . (where 1 = ), $ builds the trees for 2, . . . , , binds them with into the tree for . The whole procedure can be seen as parsing procedure for new non-terminal: where 2, . . . , are procedures for these expressions and # continues the growing.
If → 1| . . . | (where = for some ), the procedure just adds on top of and proceeds to grow that tree. This can be seen as parsing procedure for: $ → 2 . . . #
$ → # .
# → $1| . . . |$
Procedure # consists of choosing a possible parent of node and adding that parent to the tree. This can be seen as parsing procedure for another new non-terminal: where are all members of C such that →ifrst − .
In our example, the choice (
If is identical to , # can choose to terminate building of the tree. Therefore, # must have an alternative to allow that:
# → $1| . . . |$|$ where procedure $ returns the tree constructed for . It was not chosen in step 4, but terminated the process in step 13.
As shown above, parsing procedure for an entry expression can be implemented by a set of
procedures that reconstruct portion of syntax tree bottom-up, by "recursive ascent". These
procedures can be seen as parsing procedures for new non-terminals. We can add these
nonterminals to the original grammar. The result for the grammar of Figure 1 is shown in Figure 4.
Here we replaced the expression for entry A by (
In general, the dual grammar is obtained as follows: • For each entry replace ℰ () by 1 $1| . . . | $
where 1, . . . , are all seeds of C(), and is the exit containing . • Replace each recursive → 12 . . . by $ → 2 . . . #. • Replace each recursive → 1| . . . | by $ → #. • For each ∈ R create: – # → $1| . . . |$ if ̸= , – # → $1| . . . |$|$ if = , ifrst where 1, . . . , are all members of C() such that →− , and is the entry of C.
The dual grammar is an n-tuple = (N, Σ, E, ℰ, ). Its set N consists of: • The non-recursive members of N; • The entries to recursion classes; • The $-expressions; • The #-expressions.
In the following, the set of all non-recursive members of N is denoted by R, and the set of all entries by RE. They appear as non-terminals in both and . The set R ∪ RE of these common symbols is denoted by N. Functions ℰ and ℰ assign the same expressions to members of R. The two important facts about the dual grammar are: Proposition 1. The dual grammar is left-recursive only if the original grammar contains a cycle, that is, a non-terminal that derives itself.
Proof is found in the Appendix.
Proposition 2. ℒ( ) = ℒ( ) for all ∈ N.
The start symbol is either non-recursive or an entry, so it appears in both grammars, and thus both grammars define the same language. It means that recursive-descent parser for the dual grammar is a correct parser for the original grammar, and its "semantic actions" build syntax tree for the original grammar.
The construction of dual grammar introduces a number of choice expressions. We assume that
they are treated in the same way as those originally present in the grammar. If dual grammar
has the LL() property, the choice can be made by looking at the next input terminals. The
dual grammar of Figure 4 is LL(
If the dual grammar is not LL(), the possible option is trial-and-error with backtracking. As this may result in exponential processing time, the practical solution is limited backtracking, recently being popular as the core of Parsing Expression Grammar (PEG) [5]. (As a matter of fact, the three solutions named in the Introduction are all suggested as modifications to PEG.)
The problem with limited backtracking is that it may fail to accept some legitimate input strings. For some grammars, which may be called "PEG-complete", limited backtracking does accept all legitimate strings. Thus, if the dual grammar is PEG-complete, it provides a correct parser for the original grammar.
There exist a suficient condition that may be used to check if the dual grammar is PEGcomplete [6].
The checks for LL() and PEG-completeness are carried on dual grammar. It is the subject of further research how they can be replaced by checks applied to the original grammar.
We made here two simplifying assumptions. First, we did not include empty string in the grammar. Second, we assumed a unique entry to each recursion class.
The result of adding is that some expressions may derive empty string. These expressions are referred to as nullable, and can be identified as such by analyzing the grammar.
Nullable 1 in → 1 . . . invalidates the whole analysis in Section 2. Nullable 2 . . . in recursive → 12 . . . invalidates the proof of Proposition 1. Except for these two cases, our approach seems to work with empty string.
The assumption of unique entry per recursion class is not true for many grammars; for example, the class of Primary in Java has four entries.
The exit alternative $ must appear in # for the entry that actually started the ascent. This can be solved by having a separate version of # and $ for each entry, multiplying the number of these non-terminals by the number of entries.
A practical shortcut can exploit the fact that the ascents are nested. One can keep the stack of entries for active ascents and modify the procedure for # to check if is the entry to current ascent.
The traditional way of eliminating left recursion is to rewrite the grammar so that left recursion is replaced by right recursion. It can be found, for example, in [7], page 177. The process is cumbersome and produces large results; most important, it loses the spirit of the grammar. Our rewriting is straightforward and produces correct syntax tree for the original grammar.
The methods described in [1, 2, 3] use memoization tables and special code to handle them. The procedures are repeatedly applied to the same input. Our approach is in efect just another recursive-descent parser.
Our idea of recursive ascent is in principle the same as that of [4], but this latter uses specially coded "grower" to interpret data structures derived from the grammar.
As indicated in Section 6, our method does not handle some cases of nullable expressions. Among them is the known case of "hidden" left recursion: → 12 . . . becomes left recursive when 1 derives . Another unsolved problem is → + | , which results in a right-recursive parse for . For ∈ N and ∈ N ∪ Σ, define parsing procedure on the same input:
→r−stD fi (a) For ∈ R, →r−stD if is the same as →first − .
ifrstD for each seed of C( ). (b) For ∈ RE, →− (c) For $ → 2 . . . #, $ →r−stD fi 2. (d) For $ → #, $ →r−stD fi
#. ifrstD $ for each ∈ C() such that →− ifrst (e) # →− .
to mean that parsing procedure may call Grammar is left-recursive if F− →irstD for some ∈ N, where F− →irstD is the transitive closure ifrstD . of →−
FirstD and = 1. We start by showing that none of them can be in N. . . . →− Suppose is left-recursive, that is, exist 1, 2, . . . , ∈ N such that 1 F− →irstD 2 F− →irstD Assume, by contradiction, that 1 ∈ N. We show that in this case 2 ∈ N and 1 →−First 2. (Case 1) 1 ∈ R. Because ℰ(1) = ℰ (1), 2 is in N, and thus in N. We have 1 →first − 2. (Case 2) 1 ∈ RE. According to (b), 2 is a seed of C(1), which is either non-recursive or an First 2. entry, and thus is in N. For a seed 2 of C(1) holds 1 →− (Conclusion) The above can be repeated with 2, . . . , − 1 to show that if any of is in N, then for all , 1 ≤ ≤ ∈ N and →−First . Thus, all belong to R and are all in the same recursion class. As none of belongs to R, they must all be in RE. Then, in particular, 1 ∈ RE. But, according to (b), 2 is a seed of C(1), that cannot be a member of C(1). Thus, 1 ∈/ N.
It follows that each is $ or # for some ∈ R. If → 2 . . . , we have from (c) $ →r−stD fi 2, and 2 ∈ N. That means all are choice expressions. Thus, the sequence of is a repetition of $, #+1, $+2 where, according to (d), +1 = , and according to (e), +2 → . . . |+1| . . . . That means +2 derives , and in /2 steps derives itself. □
The proof is in terms of syntax trees. We write ◁ for syntax tree of with root . We write ◁ [1◁ 1+· · · +◁ ] to represent syntax tree with root and children 1◁ 1, . . . , ◁ where 1 . . . = .
To distinguish between the trees according to grammar (-trees) and those according to grammar (-trees) we use the symbols ◁ respectively ◁ .
Assuming that a terminal derives itself, we show that every string derived from ∈ N ∪ Σ according to can be also derived from according to and vice-versa. The proof is by induction on height of syntax trees. (Induction base) Syntax tree of height 0. This is the syntax tree of a terminal. The terminals and their syntax trees are identical in both grammars. (Induction step) Assume that the stated property holds for all strings having syntax tree of height ℎ ≥ 0 or less. Lemmas 1 and 2 below show that it holds then for syntax trees of height ℎ + 1.
Lemma 1. Assume that for each ◁ of height ℎ ≥ 0 with ∈ N ∪ Σ exists ◁ . Then the same holds for each ◁ of height ℎ + 1.
Proof. Take any ◁ of height ℎ + 1 where ∈ N. (Case 1) ∈ R. It means → 1 . . . or → 1| . . . |.
We have ◁ [1◁ 1 + · · · + ◁ ] respectively ◁ [ ◁ ]. Each of the subtrees ◁ has height ℎ or less and each is in N ∪ Σ. By assumption, exists ◁ for each . The required -tree is ◁ [1◁ 1 + · · · + ◁ ] respectively ◁ [ ◁ ]. (Case 2) ∈ RE. The tree ◁ has the leftmost path →ifrst − . . . →first − 1 →first − 0 where = , ∈ C( ) for ≥ > 0, and 0 is a seed of C( ). Define to be the string derived by from , for 0 ≤ ≤ . We have thus = .
Define 0 be the string derived by from 0, so the subtree for 0 is 0◁ 0. Let 1 ≤ ≤ . If → 12 . . . , the subtree for is ◁ [− 1◁ − 1 + 2◁ 2 + · · · + ◁ ]. Define = 2 . . . , so = − 1. if → 1| . . . |, the subtree for is ◁ [− 1◁ − 1] Define = , so we have again = − 1.
One can easily see that = = 0 . . . .
Define to be the string derived by from $, and to be the string derived by from #, for 0 ≤ ≤ .
For entry exists the tree #◁ . If $ → #, exists the tree $◁ [#◁ ] = . If $ → 2 . . . #, exists by assumption D-tree for each of , deriving, respectively, . Thus, exists the tree $◁ [2◁ 2 + + ◁ + #◁ ]2 . . . = . Define = .
Suppose that exists the tree $◁ . Then exists the tree #− 1[◁ $◁ ]. By construction similar to the above, w find the D-tree for $− 1 deriving − 1 = − 1. At the end, we ifnd the D-tree for $ 1 deriving 1 = 12.
By assumption there exists D-tree for the seed 0 deriving 0. For entry we have → 0$1, which gives the D-tree ◁ [0◁ 0 + $◁ 1]01. One can easily see that 1 = 1 . . . , so we have a D-tree for = deriving = 0 . . . . □ Lemma 2. Assume that for each ◁ of height ℎ ≥ 0 with ∈ N ∪ Σ exists ◁ . Then the same holds for each ◁ of height ℎ + 1.
Proof. Take any ◁ of height ℎ + 1 where ∈ N. (Case 1) ∈ R. It means → 1 . . . or → 1| . . . |. We have ◁ [1◁ 1 + · · · + ◁ ] respectively ◁ [ ◁ ]. Each of the subtrees ◁ has height ℎ or less and each is in N ∪ Σ. By assumption, exists ◁ for each . The required -tree is + ◁ ] respectively ◁ [ ◁ ]. ◁ [1◁ 1 + · · · (Case 2) ∈ RE. The D-tree of has root , node for seed of C( ),and nodes $, # for 1 ≤ ≤ . Denote = and 0 = . Denote the string derived by $ and that derived by #. We have = +1 for < and = . Denote by 0 the string derived by 0 and by one derived by = .
The D-tree for is ◁ [0◁ 0 + $1◁ 1]01 = .
If $ → 2 . . . #, we have = 2 . . . . where is the string derived by . Defining = 2 . . . by , we have = .
If $#, we have = . Defining = , we have again = .
We have = ( + 1) for < and = , so = ( + 1) for < and = . One can easily see that = 0 . . . .
By assumption exists G-tree 0◁ 0. Suppose we have the G-tree for − 1 where 1 ≤ ≤ that derives − 1.
Suppose → ( − 1)2 . . . . By assumption exist G-trees that derive 2 . . . from 2 . . . , so exists G-tree for deriving = ( − 1)2 . . . = ( − 1). Suppose → ( − 1). Then exists G-tree deriving = ( − 1) = ( − 1). One can easily see that the string derived by is 0 . . . = □