北方工业大学16编译原理期末复习题答案资料.docx
《北方工业大学16编译原理期末复习题答案资料.docx》由会员分享，可在线阅读，更多相关《北方工业大学16编译原理期末复习题答案资料.docx（19页珍藏版）》请在冰点文库上搜索。
北方工业大学16编译原理期末复习题答案资料
北方工业大学
《编译原理》课程期末复习题（答案）
A卷
2016年春季学期
开课学院
考试方式：
闭卷
考试时间：
120分钟
班级姓名学号
题号
一
二
三
四
五
六
七
八
九
十
总分
得分
阅卷人
一判断题（每个小题1分，共10分）
1.程序语言主要由语法和语义两方面定义。
（）
2.自上而下分析方法会遇到的主要问题有左递归和回溯。
（）
3.已知文法G：
Ei|EAE，A+|*，其中的终结符号集包括{i，+}。
（）
4.编译程序是将高级语言程序翻译成机器语言程序。
（）
5.只含有综合属性的属性文法称为S-属性文法。
（）
6.LL
（1）文法中第一个L的含义是从左到右扫描输入串。
（）
7.在编译中进行语法检查的目的是为了发现程序中所有错误。
（）
8.一个语义子程序描述了一个文法所对应的翻译工作。
（）
9.一个句型的直接短语是唯一的。
（）
10.确定的自动机以及不确定的自动机都能正确地识别正规集。
（）
解：
1.√2.√3.×4.×5.√6.√7.×8.×9.×10.√
二、选择题（每个小题1分，共20分）
1.文法分为四种类型，即0型、1型、2型、3型。
其中3型文法是____。
A.短语文法 B.正规文法C.上下文有关文法 D.上下文无关文法
2. 不可能是目标代码。
A.汇编指令代码 B.可重定位指令代码 C.绝对指令代码 D.中间代码
3.将编译程序分成若干个“遍”是为了。
A.提高程序的执行效率B.利用有限的机器内存并提高机器的执行效率
C.使程序的结构更加清晰D.利用有限机器内存但降低了机器的执行效率
4.后缀式ab+cd+/可用表达式来表示。
A.a+b/c+dB.（a+b）/（c+d）C.a+b/（c+d）D.a+b+c/d
5.文法G：
S→xSx|y所识别的语言是。
A.xyxB.（xyx）*C.xnyxn（n≥0）D.x*yx*
6.文法G[E]：
E→E+T|T
T→T*P|P
P→（E）|i
则句型P+T+i的句柄和最左素短语为。
A.P+T和iB.P和P+TC.i和P+T+iD.P和T
7.设有文法G[E]：
E→E*T|T
T→T+i|i
句子1+2*8+6按该文法G归约，其值为。
A.42B.23C.30D.17
8.规范归约指。
A.最右推导的逆过程B.最左推导的逆过程
C.规范推导D.最左归约的逆过程
9.词法分析所依据的是。
A.语义规则B.构词规则C.语法规则D.等价变换规则
10.状态转换图（见下图）接受的集合为。
A.以0开头的二进制数组成的集合B.以0结尾的二进制数组成的集合
C.含奇数个0的二进制数组成的集合D.含偶数个0的二进制数组成的集合
11.词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，。
A.词法分析器作为子程序较好B.词法分析器并不作为一个独立的阶段
C.词法分析器分解为多个过程，由语法分析器选择使用D.词法分析器应作为独立的一遍
12.若a为终结符，则A→α·aβ为项目。
A.移进B.归约C.接受D.待约
13.中间代码生成所依据的是。
A.语法规则B.词法规则C.语义规则D.等价变换规则
14.终结符具有属性。
A.传递B.继承C.抽象D.综合
15.下推自动机识别的语言是。
A.0型语言B.1型语言C.2型语言D.3型语言
16.常用的中间代码形式不含。
A.三元式B.四元式C.逆波兰表达式D.语法树
17.算符文法是指的文法。
A.没有形如U→...VW...的产生式（U、V、WVN）
B.VT中任意两个符号之间至多存在一种算符优先关系
C.没有相同右部的产生式
D.没有形如U→ε的产生式
18.下述语句类中，____________在编译阶段通常不产生可执行代码。
A.变量说明语句B.流程控制语句C.输入输出语句D.赋值语句
19.文法所描述的语言是的集合。
A.文法的字母表中符号组成的符号串
B.文法的字母表中终结符号组成的符号串
C.由文法开始符号推导的符号串
D.由文法开始符号推导的终结符号串
20.符号串ab1b2是文法G[A]：
A→aB,B→bB|b的句子，该句子的句柄是________。
A.b1B.b2C.aD.b1b2
解：
1.B2. D3.C4.B5.C
6.B7.A8.A9.B10.D
11.A12.A13.C14. D15.C
16. D17.A18.A19.D20.B
三、已知文法G的产生式为：
ET|E+T|E-T
TF|T*F（2-1）
F（E）|i
试求：
（1）消除该文法的左递归；（5分）
（2）利用
（1）得到的文法G’（2-1），求（i+i*i）的最左推导和语法分析树。
（5分）
解：
（1）
ETE’
E’+TE’|-TE’|ε
TFT’|
T’*FT’|ε（2-1）’
F（E）|i
（2）
ETE’FT’E’（E）T’E’（E）εε（TE’）（FT’E’）（iT’E'）（iεE’）（i+TE’）（i+FT’E’）（i+iT’E’）（i+i*FT’E’）（i+i*iT’E’）（i+i*iεε）（i+i*i）
四、已知文法G的产生式：
ETE’
E’+TE’|-TE’|ε
TFT’|
T’*FT’|ε（2-1）’
F（E）|i
试求：
（1）每个非终结符的FIRST集合；（5分）
（2）每个非终结符的FOLLOW集合。
（5分）
答：
FIRST（E）={（,i}FOLLOW（E）={）,#}
FIRST（E’）={-,+,ε}FOLLOW（E’）={）,#}
FIRST（T）={（,i}FOLLOW（T）={-,+,）,#}
FIRST（T’）={*,ε}FOLLOW（T’）={-,+,）,#}
FIRST（F）={（,i}FOLLOW（F）={*,-,+,）,#}
五、已知文法G3：
Sa|^|（T）;
TT,S|S
其中：
S、T是非终结符，a、^、,、（和）是终结符，S为开始符合，试求：
（1）计算非终结符的FISTVT和LASTVT;
（2）给出终结符的算符优先关系表；
（3）给出（a,（a,a））的算符优先分析过程，指出每次规约的素短语。
（共30分，每小题10分）
解：
（1）FIRSTVT和LASTVT如下：
FIRSTVT（S）={a，∧，（}
FIRSTVT（T）={，，a，∧，（}
LASTVT（S）={a，∧，）}
LASTVT（T）={，，a，∧，）}
（2）构造优先关系表如下：
a
∧
（
）
，
#
a
>
>
>
^
>
>
>
（
<
<
<
=
<
）
>
>
>
，
<
<
<
>
>
#
<
<
<
=
（3）输入串（a,（a,a））的算符优先分析过程如下：
栈
输入字符串
动作
#
（a，（a，a））#
预备
#（
a，（a，a））#
进
#（a
（a，a））#
进
#（s
（a，a））#
归
#（t
（a，a））#
归
#（t，
（a，a））#
进
#（t，（
a，a））#
进
#（t，（a
a））#
进
#（t，（s
a））#
归
#（t，（t
a））#
归
#（t，（t,
a））#
进
#（t，（t，a
））#
进
#（t，（t，s
））#
归
#（t，（t
））#
归
#（t，（t）
）#
进
#（t，s
）#
归
#（t
）#
归
#（t）
#
进
#s
#
归
六、已知文法G的产生式为：
ET|E+T|E-T
TF|T*F（2-1）
F（E）|i
试给出表达式i1*i2+i3的规范式规约过程。
用下面的格式描述该过程。
（10分）
步骤符号栈输入串所用产生式
答：
输入串i1*i2+i3的分析步骤：
步骤符号栈输入串所用产生式
0#i1*i2+i3#预备
1#i1*i2+i3#进
2#F*i2+i3#归，用F→i
3#T*i2+i3#归，用T→F
4#T*i2+i3#进
5#T*i2+i3#进
6#T*F+i3#归，用F→i
7#T+i3#归，用F→E*F
8#E+i3#归，用F→T
9#E+i3#进
10#E+i3#进
11#E+F#归，用E→i
12#E+T#归，用T→F
13#E#归，用E→E+T
14#E#接受
七、属性文法如表5-1所示，试求表达式a+4+c的抽象语法树，并描述建立抽象语法树过程。
（10分）
表6-1属性文法
产生式语义规则
E→E1+TE.nptr:
=mknode（‘+’,E1.nptr,T.nptr）
E→E1-TE.nptr:
=mknode（‘-’,E1.nptr,T.nptr）
E→TE.nptr:
=T.nptr
T→（E）T.nptr:
=E.nptr
T→idT.nptr:
=mklear（id,id.entry）
T→numT.nptr:
=mklear（num,num.val）
答：
（1）p1:
=mkleaf（id,entrya）;
（2）p2:
=mkleaf（num,4）;
（3）p3:
=mknode（‘+’,p1,p2）;
（4）p4:
=mkleaf（id,entryc）;
（5）p5:
=mknode（‘+’,p3,p4）;
八、已知翻译模式如下：
产生式
语义规则
E→E1orE2
E→E1andE2
E→id1relopid2
{E.place:
=newtemp;
emit（E.place‘:
=’E1.place‘or’E2.place）}
{E.place:
=newtemp;
emit（E.place‘:
=’E1.place‘and’E2.place）}
{E.place:
=newtemp;
emit（‘if’id1.placerelop.opid2.place‘goto’nextstat+3）;
emit（E.place‘:
=’‘0’）;
emit（‘goto’nextstat+2）;
emit（E.place‘:
=’‘1’）}
试给出布尔表达式a107：
t2:
=1
108：
ife109：
t3:
=0
110：
goto112
111：
t3:
=1
112：
t4:
=t1andt2
113：
t5:
=t3ort4
100：
ifa101：
t1:
=0
102：
goto104
103：
t1:
=1
104：
ifc105：
t2:
=0
106：
goto108
答：
九、已知翻译规则
产生式
语义规则
S→ifEthenS1
S→ifEthenS1elseS2
E.true:
=newlabel;
E.false:
=S.next;
S1.next:
=S.next;
S.code:
=E.code||gen（E.true’:
’）||S1.code
E.true:
=newlabel;
E.false:
=newlabel;
S1.next:
=S.next;
S2.next:
=S.next;
S.code:
=E.code||
gen（E.true‘:
’）||S1.code||
gen（’goto’S.next）||
gen（E.false‘:
’）||S2.code
S→whileEdoS1
S.begin:
=newlabel;
E.true:
=newlabel;
E.false:
=S.next;
S1.next:
=S.begin;
S.code:
=gen（S.bgein‘:
’）||E.code||
gen（E.true‘:
’）||S1.code||
gen（‘goto’S.begin）
试把下面的语句翻译成三地址代码
WhileAIfA=1thenC:
=C+1else
WhileA<=DDoA:
=A+2
108：
gotoS.next113
109：
ifA<=Dgoto111
110：
gotoS.next113
111：
T2=A+2
112：
A:
=T2
113：
goto109
114：
goto100
100：
ifA101：
gotoL.false115
102：
ifB103：
gotoL.false115
104：
goto106
105：
gotoL.false109
106：
T1=C+1
107：
C:
=T1
答：
十、已知翻译规则（见第九题），试把下面的原程序翻译成三地址代码。
whileaifcx:
=y+z
else
x:
=y-z
答：
L1:
ifagotoLnext
L2:
ifcgotoL4
L3:
t1:
=y+z
x:
=t1
gotoL1（gotoL5）
L4:
t2:
=y-z
x:
=t2
L5gotoL1
Lnext:
gotoL1
十一、对以下四元式程序，试求：
（1）它的流图（5分），
（2）对其中的循环进行循环优化（10分）。
I:
=1
ReadJ,K
L:
A:
=K*I
B:
=J*I
C:
=A*B
WriteC
I:
=I+1
IfI<100gotoL
Halt
十二、已知一个三地址代码如下。
试完成
（1）给出对应的流图（5分）；
（2）对流图中的代码进行优化（10分）。
I:
=1
ReadJ,K
L1:
IfI>100gotoL2
A:
=K*I
B:
=J*I
C:
=A*B
WriteC
I:
=I+1
GotoL1
L2:
Halt
升级会员 