编译原理及实现课后习题答案.docx
《编译原理及实现课后习题答案.docx》由会员分享，可在线阅读，更多相关《编译原理及实现课后习题答案.docx（49页珍藏版）》请在冰点文库上搜索。
编译原理及实现课后习题答案
2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：
x0,xx,x5以及A+和A*.
x0=（aaa）0=ε|x0|=0
xx=aaaaaa|xx|=6
x5=aaaaaaaaaaaaaaa|x5|=15
A+=A1∪A2∪….∪An∪…={a,aa,aaa,aaaa,aaaaa…}
A*=A0∪A1∪A2∪….∪An∪…={ε,a,aa,aaa,aaaa,aaaaa…}
2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：
xy，xyz，（xy）3
xy=abcb|xy|=4
xyz=abcbaab|xyz|=7
（xy）3=（abcb）3=abcbabcbabcb|（xy）3|=12
2.3设有文法G[S]：
S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。
S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
S
S
S
*
S
S
+
a
a
a
2.4已知文法G[Z]：
Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文法描述的只含有四个符号的句子。
Z=>U0=>Z10=>U010=>1010
Z=>U0=>Z10=>V110=>0110
Z=>V1=>Z01=>U001=>1001
Z=>V1=>Z01=>V101=>0101
2.5已知文法G[S]：
S∷=ABA∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。
A∷=aA︱ε描述的语言:
{an|n>=0}
B∷=bBc︱bc描述的语言：
{bncn|n>=1}
L（G[S]）={anbmcm|n>=0,m>=1}
2.6已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=（E）∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。
开始符号：
E
Vt={+,-,*,/,（,）,i}
Vn={E,F,T}
E
T
E
+
F
T
E
+
i
F
T
*
T
2.7对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。
短语：
T+T*F+iT+T*F
ii
TT*F
简单短语：
iT*F
T
句柄：
T
2.8设有文法G[S]：
S∷=S*S|S+S|（S）|a，该文法是二义性文法吗？
S
S
S
*
S
+
S
a
a
a
S
S
S
+
S
*
S
a
a
a
根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。
2.9写一文法，使其语言是奇正整数集合。
A:
:
=1|3|5|7|9|NA
N:
:
=0|1|2|3|4|5|6|7|8|9
2.10给出语言{anbm|n,m≥1}的文法。
G[S]:
S:
:
=AB
A:
:
=aA|a
B:
:
=bB|b
3.1有正则文法G[Z]：
Z:
:
=Ua|Vb，U:
:
=Zb|b，V:
:
=Za|a，画出该文法的状态图，并检查句子abba是否合法。
解：
该文法的状态图如下：
S
U
V
Z
a
a
a
b
b
b
句子abba合法。
3.2状态图如图3.35所示，S为开始状态，Z为终止状态。
写出相应的正则文法以及V，Vn和Vt。
S
A
Z
a
b
a
b
图3-35状态图
解：
左线性文法G[Z]:
右线性文法G’[S]:
Z:
:
=Ab|bS:
:
=aA|b
A:
:
=Aa|aA:
:
=aA|b
V={Z,A,a,b}V={S,A,a,b}
Vn={Z,A}Vn={S,A}
Vt={a,b}Vt={a,b}
3.3构造下列正则表达式相应的NFA：
1（1|0）*|0
1（1010*|1（010）*1）*0
解：
正则表达式：
1（1|0）*|0
1、
S
Z
1（1|0）*|0
2、
S
Z
1（1|0）*
0
3、
S
A
Z
0
1
ε
0
1
4、
q0
q1
0
1
0,1
q2
正则表达式：
1（1010*|1（010）*1）*0
0
1
3
5
4
6
2
1
0
1
0
1
0
7
8
0
1
0
1
1
ε
3.4
0
1
a,b
a
a
将图3.36的NFAM确定化
图3.36状态图
解：
a
b
q0={0}
{0,1}
{1}
q1={0,1}
{0,1}
{1}
q2={1}
{0}
Φ
DFA:
q0
q1
q2
a
b
a
b
a
3.5将图3.37的DFA化简。
0
1
4
2
5
3
a
a
a
a
a
a
b
b
b
b
b
b
图3.37DFA状态图
解：
划分
a
b
{0,1}
{1}
{2,4}
{2,3,4,5}
{1,0,3,5}
{3,5,2,4}
划分
a
b
{0,1}
{1}
{2,4}
{2,4}
{0,1}
{3,5}
{3,5}
{3,5}
{2,4}
q0={0,1}q1={2,4}q2={3,5}
化简后的DFA：
q0
q1
q2
b
a
a
a
b
b
4.1对下面文法，设计递归下降分析程序。
S→aAS|（A）,A→Ab|c
解：
首先将左递归去掉，将规则A→Ab|c改成A→c{b}
非终结符号S的分析程序如下：
过程S
INPUTSYM=’a’
INPUTSYM=下一个符号
Y
N
INPUTSYM=’（’
INPUTSYM=下一个符号
Y
INPUTSYM=’）’
INPUTSYM=下一个符号
Y
N
N
出口
错误
错误
过程A
过程S
过程A
非终结符号A的分析程序如下：
过程A
INPUTSYM=’c’
INPUTSYM=下一个符号
Y
INPUTSYM=’b’
N
错误
INPUTSYM=下一个符号
Y
出口
N
4.2设有文法G[Z]：
Z∷=（A）,A∷=a|Bb,B∷=Aab
若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？
为什么？
解：
若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。
因为规则A∷=a|Bb和规则B∷=Aab构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件
（1）（书P67），且规则A:
:
=a|Bb，FIRST（a）={a}，FIRST（Bb）={a}，即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件
（2）（书P67），在分析过程中，将造成回溯。
改写文法可避免回溯：
将规则B∷=Aab代入规则A∷=a|Bb得：
A∷=a|Aabb，再转换成：
A∷=a{abb}，可避免回溯。
4.3若有文法如下，设计递归下降分析程序。
<语句>→<语句><赋值语句>|ε
<赋值语句>→ID=<表达式>
<表达式>→<项>|<表达式>＋<项>|<表达式>－<项>
<项>→<因子>|<项>*<因子>|<项>/<因子>
<因子>→ID|NUM|（<表达式>）
解：
首先，去掉左递归
<语句>→<语句><赋值语句>|ε改为：
<语句>→{<赋值语句>}
<表达式>→<项>|<表达式>+<项>|<表达式>-<项>改为：
<表达式>→<项>{（+|-）<项>}
<项>→<因子>|<项>*<因子>|<项>/<因子>改为：
<项>→<因子>{（*|/）<因子>}
则文法变为：
<语句>→{<赋值语句>}
<赋值语句>→ID=<表达式>
<表达式>→<项>{（+|-）<项>}
<项>→<因子>{（*|/）<因子>}
<因子>→ID|NUM|（<表达式>）
<语句>→{<赋值语句>}
非终结符号<语句>的分析程序如下：
FIRST（<赋值语句>）={ID}
语句
INPUTSYM=’ID’
N
Y
赋值语句
出口
<赋值语句>→ID=<表达式>
非终结符号<赋值语句>的分析程序如下：
赋值语句
INPUTSYM=’ID’
错误
N
INPUTSYM=下一个符号
INPUTSYM=’=’
错误
N
INPUTSYM=下一个符号
Y
表达式
出口
<表达式>→<项>{（+|-）<项>}
非终结符号<表达式>的分析程序如下：
表达式
INPUTSYM=’+’
N
INPUTSYM=’-’
INPUTSYM=下一个符号
Y
出口
项
N
Y
<项>→<因子>{（*|/）<因子>}
非终结符号<项>的分析程序如下：
复值语句的分析程序
项
INPUTSYM=’*’
N
INPUTSYM=’/’
INPUTSYM=下一个符号
Y
出口
因子
N
Y
项
<因子>→ID|NUM|（<表达式>）
非终结符号<因子>的分析程序如下：
因子
INPUTSYM=’ID’
Y
出口
INPUTSYM=’NUM’
INPUTSYM=下一个符号
N
Y
N
INPUTSYM=’（’
INPUTSYM=下一个符号
Y
表达式
INPUTSYM=’）’
错误
N
Y
错误
N
4.4有文法G[A]：
A:
:
=aABe|ε，B:
:
=Bb|b
（1）求每个非终结符号的FOLLOW集。
（2）该文法是LL
（1）文法吗？
（3）构造LL
（1）分析表。
解：
（1）FOLLOW（A）=First（B）∪{#}={b,#}
FOLLOW（B）={e,b}
（2）该文法中的规则B:
:
=Bb|b为左递归，因此该文法不是LL
（1）文法
（3）先消除文法的左递归（转成右递归），文法变为：
A:
:
=aABe|ε，B:
:
=bB’，B’=bB’|ε，该文法的LL
（1）分析表为：
a
e
b
#
A
POP，
PUSH（eBAa）
POP
POP
B
POP，
PUSH（B’b）
B’
POP
POP，
PUSH（B’b）
a
POP,
NEXTSYM
e
POP,
NEXTSYM
b
POP,
NEXTSYM
#
ACCEPT
更常用且简单的LL
（1）分析表：
a
e
b
#
A
A→aABe
A→ε
A→ε
B
B→bB’
B’
B’→ε
B’→bB’
4.5若有文法A→（A）A|ε
（1）为非终结符A构造FIRST集合和FOLLOW集合。
（2）说明该文法是LL
（1）的文法。
解：
（1）FIRST（A）＝｛（,ε｝
FOLLOW（A）＝｛），#｝
（2）
该文法不含左递归；
FIRST（（A）A）={（}，FIRST（ε）={ε}，FIRST（（A）A）∩FIRST（ε）=Φ，
且FOLLOW（A）＝｛），#｝，FIRST（（A）A）∩FOLLOW（A）=Φ，
因此，该文法满足LL
（1）文法的条件，是LL
（1）文法。
4.6利用分析表4-1，识别以下算术表达式，请写出分析过程。
（1）i+i*i+i
（2）i*（i+i+i）
解：
（1）i+i*i+i
步骤
分析栈
余留输入串
分析表元素
所用产生式
1
#E
i+i*i+i#
POP,PUSH（E’T）
E→TE’
2
#E’T
i+i*i+i#
POP,PUSH（T’F）
T→FT’
3
#E’T’F
i+i*i+i#
POP,PUSH（i）
F→i
4
#E’T’i
i+i*i+i#
POP,NEXTSYM
5
#E’T’
+i*i+i#
POP
T’→ε
6
#E’
+i*i+i#
POP,PUSH（E’T+）
E’→+TE’
7
#E’T+
+i*i+i#
POP,NEXTSYM
8
#E’T
i*i+i#
POP,PUSH（T’F）
T→FT’
9
#E’T’F
i*i+i#
POP,PUSH（i）
F→i
10
#E’T’i
i*i+i#
POP,NEXTSYM
11
#E’T’
*i+i#
POP,PUSH（T’F*）
T’→*FT’
12
#E’T’F*
*i+i#
POP,NEXTSYM
13
#E’T’F
i+i#
POP,PUSH（i）
F→i
14
#E’T’i
i+i#
POP,NEXTSYM
15
#E’T’
+i#
POP
T’→ε
16
#E’
+i#
POP,PUSH（E’T+）
E’→+TE’
17
#E’T+
+i#
POP,NEXTSYM
18
#E’T
i#
POP,PUSH（T’F）
T→FT’
19
#E’T’F
i#
POP,PUSH（i）
F→i
20
#E’T’i
i#
POP,NEXTSYM
21
#E’T’
#
POP
T’→ε
22
#E’
#
POP
E’→ε
23
#
#
ACCEPT
（2）i*（i+i+i）
步骤
分析栈
余留输入串
分析表元素
所用产生式
1
#E
i*（i+i+i）#
POP,PUSH（E’T）
E→TE’
2
#E’T
i*（i+i+i）#
POP,PUSH（T’F）
T→FT’
3
#E’T’F
i*（i+i+i）#
POP,PUSH（i）
F→i
4
#E’T’i
i*（i+i+i）#
POP,NEXTSYM
5
#E’T’
*（i+i+i）#
POP,PUSH（T’F*）
T’→*FT’
6
#E’T’F*
*（i+i+i）#
POP,NEXTSYM
7
#E’T’F
（i+i+i）#
POP,PUSH（）E（）
F→（E）
8
#E’T’）E（
（i+i+i）#
POP,NEXTSYM
9
#E’T’）E
i+i+i）#
POP,PUSH（E’T）
E→TE’
10
#E’T’）E’T
i+i+i）#
POP,PUSH（T’F）
T→FT’
11
#E’T’）E’T’F
i+i+i）#
POP,PUSH（i）
F→i
12
#E’T’）E’T’i
i+i+i）#
POP,NEXTSYM
13
#E’T’）E’T’
+i+i）#
POP
T’→ε
14
#E’T’）E’
+i+i）#
POP,PUSH（E’T+）
E’→+TE’
15
#E’T’）E’T+
+i+i）#
POP,NEXTSYM
16
#E’T’）E’T
i+i）#
POP,PUSH（T’F）
T→FT’
17
#E’T’）E’T’F
i+i）#
POP,PUSH（i）
F→i
18
#E’T’）E’T’i
i+i）#
POP,NEXTSYM
19
#E’T’）E’T’
+i）#
POP
T’→ε
20
#E’T’）E’
+i）#
POP,PUSH（E’T+）
E’→+TE’
21
#E’T’）E’T+
+i）#
POP,NEXTSYM
22
#E’T’）E’T
i）#
POP,PUSH（T’F）
T→FT’
23
#E’T’）E’T’F
i）#
POP,PUSH（i）
F→i
24
#E’T’）E’T’i
i）#
POP,NEXTSYM
25
#E’T’）E’T’
）#
POP
T’→ε
26
#E’T’）E’
）#
POP
E’→ε
27
#E’T’）
）#
POP,NEXTSYM
28
#E’T’
#
POP
T’→ε
29
#E’
#
POP
E’→ε
30
#
#
ACCEPT
4.7考虑下面简化了的C声明文法：
<声明语句>→<类型><变量表>；
<类型>→int|float|char
<变量表>→ID,<变量表>|ID
（1）在该文法中提取左因子。
（2）为所得的文法的非终结符构造FIRST集合和FOLLOW集合。
（3）说明所得的文法是LL
（1）文法。
（4）为所得的文法构造LL
（1）分析表。
（5）假设有输入串为“charx，y，z；”，写出相对应的LL
（1）分析过程。
解：
（1）规则<变量表>→ID,<变量表>|ID提取公因子如下：
<变量表>→ID（,<变量表>|ε）
增加新的非终结符<变量表1>，规则变为：
<变量表>→ID<变量表1>
<变量表1>→，<变量表>|ε
C声明文法改变为：
<声明语句>→<类型><变量表>；
<类型>→int|float|char
<变量表>→ID<变量表1>
<变量表1>→，<变量表>|ε
（2）FIRST（<声明语句>）＝FIRST（<类型>）＝｛int，float，char｝
FIRST（<变量表>）＝｛ID｝
FIRST（<变量表1>）＝｛，，ε｝
FOLLOW（<声明语句>）＝｛#｝
FOLLOW（<类型>）＝FIRST（<变量表>）＝｛ID｝
FOLLOW（<变量表>）＝FOLLOW（<变量表1>）＝｛；｝
（3）所得文法无左递归，且
FIRST（int）∩FIRST（float）∩FIRST（char）＝Φ
FIRST（，<变量表>）∩FIRST（ε）＝Φ
FIRST（，<变量表>）∩FOLLOW（<变量表1>）＝Φ
因此，所得文法为LL
（1）文法。
（4）所得的文法构造LL
（1）分析表如下所示：
；
int
float
char
ID
，
#
<声明语句>
POP，
PUSH（；<变量表><类型>）
POP，
PUSH（；<变量表><类型>）
POP，
PUSH（；<变量表><类型>）
<类型>
POP，
PUSH（int）
POP，
PUSH（float）
POP，
PUSH（char）
<变量表>
POP，
PUSH（<变量表1>ID）
<变量表1>
POP
POP，
PUSH（<变量表>，）
；
POP,
NEXTSYM
int
POP,
NEXTSYM
float
POP,
NEXTSYM
char
POP,
NEXTSYM
ID
POP,
NEXTSYM
，
POP,
NEXTSYM
#
ACCEPT
更常用且简单的LL
（1）分析表：
；
int
float
char
ID
，
#
<声明语句>
<声明语句>→<类型><变量表>；
<声明语句>→<类型><变量表>；
<声明语句>→<类型><变量表>；
<类型>
<类型>→int
<类型>→float
<类型>→char
<变量表>
<变量表>→ID<变量表1>
<变量表1>
<变量表1>→ε
<变量表1>→,<变量表>
（5）输入串“charx，y，z；”相对应的LL
（1）分析过程如下：
步骤
分析栈
余留输入串
分析表元素
所用产生式
1
#<声明语句>
charx，y，z；#
POP，
PUSH（；<变量表><类型>）
<声明语句>→<类型><变量表>；
2
#；<变量表><类型>
charx，y，z；#
POP，
PUSH（char）
<类型>→char
3
#；<变量表>char
charx，y，z；#
POP,
NEXTSYM
4
#；<变量表>
x，y，z；#
POP，
PUSH（<变量表1>ID）
<变量表>→ID<变量表1>
5
#；<变量表1>x
x，y，z；#
POP,
NEXTSYM
6
#；<变量表1>
，y，z；#
POP，
PUSH（<变量表>，）
<变量表1>→，<变量表>
7
#；<变量表>，
，y，z；#
POP,
NEXTSYM
8
#；<变量表>
y，z；#
POP，
PUSH（<变量表1>ID）
<变量表>→ID<变量表1>
9
#；<变量表1>y
y，z；#
POP,
NEXTSYM
10
#；<变量表1>
，z；#
POP，
PUSH（<变量表>，）
<变量表1>→，<变量表>
11
#；<变量表>，
，z；#
POP,
NEXTSYM
12
#；<变量表>
z；#
POP，
PUSH（<变量表1>ID）
<变量表>→ID<变量表1>
13
#；<变量表1>z
z；#
POP,
NEXTSYM
14
#；<变量表1>
；#
POP
<变量表1>→ε
15
#；
；#
POP,
NEXTSYM
16
#
#
ACCEPT
5.1考虑以下的文法：
S→S;T|T
T→a
（1）为这个文法构造LR（0）的项目集规范族。
（2）这个文法是不是LR（0）文法？
如果是，则构造LR（0）分析表。
（3）对输入串“a;a”进行分析。
解：
（1）拓广文法G[S’]：
0：
S’→S
1：
S→S;T
2：
S→T
3：
T→a
构造LR（0）项目集规范族
状态
项目集
转换函数
0
S’→·S
S→·S;T
S→·T
T→·a
GO[0，S]＝1
GO[0，S]＝1
GO[0，T]＝2
GO[0，a]＝3
1
S’→S·
S→S·;T
ACCEPT
GO[1，;]＝4
2
S→T·
R2
3
T→a·
R3
4
S→S;·T
T→·a
GO[4，T]＝5
GO[4，a]＝3
5
S→S;T·
R1
（2）该文法不存在“归约－归约”和“归约－移进”冲突，因此是LR（0）文法。
升级会员 