ANTLR nested semantic predicates with wildcard operator

Question

I created a grammar for a Scheme-like language interpreter. Initially, I had one semantic predicate for the if-then-else statement to control evaluation i.e. when the conditional is true only the 'then' is evaluated; when it's false, only the 'else' is evaluated. To add type-checking functionality, I added a second semantic predicate enclosing the first one. It's a hack, though, because to type-check or evaluate I have to manually change the global boolean typeCheck to either true or false.

The AST for the IF statement now has two branches. The first (IFT) is for type-checking the IF statement's arguments. [this is why of two predicates; to type-check, all arguments must be evaluated] The second branch (IFE) is for evaluating the short-circuiting if-then-else. The problem started when I added a second semantic predicate that enclosed the first, getting the infamous "no viable alternative at input" error. After getting nowhere slowly, I created new grammars with just the essentials. Same issue. Here is the stripped down AST:

IF AST

Though I have never experienced one, I've seen issues reported on SO with the ANTLR IDE in Eclipse. So I fired up ANTLRWorks, debugged the parser grammar, then tried to debug the tree grammar. Versions 1.4.3 and 1.4.2 both popup this box, "warning: the grammar used by the remote parser is not the same". I click OK then in the debugger click Step Forward just once and the java.exe*32 process dies. As a final test, I manually compiled from the command line with antlr-3.3 and antlr-3.4 complete jars, no change.

The parser:

grammar NestedSemPreds;

options {
    output = AST;
    ASTLabelType = CommonTree;
}

tokens {
    IF;
    IFT;
    IFE;
}   

/** parser rules **/
ifstmt  : '(' 'if' COND THEN ELSE ')' NEWLN
            -> ^(IF ^(IFT COND THEN ELSE)
                    ^(IFE COND THEN ELSE)
                )
        ;

/** lexer rules **/
COND    : 'true' ; 
THEN    : 'then' ;
ELSE    : 'else' ;
COMMENT :   ('//' .* NEWLN) { skip(); } ; //for lines in datafile I don't want processed
NEWLN   :   '\r'? '\n' ;
WS      :   (' '|'\t')+ { skip(); } ;

The tree grammar:

tree grammar treeEval;

options {
    tokenVocab = NestedSemPreds;
    ASTLabelType = CommonTree;
}

@members {
    boolean typeCheck = false;
}

ifstmt 
@init {
    boolean condition = true;
}
 : ^(IF (  
           {typeCheck}? => //{System.out.println("typeCheck is true");}
                            ^(IFT COND THEN ELSE) {System.out.println("IFT COND THEN ELSE");}
                            ^(IFE . . .) {System.out.println("    SKIP IFE WITH . WILDCARD");}
        | {!typeCheck}? => //{System.out.println("typeCheck is false");} 
                            ^(IFT . . .) {System.out.println("skip ift with . wildcard");}
                            ^(IFE COND
                                    (  {condition}? => ({System.out.println("    condition is true");}
                                                       THEN . {System.out.println("        evaluate THEN");})
                                    | {!condition}? => ({System.out.println("    condition is false");}
                                                      . ELSE {System.out.println("        evaluate else");})
                                    )//close inner predicate
                             )//close ^IFE
        )//close outer predicate
    )//close ^IF
 ;

I couldn't find any particular issues on nested semantic predicates, but I didn't find any examples either. Why is this code failing? Any ideas on the issue with ANTLRWorks debugger?

@BartKiers: got an error editing my comment to you. Thx for your answer! I now know that a predicate for the 2nd option isn't always needed. I simply mimicked the example in _The Definitive ANTLR Reference_, p146. Yes, using actual tokens works but it breaks short-circuiting in the ifstmt (reqd for recursive function call support). My interpreter is more complex (eg. THEN & ELSE can be nested function calls or expr's) than this stripped-down test case created just to isolate the problem. — cb4, Aug 05 '12 at 21:58
yeah, I removed my answer. I might have misunderstood what you were trying to do, and/or your stripped down grammar wasn't a good representation of your entire grammar, so parts of my answer didn't make sense. And since you posted an answer yourself already, I removed mine instead of editing the confusing parts out. Good to hear you resolved the issue, of course! — Bart Kiers, Aug 06 '12 at 08:28
I probably could have worded it better. Anyway, all's well that ends well and thanks again for the hint that led to the answer! — cb4, Aug 06 '12 at 18:20

score 2 · Accepted Answer · answered Aug 05 '12 at 20:35

Using Bart's comment about not needing to "add a predicate before the second alternative", I did some additional testing. All tested options were valid syntax so I think this is an ANTLR bug. To cut to the chase, here is what works:

ifstmt 
@init {
    boolean condition = true;
}
 : ^(IF (  
           {typeCheck}? => ^(IFT COND THEN ELSE) {System.out.println("IFT COND THEN ELSE");}
                           . //MUST use only one dot
        | {!typeCheck}? => . //also works with ^(IFT . . .) here
                            ^(IFE COND
                                    (  {condition}? => ({System.out.println("    condition is true");}
                                                       THEN . {System.out.println("        evaluate THEN");})
                                    | {!condition}? => //this inner 2nd predicate not required
                                                      . ELSE {System.out.println("        evaluate else");})
                                    )//close inner predicates
                             )//close ^IFE
        )//close outer predicates
    )//close ^IF
 ;

These two steps are required:

Both outer predicates, {typeCheck}? and {!typeCheck}?, are necessary.
The first outer predicate, a single . operator to skip the whole subtree

As noted in the code sample, it still works with either of these two syntax changes:

The second outer predicate, {!typeCheck}?, can use a single . or the original ^(IFT . . .) syntax.
The second inner predicate is optional, as Bart mentioned.

Another solution that worked was to manually process the node stream and add appropriate code, but that's not as clean as letting ANTLR do its thing.

ANTLR nested semantic predicates with wildcard operator

1 Answers1