3

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.

Nicolas Kaiser
  • 1,628
  • 2
  • 14
  • 26
Dan
  • 33,953
  • 24
  • 61
  • 87
  • What kind of code are you generating? If you're generating machine code (as most people would assume in this context) then your question is a bit nonsensical. *Are you generating a high(er) level language like C?* – BCS Dec 01 '10 at 03:20
  • Apologies, I guessed that generating a higher level language would be more common or at least that using the term code as opposed to assembly would make this clear. I've updated the question to reflect this... – Dan Dec 01 '10 at 10:17

2 Answers2

4

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.

munificent
  • 11,946
  • 2
  • 38
  • 55
  • 1
    Another way of looking at the associativity bit would be to have the left and right hand sides compare with different precedences, generally one step higher when looking at the right than when looking at the left. To make that work correctly you may need to have gaps in the levels actual assigned to nodes. – BCS Dec 09 '10 at 03:17
  • You might find this answer on prettyprinting generally helpful: http://stackoverflow.com/a/5834775/120163 – Ira Baxter Dec 07 '11 at 16:42
2

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.

Alexander Gorshenev
  • 2,769
  • 18
  • 33