0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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 -? $\endgroup$ – greybeard Nov 19 '19 at 22:32
  • $\begingroup$ 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)). $\endgroup$ – Karthik Chennupati Nov 20 '19 at 2:52
  • $\begingroup$ above examples will translate into (2+3) * (3 - (5)*(3)) and … I get (2+3*3-(5*3)): go figure. $\endgroup$ – greybeard Nov 20 '19 at 6:00
  • $\begingroup$ (Hint: you got binary operators, only. (Imagine a dash was allowed before a digit…)) $\endgroup$ – greybeard Nov 20 '19 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.