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