How to generate syntax tree for a particular sentence like a+b*c where id->a|b|c?

Question

Consider grammar : E-> E+E|E-E|E*E|E/E|(E)|id

I have tried at least 5 hours to solve this problem but failed. Please tell me,

• what is the idea to solve this problem?

• How to implement this?

Answer 1

The syntax tree is built by parsing, which is in some sense applying the grammar in reverse. So you see that a, b, and c can only come from id which in turn can only come from E. Now you are at E+E*E. You can either reduce the E+E first or the E*E, then the other. The resulting E is the root of the tree. One of the two possible syntax trees (the one reducing first E*E) is this

  E
 /| \
E +   E
|    /|\
id  E * E
|   |   |
a   id  id
    |   |
    b   c

About the implementation, you would have to specifiy where and to what end you want to implement this.