Chapter 2, Problem 13E

Explanation of Solution

a.

Parse tree for the string foo (a, b):

Explanation of Solution

b.

Canonical (rightmost) derivation:

• Canonical derivation is a leftmost or rightmost derivations that may not be unique but they allow describing a derivation by the sequence of production rules taken.
• In the rightmost derivation, the rightmost nonterminal on the right hand side of a rule is replaced by a suitable rule.
• The complete derivation in this case is processed in the rightmost way.

$\begin{array}{c}\text{stmt }\Rightarrow \text{ subr\_call}\\ \Rightarrow \text{id ( }\underset{\_}{\text{arg\_list}}\text{ )}\\ \Rightarrow \text{id ( expr }\underset{\_}{\text{args\_tail}}\text{ )}\\ \Rightarrow \text{id ( expr , }\underset{\_}{\text{arg\_list}}\text{ )}\end{array}$

        $\begin{array}{c}\Rightarrow \text{id ( expr , expr }\underset{\_}{\text{args\_tail}}\text{ )}\\ \Rightarrow \text{id ( expr , }\underset{\_}{\text{expr}}\text{ )}\\ \Rightarrow \text{id ( expr , primary }\underset{\_}{\text{expr\_tail}}\text{ )}\\ \Rightarrow \text{id ( expr , }\underset{\_}{\text{primary}}\text{ )}\end{array}$

        $\begin{array}{c}\Rightarrow \text{id ( }\underset{\_}{\text{expr}}\text{ , id )}\\ \Rightarrow \text{id ( primary }\underset{\_}{\text{expr\_tail}}\text{ , id )}\\ \Rightarrow \text{id ( }\underset{\_}{\text{primary}}\text{ , id )}\\ \Rightarrow \text{id ( id , id )}\end{array}$

Explanation of Solution

c.

Proof:

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

Terminals and non-terminals	EPS	FIRST	FELLOW
stmt	False	id	empty
assignment	False	id	empty
subr_call	False	id	empty
expr	False	id, (	‘,’, )
expr_tail	True	+, -, *, /	‘,’, )
primary	False	id, (	+, -, *, /
op	False	+, -, *, /	id, (
arg_list	False	id, (	)
args_tail	True	‘,’	)

Now add the predict sets to the grammar above:

$\begin{array}{l}\text{1}\text{. stmt }\to \text{assignment {id}}\\ \text{2}\text{. stmt }\to \text{subr\_call {id} }\\ \text{3}\text{. assignment }\to \text{id := expr {id}}\\ \text{4}\text{. subr\_call }\to \text{id ( arg\_list ) {id}}\end{array}$

$\begin{array}{l}\text{5}\text{. expr }\to \text{primary expr\_tail {id, (}}\\ \text{6}\text{. expr\_tail }\to \text{op expr {+, -, *, /}}\\ \text{7}\text{. expr\_tail }\to \epsilon \text{ {',', ) }}\\ \text{8}\text{. primary }\to \text{id {id}}\end{array}$

$\begin{array}{l}\text{9}\text{. primary }\to \text{subr\_call {id}}\\ \text{10}\text{. primary }\to \text{( expr ) {(}}\\ \text{11}\text{. op }\to \text{+ | - | * | / {+, -, *, /}}\\ \text{12}\text{. arg\_list }\to \text{expr args\_tail {id, (}}\end{array}$

$\begin{array}{l}\text{13}\text{. args\_tail }\to \text{ , arg\_list {','}}\\ \text{14}\text{. args\_tail }\to \epsilon \text{ {)}}\end{array}$

Parse table for the above grammar:

	Id	:=	(	+	-	*	/	,	)
stmt	1, 2
assignment	3
subr_call	4
expr	5		5
expr_tail	-			6	6	6	6	7	7
primary	8, 9		10
op	-			11	11	11	11
arg_list	12		12
args_tail	-							13	14

• The entries in the above table indicates the production of predict. The “-” means an error.
• If the top-of-stack is terminal, the appropriate action is always to match it against an incoming token from the scanner.

The given grammar can’t be LL (1) because of confusion with “stmt” and “id”.

Explanation of Solution

d.

Modified grammar to make it is LL (1):

Factor out “id” from productions with “stmt” and “expr”.

$\begin{array}{l}\text{1}\text{. stmt }\to \text{id stmt\_tail }\\ \text{2}\text{. stmt\_tail }\to :=\text{expr }\\ \text{3}\text{. stmt\_tail }\to \text{( arg\_list ) }\\ \text{4}\text{. expr }\to \text{primary expr\_tail }\end{array}$

$\begin{array}{l}\text{5}\text{. expr\_tail }\to \text{op expr }\\ \text{6}\text{. expr\_tail }\to \epsilon \\ \text{7}\text{. primary }\to \text{id primary\_tail }\\ \text{8}\text{. primary\_tail }\to \epsilon \end{array}$

$\begin{array}{l}\text{9}\text{. primary }\to \left(\text{arg\_list}\right)\\ \text{10}\text{. primary }\to \text{( expr ) }\\ \text{11}\text{. op }\to \text{+ | - | * | / }\\ \text{12}\text{. arg\_list }\to \text{expr args\_tail }\end{array}$

$\begin{array}{l}\text{13}\text{. args\_tail }\to \text{ , arg\_list }\\ \text{14}\text{. args\_tail }\to \epsilon \end{array}$