# Syntax Directed Translation Scheme for Postfix to Infix Notation

I'm reading Compilers Principles, Techniques and Tools textbook and I encountered a problem from exercise 2.3

We have to construct a syntax-directed translation scheme that translates arithmetic expression from postfix notation into infix notation. I constructed a scheme the following way.

expr -> expr expr + | expr expr - | expr expr * | expr expr / | digit


into

expr -> expr {print('+')} expr +
| expr {print('-')} expr -
| {print('(')} expr {print(') * (')} expr {print(')')} *
| {print('(')} expr {print(') / (')} expr {print(')')} /
| digit {print(digit)}


The translation seems pretty valid, but I can't figure out how to construct parse tree using that translation.

Can anyone explain me how to construct parse tree for 2 3 + 3 5 3 * - * and 9 5 2 * -? Thanks in advance!

• Welcome to CS@SE. The translation seems pretty valid can you please argue how parentheses are more useful with * and / than they are with + and -? – greybeard Nov 19 '19 at 22:32
• The above examples will translate into (2+3) * (3 - (5)*(3)) and 9 - (5)*(2) using that translation scheme. There is no need of parenthesis for simple digits as in 9 - (5)*(2). But for complex expressions as in the other example, parentheses is needed for multiplication and division. Again, adding parentheses for plus and minus also seems to be meaningful, but I don't think it is necessary since 9 - (5)*(2) is same as (9) - ((5)*(2)). – Karthik Chennupati Nov 20 '19 at 2:52
• above examples will translate into (2+3) * (3 - (5)*(3)) and … I get (2+3*3-(5*3)): go figure. – greybeard Nov 20 '19 at 6:00
• (Hint: you got binary operators, only. (Imagine a dash was allowed before a digit…)) – greybeard Nov 20 '19 at 6:05