[antlr-interest] RFC re/ Left factoring and Syntactic Predicate
Ric Klaren
ric.klaren at gmail.com
Wed Jul 6 14:49:47 PDT 2005
Subhobroto Sinha wrote:
> The FLOAT vs INT issue is an often repeated topic, and as I am
> currently in the same trap, I wish to resolve it as much as possible
> (to benefit me as well as others)
>
> Intutively defn. of an INT is : ('0' .. '9')+;
> A FLOAT is : : INT '.' INT;
>
> Let's write that again :
>
> coefficient : INT | INT DOT INT;
>
> Left Factoring :
>
> coefficient : INT leftNumFactor;
>
> leftNumFactor : DOT INT | /* epsilon */;
>
> However, ANTLR barks at me in a rule in my TreeWalker :
>
> csvCoeffs : (coefficient)+;
>
> It says :
>
> DSD.mail.g:40: warning:nondeterminism upon DSD.mail.g:40: k==1:INT
> DSD.mail.g:40: between alt 1 and exit branch of block
Not sure.. it can also be due to other parts of your grammar non
determinism errors are usually dependent on your whole grammar (the
links didn't work when I tried). Also you left out which rules in the
above are protected. I would suspect that leftNumFactor should be
protected in a lexer (all non protected rules get or-ed together in the
nextToken rule which usually leads for newcomers to unexpected non
determinism)
I'd be inclined to write the left factor like:
coefficient : INT {$setType(INT);}( DOT INT {$setType(FLOAT) )?;
> I am really in the dark here. I am sure I left factored right, so
> where is the problem ? I might mention that the program is working
> just as I wanted, but I feel bad about any warnings ;)
Some antlr warnings are hard to shut up. (I personally do not bother
about them since adding/removing/modifying a rule can turn up things
that you want to be warned about in spots were you previously turned of
warnings)
> On the other hand, an alternate version of mine, which employs
> syntactic predicate on FLOAT and INT seems to work too, but issues
> similar nondeterminism warnings in the TreeWalker ?
Syntactic predicates are performance killers. Only use them during
prototyping and when you really cannot do something else. Or if you have
other reasons like readability etc.
> What am I doing wrong in the tree walker ?
> Also, what are your views on left factoring vs. syntactic predicates
Left factoring is better performance wise. It may kill the readability
of your grammar though.
Cheers,
Ric
More information about the antlr-interest
mailing list