[antlr-interest] pls help
Terence Parr
parrt at jguru.com
Thu Dec 13 17:37:17 PST 2001
On Thursday, December 13, 2001, at 04:14 PM, leonchiver wrote:
> Hi,
>
> I have following stripped down grammar:
>
> class MyParser extends Parser;
>
> options {
> k = 2;
> }
>
> startRule :
> rule
> (OR rule)*;
> rule :
> S
> (X startRule Y)*
> (X Y)?;
>
> ...
> for which I'm getting the warning:
>
> nd.g:12 warning: nondeterminism upon
> nd.g:12: k==1:X
> nd.g:12: k==2:S
> nd.g:12: between alt 1 and exit branch of block
>
> (line 12 is >>>> (X startRule Y)* <<<<)
>
>
> I just can't figure out where the ambiguity comes from. For k = 1 it's
> clear
> that the subrules (X startRule Y)* and (X Y)? will generate an ambiguity
> but where from comes the warning for k = 2?
>
> I would be very grateful if someone could explain me where my error
> lies.
The answer lies in the diff between approx and full LL(k) lookahead. S
can appear in *a* place at k=2 but not necessarily after X directly. It
would be OR S as far as I can guess. X S is the path that chooses to
enter loop (X startRule Y)*. XY is the path choosing (X Y)? but must be
combined with path that ignores (X Y)?. OR S is the path ignoring (X
Y)? and looping in the (OR rule)* to have OR followed by FIRST(rule),
which is S. Merging lookahead at k=1 and then k=2 you have k=1:
{OR,X} then k=2:{S,Y}. So enter loop induced by X S that intersections
with lookahead for exit.
This is a limitation of the parser not your understanding. The solution
is to shuffle your grammar a bit.
Ter
--
Chief Scientist & Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list