GATE CSE 2001 | Question: 16

Question

Consider the following grammar with terminal alphabet $\Sigma =\{a,(,),+,* \}$ and start symbol $E$. The production rules of the grammar are:

• $ E \rightarrow aA$
• $ E \rightarrow (E)$
• $A \rightarrow +E$
• $A \rightarrow *E$
• $A \rightarrow \epsilon $

1. Compute the FIRST and FOLLOW sets for $E$ and $A$.
2. Complete the LL(1) parse table for the grammar.

Comments

I came across a very tricky case while solving this question ie. Follow(E) contains Follow(A) because of the third production and at the same time Follow(A) contains the Follow(E) because of the first production .. how do we handle such a situation in follows of one anouther are depending ..

Answer 1

First $(E) = \{ a,( \}$

First $(A) = \{ +,*, \epsilon \}$

Follow $(E) =$ Follow $(A) =$ $\{$ $\$$ $,) \}$

LL(1) Parsing Table:

$$\begin{array}{|c|c|c|c|c|c|c|} \hline \textbf{} & \textbf{a} & \textbf{(} & \textbf{)} & \textbf{+} & \bf{*} & \textbf{\$} \\\hline \text{E} & \text{E} \rightarrow \text{aA} & \text{E} \rightarrow \text{(E)} & \text{} & \text{} & \text{} & \text{} \\\hline \text{A} & \text{}& \text{} & \text{A} \rightarrow \epsilon & \text{A} \rightarrow \text{+E} & \text{A} \rightarrow *\text{E} & \text{A} \rightarrow \epsilon \\\hline \end{array}$$

Comments

Hello @aditya i have just structured your parsing table

Answer 2

First(E) = a,(   and   First(A) = +,*,epsilon

Follow(E)= ),\$    and  Follow(A) = ),\$

Comments

how did $ come in follow of A, can somebody pls explain ??

---

because Follow of A will  contain Follow of E, due to production E->aA

And since Follow of E would contain $

(Since it is the start symbol) hence Follow of A will also contain $.