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

Tomasz Jastrzebski tdjastrzebski at yahoo.com
Sat Aug 8 12:47:47 PDT 2009


This approach was borrowed right from Terence's book, page 187. He even stated that it looked odd, but made sense - explanation follows. Anyway, I tested it. With rewrite like (multExpr -> multExpr) it works as expected, without it does not.
 
The point is that I need binary tree. Rewrite like:
 
multExpr
 : primaryExpr ((o='*' | o='/') e=primaryExpr -> ^($o $e) )*
 ;
 
or:

multExpr
 : (primaryExpr -> primaryExpr) ( (o='*' | o='/') e=primaryExpr -> ^($o $multExpr $e) )*
 ;
 
produces desired default AST binary tree. Just how modify it so it builds my binary tree...
I cannot figure this out.
 
Thanks,
 
Tomasz

--- On Sat, 8/8/09, Sam Barnett-Cormack <s.barnett-cormack at lancaster.ac.uk> wrote:


From: Sam Barnett-Cormack <s.barnett-cormack at lancaster.ac.uk>
Subject: Re: [antlr-interest] could not even do k=1 for decision xx; reason: timed out
To: "Tomasz Jastrzebski" <tdjastrzebski at yahoo.com>
Cc: "antlr-interest" <antlr-interest at antlr.org>
Date: Saturday, August 8, 2009, 2:50 PM


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




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


More information about the antlr-interest mailing list