Compiler-As-2

Question 1

Given the set of tokens $\{\sigma {,}_{,}\times ,r,\wedge ,=,id,lit,(,)\}$ (pay attention to the underline "_ ") and the following CFG grammar:

1. $E\to \sigma \mathrm{\_}P(E)$
2. $E\to \sigma \mathrm{\_}P(E)\times E$
3. $E\to r\times E$
4. $E\to r$
5. $P\to P\wedge A$
6. $P\to A$
7. $A\to I=I$
8. $I\to id$
9. $I\to lit$

and answer the following questions. Show the detail of each step.

1. Use the grammar to do left-most and right-most derivation on the input "$\sigma \mathrm{\_}id=lit(r)$" and draw the parse tree. (12 pt)

Left-most derivation:

1. $E$
2. $\sigma \mathrm{\_}P(E)$
3. $\sigma \mathrm{\_}A(E)$
4. $\sigma \mathrm{\_}I=I(E)$
5. $\sigma \mathrm{\_}id=I(E)$
6. $\sigma \mathrm{\_}id=lit(E)$
7. $\sigma \mathrm{\_}id=lit(r)$

Right-most derivation:

1. $E$
2. $\sigma \mathrm{\_}P(E)$
3. $\sigma \mathrm{\_}P(r)$
4. $\sigma \mathrm{\_}A(r)$
5. $\sigma \mathrm{\_}I=I(r)$
6. $\sigma \mathrm{\_}I=lit(r)$
7. $\sigma \mathrm{\_}id=lit(r)$

2. Eliminate the left recursions. (6 pt)

There is only one production rule that has left recursion, which is $P\to P\wedge A$. We can eliminate it by introducing a new non-terminal symbol $P^{\prime }$ and rewrite the grammar as follows:

• $P\to P\wedge A|A$

Eliminate the left recursions：

• $P\to A{P}^{\prime }$
• $P^{\prime }\to \wedge A{P}^{\prime }|ϵ$

Due to $P^{\prime }\to ϵ$ ; Therefore,

• $P\to A{P}^{\prime }$
• $P^{\prime }\to \wedge A{P}^{\prime }|ϵ$
• $P\to A$

can be simplified as follows:

$P\to A{P}^{\prime }$$P^{\prime }\to \wedge A{P}^{\prime }|ϵ$

Rewrite the grammar as follows:

1. $E\to \sigma \mathrm{\_}P(E)$
2. $E\to \sigma \mathrm{\_}P(E)\times E$
3. $E\to r\times E$
4. $E\to r$
5. $P\to A{P}^{\prime }$
6. $P^{\prime }\to \wedge A{P}^{\prime }|ϵ$
7. $A\to I=I$
8. $I\to id$
9. $I\to lit$

3. Base on the grammar without left recursions from Q2, left factorize the grammar. (6 pt)

There are several productions that have common prefixes:

• $E\to \sigma \mathrm{\_}P(E)|\sigma \mathrm{\_}P(E)\times E$
• $E\to r\times E|r$

We can left factorize the grammar as follows:

• $E\to \sigma \mathrm{\_}P(E)E^{\prime }$

• $E^{\prime }\to ϵ|\times E$

• $E\to r{E}^{″}$

• $E^{″}\to \times E|ϵ$

And it can be simplified as follows:

• $E\to \sigma \mathrm{\_}P(E)E^{\prime }|r{E}^{\prime }$
• $E^{\prime }\to ϵ|\times E$

Rewrite the grammar as follows:

1. $E\to \sigma \mathrm{\_}P(E)E^{\prime }|r{E}^{\prime }$
2. $E^{\prime }\to ϵ|\times E$
3. $P\to A{P}^{\prime }$
4. $P^{\prime }\to \wedge A{P}^{\prime }|ϵ$
5. $A\to I=I$
6. $I\to id|lit$

4. Base on the grammar from Q3, find the $First$ set and the $Follow$ set. (10 pt)

First set

For all terminals:

$X$	$\sigma$	$\mathrm{\_}$	$\times$	$r$	$\wedge$	$=$	$id$	$lit$	$($	$)$
$First(X)$	$\{\sigma \}$	$\{\mathrm{\_}\}$	$\{\times \}$	$\{r\}$	$\{\wedge \}$	$\{=\}$	$\{id\}$	$\{lit\}$	$\{(\}$	$\{)\}$

For $E\to \sigma \mathrm{\_}P(E)E^{\prime }|r{E}^{\prime }$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$First(X)$	$\{\sigma ,r\}$	$\{\}$	$\{\}$	$\{\}$	$\{\}$	$\{\}$

For $E^{\prime }\to ϵ|\times E$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$First(X)$	$\{\sigma ,r\}$	$\{\times ,ϵ\}$	$\{\}$	$\{\}$	$\{\}$	$\{\}$

For $P\to A{P}^{\prime }$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$First(X)$	$\{\sigma ,r\}$	$\{\times ,ϵ\}$	$\{FIRST(A)\}$	$\{\}$	$\{\}$	$\{\}$

For $P^{\prime }\to \wedge A{P}^{\prime }|ϵ$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$First(X)$	$\{\sigma ,r\}$	$\{\times ,ϵ\}$	$\{FIRST(A)\}$	$\{\wedge ,ϵ\}$	$\{\}$	$\{\}$

For $A\to I=I$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$First(X)$	$\{\sigma ,r\}$	$\{\times ,ϵ\}$	$\{FIRST(A)\}$	$\{\wedge ,ϵ\}$	$\{FIRST(I)\}$	$\{\}$

For $I\to id|lit$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$First(X)$	$\{\sigma ,r\}$	$\{\times ,ϵ\}$	$\{FIRST(A)\}$	$\{\wedge ,ϵ\}$	$\{FIRST(I)\}$	$\{id,lit\}$

Final First set:

$X$	$\sigma$	$\mathrm{\_}$	$\times$	$r$	$\wedge$	$=$	$id$	$lit$	$($	$)$
$First(X)$	$\{\sigma \}$	$\{\mathrm{\_}\}$	$\{\times \}$	$\{r\}$	$\{\wedge \}$	$\{=\}$	$\{id\}$	$\{lit\}$	$\{(\}$	$\{)\}$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$First(X)$	$\{\sigma ,r\}$	$\{\times ,ϵ\}$	$\{id,lit\}$	$\{\wedge ,ϵ\}$	$\{id,lit\}$	$\{id,lit\}$

Follow set:

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$First(X)$	$\{\sigma ,r\}$	$\{\times ,ϵ\}$	$\{id,lit\}$	$\{\wedge ,ϵ\}$	$\{id,lit\}$	$\{id,lit\}$

$E$ is the start symbol, $FOLLOW(E)\supseteq \{\mathrm{\$}\}$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$Follow(X)$	$\{\mathrm{\$}\}$	$\{\}$	$\{\}$	$\{\}$	$\{\}$	$\{\}$

For $E\to \sigma \mathrm{\_}P(E)E^{\prime }|r{E}^{\prime }$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$Follow(X)$	$\{\mathrm{\$},FIRST())/ϵ\}$	$\{FOLLOW(E)\}$	$\{FIRST(()/ϵ\}$	$\{\}$	$\{\}$	$\{\}$

For $E^{\prime }\to ϵ|\times E$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$Follow(X)$	$\{\mathrm{\$},FIRST())/ϵ,FOLLOW(E^{\prime }))\}$	$\{FOLLOW(E)\}$	$\{FIRST(()/ϵ\}$	$\{\}$	$\{\}$	$\{\}$

For $P\to A{P}^{\prime }$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$Follow(X)$	$\{\mathrm{\$},FIRST())/ϵ,FOLLOW(E^{\prime }))\}$	$\{FOLLOW(E)\}$	$\{FIRST(()/ϵ\}$	$\{FOLLOW(P)\}$	$\{FIRST(P^{\prime })/ϵ,FOLLOW(P)\}$	$\{\}$

For $P^{\prime }\to \wedge A{P}^{\prime }|ϵ$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$Follow(X)$	$\{\mathrm{\$},FIRST())/ϵ,FOLLOW(E^{\prime }))\}$	$\{FOLLOW(E)\}$	$\{FIRST(()/ϵ\}$	$\{FOLLOW(P)\}$	$\{FIRST(P^{\prime })/ϵ,FOLLOW(P)\}$	$\{\}$

For $A\to I=I$

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$Follow(X)$	$\{\mathrm{\$},FIRST())/ϵ,FOLLOW(E^{\prime }))\}$	$\{FOLLOW(E)\}$	$\{FIRST(()/ϵ\}$	$\{FOLLOW(P)/ϵ\}$	$\{FIRST(P^{\prime })/ϵ,FOLLOW(P)\}$	$\{FOLLOW(A),=\}$

For $I\to id|lit$

These are terminal symbols. So, Follow($I$) is only influenced by the productions involving $A$.

Final Follow set:

$X$	$E$	$E^{\prime }$	$P$	$P^{\prime }$	$A$	$I$
$Follow(X)$	$\{\mathrm{\$},)\}$	$\{\mathrm{\$},)\}$	$\{(\}$	$\{(\}$	$\{\wedge ,(\}$	$\{\wedge ,=,(\}$

5. Base on the grammar from Q3, construct the $LL(1)$ parsing table. (6 pt)

$LL(1)$ parsing table

1. $E\to \sigma \mathrm{\_}P(E)E^{\prime }|r{E}^{\prime }$
2. $E^{\prime }\to ϵ|\times E$
3. $P\to A{P}^{\prime }$
4. $P^{\prime }\to \wedge A{P}^{\prime }|ϵ$
5. $A\to I=I$
6. $I\to id|lit$

	$\sigma$	$\mathrm{\_}$	$\times$	$r$	$\wedge$	$=$	$id$	$lit$	$($	$)$	$\mathrm{\$}$
$E$	$E\to \sigma \mathrm{\_}P(E)E^{\prime }$			$E\to r{E}^{\prime }$
$E^{\prime }$			$E^{\prime }\to \times E$							$E^{\prime }\to ϵ$	$E^{\prime }\to ϵ$
$P$							$P\to A{P}^{\prime }$	$P\to A{P}^{\prime }$
$P^{\prime }$					$P^{\prime }\to \wedge A{P}^{\prime }$				$P^{\prime }\to ϵ$
$A$							$A\to I=I$	$A\to I=I$
$I$							$I\to id$	$I\to lit$

6. Base on the original grammar construct the DFA from the set of $LR(0)$ items (18 pt)

1. $E\to \sigma \mathrm{\_}P(E)|\sigma \mathrm{\_}P(E)\times E|r\times E|r$
2. $P\to P\wedge A|A$
3. $A\to I=I$
4. $I\to id|lit$

Construct the corresponding augmented grammar

1. $E^{\prime }\to E$
2. $E\to \sigma \mathrm{\_}P(E)|\sigma \mathrm{\_}P(E)\times E|r\times E|r$
3. $P\to P\wedge A|A$
4. $A\to I=I$
5. $I\to id|lit$

Construct the $LR(0)$ items:

$I_0=closure(E^{\prime }\to \cdot E)=\{E^{\prime }\to \cdot E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}$

• $goto(I_0,E)=closure(\{E^{\prime }\to E\cdot \})=\{E^{\prime }\to E\cdot \}=I_1$
• $goto(I_0,\sigma )=closure(\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\})=\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\}=I_2$
• $goto(I_0,r)=closure(\{E\to r\cdot \times E,E\to r\cdot \})=\{E\to r\cdot \times E,E\to r\cdot \}=I_3$

For $I_1=\{E^{\prime }\to E\cdot \}$ nothing can be done

For $I_2=\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\}$

• $goto(I_2,\mathrm{\_})=closure(\{E\to \sigma \mathrm{\_}\cdot P(E),E\to \sigma \mathrm{\_}\cdot P(E)\times E\})=\{E\to \sigma \mathrm{\_}\cdot P(E),E\to \sigma \mathrm{\_}\cdot P(E)\times E,P\to \cdot P\wedge A,P\to \cdot A,A\to \cdot I=I,I\to \cdot id,I\to \cdot lit\}=I_4$

For $I_3=\{E\to r\cdot \times E,E\to r\cdot \}$

• $goto(I_3,\times )=closure(\{E\to r\times \cdot E\})=\{E\to r\times \cdot E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}=I_5$

For $I_4=\{E\to \sigma \mathrm{\_}\cdot P(E),E\to \sigma \mathrm{\_}\cdot P(E)\times E,P\to \cdot P\wedge A,P\to \cdot A,A\to \cdot I=I,I\to \cdot id,I\to \cdot lit\}$

• $goto(I_4,P)=closure(\{E\to \sigma \mathrm{\_}P\cdot (E),E\to \sigma \mathrm{\_}P\cdot (E)\times E,P\to P\cdot \wedge A\})=\{E\to \sigma \mathrm{\_}P\cdot (E),E\to \sigma \mathrm{\_}P\cdot (E)\times E,P\to P\cdot \wedge A\}=I_6$
• $goto(I_4,A)=closure(\{P\to A\cdot \})=\{P\to A\cdot \}=I_7$
• $goto(I_4,I)=closure(\{A\to I\cdot =I\})=\{A\to I\cdot =I\}=I_8$
• $goto(I_4,id)=closure(\{I\to id\cdot \})=\{I\to id\cdot \}=I_9$
• $goto(I_4,lit)=closure(\{I\to lit\cdot \})=\{I\to lit\cdot \}=I_{10}$

For $I_5=\{E\to r\times \cdot E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}$

• $goto(I_5,E)=closure(\{E\to r\times E\cdot \})=\{E\to r\times E\cdot \}=I_{11}$
• $goto(I_5,\sigma )=closure(\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\})=\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\}=I_2$
• $goto(I_5,r)=closure(\{E\to r\cdot \times E,E\to r\cdot \})=\{E\to r\cdot \times E,E\to r\cdot \}=I_3$

For $I_6=\{E\to \sigma \mathrm{\_}P\cdot (E),E\to \sigma \mathrm{\_}P\cdot (E)\times E,P\to P\cdot \wedge A\}$

• $goto(I_6,()=closure(\{E\to \sigma \mathrm{\_}P(\cdot E),E\to \sigma \mathrm{\_}P(\cdot E)\times E\})=\{E\to \sigma \mathrm{\_}P(\cdot E),E\to \sigma \mathrm{\_}P(\cdot E)\times E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}=I_{12}$
• $goto(I_6,\wedge )=closure(\{P\to P\wedge \cdot A\})=\{P\to P\wedge \cdot A,A\to \cdot I=I,I\to \cdot id,I\to \cdot lit\}=I_{13}$

For $I_7=\{P\to A\cdot \}$ nothing can be done

For $I_8=\{A\to I\cdot =I\}$

• $goto(I_8,=)=closure(\{A\to I=\cdot I\})=\{A\to I=\cdot I,I=\to \cdot id,I\to \cdot lit\}=I_{14}$

For $I_9=\{I\to id\cdot \}$ nothing can be done For $I_{10}=\{I\to lit\cdot \}$ nothing can be done For $I_{11}=\{E\to r\times E\cdot \}$ nothing can be done

For $I_{12}=\{E\to \sigma \mathrm{\_}P(\cdot E),E\to \sigma \mathrm{\_}P(\cdot E)\times E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}$

• $goto(I_{12},E)=closure(\{E\to \sigma \mathrm{\_}P(E\cdot ),E\to \sigma \mathrm{\_}P(E\cdot )\times E\})=\{E\to \sigma \mathrm{\_}P(E\cdot ),E\to \sigma \mathrm{\_}P(E\cdot )\times E\}=I_{15}$

• $goto(I_{12},\sigma )=closure(\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\})=\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E,P\to \cdot P\wedge A,P\to \cdot A,A\to \cdot I=I,I\to \cdot id,I\to \cdot lit\}=I_4$

• $goto(I_{12},r)=closure(\{E\to r\cdot \times E,E\to r\cdot \})=\{E\to r\cdot \times E,E\to r\cdot \}=I_3$

For $I_{13}=\{P\to P\wedge \cdot A,A\to \cdot I=I,I\to \cdot id,I\to \cdot lit\}$

• $goto(I_{13},A)=closure(\{P\to P\wedge A\cdot \})=\{P\to P\wedge A\cdot \}=I_{16}$
• $goto(I_{13},I)=closure(\{A\to I\cdot =I\})=\{A\to I\cdot =I\}=I_8$
• $goto(I_{13},id)=closure(\{I\to id\cdot \})=\{I\to id\cdot \}=I_9$
• $goto(I_{13},lit)=closure(\{I\to lit\cdot \})=\{I\to lit\cdot \}=I_{10}$

For $I_{14}=\{A\to I=\cdot I,I=\to \cdot id,I\to \cdot lit\}$

• $goto(I_{14},I)=closure(\{A\to I=I\cdot \})=\{A\to I=I\cdot \}=I_{17}$
• $goto(I_{14},id)=closure(\{I\to id\cdot \})=\{I\to id\cdot \}=I_9$
• $goto(I_{14},lit)=closure(\{I\to lit\cdot \})=\{I\to lit\cdot \}=I_{10}$

For $I_{15}=\{E\to \sigma \mathrm{\_}P(E\cdot ),E\to \sigma \mathrm{\_}P(E\cdot )\times E\}$

• $goto(I_{15},))=closure(\{E\to \sigma \mathrm{\_}P(E)\cdot ,E\to \sigma \mathrm{\_}P(E)\cdot \times E\})=\{E\to \sigma \mathrm{\_}P(E)\cdot ,E\to \sigma \mathrm{\_}P(E)\cdot \times E\}=I_{18}$

For $I_{16}=\{P\to P\wedge A\cdot \}$ nothing can be done For $I_{17}=\{A\to I=I\cdot \}$ nothing can be done

For $I_{18}=\{E\to \sigma \mathrm{\_}P(E)\cdot ,E\to \sigma \mathrm{\_}P(E)\cdot \times E\}$

• $goto(I_{18},\times )=closure(\{E\to \sigma \mathrm{\_}P(E)\times \cdot E\})=\{E\to \sigma \mathrm{\_}P(E)\times \cdot E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}=I_{19}$

For $I_{19}=\{E\to \sigma \mathrm{\_}P(E)\times \cdot E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}$

• $goto(I_{19},E)=closure(\{E\to \sigma \mathrm{\_}P(E)\times E\cdot \})=\{E\to \sigma \mathrm{\_}P(E)\times E\cdot \}=I_{20}$
• $goto(I_{19},\sigma )=closure(\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\})=\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\}=I_2$
• $goto(I_{19},r)=closure(\{E\to r\cdot \times E,E\to r\cdot \})=\{E\to r\cdot \times E,E\to r\cdot \}=I_3$

For $I_{20}=\{E\to \sigma \mathrm{\_}P(E)\times E\cdot \}$ nothing can be done

Here is the list of sets of items.

$i$	$I_i$
0	$\{E^{\prime }\to \cdot E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}$
1	$\{E^{\prime }\to E\cdot \}$
2	$\{E\to \sigma \cdot \mathrm{\_}P(E),E\to \sigma \cdot \mathrm{\_}P(E)\times E\}$
3	$\{E\to r\cdot \times E,E\to r\cdot \}$
4	$\{E\to \sigma \mathrm{\_}\cdot P(E),E\to \sigma \mathrm{\_}\cdot P(E)\times E,P\to \cdot P\wedge A,P\to \cdot A,A\to \cdot I=I,I\to \cdot id,I\to \cdot lit\}$
5	$\{E\to r\times \cdot E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}$
6	$\{E\to \sigma \mathrm{\_}P\cdot (E),E\to \sigma \mathrm{\_}P\cdot (E)\times E,P\to P\cdot \wedge A\}$
7	$\{P\to A\cdot \}$
8	$\{A\to I\cdot =I\}$
9	$\{I\to id\cdot \}$
10	$\{I\to lit\cdot \}$
11	$\{E\to r\times E\cdot \}$
12	$\{E\to \sigma \mathrm{\_}P(\cdot E),E\to \sigma \mathrm{\_}P(\cdot E)\times E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}$
13	$\{P\to P\wedge \cdot A,A\to \cdot I=I,I\to \cdot id,I\to \cdot lit\}$
14	$\{A\to I=\cdot I,I\to \cdot id,I\to \cdot lit\}$
15	$\{E\to \sigma \mathrm{\_}P(E\cdot ),E\to \sigma \mathrm{\_}P(E\cdot )\times E\}$
16	$\{P\to P\wedge A\cdot \}$
17	$\{A\to I=I\cdot \}$
18	$\{E\to \sigma \mathrm{\_}P(E)\cdot ,E\to \sigma \mathrm{\_}P(E)\cdot \times E\}$
19	$\{E\to \sigma \mathrm{\_}P(E)\times \cdot E,E\to \cdot \sigma \mathrm{\_}P(E),E\to \cdot \sigma \mathrm{\_}P(E)\times E,E\to \cdot r\times E,E\to \cdot r\}$
20	$\{E\to \sigma \mathrm{\_}P(E)\times E\cdot \}$

7. Convert the DFA from Q6 to an $SLR(1)$ parsing table. (15 pt)

1. $E^{\prime }\to E$
2. $E\to \sigma \mathrm{\_}P(E)$
3. $E\to \sigma \mathrm{\_}P(E)\times E$
4. $E\to r\times E$
5. $E\to r$
6. $P\to P\wedge A$
7. $P\to A$
8. $A\to I=I$
9. $I\to id$
10. $I\to lit$

$SLR(1)$ parsing table

$X$	$E^{\prime }$	$E$	$P$	$A$	$I$
$FIRST(X)$	$FIRST(E)$	$\{\sigma ,r\}$	$FIRST(A)$	$FIRST(I)$	$\{id,lit\}$

$X$	$E^{\prime }$	$E$	$P$	$A$	$I$
$FIRST(X)$	$\{\sigma ,r\}$	$\{\sigma ,r\}$	$\{id,lit\}$	$\{id,lit\}$	$\{id,lit\}$

$X$	$E^{\prime }$	$E$	$P$	$A$	$I$
$FOLLOW(X)$	$\mathrm{\$}$	$),\mathrm{\$}$	$\wedge ,($	$\wedge ,($	$\wedge ,(,=$

$STATE$	$\sigma$	$\mathrm{\_}$	$\times$	$r$	$\wedge$	$=$	$id$	$lit$	$($	$)$	$\mathrm{\$}$	$E$	$P$	$A$	$I$
0	$S2$			$S3$								$1$
1											$acc$
2		$S4$
3			$S5$							$R5$	$R5$
4							$S9$	$S10$					$6$	$7$	$8$
5	$S2$			$S3$								11
6					$S13$				$S12$
7					$R7$				$R7$
8						$S14$
9					$R9$	$R9$			$R9$
10					$R10$	$R10$			$R10$
11										$R4$	$R4$
12	$S4$			$S3$								$15$
13							$S9$	$S10$						$16$	$8$
14							$S9$	$S10$							$17$
15										$S18$
16					$R6$				$R6$
17					$R8$	$R8$			$R8$
18			$S19$							$R2$	$R2$
19	$S2$			$S3$								$20$
20										$R3$	$R3$

8. Use the $SLR(1)$ parsing table to parse "$\sigma \mathrm{\_}id=lit(r)$". Show the configuration and the output for each step. (10 pt)

Stack	Input	Output
$0$	$\sigma \mathrm{\_}id=lit(r)\mathrm{\$}$
$0\underset{―}{\sigma 2}$	$\mathrm{\_}id=lit(r)\mathrm{\$}$	$Shift2$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}$	$id=lit(r)\mathrm{\$}$	$Shift4$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{id9}$	$=lit(r)\mathrm{\$}$	$Shift9$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{I8}$	$=lit(r)\mathrm{\$}$	$Reduce9.I\to id$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{I8}\underset{―}{=14}$	$lit(r)\mathrm{\$}$	$Shift14$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{I8}\underset{―}{=14}\underset{―}{lit10}$	$(r)\mathrm{\$}$	$Shift10$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{I8}\underset{―}{=14}\underset{―}{I17}$	$(r)\mathrm{\$}$	$Reduce10.I\to lit$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{A7}$	$(r)\mathrm{\$}$	$Reduce8.A\to I=I$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{P6}$	$(r)\mathrm{\$}$	$Reduce7.P\to A$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{P6}\underset{―}{(12}$	$r)\mathrm{\$}$	$Shift12$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{P6}\underset{―}{(12}\underset{―}{r3}$	$)\mathrm{\$}$	$Shift3$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{P6}\underset{―}{(12}\underset{―}{E15}$	$)\mathrm{\$}$	$Reduce5.E\to r$
$0\underset{―}{\sigma 2}\underset{―}{\mathrm{\_}4}\underset{―}{P6}\underset{―}{(12}\underset{―}{E15}\underset{―}{)18}$	$\mathrm{\$}$	$Shift18$
$0\underset{―}{E1}$	$\mathrm{\$}$	$Reduce2.E\to \sigma \mathrm{\_}P(E)$
$0\underset{―}{E1}$	$\mathrm{\$}$	$Accept$

Question 2

Given the following grammar:

1. $E\to E+E$
2. $E\to id$

9. Show that the grammar is ambiguous. (6 pt)

The grammar $G$ is ambiguous if there is a sentence in $L(G)$ from which it is possible to construct multiple parse trees (using any type of derivation).

For example the sentence $id+id+id$ can be derived in two different ways:

1. $E\to E+E\to E+E+E\to id+E+E\to id+id+E\to id+id+id$
2. $E\to E+E\to id+E\to id+E+E\to id+id+E\to id+id+id$

Obviously, the sentence $id+id+id$ can be derived in two different ways, which means the grammar is ambiguous.

10. Find a sentence in the language such that the sentence is ambiguous but left-most derivation and right-most derivation can produce a same parse tree. You need to prove your answer. (9 pt)

For example the sentence $id+id+id$ can be derived in two different ways:

Left-Most Derivation:

1. $E$
2. $E+E$
3. $E+E+E$
4. $id+E+E$
5. $id+id+E$
6. x$id+id+id$

Right-Most Derivation:

1. $E$
2. $E+E$
3. $E+id$
4. $E+E+id$
5. $E+id+id$
6. $id+id+id$