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

第三章课后习题

T 3.1

考虑文法
【编译原理】第三章部分课后题答案
(a) 建立句子和的分析树。

见下面两题。

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

【编译原理】第三章部分课后题答案最左推导的分析树（包括推导过程中的分析树）：

【编译原理】第三章部分课后题答案最左推导的分析树：

(c) 为 (a) 的两个句子构造最右推导。

【编译原理】第三章部分课后题答案最右推导的分析树（包括推导过程中的分析树）：

【编译原理】第三章部分课后题答案最右推导：

【编译原理】第三章部分课后题答案
(d) 这个文法产生的语言是什么？

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

T 3.2

考虑文法
【编译原理】第三章部分课后题答案
(a) 为句子构造两个不同的最左推导，以此说明该文法是二义的。

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

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

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

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

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

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

见上面四幅图。

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

通过最左推导的方式和产生式【编译原理】第三章部分课后题答案可以得到前缀为若干个的任意长度的串；

题目给的产生式为【编译原理】第三章部分课后题答案、和，由可以推导出空串，可以说明可以产生和，因此由任意长度的前缀和前缀的子串可以构成和任意交错的串；

又因为每个产生式中【编译原理】第三章部分课后题答案和的个数都相同，故产生和数目相等且任意长度的串。

T 3.3

下面的二义文法描述命题演算公式，为它写一个等价的非二义性文法。
【编译原理】第三章部分课后题答案
通过引入非终结符消除二义性：

T 3.4

文法
【编译原理】第三章部分课后题答案
产生字母表上所有不含的正规式。注意，第一条竖线加了引号，它是正规式的或运算符号，而不是文法产生式右部各选择之间的分隔符，另外在这里是一个普通的终结符。该文法是二义的。

(a) 证明该文法产生字母表上的所有正规式。

证明：

(1) 该文法产生的串是字母表【编译原理】第三章部分课后题答案上的正规式：

【编译原理】第三章部分课后题答案和产生和，而和是上的符号，因此是正规式。若，产生正规式和
则：
产生正规式

【编译原理】第三章部分课后题答案产生正规式

(2) 字母表【编译原理】第三章部分课后题答案上的所有正规式都可由此文法产生：

字母表【编译原理】第三章部分课后题答案上的任一正规式（其中，为正规式）必为以下形式之一：

【编译原理】第三章部分课后题答案，可由产生

因而，该文法产生字母表【编译原理】第三章部分课后题答案上的所有正规式

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

该文法没有体现运算符【编译原理】第三章部分课后题答案、、和连接的优先级，因而是二义的。例如：

通过引入非终结符消除二义性：

消除二义性后：

(c) 按上面两个文法构造句子的分析树。

存在二义性：

不存在二义性：

T 3.5

条件语句文法
【编译原理】第三章部分课后题答案

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

由于【编译原理】第三章部分课后题答案不能保证和的配对，因而存在二义性。

句型【编译原理】第三章部分课后题答案存在两个不同的最左推导。

期望的是：

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 文法的左递归。
【编译原理】第三章部分课后题答案
(b) 为 (a) 的文法构造预测分析器。

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

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

T 3.10

构造下面文法的 LL(1) 分析表。
【编译原理】第三章部分课后题答案
先确定非终结符的和集：

非终结符	输入符号
非终结符	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) 分析表。
【编译原理】第三章部分课后题答案

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

非终结符	输入符号
非终结符	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) 文法，说明理由。
【编译原理】第三章部分课后题答案
上面文法不是 LL(1) 文法。

LL(1) 文法：对于产生式【编译原理】第三章部分课后题答案满足：

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

② 若【编译原理】第三章部分课后题答案，那么

而本题中，【编译原理】第三章部分课后题答案，，不满足条件 ①，故，上面文法不是 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