Question

Recall the CFG G4 that we gave in Example 2.4. For convenience, let’s rename its variables with single letters as follows.
$$\begin{gathered} \mathit{E}\mathbf{\to }\mathit{E}\mathbf{+}\mathit{T}\mathbf{}\overline{)\mathbf{T}} \\ \mathit{T}\mathbf{\to }\mathit{T}\mathbf{\times }\mathit{F}\mathbf{}\overline{)\mathbf{F}} \\ \mathit{F}\mathbf{\to }\mathbf{\left(}\mathbf{E}\mathbf{\right)}\mathbf{}\overline{)\mathbf{a}} \end{gathered}$$

Give parse trees and derivations for each string.

a. a

b. a+a

c. a+a+a

d. ((a))

Short answer

1. a parse trees and derivation is given below.
2. a+a parse trees and derivation is given below.
3. a+a+a parse trees and derivation is given below.
4. ((a)) parse trees and derivation is given below.

Step-by-step solution

Parse tree.

Parse tree is a derivation tree of any string for language in context free grammar. Parse tree may be of right hand derivation tree or it may be left hand derivation tree.

parse trees for part a.

a).

$$\begin{gathered} E\to E+T\overline{)\mathrm{T}} \\ T\to T\times F\overline{)\mathrm{F}} \\ F\to \left(\mathrm{E}\right)\overline{)\mathrm{a}} \end{gathered}$$

Fig: parse trees for string a

parse trees for part b.

(b)

$$\begin{gathered} E\to E+T\overline{)\mathrm{T}} \\ T\to T\times F\overline{)\mathrm{F}} \\ F\to \left(\mathrm{E}\right)\overline{)\mathrm{a}} \\ a+a \end{gathered}$$

Fig: parse trees for string a + a.

parse trees for part c.

c).

$$\begin{gathered} E\to E+T\overline{)\mathrm{T}} \\ T\to T\times F\overline{)\mathrm{F}} \\ F\to \left(\mathrm{E}\right)\overline{)\mathrm{a}} \\ a+a+a \end{gathered}$$

Fig: parse trees for string a + a + a

parse trees for part d.

(d)

$$\begin{gathered} E\to E+T\overline{)\mathrm{T}} \\ T\to T\times F\overline{)\mathrm{F}} \\ F\to \left(\mathrm{E}\right)\overline{)\mathrm{a}} \\ \left(\left(a\right)\right) \end{gathered}$$

Fig: parse trees for string ((a)),