[antlr-interest] Why is this nondeterministic?

[Terence Parr]

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/