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

The given grammar is: 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++.