[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