9 Sep 2003 22:58:09 -0400

Related articles |
---|

General Parser Question: Choicepoints agrosam@onlinehome.de (2003-09-09) |

From: | agrosam@onlinehome.de (Andreas Grosam) |

Newsgroups: | comp.compilers |

Date: | 9 Sep 2003 22:58:09 -0400 |

Organization: | http://groups.google.com/ |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.