[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