Spurious nondeterminism warnings from antlr 2.7.6

Question

I'm trying to create a simple expression parser with antlr 2.7.6 and am getting some nondeterminism warnings during compilation. The generated java source seems to work exactly as i want it, but I would like to know if its possible to suppress this warnings or if I'm doing something wrong in the grammar.

The parser is to be used in a project that already has a dependency on this old antlr version, so upgrading to 3.4 is probably not an option. The grammar itself look similar to the one in this answer.

Here is the output during compilation:

Using Antlr grammar: expr.g
ANTLR Parser Generator   Version 2.7.6 (2005-12-22)   1989-2005
expr.g:15: warning:nondeterminism upon
expr.g:15:     k==1:OR
expr.g:15:     between alt 1 and exit branch of block
expr.g:19: warning:nondeterminism upon
expr.g:19:     k==1:AND
expr.g:19:     between alt 1 and exit branch of block

And here is the simplified grammar exhibiting the problem:

header {
package net.jhorstmann.i18n.tools;

import net.jhorstmann.i18n.tools.*;
import net.jhorstmann.i18n.tools.expr.*;
}

class ExprParser extends Parser;

expression returns [Expression r = null]
    : r=or_expr
    ;

or_expr returns [Expression r = null] { Expression e = null; }
    : r=and_expr   (OR e=and_expr   { r = new OrExpression(r, e); })*
    ;

and_expr returns [Expression r = null] { Expression e = null; }
    : r=prim_expr  (AND e=prim_expr { r = new AndExpression(r, e); })*
    ;

prim_expr returns [Expression r = null] { Expression e = null; }
    : b:BOOL                   { r = new ConstantExpression(Integer.parseInt(b.getText())); }
    | NOT e=expression         { r = new NotExpression(e); }
    | OPEN e=expression CLOSE  { r = e; }
    ;

class ExprLexer extends Lexer;

options {
    k=2;
}

WS      : (' ' | '\t')+ { $setType(Token.SKIP); };
BOOL    : '0' | '1';
NOT     : '!';
OPEN    : '(';
CLOSE   : ')';
OR      : '|' '|';
AND     : '&' '&';

score 2 · Accepted Answer · edited Feb 19 '12 at 13:14

2

Odd, ANTLR 3 has no problems with such a grammar.

Because its warning about an "exit branch of block", try anchoring your entry rule with an end-of-file token (EOF):

expression returns [Expression r = null]
    : r=or_expr EOF
    ;

EDIT

I'd include an unary negate-expression like this:

expression
    : or_expr EOF
    ;

or_expr
    : and_expr (OR and_expr)*
    ;

and_expr
    : unary_expr (AND unary_expr)*
    ;

unary_expr
    : NOT prim_expr
    | prim_expr
    ;

prim_expr
    : BOOL
    | OPEN or_expr CLOSE
    ;

edited Feb 19 '12 at 13:14

Jörn Horstmann

33,639
11
75
118

answered Feb 19 '12 at 10:16

Bart Kiers

166,582
36
299
288

Thanks, adding `EOF` fixed the warning, if antlr is allowed to NOT consume all the input then I see where the nondeterminism is. Adding `options {greedy=true;}:` before the `OR` token also shut up the warning but your solution is much better. The colon seems to be required for assignments from lexer rules. – Jörn Horstmann Feb 19 '12 at 12:35
@JörnHorstmann, ah, I see, didn't know about the difference between `x:TERMINAL` and `y=production` in v2.7. – Bart Kiers Feb 19 '12 at 12:47
Hm, I spoke too soon, if I simply add the `EOF` then the expression `!(0)` won't be parsed anymore, if I change the rule to `NOT e=or_expr` the warnings return. – Jörn Horstmann Feb 19 '12 at 12:51

Spurious nondeterminism warnings from antlr 2.7.6

1 Answers1

EDIT