[antlr-interest] could not even do k=1 for decision xx; reason: timed out

[Sam Barnett-Cormack]

Tomasz Jastrzebski wrote:
> Thanks.
>  
> Now I understand that the only reasonable such declaration must look like:
>  
> multExpr
>  : primaryExpr (('*' | '/') primaryExpr)*
>  ;
>  
> After adding rewrite rules this may look like that:
> addExpr
>  : (multExpr -> multExpr) ( (o='+' | o='-') e=multExpr -> ^($o $addExpr 
> $e) )*
>  ;
> multExpr
>  : (primaryExpr -> primaryExpr) ( (o='*' | o='/') e=primaryExpr -> ^($o 
> $multExpr $e) )*
>  ;
>  
> (tested, it works)

Well, you don't need "-> primaryExpr" in the first subrule there - it's 
implicit. To make your tree nodes binary only, I don't think you can use 
EBNF like that, I think you'll need to use recursion. After all, you want

3 + 2 - 4

to produce a tree like

    +
   / \
  3   -
     / \
    2   4

(Whether the - or + is at the root doesn't matter)

I don't think this is possible with just EBNF constructs. You need it to 
parse 2-4 as an expression that produces a subtree, and that expression 
be picked up by the match of the + operator. Alternatively, you could 
produce a non-binary tree like

     +
    /|\
   3 2 -4

Because subtraction is associative, this is viable. Same for 
multiplication/division, with  '/ a' becoming '* a^-1', if you care to 
model them via inverses as is typical in group/ring theory in 
mathematics. Personally, I think a binary tree is cleaner, but you have 
to do something much cleverer than normal EBNF to produce that, AFAICT.

> I would think that now I can simply replace:
> -> ^($o $addExpr $e)
> with
> -> ^(BIN_EXPR<BinaryExpression>[o.text, $addExpr.tree, $e.tree]>)
>  
> - but not. $addExpr.tree in the second version is always NIL.

Well, $addExpr is the result of the current parser rule, as that 
expression appears to appear in the addExpr: rule. Of course it's going 
to produce odd results.

-- 
Sam Barnett-Cormack