Would like to render properly parenthesized expressions from AST

[Phil McGee]

Hello.  I'm a new user of ANTLR and I'm very impressed with the power and elegance of the tool.

I'm working on a language transformation project that takes some input DSL and produces SQL output.  Common to both the DSL and SQL are a set of boolean, arithmetic and miscellaneous other operators that comprise an expression language with the usual kind of operator precedence and associativity rules. 

The ANTLR reference book (and other sources) give pretty good guidance on parsing the expression language into an AST.  So far, so good.  Now I am trying to take the AST and render the SQL expressions from it, using StringTemplate for output creation.  It's not hard to create technically correct expressions if I render every operand with parentheses around it and just follow the AST for determining precedence, but the result is ugly and hard to read.  I would like to use parentheses only where necessary to override the default operator precedence but I'm not sure of the best way to approach the problem.  I could probably find a way to produce what I want, but I have a feeling that I could invest a lot of time in putting together a bad hack.

Rendering expressions from an AST seems like such a common requirement that I assume its been done many times over, and that some standard approaches have been developed.  But I haven't been able to find anything.  Can anyone point me at any discussions that might help, or projects I might use as a model?  If anyone is aware of an ANTLR3/StringTemplate4 project that does this that would be fantastic.

I'd greatly appreciate any help.

Phil McGee

[Eric]

Hi Phil,

 

Off the top of my head.

 

If the expressions in the AST are setup as op(x,y), e.g.

 

3*4+1 = (+,[(*,[3;4]);1])

 

3*(4+1) = (*,[(+,[4;1]);3])

 

with the precedence of

 

+ = 1

* = 2

 

then as you traverse the tree in the evaluation order, if you see a lower precedence, e.g. +, before a higher precedence, e.g. *, you add the parens.

 

so for

(*,[(+,[4;1]);3])

 

we see * and set precedence at 2 but need to evaluate the children first,

For the left child we see + at 1 which is lower 2 so this will need parens for the + expression.

 

Just keep doing that and you should have it.

 

On the other hand:

Shouldn't a good pretty printer for an SQL already be able to this? You just feed in the AST and out comes the SQL with the parenthesis were needed. The trick is finding a good pretty printer that can do this versus one that was just thrown together.

 

 

Regards, Eric

 

 

 

 

 

 

--
You received this message because you are subscribed to the Google Groups "antlr-discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to antlr-discussi...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Jim Idle]

If the language that you are paring originally, used parentheses then just make sure that you mark this as such in the AST:

atoms: LPAREN e=expression RPAREN ->^(PARENS $e) ...

Then your AST is:

expression: ^(PARENS e=expression) {call the parens template }

      | ^(PLUS expression expression) {template without parens for everythign else{

...

Basically you need to preserve the parentheses information in your AST in the first place and then it is a trivial problem. If your input DSL has a different order of operator precedence, then you might be able to adorn the AST appropriately as you create it but I would advise against creating a DSL that has different operator precedence. Presumably if your DSL creator thought that parentheses made it easier to read, then you should preserve them even if they seem to be logically superfluous.

Jim

[Phil McGee]

Thanks Eric,

What you suggests makes sense.  I guess to make it work I'll need to keep an operator precedence stack in the tree parser that I push when I find a matching operator rule while walking the AST and pop in an @after action for each operator rule.  Then I should be able to compare the top two  precedences to determine the need for parentheses.  That seems neat enough.

[Phil McGee]

Thanks for responding Jim.  That's an approach I hadn't considered but it certainly makes sense for a straight expression pass through.  Unfortunately, for my use case it's probably not flexible enough because in some cases my code needs to "enhance" some of the expressions in the AST from the DSL.  Typically I would do this to add some additional predicates to "join on" or "where" expressions.

I'll file away your suggestion for future use, though.  It is a lot less fiddly than pushing and popping precedences in all the operator rules.

Regards,
Phil