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 ..

---

@Shaik Masthan sir, How the follow is calculated here as Follow(E) depends upon Follow(F) and vice versa .

---

@arpit.jha, In such situations,  

calculate follow(E) independently first as it is the start symbol.

Then calculate follow(A) independently. 

Now as Follow(A) containts follow(E) add those to follow(A). Then add all together of Follow(A) to follow (E).

In most of the cases, it is sufficient.  

Sometimes you need to do it one more time. Add all follow(E) to follow(A) then all together to follow (E).

---

Good video to remove doubts about First and Follow : https://www.youtube.com/watch?v=oOCromcWnfc

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 $.