Associativity and Precedence of Expressions when Generating C / C++ Code?

I have written a basic compiler which generates an AST, 开发者_高级运维correctly taking account of the operator precedence in expressions. However, when performing code generation to produce C++ code, I'm unsure of how to handle the use of brackets.

For this expression:

A - (B - c)

The AST below:

   -
  / \
 A   -
    / \
   B   C

Should correctly generate the previous expression including the parentheses, however if the second operator was an addition operator (for example), the parentheses would be unecessary. I would prefer to only use them where necessary to improve readability.

Are there any rules dictating this kind of behaviour and how to know when to use parentheses. Plus and minus have the same level of precedence in most languages and I'd like to make this work for all operators.

Historically, they call this "pretty printing". If you Google that plus "precedence", you may find some examples to help you.

Informally, I think the basic idea is that when you recurse into a subexpression, you compare its precedence to the current expression. If it's lower, you need parentheses. Otherwise you don't. Associativity can be handled by doing a similar check: if the subexpression has the same precedence as the parent you need parentheses if it's on the wrong side according to associativity.

If an operation with a higher precedence is lower in the tree you don't need to put it into parentheses.

It is not enough to know the precedence of the operations though. You also need to know the associativity of the operations. It allows to group operations of equal precedence properly. Say, subtraction is left associative, so A-B-C is equal to (A-B)-C, but not to A-(B-C).

Just write down the whole table of precedence and associativities for all your operations and consult it as you generate your expression.