Re: Why LL(1) Parsers do not support left recursion?
- From: "Michael J. Fromberger" <Michael.J.Fromberger@xxxxxxxxxxxxxxxxxxxxxx>
- Date: Fri, 14 Jul 2006 22:41:35 -0400
In article <1152901010.912831.237230@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"DevInstinct" <martin_lapierre@xxxxxxxxxxxx> wrote:
Hi, first of all, I'm not an expert in the theory of computation.
I've read about LL(1) parsers and I have seen that they do not support
left recursion, because it is said that it would lead to infinite
recursivity.
My question: why is that? In which case a LL(1) parser can enter
infinite recursivity?
I can't find a good example that demonstrates that.
The short answer is, "because a grammar with left recursion is not
LL(1)." But if you wanted a more detailed response, please read on! :)
Strictly speaking, it is a property of a _grammar_ to be LL(1), not a
parser. So, someone who speaks of "an LL(1) parser" probably means "a
parser capable of processing a language whose grammar is LL(1)."
In order for a grammar to be LL(1), it must be possible to construct a
leftmost derivation for any string in its language with only the pieces
of the string prior to the leftmost nonterminal, plus one token of
lookahead. For example, let's consider the following simple grammar:
A = b C b
C = D S
D = d D | x
S = s S | y
With this grammar, whose start symbol is A, let's consider parsing the
string "bdxsyb". Our derivation begins with A. Now A is the leftmost
nonterminal, so we have to find a rule to expand. Since the first input
token is "b" and we have only one rule for A that begins with a "b", we
can expand by that rule,
A ==>
b C b
Now, C is the leftmost nonterminal. There is only one rule for C, so we
use it, giving
b C b ==>
b D S b
Now, D is leftmost. There are two rules for D (D = d D and D = x), but
the next input is "d" so we can only choose D = d D, giving
b D S b ==>
b d D S b
Now, D is again leftmost. The next input is "x", so this time we choose
D = x, giving
b d D S b ==>
b d x S b
Now, S is leftmost. There are two rules for S (S = s S and S = y), but
the next input is "s" so we choose S = s S, giving
b d x S b ==>
b d x s S b
Now, S is again leftmost. The next input is "y", so this time we choose
S = y, giving
b d x s S b ==>
b d x s y b
At this point, we are finished with the parse, because there are no more
nonterminals to be replaced. At each stage, you see that we were able
to figure out which rule to use with only one extra input token.
Unfortunately, a grammar with left recursion is not LL(1). For example,
here is such a grammar:
A = B C
B = B b | c
C = c
Now consider the problem of parsing the string "cbbc" with this grammar.
It should work, because A ==> B C ==> B b C ==> B b b C ==> c b b C ==>
c b b c. But let's see what happens. We start with A, and we have only
one rule, so we use it:
A ==>
B C
Now, B is leftmost. There are two rules, and the first token is "c".
But BOTH rules for B can begin with a "c", so we cannot tell which to
expand without looking further ahead. Since we are only allowed to look
1 token ahead (as this is LL(1)), we can't choose.
You might say, "well, B = c is the obvious choice, because it really
begins with c." But if you do that, the parse fails:
B C ==>
c C
Now there is only one rule for C (C = c), but it does not begin with
"b", which is the next input character, and so we would mistakenly
conclude that "cbbc" is not a valid string for this grammar.
You mentioned some concern about "infinite recursion" when parsing a
grammar with left recursion -- this is chiefly a problem for parsers
using the "recursive descent" method of implementation, but I think it
is mostly orthogonal to the LL(1) issue.
I hope this helps!
Cheers,
-M
--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA
.
- References:
- Why LL(1) Parsers do not support left recursion?
- From: DevInstinct
- Why LL(1) Parsers do not support left recursion?
- Prev by Date: Re: solving #SAT in poly(number of vars) and exp(number of clauses)?
- Next by Date: Reductions in P
- Previous by thread: Why LL(1) Parsers do not support left recursion?
- Next by thread: Reductions in P
- Index(es):
Relevant Pages
|
