|General Parser Question: Choicepoints email@example.com (2003-09-09)|
|From:||firstname.lastname@example.org (Andreas Grosam)|
|Date:||9 Sep 2003 22:58:09 -0400|
|Keywords:||parse, LL(1), question|
|Posted-Date:||09 Sep 2003 22:58:09 EDT|
I have a recursive decent parser generator which accepts LL(k) class
grammar, and the following grammar:
S = (A | B) a | C
(where upper case letters denote non terminals, and lower case letters
Suppose, the grammar does not have left recursion.
My question is, whether a recursive decent parser shall try the second
alternative (B a) if the first (A a) fails, before it tries C.
Just to mention this, the parser generator in question is Spirit
(www.boost.org, Spirit framework). The generated parser does not try
the alternative B, if A was successful, but (A a) failed. In that
case, it immediately tries C, without considering B a.
IMO, this is a more general question, namely, the question where a
parser sets its "choicepoint". For Spirit, it looks like it doesn't
remember the choice point within a production if one alternative
within this production succeeded.
If we restructure the BNF, we get:
S = A a | B a | C
Now, it looks more obvious, so that we suppose that a parser tries all
alternatives until one is successful: if (A a) fails, it tries the
next (B a) and then C. And Spirit does it as well.
But what is exactly the difference? Is Spirit behaving well? If yes,
is there a name for such "conflicts", or for the effect of using
parentheses? Are there differences with other classes of parsers, say
For your test case:
A = (ba)*
B = b*
C = c
and try "ba".
"ba" = B -> a
Any help appreciated, thanks!
Return to the
Search the comp.compilers archives again.