【编译原理】第三章部分课后题答案

第 三 章 课 后 习 题

T 3.1

考虑文法
$$S\to (L)|aL\to L,S|S$$
(a) 建立句子 $(a,(a,a))$ 和 $(a,(a,a),(a,a))$ 的分析树。

见下面两题。

(b) 为 (a) 的两个句子构造最左推导。

$(a,(a,a))$ 最左推导的分析树（包括推导过程中的分析树）：

$(a,(a,a),(a,a))$ 最左推导的分析树：

S
⇒
l
m
(
L
)
⇒
l
m
(
L
,
S
)
⇒
l
m
(
S
,
S
)
⇒
l
m
(
a
,
S
)
⇒
l
m
(
a
,
(
L
)
)
⇒
l
m
(
a
,
(
L
,
S
)
)
⇒
l
m
(
a
,
(
S
,
S
)
)
⇒
l
m
(
a
,
(
(
L
)
,
S
)
)
⇒
l
m
(
a
,
(
(
L
,
S
)
,
S
)
)
⇒
l
m
(
a
,
(
(
S
,
S
)
,
S
)
)
⇒
l
m
(
a
,
(
(
a
,
S
)
,
S
)
)
⇒
l
m
(
a
,
(
(
a
,
a
)
,
S
)
)
⇒
l
m
(
a
,
(
(
a
,
a
)
,
(
L
)
)
)
⇒
l
m
(
a
,
(
(
a
,
a
)
,
(
L
)
)
)
⇒
l
m
(
a
,
(
(
a
,
a
)
,
(
L
,
S
)
)
)
⇒
l
m
(
a
,
(
(
a
,
a
)
,
(
S
,
S
)
)
)
⇒
l
m
(
a
,
(
(
a
,
a
)
,
(
a
,
S
)
)
)
⇒
l
m
(
a
,
(
(
a
,
a
)
,
(
a
,
a
)
)
)
S\Rightarrow_{lm} (L)\Rightarrow_{lm} (L,S) \Rightarrow_{lm} (S,S) \Rightarrow_{lm} (a,S) \Rightarrow_{lm}(a,(L)) \Rightarrow_{lm} (a,(L,S)) \Rightarrow_{lm} (a,(S,S)) \Rightarrow_{lm} (a,((L),S))\\ \Rightarrow_{lm} (a,((L,S),S)) \Rightarrow_{lm} (a,((S,S),S))\Rightarrow_{lm} (a,((a,S),S)) \Rightarrow_{lm} (a,((a,a),S)) \Rightarrow_{lm} (a,((a,a),(L)))\\ \Rightarrow_{lm} (a,((a,a),(L))) \Rightarrow_{lm} (a,((a,a),(L,S)))\Rightarrow_{lm} (a,((a,a),(S,S))) \Rightarrow_{lm} (a,((a,a),(a,S))) \Rightarrow_{lm} (a,((a,a),(a,a)))
S⇒lm​(L)⇒lm​(L,S)⇒lm​(S,S)⇒lm​(a,S)⇒lm​(a,(L))⇒lm​(a,(L,S))⇒lm​(a,(S,S))⇒lm​(a,((L),S))⇒lm​(a,((L,S),S))⇒lm​(a,((S,S),S))⇒lm​(a,((a,S),S))⇒lm​(a,((a,a),S))⇒lm​(a,((a,a),(L)))⇒lm​(a,((a,a),(L)))⇒lm​(a,((a,a),(L,S)))⇒lm​(a,((a,a),(S,S)))⇒lm​(a,((a,a),(a,S)))⇒lm​(a,((a,a),(a,a)))
(c) 为 (a) 的两个句子构造最右推导。

$(a,(a,a))$ 最右推导的分析树（包括推导过程中的分析树）：

$(a,(a,a),(a,a))$ 最右推导：

S
⇒
r
m
(
L
)
⇒
r
m
(
L
,
S
)
⇒
r
m
(
L
,
(
L
)
)
⇒
r
m
(
L
,
(
L
,
S
)
)
⇒
r
m
(
L
,
(
L
,
(
L
)
)
)
⇒
r
m
(
L
,
(
L
,
(
L
,
S
)
)
)
⇒
r
m
(
L
,
(
L
,
(
L
,
a
)
)
)
⇒
r
m
(
L
,
(
L
,
(
S
,
a
)
)
)
⇒
r
m
(
L
,
(
L
,
(
a
,
a
)
)
)
⇒
r
m
(
L
,
(
S
,
(
a
,
a
)
)
)
⇒
r
m
(
L
,
(
(
L
)
,
(
a
,
a
)
)
)
⇒
r
m
(
L
,
(
(
L
,
S
)
,
(
a
,
a
)
)
)
⇒
r
m
(
L
,
(
(
L
,
a
)
,
(
a
,
a
)
)
)
⇒
r
m
(
L
,
(
(
S
,
a
)
,
(
a
,
a
)
)
)
⇒
r
m
(
L
,
(
(
a
,
a
)
,
(
a
,
a
)
)
)
⇒
r
m
(
S
,
(
(
a
,
a
)
,
(
a
,
a
)
)
)
⇒
r
m
(
a
,
(
(
a
,
a
)
,
(
a
,
a
)
)
)
S\Rightarrow_{rm} (L) \Rightarrow_{rm} (L,S) \Rightarrow_{rm} (L,(L)) \Rightarrow_{rm} (L,(L,S)) \Rightarrow_{rm} (L,(L,(L)))\Rightarrow_{rm} (L,(L,(L,S)))\Rightarrow_{rm} (L,(L,(L,a))) \\ \Rightarrow_{rm} (L,(L,(S,a))) \Rightarrow_{rm} (L,(L,(a,a))) \Rightarrow_{rm} (L,(S,(a,a))) \Rightarrow_{rm} (L,((L),(a,a)))\Rightarrow_{rm} (L,((L,S),(a,a))) \\ \Rightarrow_{rm} (L,((L,a),(a,a))) \Rightarrow_{rm} (L,((S,a),(a,a)))\Rightarrow_{rm} (L,((a,a),(a,a))) \Rightarrow_{rm} (S,((a,a),(a,a)))\Rightarrow_{rm} (a,((a,a),(a,a)))
S⇒rm​(L)⇒rm​(L,S)⇒rm​(L,(L))⇒rm​(L,(L,S))⇒rm​(L,(L,(L)))⇒rm​(L,(L,(L,S)))⇒rm​(L,(L,(L,a)))⇒rm​(L,(L,(S,a)))⇒rm​(L,(L,(a,a)))⇒rm​(L,(S,(a,a)))⇒rm​(L,((L),(a,a)))⇒rm​(L,((L,S),(a,a)))⇒rm​(L,((L,a),(a,a)))⇒rm​(L,((S,a),(a,a)))⇒rm​(L,((a,a),(a,a)))⇒rm​(S,((a,a),(a,a)))⇒rm​(a,((a,a),(a,a)))
(d) 这个文法产生的语言是什么？

该文法产生的语言是括号匹配的串，串中的各项用“，”隔开，项可以是括号匹配的子串或 a。

T 3.2

考虑文法
$$S\to aSbS|bSaS|\epsilon$$
(a) 为句子 $abab$ 构造两个不同的最左推导，以此说明该文法是二义的。

第一种最左推导的分析树（包括推导过程中的分析树）：

​

第二种最左推导的分析树（包括推导过程中的分析树）：

一个文法，如果存在某个句子有不止一棵分析树与之对应，那么称这个文法是二义的；故，该文法是是二义的。

(b) 为 $abab$ 构造对应的最右推导。

两种最右推导的分析树（包括推导过程中的分析树）如下：

(c) 为 $abab$ 构造对应的分析树。

见上面四幅图。

(d) 这个文法产生的语言是什么？

通过最左推导的方式和产生式 $S\to aSb$ 可以得到前缀为若干个 $a$ 的任意长度的串；

通过最左推导的方式和产生式 $S\to bSa$ 可以得到前缀为若干个 $b$ 的任意长度的串；

题目给的产生式为 $S\to aSbS$ 、 $S\to bSaS$ 和 $S\to \epsilon$，由 $S$ 可以推导出空串，可以说明可以产生 $S\to aSb$ 和 $S\to bSa$，因此由任意长度的前缀 $a$ 和前缀 $b$ 的子串可以构成 $a$ 和 $b$ 任意交错的串；

又因为每个产生式中 $a$ 和 $b$ 的个数都相同，故产生 $a$ 和 $b$ 数目相等且任意长度的串。

T 3.3

下面的二义文法描述命题演算公式，为它写一个等价的非二义性文法。
$$S\to S\text{and}S|S\text{or}S|\text{not}S|\text{true}|\text{false}|(S)$$
通过引入非终结符消除二义性：
$$E\to E\text{or}T|TT\to T\text{and}F|FF\to \text{not}F|(E)|\text{true}|\text{false}$$

T 3.4

文法

R
→
R
 
′
∣
′
 
R
 
∣
 
R
 
R
 
∣
 
R
∗
 
∣
 
(
R
)
 
∣
 
a
 
∣
 
b
R\rightarrow R\space '|' \space R \space |\space R \space R \space|\space R^*\space|\space(R)\space|\space a \space | \space b
R→R ′∣′ R ∣ R R ∣ R∗ ∣ (R) ∣ a ∣ b
产生字母表 $\{a,b\}$ 上所有不含 $\epsilon$ 的正规式。注意，第一条竖线加了引号，它是正规式的或运算符号，而不是文法产生式右部各选择之间的分隔符，另外
∗
^*
∗在这里是一个普通的终结符。该文法是二义的。

(a) 证明该文法产生字母表 $\{a,b\}$ 上的所有正规式。

证明：

(1) 该文法产生的串是字母表 $\{a,b\}$ 上的正规式：

$R\to a$和$R\to b$产生$a$和$b$，而$a$和$b$是 $\{a,b\}$上的符号，因此是正规式。若
R
1
R_1
R1​，
R
2
R_2
R2​产生正规式$\alpha$和$\beta$
则：

R
→
R
1
R
2
R\rightarrow R_1R_2
R→R1​R2​ 产生正规式 $\alpha \beta$

R
→
R
1
∣
R
2
R\rightarrow R_1|R_2
R→R1​∣R2​ 产生正规式 $\alpha |\beta$

R
→
R
1
∗
R\rightarrow R_1^*
R→R1∗​ 产生正规式
α
∗
\alpha^*
α∗

R
→
(
R
1
)
R\rightarrow (R_1)
R→(R1​) 产生正规式 $(\alpha )$

(2) 字母表 $\{a,b\}$ 上的所有正规式都可由此文法产生：

字母表 $\{a,b\}$ 上的任一正规式（其中 $\alpha$，$\beta$ 为正规式）必为以下形式之一：

$\alpha \beta$，可由 $R\to RR$ 产生

$\alpha |\beta$，可由 $R\to R|R$ 产生

α
∗
\alpha^*
α∗，可由
R
→
R
∗
R\rightarrow R^*
R→R∗ 产生

$(\alpha )$，可由 $R\to (R)$ 产生

$a$，可由 $R\to a$ 产生

$b$，可由 $R\to b$ 产生

因而，该文法产生字母表 $\{a,b\}$ 上的所有正规式

(b) 为该文法写一个等价的非二义文法。它给予算符
∗
^*
∗ 、连接和 $|$ 的优先级和结合性同 2.2 节中定义的一致。

该文法没有体现运算符
∗
^*
∗ 、$()$、 $|$ 和连接的优先级，因而是二义的。例如：

R
⇒
R
 
∣
 
R
⇒
a
 
∣
 
R
 
⇒
a
 
∣
 
R
∗
⇒
a
 
∣
 
b
∗
R
⇒
R
∗
⇒
R
 
∣
 
R
∗
 
⇒
a
 
∣
 
R
∗
⇒
a
 
∣
 
b
∗
R\Rightarrow R\space | \space R \Rightarrow a\space | \space R\space\Rightarrow a\space|\space R^*\Rightarrow a\space|\space b^* \\ R\Rightarrow R^* \Rightarrow R\space | \space R^*\space\Rightarrow a\space|\space R^*\Rightarrow a\space|\space b^*
R⇒R ∣ R⇒a ∣ R ⇒a ∣ R∗⇒a ∣ b∗R⇒R∗⇒R ∣ R∗ ⇒a ∣ R∗⇒a ∣ b∗
通过引入非终结符消除二义性：

E
→
E
 
′
∣
′
 
T
 
∣
 
T
T
→
T
F
 
∣
 
F
F
→
F
∗
 
∣
 
(
E
)
 
∣
 
a
 
∣
 
b
E\rightarrow E\space'|' \space T \space|\space T \\ T\rightarrow TF\space |\space F \\ F\rightarrow F^*\space | \space (E)\space |\space a \space |\space b
E→E ′∣′ T ∣ TT→TF ∣ FF→F∗ ∣ (E) ∣ a ∣ b
消除二义性后：

E
⇒
E
 
∣
 
T
⇒
E
 
∣
 
F
⇒
E
 
∣
 
F
∗
 
⇒
E
 
∣
 
b
∗
⇒
T
 
∣
 
b
∗
⇒
F
 
∣
 
b
∗
⇒
a
 
∣
 
b
∗
E\Rightarrow E\space|\space T\Rightarrow E\space|\space F\Rightarrow E\space|\space F^*\space\Rightarrow E\space |\space b^* \Rightarrow T\space | \space b^* \Rightarrow F \space | \space b^*\Rightarrow a \space | \space b^*
E⇒E ∣ T⇒E ∣ F⇒E ∣ F∗ ⇒E ∣ b∗⇒T ∣ b∗⇒F ∣ b∗⇒a ∣ b∗
(c) 按上面两个文法构造句子
a
b
 
∣
 
b
∗
a
ab\space|\space b^*a
ab ∣ b∗a 的分析树。

存在二义性：

不存在二义性：

T 3.5

条件语句文法
$$stmt\to \text{if}expr\text{then}stmt|matched\_stmtmatched\_stmt\to \text{if}expr\text{then}matched\_stmt\text{else}stmst|\text{other}$$

试图消除悬空 $else$ 的二义性，请证明该文法仍然是二义的。

由于$matched\_stmt$不能保证$then$和$else$的配对，因而存在二义性。

句型 $ifexprthenifexprthenmatched\_stmtelseifexprthenmatched\_stmtelsestmt$ 存在两个不同的最左推导。

期望的是：

if expr then
	if expr then
		matched_stmt
	else 
		if expr then
			matched_stmt
		else 
			stmt

一种和期望不一样的推导：

stmt
=> matched_stmt
=> if expr then matched_stmt else stmt
=> if expr then if expr then matched_stmt else stmt else stmt
=> if expr then if expr then matched_stmt else if expr then stmt else stmt
=> if expr then if expr then matched_stmt else if expr then matched_stmt else stmt
if expr then
	if expr then
		matched_stmt
	else 
		if expr then
			matched_stmt
else 
	stmt

另一种推导：

stmt
=> if expr then stmt
=> if expr then matched_stmt
=> if expr then if expr then matched_stmt else stmt
=> if expr then if expr then matched_stmt else matched_stmt 
=> if expr then if expr then matched_stmt else if expr then matched_stmt else stmt
if expr then
	if expr then
		matched_stmt
	else 
		if expr then
			matched_stmt
		else 
			stmt

T 3.8

(a) 消除习题 3.1 文法的左递归。

S
→
(
L
)
 
∣
 
a
L
→
S
L
′
L
′
→
 
,
S
L
′
 
∣
 
ε
S\rightarrow (L)\space | \space a \\ L\rightarrow SL' \\ L'\rightarrow\space ,SL'\space | \space \varepsilon
S→(L) ∣ aL→SL′L′→ ,SL′ ∣ ε
(b) 为 (a) 的文法构造预测分析器。

F
i
r
s
t
(
S
)
=
{
 
(
 
,
 
a
 
}
F
i
r
s
t
(
L
)
=
{
 
(
 
,
 
a
 
}
F
i
r
s
t
(
L
′
)
=
{
 
′
,
′
 
,
 
ε
 
}
F
o
l
l
o
w
(
S
)
=
{
 
)
 
,
 
′
,
′
 
,
 
$
 
}
F
o
l
l
o
w
(
L
)
=
{
 
)
 
,
 
$
 
}
F
o
l
l
o
w
(
L
′
)
=
{
 
)
 
,
 
$
 
}
First(S) = \{\space(\space,\space a\space\} \\ First(L) = \{\space(\space,\space a\space\} \\ First(L') = \{\space','\space,\space\varepsilon\space\} \\\\ Follow(S) = \{\space)\space,\space','\space,\space\$\space\} \\ Follow(L) = \{\space)\space, \space\$\space\} \\ Follow(L')= \{\space)\space, \space\$\space\} \\
First(S)={ ( , a }First(L)={ ( , a }First(L′)={ ′,′ , ε }Follow(S)={ ) , ′,′ , $ }Follow(L)={ ) , $ }Follow(L′)={ ) , $ }

非终结符	输入符号
	(	)	a	,	$
S	S→(L)	S→a
L	L→SL'	L→SL'
L'	L'→ε	L→,SL'	L'→ε

T 3.10

构造下面文法的 LL(1) 分析表。
$$D\to TLT\to \text{int}|\text{real}L\to \text{id}RR\to ,\text{id}R|\epsilon$$
先确定非终结符的 $First$ 和 $Follow$ 集：

F
i
r
s
t
(
D
)
=
F
i
r
s
t
(
T
)
=
{
int
,
real
}
F
i
r
s
t
(
L
)
=
{
id
}
F
i
r
s
t
(
R
)
=
{
′
,
′
,
ε
}
F
o
l
l
o
w
(
D
)
=
F
o
l
l
o
w
(
L
)
=
{
$
}
F
o
l
l
o
w
(
T
)
=
{
id
}
F
o
l
l
o
w
(
R
)
=
{
$
}
First(D)=First(T) = \{\textbf{int}, \textbf{real}\}\\ First(L)=\{\textbf{id}\} \\ First(R)=\{',', \varepsilon\} \\ \\ Follow(D)=Follow(L)=\{\$\} \\ Follow(T)=\{\textbf{id}\} \\ Follow(R)=\{\$\}
First(D)=First(T)={int,real}First(L)={id}First(R)={′,′,ε}Follow(D)=Follow(L)={$}Follow(T)={id}Follow(R)={$}

非终结符	输入符号
	int	real	id	,	$
D	D→TL	D→TL
T	T→int	T→real
L	L→idR
R	R→,idR	R→ε

T 3.11

构造下面文法的 LL(1) 分析表。
$$S\to aBS|bAS|\epsilon A\to bAA|aB\to aBB|b$$

$$First(S)=\{a,b,\epsilon \}First(A)=First(B)=\{a,b\}Follow(S)=Follow(A)=Follow(B)=\{\$\}$$

非终结符	输入符号
	a	b	$
S	S→aBS S→ε	S→bAS S→ε	S→ε
A	A→a	A→bAA
B	B→aBB	B→b

T 3.12

下面的文法是否为 LL(1) 文法，说明理由。
$$S\to AB|PQxA\to xyB\to bcP\to dP|\epsilon Q\to aQ|\epsilon$$
上面文法不是 LL(1) 文法。

LL(1) 文法：对于产生式 $A\to \alpha |\beta$ 满足：

① $FIRST(\alpha )\cap FIRST(\beta )=\varphi$

② 若
β
⇒
∗
ε
\beta\Rightarrow ^* \varepsilon
β⇒∗ε ，那么 $FIRST(\alpha )\cap Follow(A)=\varphi$

而本题中，$FIRST(AB)=\{x\}$，$FIRST(PQx)=\{d,a,x\}$，不满足条件 ①，故，上面文法不是 LL(1) 文法。

T 3.18

为习题3.3的文法构造SLR分析表

扩展文法：

action								goto
and	or	not	true	false	(	)	$	S
0	s2	s3	s4	s5	1
1	s6	s7	acc
2	s2	s3	s4	s5	8
3	r4	r4	r4	r4
4	r5	r5	r5	r5
5	s2	s3	s4	s5	9
6	s2	s3	s4	s5	10
7	s2	s3	s4	s5	11
8	s6/r3	s7/r3	r3	r3
9	s6	s7	r12
10	s6/r1	s7/r1	r1	r1
11	s6/r2	s7/r2	r2	r2
12	r6	r6	r6	r6

T 3.29

(a) 为下面文法构造规范LR(1)分析表，画出像图3.20这样的状态转换图就可以。
$$S\to V\text{=}E|EV\to \text{*}E|\text{id}E\to V$$
详述构建
I
I_0
I0​的过程：

① 拓展文法：

S
′
→
S
    
(
)
S
→
V
=
E
    
(
1
)
S
→
E
    
(
2
)
V
→
*
E
    
(
3
)
V
→
id
    
(
4
)
E
→
V
    
(
5
)
S'\rightarrow S\space\space\space\space (0)\\ S\rightarrow V\textbf{=}E\space\space\space\space (1) \\ S\rightarrow E\space\space\space\space (2) \\ V\rightarrow \textbf{*}E\space\space\space\space (3) \\ V\rightarrow\textbf{id}\space\space\space\space (4)\\ E\rightarrow V \space\space\space\space (5)
S′→S    (0)S→V=E    (1)S→E    (2)V→*E    (3)V→id    (4)E→V    (5)
② 由于
S
′
S'
S′后面不会存在任何字符，所以其$Follow$集中只有$元素，因此产生式(0)的搜索符为$

③ 对于项目
S
′
→
⋅
 
S
 
,
 
S'\rightarrow ·\space S\space, \space
S′→⋅ S ,  $
 
\space
 ，可以将产生式(1)代入，因为项目右部$S$后面为空串，所以新项目的搜索符为$，故得到新项目$S\to \cdot V\text{=}E,$ $
 
\space
 ；类似地，将产生式(2)代入，得到新项目$S\to \cdot E,$ $

④ 对于项目$S\to \cdot V\text{=}E,$ $，可以将产生式(3)和(4)代入，因为项目右部$V$后面为$=$，所以新项目的搜索符为$=$，而不是$，故得到新项目$V\to \cdot \text{*}E,=$和$V\to \cdot \text{id},=$

⑤ 对于项目$S\to \cdot E,$$，可以将产生式(5)代入，因为项目右部$E$后面为空串，所以新项目的搜索符为$，故得到新项目$S\to \cdot V,$ $

⑥ 项目$V\to \cdot \text{*}E$和$V\to \cdot \text{id}$ 不会产生新的项目

⑦ 对于项目$S\to \cdot V,$ $，可以将产生式(3)和(4)代入，注意此时产生的新项目应该继承项目$S\to \cdot V,$ $的搜索符$，因此两个新项目为$V\to \cdot \text{*}E,$$和$V\to \cdot \text{id},$$

⑧ 不妨将第一个分量相同的项目对应的搜索符集合合并一下

生成其他状态的道理类似，只展示结果。

(b) 上述状态转换图有同心项目集吗？若有，合并同心项目集后是否会出现动作冲突？

其中
I
4
I_4
I4​和
I
11
I_{11}
I11​、
I
5
I_5
I5​和
I
12
I_{12}
I12​、
I
7
I_7
I7​和
I
13
I_{13}
I13​、
I
8
I_8
I8​和
I
10
I_{10}
I10​分别为同心项目集。

同心项目集的合并（又得到LALR自动机的过程）不会引入新的移进-归约冲突，可能会引入新的归约-归约冲突；又因为规范LR(1)自动机已经解决了移进-归约冲突的问题，所以只需要验证是否存在归约-归约冲突即可。显然合并后不存在归约-归约冲突，综上，不存在动作冲突。