Question

2A. Check if the given Grammar G is LL (1) by constructing a predictive parse table Clearly specify the different steps involved during the construction of parse table. A BCg DBCe B BDb E C DCf & D ale Grammar G 4M

Answer 1

Theory : First of all to construct LL(1) parser we have to know what is the First and Follow of all the each production during construction of table if we get multiple entry corresponding to a particular cell this means ambiguity and grammar can not be parse with LL(1) parser. So proceed with this problem We have to first find find "First and Follow " of production which is as follows:

Production	First	Follow
A BCg DBCe	a, b,e, f,g	$\left \{ \$ \right \}$
B BDbe	Ка, b, е! a.	a, b,e, f,g
C DCfe	a, f, e	e, f,g
$D \rightarrow a | \epsilon$	{а, e]	$\left \{ a,b,e,f\right \}$

First try and understand how first and follow is calculated for productions.First and Follow is terminal symbol which can be produced from production. We first calculate first and then follow.

FIRST: Start from symbol D, first terminal symbols we can get is 'a' and ;epsilon , it's easily observable. Let's move to C ,here first of C will be first of symbol D , this means 'a ' will be included in the first of C but we will not get epsilon as input in our grammar, So D will be replaced with epsilon and our new equation will be C => Cf | epsilon. Here first of C will first of C ,no change in our FIRST of C but C also produced epsilon, so after replacing right hand side of C with epsilon, our equation will be change to C=>f | epsilon, now it's similar to same equation as D, so our first symbol of C will be {a,f,$\epsilon$}. Similarly for equating for B and A.

Basic rule is if first symbol is non-terminal then FIRST of that non-terminal will be included to the FIRST of symbol we are calculating and careful thing to notice is that first symbol has epsilon production. If it has then replace with it epsilon and we will get new production and kept repeating above process.

FOLLOW: Start symbol always contain $ as it follows and it similar to calculating FIRST with similar change. Here we will search same Non-Terminal symbol on right hand side of production. if exist then first symbol exactly after it will be follow of it. But here it can be non-terminal symbol also. So in that Case it will be FIRST of that non-terminal symbol which will be included as follow otherwise terminal symbol will be included. Last case can be , there is no symbol after it. So in that case FOLLOW of right hand symbol will be equal to FOLLOW of left hand symbol.

Now the construction of Parsing table with the help of FIRST and FOLLOW. Here First column is non-terminal symbol and all other are terminal symbol.

How to fill entry in the table:

Here we will see productions form which a particular symbol can be produced and we will put that particular production in that particular symbol column. For example terminal symbol 'a' is included in  FIRST of all the production exist so it is putted on all column. But symbol e is produced by A=>DBCe production, so it placed on A symbol. What about epsilon symbol where does FOLLOW is used so answer is here. If some epsilon production is exists for some non-terminal symbol then it will be placed on the follow of that particular non-terminal symbol. Following these rule , our table will be constructed.

	a	b	e	f	g	$
A	A BCg DBCe	A BCg DBCe	A DBCe	A BCg DBCe	$A\rightarrow BCg$
B	B BDbe	B BDbe	$B\rightarrow \epsilon$	$B\rightarrow \epsilon$	$B\rightarrow \epsilon$
C	$C \rightarrow DCf$		$C \rightarrow \epsilon$	C DCfe	$C \rightarrow \epsilon$
D	$D \rightarrow a | \epsilon$	$D \rightarrow \epsilon$	$D \rightarrow \epsilon$	$D \rightarrow \epsilon$

But our original question was to check, whether grammar is LL(1). This is not a LL(1) grammar because as you can clearly see that many cell has contained multiple entry. It is not allowed in LL(1) grammar. It's because when our parser will be parsing string/input and a particular terminal comes and that terminal symbol contains multiple entry so parser will get confused, which production to use. It is not a LL(1) parser.

Thanks.