编译原理考试试题及答案.docx
《编译原理考试试题及答案.docx》由会员分享，可在线阅读，更多相关《编译原理考试试题及答案.docx（49页珍藏版）》请在冰点文库上搜索。
编译原理考试试题及答案
编译原理?
考试试题及答案〔附录〕
一、判断题：
1.一个上下文无关文法的开始符，可以是终结符或非终结符。
（X）
2.一个句型的直接短语是唯一的。
（X）
3.已经证明文法的二义性是可断定的。
〔X〕
4.每个根本块可用一个DAG表示。
〔√〕
5.每个过程的活动记录的体积在编译时可静态确定。
〔√〕
6.2型文法一定是3型文法。
〔x〕
7.一个句型一定句子。
（X）
8.算符优先分析法每次都是对句柄进展归约。
（应是最左素短语）（X）
9.采用三元式实现三地址代码时，不利于对中间代码进展优化。
〔√〕
10.编译过程中，语法分析器的任务是分析单词是怎样构成的。
（x）
11.一个优先表一定存在相应的优先函数。
（x）
12.目的代码生成时，应考虑如何充分利用计算机的存放器的问题。
（）
13.递归下降分析法是一种自下而上分析法。
（）
14.并不是每个文法都能改写成LL
（1）文法。
（）
15.每个根本块只有一个入口和一个出口。
（）
16.一个LL
（1）文法一定是无二义的。
（）
17.逆波兰法表示的表达试亦称前缀式。
（）
18.目的代码生成时，应考虑如何充分利用计算机的存放器的问题。
（）
19.正规文法产生的语言都可以用上下文无关文法来描绘。
（）
20.一个优先表一定存在相应的优先函数。
（）
21.3型文法一定是2型文法。
（）
22.假设一个文法存在某个句子对应两棵不同的语法树，那么文法是二义性的。
（）
二、填空题：
1.（最右推导）称为标准推导。
2.编译过程可分为〔词法分析〕，〔语法分析〕，〔语义分析和中间代码生成〕，〔代码优化〕和〔目的代码生成〕五个阶段。
3.假设一个文法存在某个句子对应两棵不同的语法树，那么称这个文法是〔〕。
4.从功能上说，程序语言的语句大体可分为〔〕语句和〔〕语句两大类。
5.语法分析器的输入是〔〕，其输出是〔〕。
6.扫描器的任务是从〔〕中识别出一个个〔〕。
7.符号表中的信息栏中登记了每个名字的有关的性质，如〔〕等等。
8.一个过程相应的DISPLAY表的内容为〔〕。
9.一个句型的最左直接短语称为句型的〔〕。
10.常用的两种动态存贮分配方法是〔〕动态分配和〔〕动态分配。
11.一个名字的属性包括（）和（）。
12.常用的参数传递方式有〔〕，〔〕和〔〕。
13.根据优化所涉及的程序范围，可将优化分成为〔〕，〔〕和〔〕三个级别。
14.语法分析的方法大致可分为两类，一类是〔〕分析法，另一类是〔〕分析法。
15.预测分析程序是使用一张〔〕和一个〔〕进展结合控制的。
16.常用的参数传递方式有〔〕，〔〕和〔〕。
17.一张转换图只包含有限个状态,其中有一个被认为是〔〕态;而且实际上至少要有一个〔〕态。
18.根据优化所涉及的程序范围，可将优化分成为〔〕，〔〕和〔〕三个级别。
19.语法分析是根据语言的〔〕规那么进展。
中间代码产生是根据语言的〔〕规那么进展的。
20.一个句型的最左直接短语称为句型的〔〕。
21.一个文法G，假设它的预测分析表M不含多重定义，那么该文法是〔〕文法。
22.对于数据空间的存贮分配，FORTRAN采用（）策略，PASCAL采用（）策略。
23.假设一个文法存在某个句子对应两棵不同的语法树，那么称这个文法是（）。
24.最右推导亦称为〔〕，由此得到的句型称为〔〕句型。
25.语法分析的方法大致可分为两类，一类是〔〕分析法，另一类是〔〕分析法。
26.对于文法G，仅含终结符号的句型称为（）。
27.所谓自上而下分析法是指〔〕。
28.语法分析器的输入是〔〕，其输出是〔〕。
29.局限于根本块范围的优化称〔〕。
30.预测分析程序是使用一张〔〕和一个〔〕进展结合控制的。
31.2型文法又称为〔〕文法；3型文法又称为〔〕文法。
32.每条指令的执行代价定义为〔〕。
33.算符优先分析法每次都是对〔〕进展归约。
三、名词解释题：
1.局部优化
2.二义性文法
3.DISPLAY表
4.词法分析器
5.最左推导
6.语法
7.文法
8.根本块
9.语法制导翻译
10.短语
11.待用信息
12.标准句型
13.扫描器
14.超前搜索
15.句柄
16.语法制导翻译
17.标准句型
18.素短语
19.语法
20.待用信息
21.语义
四、简答题：
1.写一个文法G,使其语言为不以0开头的偶数集。
2.文法G（S）及相应翻译方案
S→aAb{print“1〞}
S→a{print“2〞}
A→AS{print“3〞}
A→c{print“4〞}
输入acab,输出是什么？
3.文法G（S）
S→bAa
A→（B|a
B→Aa）
写出句子b（aa）b的标准归约过程。
4.考虑下面的程序：
…
procedure p（x,y,z）；
begin
y:
=x+y;
z:
=z*z;
end
begin
A:
=2;
B:
=A*2;
P（A,A,B）;
PrintA,B
end.
试问，假设参数传递的方式分别采用传地址和传值时，程序执行后输出A,B的值是什么?
5.文法G（S）
S→dAB
A→aA|a
B→Bb|ε
描绘的语言是什么？
6.证明文法G（S）
S→SaS|ε
是二义性的。
7.文法G（S）
S→BA
A→BS|d
B→aA|bS|c
的预测分析表如下
a
b
c
d
#
S
S→BA
S→BA
S→BA
A
A→BS
A→BS
A→BS
A→d
B
B→aA
B→bS
B→c
给出句子adccd的分析过程。
8.写一个文法G,使其语言为L（G）={albmclanbn|l>=0,m>=1,n>=2}
9.文法G（S）:
S→a|（T）
T→T,S|S
的优先关系表如下：
关系
a
（
）
a
-
-
.>
.>
（
<.
<.
=.
<.
）
-
-
.>
.>
<.
<.
.>
.>
请计算出该优先关系表所对应的优先函数表。
10.何谓优化？
按所涉及的程序范围可分为哪几级优化？
11.目的代码有哪几种形式？
生成目的代码时通常应考虑哪几个问题？
12.一字母表Σ={a,b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。
13.根本的优化方法有哪几种？
14.写一个文法G,使其语言为L（G）={abncn|n≥0}
15.考虑下面的程序：
…
procedurep（x,y,z）;
begin
y:
=y+z;
z:
=y*z+x
end;
begin
a:
=2;
b:
=3;
p（a+b,b,a）;
printa
end.
试问，假设参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么?
16.写出表达式a＋b*（c-d）/e的逆波兰式和三元序列。
17.证明文法G（A）
A→AA|（A）|ε
是二义性的。
18.令Σ={a,b}，那么正规式a*b|b*a表示的正规集是什么？
19.何谓DISPLAY表？
其作用是什么？
20.考虑下面的程序：
…
procedure p（x,y,z）；
begin
y:
=y+2;
z:
=z+x;
end
begin
a:
=5;
b:
=2;
p（a+b,a-b,a）;
printa
end.
试问，假设参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么?
21.写一个文法G,使其语言为L（G）={anbncm|n>0为奇数，m>0为偶数}
22.写出表达式a:
=（b+c）*e+（b+c）/f的逆波兰式和三元序列。
23.一个文法G别是LL
（1）文法的充要条件是什么？
24.文法G[S]
S→S*aF|aF|*aF
F→+aF|+a
消除文法左递归和提公共左因子。
25.符号表的作用是什么？
符号表查找和整理技术有哪几种？
五、计算题：
1.设文法G（S）:
S→^|a|（T）
T→T,S|S
⑴消除左递归；
⑵构造相应的FIRST和FOLLOW集合；
⑶构造预测分析表
2.语句ifEthenS
（1）改写文法，使之适宜语法制导翻译；
（2）写出改写后产生式的语义动作。
3.设文法G〔S〕：
S→（T）|a
T→T+S|S
（1〕计算FIRSTVT和LASTVT；
〔2〕构造优先关系表。
4.设某语言的for语句的形式为
fori:
＝E
（1）toE
（2）doS
其语义解释为
i:
＝E
（1）
LIMIT:
＝E
（2）
again:
ifi＜＝LIMITthen
Begin
S;
i:
＝i＋1
gotoagain
End;
〔1〕写出适宜语法制导翻译的产生式；
〔2〕写出每个产生式对应的语义动作。
5.把语句
whilea<10do
ifc>0thena:
=a+1
elsea:
=a*3-1;
翻译成四元式序列。
6.设有根本块
D:
=A-C
E:
=A*C
F:
=D*E
S:
=2
T:
=A-C
Q:
=A*C
G:
=2*S
J:
=T*Q
K:
=G*5
L:
=K+J
M:
=L
假设根本块出口时只有M还被引用，请写出优化后的四元序列。
7.文法G（S）
S→a|^|（T）
T→T,S|S
（1）给出句子（a,（a,a））的最左推导；
（2）给出句型（（T,S）,a）的短语,直接短语，句柄。
8.对于C语言doSwhileE语句
（1）改写文法，使之适宜语法制导翻译；
（2）写出改写后产生式的语义动作。
9.文法G（S）
S→aAcBe
A→Ab|b
B→d
（1）给出句子abbcde的最左推导及画出语法树；
（2）给出句型aAbcde的短语、素短语。
10.设文法G（S）:
S→（T）|aS|a
T→T,S|S
⑴消除左递归和提公共左因子；
⑵构造相应的FIRST和FOLLOW集合；
⑶构造预测分析表。
11.把语句
ifX>0∨Y<0
thenwhileX>0doX:
=A*3
elseY:
=B+3;
翻译成四元式序列。
12.文法G（S）
E→E+T|T
T→T*F|F
F→（E）|i
（1）给出句型（i+i）*i+i的最左推导及画出语法树；
（2）给出句型（E+T）*i+F的短语，素短语和最左素短语。
13.设文法G〔S〕：
S→T|S∨T
T→U|T∧U
U→i|-U
〔1〕计算FIRSTVT和LASTVT；
〔2〕构造优先关系表。
参考答案
一、是非题：
1.×2.×3.×4.√5.√6.×7.×8.×9.√10.×11.×
12.√13.×14.√15.√16.√17.×18.√19.√20.×21.√22.√
二、填空题：
1.（最右推导〕
2.（词法分析〕，〔语法分析〕，〔中间代码生成〕，〔代码优化〕，〔目的代码生成〕
3.（二义性的〕
4.（执行性〕，〔说明性〕
5.（单词符号〕，〔语法单位〕。
6.（源程序〕，〔单词符号〕
7.（类型、种属、所占单元大小、地址〕
8.（现行活动记录地址和所有外层最新活动记录的地址）
9.（句柄〕
10.（栈式），〔堆式〕
11.（类型），〔作用域〕
12.（传地址〕，〔传值〕，〔传名〕
13.（局部优化〕，〔循环优化〕，〔全局优化〕
14.（自上而下〕，〔自下而上〕
15.（分析表〕，〔符号栈〕
16.（传地址〕，〔传值〕，〔传名〕
17.（初〕，〔终〕
18.（局部优化〕，〔循环优化〕，〔全局优化〕
19.（语法〕，〔语义〕
20.（句柄〕
21.（LL
（1）文法〕
22.（静态〕，〔动态〕
23.（二义性文法〕
24.（标准推导〕，〔标准〕
25.（自上而下〕，〔自下而上〕
26.（句子）
27.（从开始符号出发，向下推导，推出句子〕
28.（单词符号〕，〔语法单位〕
29.（局部优化〕
30.（分析表〕，〔符号栈〕
31.（上下文无关文法〕，〔正规〕
32.（指令访问主存次数加1〕
33.（最左素短语〕
三、名词解释题：
1.局部优化-------局限于根本块范围的优化称。
2.二义性文法------假设一个文法存在某个句子对应两棵不同的语法树，那么称这个文法是二义性文法。
3.DISPLAY表----过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。
4.词法分析器-----执行词法分析的程序。
5.最左推导------任何一步α=>β都是对α中的最右非终结符交换。
6.语法------一组规那么，用它可形成和产生一组合式的程序。
7.文法------描绘语言的语法构造的形式规那么。
8.根本块------指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。
9.语法制导翻译------在语法分析过程中，根据每个产生式所对应的语义子程序进展翻译的方法叫做语法制导翻译。
10.短语------令G是一个文法，S划文法的开始符号，假定αβδ是文法G的一个句型，假设有S
αAδ且A
β，那么称β是句型αβδ相对非终结符A的短语。
11.待用信息------假设在一个根本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，那么称j是四元式i的变量A的待用信息。
12.标准句型------由标准推导所得到的句型。
13.扫描器------执行词法分析的程序。
14.超前搜索------在词法分析过程中，有时为了确定词性，需超前扫描假设干个字符。
15.句柄------一个句型的最左直接短语。
16.语法制导翻译------在语法分析过程中，根据每个产生式所对应的语义程序进展翻译的方法叫做语法制导翻译。
17.标准句型------由标准推导所得到的句型。
18.素短语------素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。
19.语法------是组规那么，用它可形成和产生一个合式的程序。
20.待用信息------假设在一个根本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，那么称j是四元式i的变量A的待用信息。
21.语义------定义程序的意义的一组规那么。
四、简答题：
1.所求文法是G[S]:
S→AB|BA0
A→AD|C
B→2|4|6|8
C→1|3|5|7|9|B
D→0|C
2.输出是4231
3.句子b（aa）b的标准归约过程：
步骤
符号栈
输入串
动作
0
#
b（aa）b#
预备
1
#b
（aa）b#
移进
2
#b（
aa）b#
移进
3
#b（a
a）b#
移进
4
#b（A
a）b#
归约
5
#b（Ma
）b#
移进
6
#b（Ma）
b#
移进
7
#b（B
b#
归约
8
#bA
b#
归约
9
#bAb
#
移进
10
#S
#
承受
4.传地址A=6,B=16
传值A=2,B=4
5.L（G）={danbm|n>0,m≥0}
6.证明：
因为文法G[S]存在句子aa有两个不同的最左推导，所以文法G[S]是是二义性的。
S=>SaS=>SaSaS=>aSaS=>aaS=>aa
S=>SaS=>aS=>aSaS=>aaS=>aa
7.句子adccd的分析过程：
步骤
符号栈
输入串
产生式
0
#S
adccd#
1
#AB
adccd#
S→BA
2
#AAa
adccd#
B→aA
3
#AA
dccd#
4
#Ad
dccd#
A→d
5
#A
ccd#
6
#SB
ccd#
A→BS
7
#Sc
ccd#
B→c
8
#S
cd#
9
#AB
cd#
B→c
10
#Ac
d#
11
#A
d#
12
#d
d#
A→d
13
#
#
8.所求文法是G[S]:
S→AB
A→aAc|D
D→bD|b
B→aBb|aabb
9.
函数
a
（
）
f
4
2
4
4
g
5
5
2
3
10.优化：
对程序进展各种等价变换，使得从变换后的程序出发，能产生更有效的目的代码。
三种级别：
局部优化、循环优化、全局优化
11.目的代码通常采用三种形式：
机器语言，汇编语言，待装配机器语言模块。
应着重考虑的问题：
（1）如何使生成的目的代码较短；
（2）如何充分利用存放器，以减少访问内存次数；
（3）如何充分利用指令系统的特点。
12.正规式a（a|b）*。
13.删除多余运算，代码外提，强度削弱，变换循环控制条件，合并量，复写传播和删除无用赋值。
14.文法G[S]:
S→aB|a
B→bc|bBc
15.传值a=2
传地址a=15
16.逆波兰式:
abcd-*e/+
三元序列:
oparg1arg2
（1）-cd
（2）*b
（1）
（3）/
（2）e
（4）+a（3）
17.证明：
因为文法G[S]存在句子（）有两个不同的最左推导，所以文法G[S]是是二义性的。
A=>AA=>（A）A=>（）A=>（）
A=>AA=>A=>（A）=>（）
18.（a*b|b*a）={a,b,ab,ba,aab,bba……}
19.Display表:
嵌套层次显示表
由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，display表就是用于登记每个外层过程的最新活动记录起始地址。
20.传地址a=12
传值a=5
21.所求文法是G[S]:
S→AC
A→aaAbb|ab
C→ccC|cc
22.逆波兰式abc+e*bc+f/+:
=
三元序列oparg1arg2
（1）+bc
（2）*
（1）e
（3）+bc
（4）/（3）f
（5）+
（2）（4）
（6）:
=a（5）
23.一个文法G别是LL
（1）文法的充要条件是:
（1）FIRST（α）∩FIRST（β）=Ф
（2）假设β=*>ε,FIRST（α）∩FOLLOW（A）=Ф
24.消除左递归
S→aFS’|*aFS’
S’→*aFS’|ε
F→+aF|+a
提公共左因子,文法G’（S）
S→aFS’|*aFS’
S’→*aFS’|ε
F→+aF’
F’→F|ε
25.作用：
登记源程序中出现的各种名字及其信息，以及理解各阶段的进展状况。
主要技术：
线性表，对折查找，杂奏技术。
五、计算题：
1.
（1）消除左递，文法变为G’[S]：
S→^|a|（T）'
T→ST’|S
T’→,ST’|ε
此文法无左公共左因子。
（2）构造相应的FIRST和FOLLOW集合：
FIRST（S）={a,^,（}，FOLLOW（S）={#,,,）}
FIRST（T）={a,^,（}，FOLLOW（T）={}}
FIRST（T’）={,,ε}，FOLLOW（F）={）}
（3）构造预测分析表：
a
^
（
）
#
S
S→a
S→^
S→（T）'
T
T→ST’
T→ST’
T→ST’
T’
T’→ε
T’→,ST’
2.
（1）
C→ifEthen
S→CS
（1）
（2）
C→ifEthen{BACK（E.TC,NXQ）;C.chain:
=E.FC}
S→CS
（1）{S.chain:
=MERG（C.Chain,S
（1）.Chain）}
3.
（1）FIRSTVT（S）={a,（}
FIRSTVT（T）={+,aa,（}
LASTVT（S）={a,）}
LASTVT（T）={+,a,）}
（2）
a
+
（
）
a
.>
.>
+
<.
.>
<.
.>
（
<.
<.
<.
=.
）
.>
.>
>.
4.
（1）F→fori:
=E
（1）toE
（2）do
S→FS
（1）
（2）F→fori:
=E
（1）toE
（2）do
{GEN（:
=,E
（1）.place,_,entry（i））;
F.place:
=entry（i）;
LIMIT:
=Newtemp;
GEN（:
=,E
（2）.place,_,LIMIT）;
Q:
=NXQ;
F.QUAD:
=q;
GEN（j≤,entry（i）,LIMIT,q+2）
F.chain:
=NXQ;
GEN（j,_,_,0）}
S→FS
（1）
{BACKPATCH（S
（1）.chain,NXQ）;
GEN（+,F.place,1,F.place）;
GEN（j,_,_,F.QUAD）;
S.chain:
=F.chain
}
5.
（1）（j<,a,‘10’,（3））
（2）（j,_,_,（12））
（3）（j>,c,‘0’,（5））
（4）（j,_,_,（8））
（5）（+,a,‘1’,T1））
（6）（:
=,T1,_,a）
（7）（j,_,_,
（1））
（8）（*,a,‘13’,T2）
（9）（-,T2,‘1’,T3）
（10）（:
=,T3,_,a）
（11）（j,_,_,
（1））
6.优化后的四元序列
D:
=A-C
E:
=A*C
F:
=D*E
M:
=F+20
7.最
升级会员 