[antlr-interest] Why is this nondeterministic?

[Brian Smith]

Terence,

I'm a newbie and I don't understand your answer (and I am not the 
original poster). There is a "simplified" version of the problem below 
(fewer subrules) that has a similar (the same?) nondeterminism. There is 
no way that REGULAR_BIT could match 'a' 'b'. So, whenever I see an 'a' 
'b' it must be a SPECIAL, right? In fact, that is what the generated 
code does.

Also, if you take the closure (...)+ off of regular_bit then it works. 
So, it must be a problem caused by strings longer than three characters, 
or a problem with the end-of-input case, AFAIK. Could somebody please 
demonstrate a string that is ambiguous with this lexer?

Thanks,
Brian

class AbcLexer extends Lexer;

options
{
     k = 2;
     charVocabulary = 'a'..'c';
}

REGULAR:
     (REGULAR_BIT)+;

SPECIAL:
     'a' 'b'
;

protected
REGULAR_BIT:
     ('b')
|   ('a' 'c')
;

Terence Parr wrote:
> On Sunday, May 26, 2002, at 03:53  PM, danfuzz wrote:
> 
> 
>>The following is a very simplified version of a grammar I'm working
>>on (attached below). When I try to compile it, I get the following
>>warning:
>>
>>warning: lexical nondeterminism between rules REGULAR and SPECIAL upon
>>/home/danfuzz/cvs/local/stuplate/com/milk/stuplate/abc.g:0: k==1:'a'
>>/home/danfuzz/cvs/local/stuplate/com/milk/stuplate/abc.g:0: k==2:'b'
>>
>>I don't understand why it's nondeterministic, and so I'm not sure how
>>to change it. Help would be appreciated. Thanks!
> 
> 
> Hi Dan,
> 
> The problem is that 'a' 'b' can start both REGULAR (via REGULAR_BIT) and 
> SPECIAL.  The lexer, given "ab" input would not know which token to 
> make.  This is an ambiguous grammar, which implies that it is also 
> nondeterministic.
> 
> Regards,
> Terence
> 
> 
>>class AbcLexer extends Lexer;
>>
>>options
>>{
>>    k = 2;
>>    charVocabulary = 'a'..'c';
>>}
>>
>>REGULAR:
>>    (REGULAR_BIT)+;
>>
>>SPECIAL:
>>    'a' 'b'
>>;
>>
>>protected
>>REGULAR_BIT:
>>    ('b' | 'c')
>>|   ('a' 'a')
>>|   ('a' 'c')
>>;
>>
>>
>>
>>
>>Your use of Yahoo! Groups is subject to 
>>http://docs.yahoo.com/info/terms/
>>
>>
> 
> --
> 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/ 
> 



 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/