General Parser Question: Choicepoints

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
are terminals)


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
LR, LALR?


For your test case:
A = (ba)*
B = b*
C = c


and try "ba".
"ba" = B -> a




Any help appreciated, thanks!


Andreas Grosam

Return to the comp.compilers page.
Search the comp.compilers archives again.