Chapter 2, Problem 18E

Explanation of Solution

a.

FIRST (Es):

• In production rule, the FIRST set is applied to the right-hand side (RHS), and tells all the terminal symbols which can start sentences derived from that RHS.
• The definition of FIRST set is FIRST (x) = {x}, here “x” is terminal symbol.
• For any non-terminal “X” with production rules $X\to x_1\left|x_2\right|\mathrm{...}|x_n,FIRST\left(X\right)=FIRST\left(x_1\right)\cup FIRST\left(x_2\right)\cup \mathrm{...}\cup FIRST\left(x_n\right)$
• The FIRST (Es) for the given LL (1) grammar is as follows:

  FIRST (Es) = {atom, (, ’, ε}.

  In the grammar, “atom”, “(“, “’”, “ε” is the first right-hand side. So it is considered as FIRST (Es).

FOLLOW (E) in the given grammar:

• FOLLOW set is used when the current non-terminal can derive.
  • S is the start symbol, so one can use FOLLOW(S) to start the FOLLOW grammar

Explanation of Solution

b.

Parse tree:

A parse tree for the given string (cdr ’ (a b c) ) $$ is ...

Explanation of Solution

c.

Left-most derivation:

The left-most derivation of (cdr ’ (a b c)) $$ is as follows:

$\begin{array}{c}\text{P }\to \underset{\_}{\text{E}}\text{ \$\$}\\ \to \text{ ( }\underset{\_}{\text{E}}\text{ Es ) \$\$}\\ \to \text{ ( cdr }\underset{\_}{\text{Es}}\text{ ) \$\$}\\ \to \text{ ( cdr }\underset{\_}{\text{E}}\text{ Es ) \$\$}\end{array}$

    $\begin{array}{l}\to \left(\text{ cdr ' }\underset{\_}{\text{E}}\text{ Es }\right)\text{ \$\$}\\ \to \left(\text{ cdr ' }\left(\underset{\_}{\text{E}}\text{ Es}\right)\text{ Es }\right)\text{ \$\$}\\ \to \left(\text{ cdr ' }\left(\text{a }\underset{\_}{\text{Es}}\right)\text{ Es }\right)\end{array}$

Explanation of Solution

d.

Table-driven top-down parse of the string (cdr ’ (a b c)):

Parse stack	Input stream	Comment
P	(cdr ’ (a b c)) $$
E$$	(cdr ’ (a b c)) $$	Predict P → E $$
( E Es ) $$	(cdr ’ (a b c)) $$	Predict E → ( E Es )
E Es ) $$	cdr ’ (a b c)) $$	Match (
atom Es ) $$	cdr ’ (a b c)) $$	Predict E → atom
Es ) $$	’ (a b c)) $$	Match atom
E Es ) $$	’ (a b c)) $$	Predict Es →E Es
’ E Es ) $$	’ (a b c)) $$	Predict E → ’ E
E Es ) $$	(a b c)) $$	Match ’
( E Es ) Es ) $$	(a b c)) $$

Explanation of Solution

e.

Decent tree for “’”:

• The given string is (cdr ’ (a b c)), here “’” is matched in a recursive descent pa...