syntax tree for the word (())()()

Question

I have to create the syntax tree for the word (())()() . That's what I have tried:

Could you tell me if it is right?

Answer 1

$\def\lp{{\mathtt (}}\def\rp{{\mathtt )}}$ You said in a comment that you are using this grammar:

$$\begin{align} I \to & \lp I\rp I \\ \mid & 0 \end{align}$$ where $0$ represents the empty sequence of symbols.

In that case your tree is not correct. The leftmost $I$ node in the second level of your tree has only three children, but it must have four or none.

The fix for this problem is pretty simple. Instead of having $I\to\lp I \rp$ as it is now, give the node four children, $I\to\lp I \rp I$, and then have the fourth one turn into nothing using the $I\to 0$ production.

Another problem is that your root node $I$ has five children, labeled with (, $I$, ), $I$, and $I$, but the only legal productions from $I$ have either four children (the $I\to\lp I\rp I$ production) or none (the $I\to 0$ peoduction).

The fix for this is a little more complicated and I don't want to lead you to possibly violate your school's ethics code by telling you what is it.

Finally, you have an inconsistency: Sometimes you have an $I$ node turn into $0$ using the $I\to 0$ production, and sometimes you just leave the $I$ as a leaf. You need to make up your mind how you want to draw the $I\to 0$ production, and then draw it that way consistently.

Answer 2

@MJD I tried to create again the syntax tree..That's what I got.Have I done something wrong or is this right?