Question

Consider the following grammar.



S→ A

A→ A+A | B++

B →y

You are required to draw parse tree for the input"y+++y++"

Answer 1

Answer:

The given grammar is: {S→ A, A→ A+A | B++, B →y.}

Now to draw the parse tree for the input "y++ + y++", follow these steps:

• To get the middle + symbol, follow the rule S→ A and then A→ A+A.

                                  S→ A→ A + A

• Now the last level of tree contains A + A.  So follow the rule A→ B++ for both A’s.

                                 S→ A→ A + A → B++ + B++

• Now the last level of tree contains B++ + B++.  So follow the rule B →y to get y++ + y++ at the last level.

                                S→ A→ A + A → B++ + B++ → y++ + y++.