Chapter 2, Problem 12E

Explanation of Solution

a.

Explanation of given grammar generation:

• In the given grammar “G”, “S”, “M”, “A”, “E”, and “B” are the non-terminal symbols, “a”, “$$”, and &#...

Explanation of Solution

b.

Parse tree:

The parse tree for the string “abaa”,

The possible parse trees for the g...

Explanation of Solution

c.

Justification:

The given grammar is ambiguous but, it can’t be LL (1) grammar. LL parser also called as top-down parser which would be unable to decide whether to predict an epsilon production when “E” is at the top of the stack.

The EPS, FIRST, and FELLOW sets table for the above grammar:

Terminals and non-terminals	EPS	FIRST	FELLOW
G	False	{a, b}	$\Phi$
S	False	{a, b}	{$$}
A	False	{a, b}	{a, b, $$}
M	True	{a, b}	{$$}
E	True	{a, b}	{a, b, $$}
B	False	{a, b}	{a, b, $$}
$$	False	{$$}	$\Phi$
a	False	{a}	{a, b, $$}
b	False	{a}	{a, b, $$}

Now add the predict sets to the grammar above:

$\begin{array}{l}\text{1}\text{. G }\to \text{S \$\$ {a, b}}\\ \text{2}\text{. S }\to \text{A M {a, b} }\\ \text{3}\text{. M }\to \text{S {a, b}}\\ \text{4}\text{. M }\to \epsilon \text{ {\$\$}}\end{array}$

$\begin{array}{l}\text{5}\text{. A }\to \text{aE {a}}\\ \text{6}\end{array}$