【编译原理】第三章部分课后题答案-电脑学习网

第三章课后习题

T 3.1

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

见下面两题。

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

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

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

$(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)))$
(c) 为 (a) 的两个句子构造最右推导。

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

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

$(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)))$
(d) 这个文法产生的语言是什么？

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

T 3.2

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

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

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

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

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

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

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

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

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

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

见上面四幅图。

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

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

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

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

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

T 3.3

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

T 3.4

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

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

证明：

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

$R\rightarrow a$ 和 $R\rightarrow b$ 产生 $a$ 和 $b$ ，而 $a$ 和 $b$ 是 ${a,b\}$ 上的符号，因此是正规式。若 $R_1$ ， $R_2$ 产生正规式 $\alpha$ 和 $\beta$
则：
$R\rightarrow R_1R_2$ 产生正规式 $\alpha\beta$

$R\rightarrow R_1|R_2$ 产生正规式 $\alpha\space|\space\beta$

$R\rightarrow R_1^*$ 产生正规式 $\alpha^*$

$R\rightarrow (R_1)$ 产生正规式 $(\alpha)$

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

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

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

$\alpha\space | \space\beta$ ，可由 $R\rightarrow R\space | \space R$ 产生

$\alpha^*$ ，可由 $R\rightarrow R^*$ 产生

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

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

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

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

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

存在二义性：

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

不存在二义性：

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

T 3.5

条件语句文法
$\rightarrow \textbf{if}\space expr \space \textbf{then} \space stmt \space | \space matched\_stmt \\ matched\_stmt \rightarrow \textbf{if} \space expr \space \textbf{then} \space matched\_stmt\space \textbf{else} \space stmst \space | \space \textbf{other}$

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

由于 $matched\_stmt$ 不能保证 $t h e n$ 和 $e l se$ 的配对，因而存在二义性。

句型 $if\space expr\space then \space if \space expr\space then \space matched\_stmt \space else \space if \space expr\space then \space matched\_stmt \space else \space stmt$ 存在两个不同的最左推导。

期望的是：

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\rightarrow (L)\space | \space a \\ L\rightarrow SL' \\ L'\rightarrow\space ,SL'\space | \space \varepsilon$
(b) 为 (a) 的文法构造预测分析器。

$\{\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\} \\$

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

T 3.10

构造下面文法的 LL(1) 分析表。
$D\rightarrow TL \\ T\rightarrow \textbf{int} \space | \space \textbf{real} \\ L\rightarrow \textbf{id} \space R \\ R\rightarrow\space ,\textbf{id}\space R \space | \space \varepsilon$
先确定非终结符的 $F i rs t$ 和 $F o ll o w$ 集：
$\{\textbf{int}, \textbf{real}\}\\ First(L)=\{\textbf{id}\} \\ First(R)=\{',', \varepsilon\} \\ \\ Follow(D)=Follow(L)=\{\$\} \\ Follow(T)=\{\textbf{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\rightarrow aBS\space |\space bAS \space | \space \varepsilon \\ A\rightarrow bAA\space | \space a \\ B\rightarrow aBB \space | \space b$

$\{a, b, \varepsilon\}\\ 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\rightarrow AB\space|\space PQx \\ A\rightarrow xy \\ B\rightarrow bc \\ P\rightarrow dP\space|\space \varepsilon\\ Q\rightarrow aQ\space | \space \varepsilon$
上面文法不是 LL(1) 文法。

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

① $FIRST(\alpha)\space∩ \space FIRST(\beta) = \phi$

② 若 $\beta\Rightarrow ^* \varepsilon$ ，那么 $FIRST(\alpha)\space∩ \space Follow(A) = \phi$

而本题中， $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\rightarrow V\textbf{=}E\space|\space E\\ V\rightarrow \textbf{*}E\space|\space\textbf{id}\\ E\rightarrow V$
详述构建 $I_0$ 的过程：

① 拓展文法：
$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^{'}$ 后面不会存在任何字符，所以其 $F o ll o w$ 集中只有$元素，因此产生式(0)的搜索符为$

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

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

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

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

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

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

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

⑥ 项目 $V\rightarrow ·\space\textbf{*}E$ 和 $V\rightarrow· \space\textbf{id}$ 不会产生新的项目

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

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

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

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

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

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

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

其中 $I_4$ 和 $I_{11}$ 、 $I_5$ 和 $I_{12}$ 、 $I_7$ 和 $I_{13}$ 、 $I_8$ 和 $I_{10}$ 分别为同心项目集。

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

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

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

T 3.1

T 3.2

T 3.3

T 3.4

T 3.5

T 3.8

T 3.10

T 3.11

T 3.12

T 3.18

T 3.29

评论(0)

提示：请文明发言取消回复

作者信息

最近更新

2024年中考修辞手法复习：夸张

2024年中考修辞手法复习：借代

2024年中考修辞手法复习：排比

2024年中考修辞手法复习：反复

2024年中考修辞手法复习：对偶

电脑学习网官网是哪一个详细介绍

卸载软件之后电脑黑屏了怎么办？

怎么刷新电脑的dns缓存

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

T 3.1

T 3.2

T 3.3

T 3.4

T 3.5

T 3.8

T 3.10

T 3.11

T 3.12

T 3.18

T 3.29

评论(0)

提示：请文明发言 取消回复

相关文章

作者信息

最近更新

提示：请文明发言取消回复