《编译原理》期末试题（五）
一、单项选择题(共10小题，每小题2分，共20分)
1．语言是
A．句子的集合B．产生式的集合
C．符号串的集合D．句型的集合
2．编译程序前三个阶段完成的工作是
A．词法分析、语法分析和代码优化
B．代码生成、代码优化和词法分析
C．词法分析、语法分析、语义分析和中间代码生成
D．词法分析、语法分析和代码优化
3．一个句型中称为句柄的是该句型的最左
A．非终结符号B．短语C．句子D．直接短语
4．下推自动机识别的语言是
A．0型语言B．1型语言
C．2型语言D．3型语言
5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即
A．字符B．单词C．句子D．句型
6．对应Chomsky四种文法的四种语言之间的关系是
A．L0?L1?L2?L3 B．L3?L2?L1?L0
C．L3=L2?L1?L0D．L0?L1?L2=L3
7．词法分析的任务是
A．识别单词B．分析句子的含义
C．识别句子D．生成目标代码
8．常用的中间代码形式不含
A．三元式B．四元式C．逆波兰式D．语法树
9．代码优化的目的是
A．节省时间B．节省空间
C．节省时间和空间D．把编译程序进行等价交换
10．代码生成阶段的主要任务是
A．把高级语言翻译成汇编语言
B．把高级语言翻译成机器语言
C．把中间代码变换成依赖具体机器的目标代码
D．把汇编语言翻译成机器语言
二、填空题（本大题共5小题，每小题2分，共10分）
1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。
3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。
4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。
5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。
三、名词解释题(共5小题，每小题4分，共20分)
1．词法分析
词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则
从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，
并转换成统一的内部表示(token)，送给语法分析程序。
2．LL(1)文法
若文法的任何两个产生式A →α | β都满足下面两个条件：
（1）FIRST(α) ? FIRST(β ) = φ；
（2）若β?* ε，那么FIRST(α) ? FOLLOW( A ) = φ。
我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步
动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一
些明显的性质，它不是二义的，也不含左递归。
3．语法树
句子的树结构表示法称为语法树(语法分析树或语法推导树)。
给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的
语法树。这棵树具有下列特征：
(1)根节点的标记是开始符号S。
(2)每个节点的标记都是V中的一个符号。
(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列
次序为A1A2…A R，那么A→A1A2…A R一定是P中的一条产生式。
(4)若一标记为A的节点至少有一个除它以外的子孙，则A∈V N。
(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G
的句型；若w中仅含终结符号，则w为文法G所产生的句子。
4．LR(0)分析器
所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的
每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再
向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否
已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是
移进还是按某一产生式进行归约等)。
5．语言和文法
文法就是语言结构的定义和描述，是有穷非空的产生式集合。
文法G定义为四元组的形式：
G=(V N，V T，P，S)
其中：V N是非空有穷集合，称为非终结符号集合；V T是非空有穷集合，
称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。
这里，V N∩V T=?，S∈V N。V=V N∪V T，称为文法G的字母表，它是出现
文法产生式中的一切符号的集合。
文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即
L(G)={x| S ?*x ，其中S 为文法开始符号，且+∈T V x }
简单的说，文法描述的语言是该文法一切句子的集合。
四、简答题(共4小题，每小题5分，共20分)
1．编译程序和高级语言有什么区别?
用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器 语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程 的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转 换过的叫目标程序，也就是机器语言。
编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来 将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。 解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令， 然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序 止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的"对话"，随时 可以修改高级语言的程序。BASIC 语言就是解释型高级语言。编译型编译程序将 级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快， 在过程中，不能进行人机对话修改。FORTRAN 语言就是编译型高级语言。 2．编译程序的工作分为那几个阶段?
词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)， 而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为 编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。 3．简述自下而上的分析方法。
所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的 开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。 4．简述代码优化的目的和意义。
代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行 一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目 标程序运行时所需要的时间短，同时所占用的存储空间少。
五、综合应用题(共3小题，每小题10分，共30分)
1．证明下述文法G ：
S →aSbS|aS|d
是二义性文法。 解：
一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个 文法是二义性文法。
句子aadbd 有两棵语法树。如下图：
S
S
a b S
S
a
S
(1) (2)
由此可知，S →aSbS|aS|d 定义的文法是二义性文法。 2．对于文法G[S]：S →AB ，A →Aa|bB ，B →a|Sb 求句型baSb 的全部短语、直接短语和句柄？
句型baSb 的语法树如图五(2)
所示。
解：baSb 为句型baSb 的相对于S 的短语，ba 为句型baSb 的相对于A 的短语，Sb 为句型baSb 的相对于
B 的短语，且为直接短语，a 为句型baSb 的相对于B 的短语，且为直接短语和句柄。
3．设有非确定的有自限动机NFA M=({A ，B ，C}，{0，1}，δ，{A}，{C})，其中： δ (A ，0)={C} δ (A ，1)={A ，B} δ (B ，1)={C} δ (C ，1)={C}。请画出状态转换距阵和状态转换图。
状态转换图为
《编译原理》期末试题（六）
编译原理 样题
A S
B
b B S a b
【】1．____型文法也称为正规文法。
[A] 0 [B] 1 [C] 2 [D] 3
【】2．____文法不是LL(1)的。
[A] 递归 [B] 右递归 [C] 2型 [D]含有公共左因子的
【】3．文法E→E+E|E*E|i的句子i*i+i*i的不同语法分析树的总数为______。
[A]1 [B]3 [C]5 [D]7
【】4．四元式之间的联系是通过实现。
[A]临时变量 [B]指示器 [C]符号表 [D]程序变量
【】5．同心集合并可能会产生的新冲突为。
[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约
【】6．代码优化时所依据的是。
[A]语法规则 [B]词法规则 [C]等价变换规则 [D]语义规则
【】7．表达式a-(-b)*c的逆波兰表示为。
[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-* （注：@为单目减运算符）
【】8．过程的DISPLAY表记录了。
[A]过程的连接数据 [B]过程的嵌套层次
[C]过程的返回地址 [D]过程的入口地址
二填空题
3．对于文法G1和G2，若有L(G1)=L(G2) （或，则称文法G1和G2是等价的。
4．对于文法G[E]：F|P P→(E)|i，句型T+T*F+i
的句柄是T ，最左素短语是
5．最右推导的逆过程称为规范归约，也称为最左归约。
6．规范规约中的可规约串是句柄，算符优先分析中的可规约串是
7．（A∨ B）∧（C∨ ?D∧ E）的逆波兰式是ＡＢ∨ＣＤ?Ｅ∧∨∧。
8。
9
段，符号表是地址分配的依据。
10．一个过程的DISPLAY的DISPLAY表的内容加上本过程的SP的地址
三有穷自动机M接受字母表 ＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的DFA M及和M等价的正规式。
【】【】
四证明正规式(ab)*a 与正规式a(ba)*等价（用构造他们的最小的DFA方法）。【答案：】
五写一个文法，使其语言是：
L ＝ { 1n0m1m0n | m,n≥0 }
【】【】五文法G：S → 1S0 | A
A →0A1 | ε
六对文法G[S]
S → aSb | P
P → bPc | bQc
Q → Qa | a
(1)它是否是算符优先文法？请构造算符优先关系表
(2)文法G[S]消除左递归、提取左公因子后是否是LL（1）文法？请
证实。
【】【】1.求出G[S]的FIRSTVT集和LASTVT集：
FIERSTVT（S）={a,b} LASTBVT（S）={b,c}
FIERSTVT(P)={b} LASTBVT（P）={c}
FIERSTVT(Q)={a} LASTBVT（Q）={a}
构造优先关系表为：
，所以该文法不是算符优先文法。
2.消除左递归和提取左公因子后的文法为：
S → aSb | P
P → bP’
P’→ Pc |Qc
Q →aQ’
Q’→aQ’|ε
求具有相同左部的两个产生式的Select集的交集：
Select(S→aSb)∩Select(S→P) = {a}∩First(P) = {a}∩{b} = Ф
Select(P’→Pc)∩Select(P’→Qc) = First(P)∩First(Q)={b}∩{a}=Ф
Select(Q’→aQ’)∩Select(Q’→ε) = {a}∩Follow(Q) = {a}∩{c} = Ф
所以修改后的文法是LL（1）文法。
七已知文法G为:
（0）S′→ S
（1）S → aAd
（2）S → bAc
（3）S → aec
（4）S → bed
（5） A → e
试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。
【】【答案：】
八
prod:=0;
i:=1;
while i≤20 do
begin
prod:=prod+a[i]*b[i];
i:=i+1
end;
试按语法制导翻译法将源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。
【答案：】
九设有以下程序段
procedure P(x,y,z)
begin
Y:=y*3;
Z:=X+z;
end;
begin
a:=5; b:=2;
p(a*b,a,a);
print(a);
end
若参数传递的方法分别为（1）传值、（2）传地址、（3）传名，试问结果分别什么？
【】【】十（1）传值 5；（2）传地址 25；（3）传名 45
十对以下文法，请写出关于括号嵌套层数的属性文法。(为S,L引入属性h,用来
答案：
十一对PL/0语言的while语句 while 条件B DO 语句S 的编译程序，请在空缺处填空，完成该语句的编译算法：
switch (SYM) { ……
case WHILESYM:
CX1=CX ;
GetSym();
CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);
CX2=CX ;
GEN(JPC,0,0);
if (SYM==DOSYM)
GetSym() ;
else Error(18);
STATEMENT(FSYS,LEV,TX);
GEN(JMP,0,CX1);
CODE[CX2].A=CX ；
break;
……}
《编译原理》期末试题（七）
一、回答下列问题：(30分)
1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？
解答：
S-属性文法是只含有综合属性的属性文法。（2分）
L-属性文法要求对于每个产生式A X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：
（1）产生式Xj的左边符号X1,X2…Xj-1的属性；
（2）A的继承属性。（2分）
S-属性文法是L-属性文法的特例。（2分）
2．什么是句柄？什么是素短语？
一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分）
3．划分程序的基本块时，确定基本块的入口语句的条件是什么？
解答：
（1）程序第一个语句，或
（2）能由条件转移语句或无条件转移语句转移到的语句，或
（3）紧跟在条件转移语句后面的语句。
4．(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？
答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记
录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，
则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直
接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。
通过DISPLAY表可以访问其外层过程的变量。
5．(6分)对下列四元式序列生成目标代码：
A:=B*C
D:=E+F
G:=A+D
H:=G*2
其中，H是基本块出口的活跃变量，R0和R1是可用寄存器
答：
LD R0，B
MUL R0，C
LD R1，E
ADD R1，F
ADD R0，R1
MUL R0，2
ST R0，H
二、设 ={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分) 答：
构造相应的正规式：(0|1)*1(0|1) (3分) NFA: (2分)
1
三、写一个文法使其语言为L(G)={ anbmambn | m,n ≥1}。(6分)
答：文法G(S):
S → aSb | B B → bBa | ba
四、对于文法G(E): (8分)
E →T|E+T T →F|T*
F F →(E)|i
1. 写出句型(T*F+i)的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语、句柄和素短语。 答： 1. (4分)
E ?T ?
F ?(E) ?(E+T) ?(E+F)
?(E+i) ?(T+i) ?(T*F+i)
2. (4分)
短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i
句柄：T*F
素短语：T*F, i
五、设文法G(S)：(12分)
(|*
)
B
B |B
A A
A |
SiA S
A →+
→
→
1．构造各非终结符的FIRSTVT和LASTVT集合；2．构造优先关系表和优先函数。(12分)
答：(6分)
FIRSTVT(S)={ i，+，)，( }
FIRSTVT(A)={ +，)，( }
FIRSTVT(B)={ )，( }
LASTVT(S)={ i，+，*，( }
LASTVT(A)={ +，*，( }
LASTVT(B)={ *，( }
六、设某语言的do-while语句的语法形式为(9分) S → do S(1) While E
其语义解释为：
真
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：
(1) 写出适合语法制导翻译的产生式；
(2) 写出每个产生式对应的语义动作。
答：(1). 适合语法制导翻译的文法(3分)
G(S):
R→ do
U→R S(1) While
S→U E
(2). (6分)
R→ do
{ R.QUAD:=NXQ }
U→R S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }
S→U E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }
答案二：
(1) S → do M1 S(1) While M2 E
M →ε (3分)
(2) M →ε { M.QUAD := NXQ } (6分)
S → do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}
七、(8分)将语句
if (A0) then while C>0 do C:=C+D
翻译成四元式。(8分)
答：
100 (j
101 (j，-，-，109)
102 (j>，B，0，104)
103 (j，-，-，109)
104 (j>，C，0，106)
105 (j，-，-，109)
106 (+，C，D，T1)
107 (:=，T1，-，C)
108 (j，-，-，104)
109
(控制结构3分，其他5分)
八、(10分) 设有基本块如下：
T1:=S+R
T2:= 3
T3:= 12/T2
T4:=S/R
A:=T1-T4
T5:=S+R
B:=T5
T6:=T5*T3
B:=T6
(1)画出DAG图；
(2)设A,B是出基本块后的活跃变量，请给出优化后的
四元式序列。
答：(1) DAG如右图：(6
(2) 四元式序列：(4分)
T1:=S+R
T4:=S/R
A:=T1-T4
B:=T1*4
九、(9分) 设已构造出文法G(S)：
(1)S BB
(2)B → aB
(3)B→ b
的LR分析表如下
假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。
答：
步骤状态符号输入串
0 0 # abab#
1 03 #a bab#
2 034 #ab ab#
3 038 #aB ab#
4 02 #B ab#
5 02
6 #Ba b#
6 026
7 #Bab #
7 0269 #BaB #
8 025 #BB #
9 01 #S # acc
《编译原理》期末试题（八）
1．（10分）处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。
2．为语言L ＝ {a m b n | 0 ≤ m ≤ 2n}（即a的个数不超过b的个数的两倍）
写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。）
3．（10分）构造下面文法的LL（1）分析表。
D → TL
T → int | real
L → id R
R → , id R | ε
4．（15分）就下面文法
S → ( L) | a L → L , S | S
?给出一个语法制导定义，它输出配对括号的个数。
?给出一个翻译方案，它输出每个a的嵌套深度。
如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。
5．（10分）Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。
6．（5分）一个C语言程序如下：
func(i1,i2,i3)
long i1,i2,i3;
{
long j1,j2,j3;
printf("Addresses of i1,i2,i3 = %o,%o,%o\n",&i1,&i2,&i3);
printf("Addresses of j1,j2,j3 = %o,%o,%o\n",&j1,&j2,&j3);
}
main()
{
long i1,i2,i3;
func(i1,i2,i3);
}
该程序在某种机器的Linux上的运行结果如下：
Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470 Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434
从上面的结果可以看出，func 函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。
7．（15分）一个C语言程序及其在某种机器linux操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。
static long aa = 10;
short bb = 20;
func()
{
static long cc = 30;
short dd = 40;
}
.file "static.c"
.version "01.01"
gcc2_compiled.:
.data
.align 4
.type aa,@object
.size aa,4
aa:
.long 10
.globl bb
.align 2
.type bb,@object
.size bb,2
bb:
.value 20
.align 4
.type cc.2,@object
.size cc.2,4
cc.2:
.long 30
.text
.align 4
.globl func
.type func,@function
func:
pushl %ebp
movl %esp,%ebp
subl $4,%esp
movw $40,-2(%ebp)
.L1:
leave
ret
.Lfe1:
.size func,.Lfe1-func
.ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)" 8．（10分）C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型语言。
9．（10分）如果在A机器上我们有C语言编译器CC A，也有它的源码S A（用C 语言写成）。如何利用它通过尽量少的工作来得到B机器的C语言编译器CC B。10．（5分）表达式(λx.(λyz.(x + y) + z) 3) 4 5和(λx.(λyz.(x + y) + z) 3 5) 4有同样的
结果。在抽象机FAM 上，哪一个表达式对应的目标代码的执行效率高？为什么？ 参考答案 1．
2．LR （1）文法 LR （1）文法 二义文法
S → AB | aABb S → AB S → AASb | ε A → aaAb | ε A → aaAb | ab | ε A → a | ε
B → Bb | ε B → Bb | ε 3． int real id , $ D D →TL D →TL T T →int T →real L L →id R R R →, id R R → ε 4． S ' → S print(S.num) S → (L) S.num := L.num +1 S → a S.num := 0 L → L 1,S L.num := L 1.num + S.num L → S L.num := S.num S ' → {S.depth := 0} S S → {L.depth := S.depth +1} (L) S → a {print(S.depth)} L → {L 1.depth := L.depth} L 1, {S.depth := L.depth} S L → { S.depth := L.depth} S 5． t 1 := initial t 2 := final if t 1 > t 2 goto L1 v := t 1 L2: stmt if v = t 2 goto L1 v := v + 1 goto L2 L1: 6．由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。 7．aa 是静态外部变量，而bb 是外部变量，它们都分配在静态数据区（由.data 伪指令开始），但是bb 由伪指令.globl 指明为全局的，用来解决其它文件中对bb 的外部引用，而aa 只能由