最新编译原理作业参考答案文档格式.docx
《最新编译原理作业参考答案文档格式.docx》由会员分享，可在线阅读，更多相关《最新编译原理作业参考答案文档格式.docx（32页珍藏版）》请在冰点文库上搜索。
目前基本分为：
诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。
第2章高级语言及其语法描述
1（P36）令文法为
N→D∣ND
D→0∣1∣2∣⋯∣9
（1）文法描述的语言L（G）是什么？
（2）给出句子34，568的最左推导和最右推导。
答：
（1）
L（G）={α∣α为可带前导0的正整数}
或L（G）={（0∣1∣2∣⋯∣9）+}
或L（G）={α∣α为数字串}
（2）
最左推导：
N⇒ND⇒DD⇒3D⇒34
N⇒ND⇒NDD⇒DDD⇒5DD⇒56D⇒568
最右推导：
N⇒ND⇒N4⇒D4⇒34
N⇒ND⇒N8⇒ND8⇒N68⇒D68⇒568
2*．写出一个文法，使其语言是奇数集，且每个奇数是不以0开头。
S→CAB|B（考虑了正负号）
A→1|2|3|4|5|6|7|8|9|AA|A0|ε
B→1|3|5|7|9
C→+|-|ε
或：
（未考虑正负号）
S→B|AB
B→1|3|5|7|9
A→AD|N
N→2|4|6|8|B
D→0|N
S→C|ABC
C→1|3|5|7|9
A→1|2|3|4|5|6|7|8|9
B→BA|B0|ε
2.（P36,8）令文法为
E→T∣E+T∣E-T
T→F∣T*F∣T/F
F→（E）∣i
（1）给出该文法的VN、VT和S。
（2）给出i+i*i，i*（i+i）的最左推导和最右推导。
（3）给出i+i+i，i+i*i的语法树。
VN={E,T,F}
VT={+,-,*,/,（,）,i}
S=E
最左推导E⇒E+T⇒T+T⇒F+T⇒i+T⇒i+T*F⇒i+F*F⇒i+i*F⇒i+i*i
E⇒T⇒T*F⇒F*F⇒i*F⇒i*（E）⇒i*（E+T）⇒i*（T+T）⇒i*（F+T）⇒i*（i+T）
⇒i*（i+F）⇒i*（i+i）
最右推导E⇒E+T⇒E+T*F⇒E+T*i⇒E+F*i⇒E+i*i⇒T+i*i⇒F+i*i⇒i+i*i
E⇒T⇒T*F⇒T*（E）⇒T*（E+T）⇒T*（E+F）⇒T*（E+i）⇒T*（T+i）⇒T*（F+i）
⇒T*（i+i）⇒F*（i+i）⇒i*（i+i）
构造语法树
E最左推导构造语法树
E+T
E+Ti
Ti
i
3.（P36,9）证明下面的文法是二义的：
S→iSeS|iS∣i
对于句子iiiei有两棵不同的语法树。
因此该文法是二义的。
S⇒iSeS⇒iiSeS⇒iiieS⇒iiiei
S⇒iS⇒iiSeS⇒iiieS⇒iiiei
第3章词法分析
1．设M=（{x，y}，{a，b}，δ，x，{y}）为一个非确定有限自动机NFAM，其中δ定义如下：
δ（x，a）={x，y}
δ（x，b）={y}
δ（y，a）=φ
δ（y，b）={x，y}
试构造其相应的最小化的确定有限自动机DFAM’。
由δ定义可知δ（x，a），δ（y，b）均为多值函数，所以是一个非确定有限自动机。
（1）根据δ函数值，先构造NFAM
（2）确定化：
①构造DFAM’的转换矩阵:
I
Ia
Ib
{x}①
{x，y}②
{y}③
{y}③
②确定DFAM’的初始状态和终态：
（a）转换矩阵中I列的第一个状态①为DFAM’的初始状态结点。
（b）含有y状态的子集均为DFAM’的终态结点（②、③为终态结点）。
③根据DFAM’的转换矩阵画出对应的状态转换图：
（3）最小化：
①首先将其划分成终态集{2，3}和非终态集{1}
②{2，3}a=｛2｝⊂{2，3}，{2，3}b=｛2｝⊂{2，3}
因此{2，3}已是不可再区分的,所以该DFAM’已是最小化的。
2.（P64，7
（1））构造正规式1（0∣1）*101相应的DFAM。
（1）构造NFAM。
1（0∣1）*101
1（0∣1）*101
1εε101
0∣1
0
1
（2）构造转换矩阵
I0
I1
{X}①
{1,2,3}②
{2,3}③
{2,3,4}④
{2,3}③
{2,3,4}④
{2,3,5}⑤
{2,3,4,Y}⑥
{2,3,4,Y}⑥
（3）由转换矩阵构造DFAM
3．（P64，12（a））将下图所示的NFAM转换为等价的DFAM’，并将该DFA’最小化。
该有限自动机状态0输入同一字符a时到达两个不同的结点,所以是NFA。
（1）构造转换矩阵
{0}①
{0，1}②
{1}③
（2）由转换矩阵构造DFAM
a
b
a
（3）将DFAM最小化
将DFAM的状态划分为非终态集{3}和终态集{1，2}
对每一个子集及每一个a∈∑进行考察；
{1，2}a={2}⊂{1，2}
{1，2}b={3}⊆{3}
因此{1，2}是不可区分的，所以最终状态为：
{1，2}，{3}
构造最小化的DFAM：
a
b
4.（P64，12（b））将下图所示的NFAM转换为等价的DFAM’，并进行最小化。
从图上可知该图已经是DFAM，先只需将其最小化。
首先划分为两个集合：
{0,1}和{2,3,4,5}
{2,3,4,5}a={1,3,0,5}，划分为：
{2,4}和｛3,5｝
{2,4}a={1,0}，{2,4}b={3,5}，无需划分
{3,5}a={3,5}，{3,5}b={2,4}，无需划分
{0,1}a={1}，{0,1}b={2,4}，无需划分
因此，最终的划分为：
{0,1}、{2,4}和｛3,5｝，化简后的结果：
5．（P65，14）构造一个DFAM，它接受∑={0，1}上所有满足如下条件的字符串：
每个1都有0直接跟在右边。
（1）根据题意，得到正规式：
（0|10）*
（2）构造对应的NFAM：
（3）将NFAM确定化为DFAM。
相应的DFAM的状态转换矩阵如下：
{X,1,Y}①
{1;
Y}②
{2}③
{1,Y}②
Y}②
{2}③
DFAM转换图：
（4）将DFAM最小化：
①将DFAM的状态划分为非终态集{3}和终态集{1,2}
②对每一个子集进行考察；
{1,2}0={2}⊆{1,2}
{1,2}1={3，3}⊆{3}
因此{0,1}是不可划分的。
因此最终划分结果为：
{1,2}和{3}
最小化后的DFAM：
第4章语法分析-自上而下
1.（P81，1）考虑下面文法G
S→a∣^∣（T）
T→T,S∣S
（1）消除文法的左递归。
（2）经改写后的文法是否是LL
（1）的？
给出它的预测分析表。
（1）消除左递归：
S→a∣^∣（T）
T→ST’
T’→,ST’|ε
（2）证明改写后的文法是否是LL
（1）的。
FIRST（S）={a,^,（}FOLLOW（S）={，,）,#}
FIRST（T）={a,^,（}FOLLOW（T）={）}
FIRST（T’）={，,ε}FOLLOW（T’）={）}
证明S→a∣^∣（T）各侯选式的FIRST是否两两相交。
FIRST（a）⋂FIRST（^）=φ
FIRST（a）⋂FIRST（（）=φ
FIRST（^）⋂FIRST（（）=φ
证明T’→，ST’∣ε的FIRST（T’）和FOLLOW（T’）是否相交。
FIRST（T’）⋂FOLLOW（T’）={，，ε}⋂{）}=φ
∴该文法是LL
（1）的。
所以，改造后的文法是LL
（1）文法
③预测分析表：
a
^
（
）
，
#
S
S→a
S→^
S→（T）
T
T→ST’
T→ST’
T’
T’→ε
T’→,ST’
2.利用P76表4.1的LL
（1）分析表写出表达式（i+i）*i的预测分析过程。
步骤符号栈输入串所用的产生式
0#E（i+i）*i#
1#E’T（i+i）*i#E→TE’
2#E’T’F（i+i）*i#T→FT’
3#E’T’）E（（i+i）*i#F→（E）
4#E’T’）Ei+i）*i#
5#E’T’）E`Ti+i）*i#E→TE’
6#E’T’）E’T’Fi+i）*i#T→FT’
7#E’T’）E’T’ii+i）*i#F→i
8#E’T’）E’T’+i）*i#
9#E’T’）E’+i）*i#T’→ε
10#E’T’）E’T++i）*i#E’→+TE’
11#E’T’）E’Ti）*i#
12#E’T’）E’T’Fi）*i#T→FT’
13#E’T’）E’T’ii）*i#F→i
14#E’T’）E’T’）*i#
15#E’T’）E’）*i#T’→ε
16#E’T’））*i#E’→ε
18#E’T’*i#
19#E’T’F**i#T’→*FT’
20#E’T’Fi#
21#E’T’ii#F→i
22#E’T’#
23#E’#T’→ε
24##E’→ε
3.（P81，2）对下面的文法G
E→TE’
E’→+E∣ε
T→FT’
T’→T∣ε
F→PF’
F’→*F’∣ε
P→（E）∣^∣a∣b
（1）计算这个文法的每个非终结符的FIRST和FOLLOW。
（2）证明这个文法是LL
（1）的。
（3）构造它的预测分析表。
（1）计算每个非终结符的FIRST和FOLLOW。
FIRST（E）={（,a,b,^}FIRST（E’）={+,ε}
FIRST（T）={（,a,b,^}FIRST（T’）={（,a,b,^,ε}
FIRST（F）={（,a,b,^}FIRST（F’）={*,ε}
FIRST（P）={（,a,b,^}
FOLLOW（E）={）,#}FOLLOW（E’）={）,#}
FOLLOW（T）={+,）,#}FOLLOW（T’）={+,）,#}
FOLLOW（F）={+,（,a,b,^,）,#}
FOLLOW（F’）={+,（,a,b,^,）,#}
FOLLOW（P）={*,+,（,a,b,^,）,#}
（求解过程：
因为E`→+E∣ε，所以FIRST（E`）={+，ε}
因为F`→*F`∣ε，所以FIRST（F`）={*，ε}
因为P→（E）∣^∣a∣b，所以FIRST（P）={（，^，a，b}
因为F→PF`，所以FIRST（F）=FIRST（P）
因为T→FT`，所以FIRST（T）={FIRST（F）
因为E→TE`，所以FIRST（E）=FIRST（T）
因为T`→T∣ε，所以FIRST（T`）=FIRST（T）⋃{ε}
={（，^，a，b，ε}
求非终结符的FOLLOW：
因为E→TE`的E是文法的开始符号，FOLLOW（E）={#}，又因为P→（E），所以FOLLOW（E）={#}⋃FIRST（））\{ε}={#，）}
因为E→TE`，所以FOLLOW（E`）=FOLLOW（E）
因为E→TE`，并且E`≠ε，所以FOLLOW（T）=FIRST（E`）\{ε},又因为E`→ε,所以FOLLOW（T）={+}⋃FOLLOW（E）={+}⋃{#,}}={+，#,）}.
因为T→FT`，所以FOLLOW（T`）=FOLLOW（T）={+，#,）}.
因为T→FT`，并且T`≠ε，所以FOLLOW（F）=FIRST（T`）\{ε},又因为T`→ε,所以FOLLOW（F）={（，^，a，b}⋃FOLLOW（T）={（，^，a，b}⋃{+，#,）}
={（，^，a，b,+，#,）}
因为F→PF`，所以FOLLOW（F`）=FOLLOW（F）={（，^，a，b,+，#,）}.
因为F→PF`，并且F`≠ε，所以FOLLOW（P）=FIRST（F`）\{ε},又因为F`→ε,所以FOLLOW（P）={*}⋃FOLLOW（F）={*}⋃{（，^，a，b,+,）,#}
={*,（，^，a，b,+，）,#}
（2）证明这个文法是LL
（1）的
该文法没有左递归，只需考察：
E’→+E∣ε
F’→*F’∣ε
由于：
E’→+E∣ε：
FIRST（E’）={+,ε}∩FOLLOW（E’）={#,}}=Ф
T’→T∣ε：
FIRST（T’）={（,a,b,^,ε}∩FOLLOW（T’）={+,）,#}=Ф
F’→*F’∣ε：
FIRST（F’）={*,ε}∩FOLLOW（F’）={+,（,a,b,^,）,#}=Ф
P→（E）∣^∣a∣b：
候选式终结符首字符集两两不相交
所以该文法为LL
（1）文法。
（3）LL
（1）分析表
+
*
b
E
E→TE’
E’
E’→+E
E’→ε
T
T→FT’
T’→T
F
F→PF’
F’
F’→ε
F’→*F’
P
P→（E）
P→a
P→b
P→^
第5章语法分析-自上而下分析
1．（P133，1）令文法G1为:
E→E+T|T
T→T*F|F
F→（E）|i
证明E+T*F是它的一个句型，指出这个句型的所有短语，直接短语和句柄。
因为有：
E⇒E+T⇒E+T*F，所以E+T*F是文法的一个句型。
短语：
E+T*F,T*F直接短语：
T*F句柄：
T*F
2.（P133，3）考虑文法G2
S→a∣∧|（T）
T→T；
S∣S
（1）计算文法G2每个非终结符的FIRSTVT和LASTVT。
（2）构造文法G2的优先关系表，该文法是算符优先文法吗？
（3）给出输入串（a；
（a；
a））的算符优先分析过程。
解：
（1）FIRSTVT和LASTVT
FIRSTVT（S）={a,∧,（}
FIRSTVT（T）={；
，a,∧,（}
LASTVT（S）={a,∧,）}
LASTVG（T）={；
，a,∧,）}
（2）优先关系表
∧
；
是算符优先分析文法，因为优先关系表中没有冲突的关系。
（3）（a,（a,a））的分析过程
步骤
栈
余留符号串
栈顶关系
下一步动作
我们认为：
创业是一个整合的过程，它需要合作、互助。
大学生创业“独木难支”。
在知识经济时代，事业的成功来自于合作，团队精神。
创业更能培养了我们的团队精神。
我们一个集体的智慧、力量一定能够展示我们当代大学生的耐心.勇气和坚强的毅力。
能够努力克服自身的弱点，取得创业的成功。
§
8-2购物环境与消费行为2004年3月20日#
a））#
大学生对手工艺制作兴趣的调研#<
.（
（进栈
1
（二）创业弱势分析#（
A；
a））#
据调查统计，有近94%的人喜欢亲戚朋友送给自己一件手工艺品。
无论是送人，个人兴趣，装饰还是想学手艺，DIY手工制作都能满足你的需求。
下表反映了同学们购买手工艺制品的目的。
如图（1-4）（<
.a
（2）缺乏经营经验a进栈
2
关于DIY手工艺制品的消费调查#（a
是□否□a.>
10、如果学校开设一家DIY手工艺制品店，你希望＿＿＿＿＿用S→a归约
3
#（S
（<
.；
此次调查以女生为主，男生只占很少比例，调查发现58％的学生月生活费基本在400元左右，其具体分布如（图1-1）;
进栈
4
#（S;
;
<
5
a；
a进栈
6
（a
a.>
用S→a归约
7
（S
8
（S;
9
））#
10
S
.>
用T→T;
S归约
11
（T
）进栈
12
（T）
）#
）.>
用S→（T）归约
13
14
#（T
15
#（T）
#
16
#S
#
#
结束
3.（P134，5）考虑文法
S→AS∣b
A→SA∣a
（1）构造这个文法的LR（0）项目规范族及识别活前缀的DFA。
（2）这个文法是SLR
（1）的吗？
若是，构造出它的SLR分析表。
构造拓广文法：
（0）S’→S
（1）S→AS
（2）S→b（3）A→SA（4）A→a
（2）证明文法是否是SLR
（1）文法？
为了验证这个文法是否是SLR
（1）文法，必须对LR（0）项目集规范族的各个项目集I，验证其是否存在“移进－归约”、“归约－归约”冲突。
该项目规范族中的I1,I5,I7存在“移进－归约”，只需证明存在集合的⎨a,b⎬，FOLLOW（S’），FOLLOW（S），FOLLOW（A）两两不相交。
对此求出FOLLOW（S’）＝⎨＃⎬，FOLLOW（S）＝⎨#,a,b⎬，FOLLOW（A）＝⎨a,b⎬。
验证如下：
对状态I1有
FOLLOW（S’）=⎨＃⎬；
A→·
S→·
b。
因此FOLLOW（S’）⋂⎨a,b⎬=⎨＃⎬⋂⎨a,b⎬=φ，所以不存在“移进－归约”冲突。
对状态I5有
FOLLOW（A）=⎨a,b⎬；
因此FOLLOW（A）⋂⎨a,b⎬=⎨a,b⎬⋂⎨a,b⎬≠φ，所以存在“移进－归约”冲突。
对状
升级会员 