[antlr-interest] Weird problem with semantic predicates. Incorrect warning message

[John B. Brodie]

On Tuesday 28 April 2009 05:08:08 pm Gabriel Petrovay wrote:
> 1. warning(200): exit_test.g:9:3: Decision can match input such as
> "IF" using multiple alternatives: 1, 3
>
> The IF does not MATCH the first alternative, therefore, the warning is
> NOT correct.

I assume by now you have taken Jim's suggestion to view your grammar in 
antlrworks and see the ambiguity on IF between alts 1 and 3 of the 
p_ExprSingle rule.

> Why is the warning disappearing when I delete the second alternative?
> If the warning were correct, it should still be displayed.

Usually antlr can resolve this sort of ambiguity by increasing its lookahead. 
In this case a lookahead of k=2 is needed to resolve the ambiguity (by seeing 
a LPAREN after an IF we know we have a p_IfExpr otherwise we have a 
p_StepExpr)

For some reason the predicate is preventing antlr from choosing k=2. perhaps 
this is the normal way predicates are handled, i do not know, i try really 
really hard to avoid any kind of predicates.

If you delete the alternative containing the predicate, antlr will now choose 
k=2 for this decision and the ambiguity thereby disappears.

Also if you specify k=2; in an options{} block at the top of the file, the 
warning also goes away.

> WITH PROBLEM
> p_ExprSingle
> ? ?: p_IfExpr
> ? ?| {false}?=> p_ExitExpr
> ? ?| p_StepExpr
> ? ?;
>
> WITHOUT PROBLEM
> p_ExprSingle
> ? ?: p_IfExpr
> // ? ?| {false}?=> p_ExitExpr
> ? ?| p_StepExpr
> ? ?;
>
>
>
> 2. I want to parse the following texts where p_ExprSingle is the start
> rule: --------
> if // rule 3
> --------
> if(blah) ?// rule 1 -> rule 3 for 'blah'
> --------
> if(if) // rule 1 -> rule 3 for the 'if' in parantheses
> --------
>
> So far the rule p_ExprSingle with only 2 alternatives does the job.
> What about the following texts:
>
> --------
> if(exit with a)
> --------
> if(exit with if)
> --------
> if(exit with exit with exit)
> --------
>
> The p_ExitExpr is only available once a flag is set (therefore I use
> the semantic predicate). If you delete the semantic predicate you will
> see some correct warnings. As long as you have the predicate, the
> warning is not correct anymore.
>
> The problem is for sure the grammar ambiguity that John pointed out in
> a previous e-mail.
>
> I hope these examples together with the shortened-revised parser
> grammar below makes a little more sense to you. I cannot make it
> simpler.

delete the ambiguous p_ReplaceExpr rule.
delete the predicate but keep the p_ExitExpr alternative in p_ExprSingle.
and now your grammar does what you want.
(i might have made some other changes, can't remember)
see attached complete example.

> PARSER GRAMMAR
> --------------------------
>
> p_ExprSingle
> ? ?: p_IfExpr
> ? ?| {false}?=> p_ExitExpr
> ? ?| p_StepExpr
> ? ?;
>
> p_IfExpr
> ? ?: IF LPAREN p_ExprSingle RPAREN
> ? ?;
>
> p_StepExpr
> ? ?: L_NCName | IF | EXIT
> ? ?| LBRACKET p_ExprSingle RBRACKET
> ? ?;
>
> p_ReplaceExpr
> ? ?: REPLACE p_ExprSingle WITH p_ExprSingle
> ? ?;
>
> p_ExitExpr
> ? ?: EXIT WITH p_ExprSingle
> ? ?;
>
>
>
> Regads,
> Gabriel
>
> Original message
>
> > Hi,
> >
> > Thanks a lot John for make it it clear. Although I see the problem and
> > I think that generates everyting, there are at least a couple of
> > problems with ANTLR:
> >
> > 1. The Warning is incorrect: Decision can match input such as "IF"
> > using multiple alternatives: 1, 4. ?As a result, alternative(s) 4 were
> > disabled for that input.
> >
> > This is non-sense to me since decision 1 in p_ExprSingle does not
> > match "IF". Only decision 4 can match it (p_StepExpr)
>
> No, the warning is perfectly correct. Use ANTLRWorks, do the Check
> Gramar, select the rule in red, select the syntax tab, turn on both
> paths, your problem will be obvious.
>
> > 2. What do those two alternatives (1 and 4) have to do with the
> > alternative 2 (p_ExitExpr) and a rule that is NOT used anywhere
> > (p_ReplaceExpr) ???
>
> Because in the look ahead set, you calculate all possible tokens that
> the grammar says can come next, not just the rule that you have
> provided. Basically your grammar does not make a lot of sense and ANTLR
> is trying to tell you this. You might be better starting with the
> examples and building up from there; trying to run before you can walk
> gets you in to trouble with grammars ;-)
>
> Jim
>
>
> --
> MSc Gabriel Petrovay
> MCSA, MCDBA, MCAD
> Mobile: +41(0)787978034

-------------- next part --------------
grammar Test;

options {
	output = AST;
	ASTLabelType = CommonTree;
}

@members {
    private static final String [] x = new String[]{
        "if", "if(a)", "if(if)",
        "if(exit with a)", "if(exit with if)", "if(exit with exit with exit)"
    };

    public static void main(String [] args) {
        for( int i = 0; i < x.length; ++i ) {
            try {
                System.out.println("about to parse:`"+x[i]+"`");
                TestLexer lexer = new TestLexer(new ANTLRStringStream(x[i]));
                CommonTokenStream tokens = new CommonTokenStream(lexer);

                TestParser parser = new TestParser(tokens);
                TestParser.start_return p_result = parser.start();

                CommonTree ast = p_result.tree;
                if( ast == null ) {
                   System.out.println("resultant tree: is NULL");
                } else {
                   System.out.println("resultant tree: " + ast.toStringTree());
                }
                System.out.println();
            } catch(Exception e) {
                e.printStackTrace();
            }
        }
    }
}

start : p_ExprSingle EOF!;

p_ExprSingle
   : p_IfExpr
   | p_ExitExpr
   | p_StepExpr
   ;

p_IfExpr
   : 'if' '(' p_ExprSingle ')'
   ;

p_StepExpr
   : 'a' | 'if' | 'exit'
   | '{' p_ExprSingle '}'
   ;

//p_ReplaceExpr
//   : 'replace' p_ExprSingle 'with' p_ExprSingle
//   ;

p_ExitExpr
   : 'exit' 'with' p_ExprSingle
   ;

WS : ' '+ { $channel = HIDDEN; } ;