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!
The translation seems pretty valid
can you please argue how parentheses are more useful with*
and/
than they are with+
and-
? $\endgroup$(2+3) * (3 - (5)*(3))
and9 - (5)*(2)
using that translation scheme. There is no need of parenthesis for simple digits as in9 - (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 since9 - (5)*(2)
is same as(9) - ((5)*(2))
. $\endgroup$above examples will translate into (2+3) * (3 - (5)*(3)) and …
I get(2+3*3-(5*3))
: go figure. $\endgroup$