[antlr-interest] Tree walker grammer help.

[Gavin Lambert]

At 19:43 22/09/2008, jack zhang wrote:
>If I use the TreeWalker version 1(see attached code),  test case 
>4 and 5 are not working.
>
>(4) a b c ==> a
>(5) a b AND c ==> a

That's because the WORD alternative will only match a single WORD 
and then stop, and you're only matching a single expression.

To match input like the above, you need to match multiple 
expressions.  That's as simple as adding this rule to your 
existing version 1 tree parser:

exprs : expr+ EOF;

After doing that, it ought to work perfectly.  (Well, after you 
modify it to produce the output you want.)

Alternatively, leave your grammar as is and call the expr() method 
multiple times.  Each call will get the next complete top-level 
expression from the input tree.

(Although you ought to remove "output=AST" from your tree 
grammars, since you're not actually generating AST output from 
them.)

>If I use the TreeWalker version 2(see attached code), test case 
>1,2,3 and 5 are not working.
[...]
>-Decision can match input such as "WORD" using multiple 
>alternatives: 1, 2
>As a result, alternative(s) 2 were disabled for that input-
[...]
>expr returns [String value=""]
>     : ^(AND a=expr b=expr) {
>         $value = "(" + $a.value + " and " + $b.value + ")";
>     }
>     | ^(OR a=expr b=expr) {
>         $value = "(" + $a.value + " or " + $b.value+ ")";
>     }
>     | ^(NOT a=expr) {
>         $value = "(not " + $a.value +")";
>     }
>     |  ( WORD {  $value +=  " " + $WORD.text;  })+  ;

It's the recursion that's doing you in here.  Follow through 
what's actually happening:

Case #1: input ^(AND a b):
   - enter rule expr
   - enter first alt (AND)
   - re-enter rule expr (for 'a')
   - enter last alt (WORD)
   - match WORD "a": value=" a"
   - match WORD "b": value=" a b"
   - exit rule expr; label a=" a b"
   - re-enter rule expr (for 'b')
   - no input left: fail

The other cases fail in a similar manner, if you follow them 
through.  (Note that this is the "greedy" interpretation of the 
parsing.  The non-greedy interpretation, which would have actually 
worked for this particular input, is the one ANTLR referred to as 
being disabled due to ambiguity.)

Just forget about parser #2 (although it would probably pay to 
look through it and work out why each of the test cases fail, now 
that you've got a hint).  The change mentioned above for parser #1 
should sort out your issue.