[antlr-interest] Problems with implicit "and" in query grammar build using Antlr

Allen Jones allengeoffreyjones at gmail.com
Mon Nov 16 13:36:24 PST 2009

Hi all.

I have been building a google-like query syntax parser in ANTLR (C#). This
is the first work I have done with ANTLR, or any parser generator, so it has
been quite an experience.

I want the user to be able to use "and" and "or" to combine search terms
e,g. "(apple or microsoft) and tablet and office". But I also want the user
to be able to enter a simple set of words and implicitly treat it as though
they are joined by "and" e.g. "apple tablet office windows" would be treated
as "apple and tablet and office and windows"

So far, I have been unable to get a syntax that correctly handles implicit
"ands" between sets of words.

Here is a snippet of my current grammar that works properly with an explicit

    : andexpression (OR_OP^ andexpression)*

options {
    : atom (AND_OP^ atom)*

The problem is that 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 can't find the right syntax to make it work.

In wanting the AND_OP to be optional, I had to move away from the tree
construction operators because the following would not work:

    : atom (AND_OP?^ atom)*

Ideally, I thought I needed to make andexpression look like this:

options {
    : l=atom (AND_OP? r=atom)* -> ^(AND_OP $l $r?)+

But I get RewriteEmptyStreamException parsing strings where words are not
joined by 'and', for example "sheep dog fish".

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


Allen Jones



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20091116/aa8b647e/attachment.html 

More information about the antlr-interest mailing list