编译原理作业5
由于格式的问题，dollar用$\psi $代替。
Exercise 5.1
Given the following grammar ：
$$
S → ( L ) | a\
L → L , S | S
$$
- Construct an LL(1) parsing table for the grammar
- Draw the detailed process of the parsing of the sentence (a, (a, a)), follow the style in the previous slides.
首先消除左递归后结果如下：
$$
S → ( L ) | a\
L → SL’\
L’ → ,SL’ | \epsilon
$$
$FIRST(L’) = {\textbf{,}\ ,\ \epsilon }$
$FIRST(L) = FIRST(S) = {\ ( \ ,\ a}$
$FOLLOW(S) = {\psi ,\ ),\ \textbf{,}}$
$FOLLOW(L) = {\ )}$
$FOLLOW(L’) = {\ )}$
画出Parsing Table，如下：
| ( | ) | a | , | $ | |
|---|---|---|---|---|---|
| S | (L) | a | |||
| L | SL’ | SL’ | |||
| L’ | $\epsilon$ | ,SL’ |
Parsing process如下：
| Step | Stack | Input | Reference | Action | Output |
|---|---|---|---|---|---|
| 0 | $\psi S$ | $(a,(a,a))\psi $ | $[S,\ (] = (L)$ | derive | $S→(L)$ |
| 1 | $\psi ) L ($ | $a,(a,a))\psi $ | match | ||
| 2 | $\psi )L$ | $a,(a,a))\psi $ | $[L,a] = SL’$ | derive | $L→SL’$ |
| 3 | $\psi )L’S$ | $a,(a,a))\psi $ | $[S,\ a] = a$ | derive | $S→a$ |
| 4 | $\psi )L’a$ | $a,(a,a))\psi $ | match | ||
| 5 | $\psi )L’$ | $,(a,a))\psi $ | $[L’,\textbf{,}] = ,SL’$ | derive | $L’→,SL’$ |
| 6 | $\psi )L’S,$ | $,(a,a))\psi $ | match | ||
| 7 | $\psi )L’S$ | $(a,a))\psi $ | $[S\ ,\ (] = (L)$ | derive | $S→(L)$ |
| 8 | $\psi )L’)L($ | $(a,a))\psi $ | match | ||
| 9 | $\psi )L’)L$ | $a,a))\psi $ | $[L,a] = SL’$ | derive | $L→SL’$ |
| 10 | $\psi )L’)L’S$ | $a,a))\psi $ | $[S,\ a] = a$ | derive | $S→a$ |
| 11 | $\psi )L’)L’a$ | $a,a))\psi $ | match | ||
| 12 | $\psi )L’)L’$ | $,a))\psi $ | $[L’,\textbf{,}] = ,SL’$ | derive | $L’→,SL’$ |
| 13 | $\psi )L’)L’S,$ | $,a))\psi $ | match | ||
| 14 | $\psi )L’)L’S$ | $a))\psi $ | $[S,\ a] = a$ | derive | $S→a$ |
| 15 | $\psi )L’)L’a$ | $a))\psi $ | match | ||
| 16 | $\psi )L’)L’$ | $))\psi $ | $[L’,)] = \epsilon$ | derive | $L’→\epsilon$ |
| 17 | $\psi )L’)$ | $))\psi $ | match | ||
| 18 | $\psi )L’$ | $)\psi $ | $[L’,)] = \epsilon$ | derive | $L’→\epsilon$ |
| 19 | $\psi )$ | $)\psi $ | match | ||
| 20 | $\psi $ | $\psi $ | accept |
Exercise 5.2
Given the following grammar
$$
A → B | B C \
B → a B | \epsilon \
C → a b\
$$
- Left factor the grammar.
- After left factoring, is the grammar an LL(1) grammar? or is it an LL(k) grammar? and why?
消除左因子后，语法如下：
$$
A → BA’ \
A’ → C | \epsilon \
B → a B | \epsilon \
C → a b\
$$
首先判断是否为LL(1)文法：
$FIRST(C) = {a}$
$FIRST(B) = {a,\epsilon}$
$FIRST(A’) = {a,\epsilon}$
$FIRST(A) = {a, \epsilon}$
$FOLLOW(A) = {\psi }$
$FOLLOW(A’) = {\psi }$
$FOLLOW(B) = {a,\psi }$
$FOLLOW(C) = {\psi }$
因为$B → a B | \epsilon $ ，$FIRST(aB)\ \cap\ FOLLOW(B) = {a}$
所以该文法不是LL(1)文法。
该文法是LL(2)文法：
$FIRST(C) = {ab}$
$FIRST(B) = {aa,\ a\epsilon,\ \epsilon}$
$FIRST(A’) = {ab,\epsilon}$
$FIRST(A) = {aa, ab , a\epsilon, \epsilon}$
$FOLLOW(A) = {\psi }$
$FOLLOW(A’) = {\psi }$
$FOLLOW(B) = {ab,\psi }$
$FOLLOW(C) = {\psi }$
做出Parsing Table，如下：
| $aa$ | $ab$ | $ba$ | $bb$ | $a\psi$ | $b\psi$ | $\psi$ | |
|---|---|---|---|---|---|---|---|
| $A$ | $BA’$ | $BA’$ | $BA’$ | $BA’$ | |||
| $A’$ | $C$ | $\epsilon$ | |||||
| $B$ | $aB$ | $\epsilon$ | $aB$ | $\epsilon$ | |||
| $C$ | $ab$ |
不会产生冲突，可以得出该文法是LL(2)文法。
