[antlr-interest] How to create binary AST with multiple operators?

Андрей Асеев andron-eiu at mail.ru
Thu Aug 9 11:54:27 PDT 2012


Hello, Maciej.

I recommend you to learn about AST parser and separate your logic into 
two grammars: "parser grammar" and "tree grammar". That's would be good 
for your taste :)

1) parser grammar

mult_expr : pow_expr (MULDIV^ pow_expr)*;
pow_expr : unary_expr (POW^ unary_expr)*;
unary_expr : not_expr | MINUS^ unary_expr | '+'! unary_expr; // which language supports +++--+---+6, huh? :)
not_expr :  term | NOT^ not_expr;

... and so on by such style

2) then, tree grammar
expr: mult_expr | pow_expr | unary_expr | not_expr;
mult_expr:  ^(MULDIV exl=expr exr=expr) {new BinaryExpression($MULDIV, $exl.tree, $exr.tree)};
pow_expr:   ^(POW exl=expr exr=expr)    {new BinaryExpression($POW, $exl.tree, $exr.tree)};
unary_expr: ^(MINUS expr)               {new UnaryExpression($MINUS, $expr.tree)};
not_expr:   ^(NOT expr)                 {new UnaryExpression($NOT, $expr.tree)};

Now, you see, that's would be much more simplified by uniting similary nodes.

Regards, colleague.

09.08.2012 21:33, Maciej Pilichowski пишет:
> Hello all,
>
>    I try to build entire AST with custom nodes, so for example my unary
> expressions look like this:
>
> -----------------------------------------------------------
> not_expr :  term
>              | op='not' ex=not_expr ->  { new UnaryExpression($op,
> $ex.tree) };
>
>
> unary_expr : not_expr
>             | op='-' ex=unary_expr ->  { new UnaryExpression(op,
> $ex.tree) }
>             | '+'! unary_expr;
> -----------------------------------------------------------
>
> I had first problems when tackling binary expression -- power (like 2
> ^ 5). But thanks it is single operator, I could write method which
> takes entire list of operands, and creates nested binary tree. And so
> the rule is simple:
>
> -----------------------------------------------------------
> pow_expr : ex+=unary_expr (op='^' ex+=unary_expr)*
>             ->  { BinaryExpression.createRightTree(op,$ex) };
> -----------------------------------------------------------
>
> However when I came to multi-operator binary expression I am lost --
> now I try to handle multiplication and division at the same time.
> This is my try:
>
> -----------------------------------------------------------
> mult_expr : exl=pow_expr { retval.tree = $exl.tree; } (
>                op=('*'|'/'|'mod'|'div') exr=pow_expr ->  { new
> BinaryExpression(op,$exl.tree,$exr.tree) }
>              )*;
> -----------------------------------------------------------
>
> First thing I don't like the start of it -- there is too much hackery
> for my taste for the initial value (retval...), second -- there is no
> mechanism which "glues" consecutive expressions (like 5*3*2), and
> third -- it does not work at all.
>
> So the question is -- how to do it?
>
> Thank you in advance,
>
>
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>



More information about the antlr-interest mailing list