Problems with implicit "and" in query grammar build using Antlr

Question

I have been building a google-like query syntax parser in ANTLR (C#).

I am finished except for one thing, which I have struggled with for a long time and failed to solve.

If the user enters "word1 word2 word3", I want the parser to treat this the same as "word1 and word2 and word3". So in effect the "and" is optional/implicit between terms.

I need the "and" to form the root of the AST subtree, which doesn't go well if the "and" isn't actually there. Even with lookahead/backtrack I cant find the right syntax to make it work.

Here is a snippet of my current grammar that works with an explicit "and":

expression
    : andexpression (OR_OP^ andexpression)*
    ;

andexpression
options {
backtrack=true;
}
    : atom (AND_OP^ atom)*
    ;

Ideally, I would like to make andexpression look like this:

andexpression
options {
backtrack=true;
}
    : l=atom (AND_OP? r=atom)* -> ^(AND_OP $l $r?)+
    ;

But I get RewriteEmptyStreamException parsing string like "sheep dog fish".

If anybody has any tips on how to make my "and" optional, it would be much appreciated.

Answer 1

Hi. Best way is to do this:

andexpression : atom (AND_OP^ atom) ;

backtrack option is unnecessary too.

Terence

Answer 2

Answer was supplied by somebody on the ANTLR mailing list. Works like a charm. Re-posting here for those interested.

expression
    : l=andexpression (OR_OP^ r=andexpression)*
    ;

andexpression
    : atom (andop^ atom)*
    ;

andop
    : AND_OP -> AND_OP
    | -> AND_OP
    ;