*
编译原理复习题
一．简答题：
1) 什么是句子？ 什么是语言?
解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T *
），则称x 是文法的一个句子。 语言——语言是句子的集合。
或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │S x,x ∈V T *} 。
2) DFA 与NFA 有何区别 ?
解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个
开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么?
解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直
接推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么?
解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图
归约到文法的开始符号。
5) 一个上下文无关文法G 包括哪四个组成部分？
解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？ 解答:关键是寻找句柄。
7) 在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。 8）什么是属性文法？
答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属
性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。 一个属性文法形式的定义为一个三元组AG ，AG=（G ，V ，E ）。
其中G 为一个上下文无关文法；V 为属性的有穷集；E 为一组语义规则。 9）语法制导翻译
语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。
语法制导翻译(Syntax-Directed Translations)：
–一个句子的语义翻译过程与语法分析过程同时进行。
在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息，语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义属性值。
10）词法分析的主要任务是什么？
解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属
性字并输出。
11)图示运行时存储空间的划分（分为哪几个区）。
解答: 一般分为静态区和动态区：
程序代码区、静态数据区、栈区和堆区
12)常用的中间语言种类有哪几种？
解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。
13）文法G所描述的语言是什么的集合？
解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。
14）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？
解答: 2型文法叫上下文无关文法。
15）常见的动态存贮分配策略有哪两种？
解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。
16）语法分析的任务是什么？
解答:语法分析的任务是识别给定的终结符串是否为给定文法的句子。
17）局部优化是局限于一个什么范围内的一种优化？
解答: 是局限于一个基本块范围内的一种优化。
18）通常一个编译程序中应包括哪七个部分？
解答: 通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化，目标代码生成以及表格处理和出错处理等七个部分。
19）代码优化的主要目标是什么？
解答: 代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。
20）.符号表的组织方式有哪几种？
答：一个编译程序对符号表的总体组织可有三种选择：
第一种：把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表。这样组织的最大优点是每个符号表的属性个数和结构完全相同。则表项是等长的，并且表项中的每个属性栏都是有效的，对于单个符号表示来说，这样使得管理方便一致，空间效率高。但这样组织的主要缺点是一个编译程序将同时管理若干个符号表，增加了总体管理的工作量和复杂度。而且对各类符号共同属性的管理必须设置重复的运行机制。使得符号表的管理显得臃肿。
第二种：把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表。这样组织方式的最大优点是总体管理非常集中单一，且不同种类符号的共同属性可一致地管理和处理。这样组织所带来的缺点是，由于属性的不同，为完整表达各类符号的全部属性必将出现不等长的表项，以及表项中属性位置的交错重叠的复杂情况，这就极大地增加了符号表管理的复杂度。为使表项等长且实现属性位置的唯一性，可以把所有符号的可能属性作为符号表项属性。这种组织方法可能有助于降低符号表管理复杂性，但对某个具体符号，可能增加了无用的属性空间，从而增加了空间开销。
第三种：折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。这种折衷的组织方式在管理复杂性及时空效率方面都取得折衷的效果，并且对复杂性和效率的取舍可由设计者根据自己的经验和要求及目标系统的客观环境和需求进行选择和调整。
21）. 在整个编译期间，对于符号表的操作有哪些？
答：在整个编译期间，对于符号表的操作大致可归纳为五类：
·对给定名字，查询此名是否已在表中；
·往表中填入一个新的名字；
·对给定名字，访问它的某些信息；
·对给定名字，往表中填写或更新它的某些信息；
·删除一个或一组无用的项。
22）.符号表的作用有哪些？
答：在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。起主要作用是：
①收集符号属性；
②上下文语义的合法性检查的依据；
③作为目标代码生成阶段地址分配的依据。
23）. 简述优化的原则是什么？
答：编译程序提供的对代码优化必须遵循的原则是：
（1）等价原则。经过优化后不应改变程序运行的结果。
（2）有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。
（3）合算原则。应尽可能以较低的代价取得较好的优化效果。
24）．简述常用的优化技术有哪些？
答：编译程序中常用的优化技术有：
删除公共子表示式；复写传播；删除无用代码；代码外提；强度削弱；删除归纳变量；合并常量。
25）.何谓优化？按所涉及的程序范围可分为哪几级优化？答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。
三种级别：局部优化、循环优化、全局优化。
26)、编译程序目标代码运行时的存储区通常被划分为几部分？
答：目标代码区、静态数据区、栈区、堆区。
27)、数组的内情向量包含哪些内容？
在编译程序对数组说明进行语义处理时，须把数组的类型type、维数n、各维的上、下界lk,uk 等有关信息记录下来。此外,如果数组是常界的,还可将各维的界差dk以及计算数组元素地址的常量C记录下来。为了便于引用，通常是把上述信息存放于数组相应的“内情向量”之中.对数组内情向量的访问,可通过数组在符号表中相应登记项的ADDR域以间接寻址方式进行（即将其ADDR域作为指针用于存放内情向量的首地址）。
28)、文法分为几种类型？其分类依据是什么？
答：分为四类：短语文法（0型文法）、前后文有关文法（1型文法）、前后文无关文法（2型文法）、正规文法（3型文法）。分类依据：对产生式家约束。
29)、一般来说编译程序至少包含哪几部分？各部分的作用是什么？
答：词法分析，语法分析，语义分析和目标代码生成是必须的，代码优化是为了提高目标代码的质量而引入的，不是必须的，没有代码优化编译程序同样生成目标代码。各部分的作用参见教材
30）、分程序结构的栈式存储管理中的活动记录包括哪些内容？
答：临时工作单元、局部变量、保存机器状态、存取链、控制链、实参，也称形式单元、返回地址，保存该被调过程返回后的地址。
31）、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？为什么？
答：不正确词法分析，语法分析，语义分析和目标代码生成是必须的，代码优化是为了提高目标代码的质量而引入的，不是必须的，没有代码优化编译程序同样生成目标代码。
二、应用题
1）写一个文法，使其语言是奇数集，且每个奇数不以0开头。
解：文法G(N)：
N→AB|B
A→AC|D
B→1|3|5|7|9
D→B|2|4|6|8
C→0|D
2）写一个文法，使其语言是无符号二进制实数（不含指数）。
解答:文法G(N)：
N→L.L|L
L→LB|B
B→0|1
3）给出上下文无关文法的定义。
一个上下文无关文法G是一个四元式(V T，V N，S，P)，其中：
V T是一个非空有限集，它的每个元素称为终结符号；
V N是一个非空有限集，它的每个元素称为非终结符号，V T∪V N=Φ；
S是一个非终结符号，称为开始符号；
P是一个产生式集合(有限)，每个产生式的形式是P→α，其中，P∈V N，α∈(V T∪V N)*。
开始符号S至少必须在某个产生式的左部出现一次。
4）．给出正规式与正规集的递归定义。
(1)ε和Φ都是∑上的正规式，它们所表示的正规集分别为{ε}和Φ；
(2)任何a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}；
(3)假定U和V都是∑上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，(U|V)、(U·V)和(U)*也都是正规式，它们所表示的正规集分别为L(U)∪L(V)、L(U)L(V)(连接积)和(L(U))*(闭包)。
仅由有限次使用上述三步骤而得到的表达式才是∑上的正规式。仅由这些正规式所表示的字集才是∑上的正规集。
5）．设文法G为：
S→aAcB|BdS
A→BaB|aBc|a
B→aScA|cAB|b
对于输入串aacabccb，给出最左推导。
答： S=>aAcB=>aaBccB=>aacABccB=>aacaBccB=>aacabccB=>aacabccb
6）设文法G为：
S→BA
A→BS|d
B→aA|bS|c
对于输入串adccd，给出最左推导。
答： S=>BA=>aAA=>adA=>adBS=>adcS=>adcBA=>adccA=>adccd
7）．给定正规文法G: Array S→aS|bA|b
A→aS
请构造与之等价的有限自动机。
8）．给定正规文法G:
S→aA
A→bA|aB|b
B→aA
9）．对下面给出的NFA确定化。
10）.将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。
G[S]：S→bSAe | bA
A→Ab | d
答：文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为：S→bB
B→SAe | A
A→d A'
A' →bA' | ε
11）消除下列文法G[A]的左递归。
A→AaB∣B
B→BbC∣C
C→eD∣D
D→(A)∣d
解答：消除文法G[A]的左递归后得到：
A →BAˊ
Aˊ→aBAˊ∣ε
B →CBˊ
Bˊ→bcBˊ∣ε
C→eD∣D
D→(A)∣d
12）正规式（a|b）*a(a|b) 构造一个等价的有限自动机。
解答：
13）将下图的NFA确定化为DFA。
答：用子集法确定化如下表
14）. 已知文法 G(E)
E →T|E＋T
T→F|T *F
F →(E)|i
(1)给出句型(T *F＋i)的最右推导；
(2)给出句型(T *F＋i)的短语、简单短语、句柄、素短语、最左素短语。
解：
(1) 最右推导：E ->T->F->(E)->(E ＋ T)->(E ＋ F)->(E ＋ i)->(T＋i)->(T*F＋i)
(2) 短语：(T*F＋i) ，T*F＋i ，T*F，i
简单短语：T*F,i
句柄：T*F
素短语：T*F,i
最左素短语：T*F
15）. 构造正规式 1(0|1)*101 相应的 DFA 。
解：先构造 NFA ：
确定化：
重新命名，令 AB 为 B、AC 为 C、ABY 为 D 得：
所以，可得 DFA 为：
16）. 文法：
S->MH|a
H ->LSo| ε
K ->dML| ε
L ->eHf
M->K|bLM
判断 G 是否为 LL(1) 文法，如果是，构造 LL(1) 分析表。解：各符号的 FIRST 集和 FOLLOW集为：
预测分析表
由于预测分析表中无多重入口，所以可判定文法是 LL(1)的17）. 对下面的文法 G ：
E ->TE'
E'->+E| ε
T ->FT'
T' ->T| ε
F-> PF'
F'-> *F'| ε
P->(E)|a|b|^
(1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (4 分)
(2) 证明这个方法是 LL(1) 的。(4 分)
(3) 构造它的预测分析表。(2 分)
解：（1）计算这个文法的每个非终结符的 FIRST 集和 FOLLOW集。FIRST 集合有：
FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(E')={+,ε }
FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(T')=FIRST(T)U{ε}={(,a,b,^, ε};
FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(F')=FIRST(P)={*, ε};
FIRST(P)={(,a,b,^};
FOLLOW 集合有：
FOLLOW(E)={),#};
FOLLOW(E')=FOLLOW(E)={),#}; FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#};//不包含εFOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#};
FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#};//不包含ε
FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,^,+,),#};
FOLLOW(P)=FIRST(F')UFOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε
(2)证明这个方法是 LL(1)的。
各产生式的 SELECT 集合有：
E->TE'： FIRST(T)={(,a,b,^};
E'->+E: FIRST(+E ) ={+};
E'->ε: FOLLOW(E')={),#}
T->FT': FIRST(F)={(,a,b,^};
T'->T: FIRST(T)={(,a,b,^};
T'->ε: FOLLOW(T/)={+,),#};
F->PF': FIRST(P)={(,a,b,^};
F'->*F': FIRST(*F)={*};
F'->ε : FOLLOW(F')={(,a,b,^,+,),#};
P->(E) FIRST((E)) ={(}
P->a FIRST(a )={a}
P->b FIRST(b)={b}
P->^ FIRST(^)={^}
可见，相同左部产生式若不能推出为空，其产生式右部的交集均为空，
相同左部产生式，若其中有一个能推出为空，其不能推出为空的产生式右部FIRST集合和左部的FOLLOW交集均为空，所以文法 G[E]是 LL(1)文法。
(3)构造它的预测分析表。文法 G[E]的预测分析表如下：
18）．设有文法G:
S →S*F|F F →F ↑P|P P →(S)|i
⑴ 完成下列算符优先关系表，并判断是否为算符优先文法（请说明理由）。
由于该文法的任何产生的右部都不含两个相继的非终结符，故属于算符文法。
从上表可以看出，任何两个终结符之间至少满足＝、＜· 、·＞三种关系之一，故G 为算符优先文法。
⑵ 给出句型S*P ↑(S)对应的语法树，指出该句型的短语、句柄
短语：S*P ↑(S) P ↑(S) P (S) 句柄: P
19） 已知文法G(S) S →T | S-T T→F | T / F F→(S) | i
（1）给出句型 T/ F-i 的最右推导；
（2）画出句型 T/F-i 规范规约的语法树及算符优先分析规约的语法树框架； （3）给出句型 T / F-i 的短语、素短语。
答：(1) 最右推导：E→T→F→(E) →(E＋T) →(E＋F) →(E＋i) →(T＋i) →(T*F＋i)
(2) 略
(3) 短语：(T*F＋i)，T*F＋i，T*F，i
素短语：T*F, i
20) 某语言的拓广文法G′为：
(0) S′→S
(1) S → Db|B
(2) D → d|ε
(3) B → Ba|ε
证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。
答：
拓广文法G'，增加产生式S'→S
在项目集I0中：
有移进项目D →·d
归约项目D →·和B →·
存在移进-归约和归约-归约冲突，所以G不是LR(0)文法。
若产生式排序为：
(0) S'→S
(1) S → Db
(2) S → B
(3) D → d
(4) D →ε
(5) B → Ba
(6) B →ε
G′的LR(0)项目集族及识别活前缀的DFA如下图：
由产生式知
Follow(S)={#}
Follow(D)= {b}
Follow(B)= {a ,#}
在I0中:
Follow(D) ∩{d}={ b} ∩{d}=
Follow(B) ∩{d}= { a ,#} ∩{d}=
Follow(D) ∩ Follow(B)= {b}∩{a ,#} =
在I3中:
Follow(S) ∩{a}={#}∩{a}=
所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法, 构造的SLR(1)分析表如下表：
21)、下面文法G 为:
（0）E’→ E
（1）E→ r B
（2）B→ B ; d
（3）B→ d
判断G 是SLR(1)还是LR(1)，说明理由，并构造相应的分析表
状态I3中含项目：
E→rB· 为归约项目
B→B·; i为移进项目
所以不是LR(0)文法
FOLLOW(S)={#} FOLLOW(S)∩{:}为空，所以该文法是SLR(1)文法。
22)、设文法G(S)：
S→(F) |d S |d
F→F ; S | S
(1) 消除左递归和回溯；
(2) 列出第一小题完成后的文法，并计算每个非终结符的FIRST和FOLLOW；
(3) 构造预测分析表。
解：
(1) S→(F) S→d S’ S’→S S’→ε 2分
F→S F’ F’ →，S F’ F’→ε 2分
评分细则：消除左递归2分，提公共因子2分。
(2) FIRST(S)＝{(，d} FOLLOW(S)＝{ # , ，, ) }
FIRST(S’)＝{d , ε} FOLLOW(S’)＝{ # , ，, ) } FIRST(L)＝{(，d} FOLLOW(L)＝{ )}
FIRST(L’)＝{，, ε} FOLLOW(L’〕＝{ )} 3分因为：
FIRST (S→(F))∩FIRST (S→dS)=∧
FIRST (S’→S)∩FOLLOW (S’→ ε)=∧
FIRST (F’ →，S F’)∩FIRST (F’→ ε)=∧
所以，此文法是LL(1)文法
(4) 预测分析表
23）. 设有基本块：
(1) a:=b-c (6) c:=b-f
(2) d:=a+4 (7) b:=b-c
(3) e:=a-b (8) f:=b+f
(4) f:=a+4 (9) a:=a-f
(5) b:=b+c
(1) 画出DAG图；
(2) 假设基本块出口时只有a，b还被引用，请写出优化后的三地址代码序列。
解答：
(1)给出DAG如右：
(2)重写三地址代码如下：
a:=b-c d:=a+4 e:=a-b
f:=d
b:=b+c c:=b-f
b:=b-c
f:=b+f
a:=a-f
24）.设有基本块 T 1：＝2 T 2：＝10/T 1 T 3：＝S －R T 4：＝S ＋R A ：＝T 2 * T 4 B ：＝A T 5：＝S ＋R T 6：＝T 3 * T 5 B ：＝T 6 (1) 画出DAG 图；
(2) 假设基本块出口时只有A ，B 还被引用，请写出优化后的三地址代码序列。 解：(1)DAG ：见右图 (2) 优化后的四元式 T 3：＝S －R T 4：＝S ＋R A ：＝5*T 4 B ：＝T 3＋T 4
25）将下面的条件语句表示成四元式序列：
if a>b then x:=a+b*c else x:=b-a; 答：
(1) ( j>, a, b, (3))
(2) ( j, , , (7) )
(3) ( *, b, c, T1)
(4) ( +, a, T1, T2)
(5) ( :=, T2, , x)
(6) ( j, , , (9))
(7) ( -, b, a, T3)
(8) ( :=, T3, , x)
(9) ( … … )
26）翻译成四元式序列。
While a＞0 ∨b＜0 do
Begin
X：＝X＋1；
if a＞0 then a：＝a－1
else b：＝b＋1
End；
答：
(1) (j＞，a，0，5)
(2) (j，－，－，3)
(5) (＋，×，1，T1)
(6) (：＝，T1，－，×)
(7) (j≥，a，0，9)
(8) (j，－，－，12)
(9) (－，a，1，T2)
(10) (：＝，T2，－，a)
(11) (j，－，－，1)
(12) (＋，b，1， T3)
(13) (：＝，T3，－，b)
(14) (j，－，－，1)
(15)
27）设有基本块：
t1:=3*A
t2:=2*C
t3:=t1+t2
t4:=t3+5
t5:=2*C
t6:=3*A
t7:=t6+t5
E:=t7-1
F:=t4-E
a)画出DAG图；
b)假设基本块出口时只有E，F还被引用，请写出优化后的三地址代码序列。
解答：
a)构造DAG：见右图。
b)优化后的三地址代码序列为：
t1:=3*A
t2:=2*C
t3:=t1+t2
t4:=t3+5
E:=t3-1
F:=t4-E
五、填空题:
1.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理 .
2.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称为编译程序.
3.对编译程序而言,输入数据是源程序 ,输出结果是目标程序 .
4.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。
5.所谓最右推导是指：任何一步α β都是对α中最右非终结符进行替换的。
6.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。
7.产生式是用于定义语法成分的一种书写规则。
8.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈V T*} 。
9.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。
10.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个句子。
11.语法分析最常用的两类方法是自上而下和自下而上分析法。
12.语法分析的任务是识别给定的终极符串是否为给定文法的句子。
13.自顶向下的语法分析方法的关键是如何选择候选式的问题。
14.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。
15.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。
16.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。
17.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最左归约，0 的含义是向貌似句柄的符号串后查看0个输入符号。
18.在SLR（1）分析法的名称中，S的含义是简单的。
19.所谓属性文法是一个属性文法是一个三元组：A＝（G，V，F），一个上下文无关文法G；
一个属性的有穷集V和关于属性的断言或谓词的有穷集F。每个断言与文法的某产生式相联。
19.综合属性是用于“自下而上”传递信息。
20.继承属性是用于“自上而下”传递信息。
21.符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。
22.常用的两种动态存贮分配办法是栈式动态分配和堆式动态分配。
《编译原理》模拟试题一 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√) 6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×) 10．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。
(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式 三、填空题(每空1分，共10分)
一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0） 项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分） 答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分） （3）（4分） 短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分） 答：句子aaa对应的两颗语法树为：
因此，文法是二义文法 四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分） 答：对应的NFA为：（6分） 状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分） 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T)
编译原理考试题及答案汇总 一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_C____。
编译原理考试题及答案汇总一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式 M 1 和 M 2 等价是指__C_。 A． M1和M2的状态数相等B． M1和M2的有向边条数相等 C． M1和M2所识别的语言集相等 D． M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A． xyx B． (xyx)* C．xnyxn(n≥0) D． x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言 C．编译方法 D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表 D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧C． AB∨┐CD∨∧ D．A┐B∨∧CD∨8. 优化可生成__D___的目标代码。 A．运行时间较短B．占用存储空间较小 C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱 B．删除归纳变量C．删除多余运算 D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x 3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4．语法分析时必须先消除文法中的左递归。X 6．逆波兰表示法表示表达式时无须使用括号。R 9．两个正规集相等的必要条件是他们对应的正规式等价。 X 1．编译程序是对高级语言程序的编译执行。X
编译原理复习题 一、填空题： 1、编译方式与解释方式的根本区别在于（是否生成目标代码）。 2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。 3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。 4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。 5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。 6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。 7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。 8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。 9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。 10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。 11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。 14、在编译程序中安排中间代码生成的目的是（便于代码优化）和（便于目标程序的移植）。 15、表达式-a+b*(-c+d)的逆波兰表示为（a-bc-d+*+ ）。 16、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为（aabcde/↑*f/+:= ）。 18、文法符号的属性有（继承属性）和（综合属性）两种。 19、一个文法符号的继承属性是通过语法树中它的（兄弟结点与父）结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。
二填空题 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两 种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为（7）。 5．文法符号的属性有综合属性和（8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，j]的地址计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 答案 (1) 栈式动态存储分配(2) 堆式动态存储分配 (3) 左(4) 语法分析(5) 目标代码生成 (6) 表格管理 (7) xyz*ab+/+ (8) 继承属性 (9) a+(i-1)*20+j-1 (10) 基本块 8 词法规则通常可以用____正规式________，正规文法、____自动机________描述；语法规则通常用___2型文法___来描述；语义规则通常用__属性文法_____来描述。
9 编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段。 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）
一、选择题（每个选择题 2 分，共 20 分） 1 ．文法 G 产生的⑴ 的全体是该文法描述的语言。 A ．句型 B. 终结符集 C. 非终结符集 D. 句子 2 ．若文法 G 定义的语言是无限集，则文法必然是⑵ ： A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的 3 ． Chomsky 定义的四种形式语言文法中， 0 型文法又称为⑶ 文法； 1 型文法又称为⑷ 文法； 2 型语言可由⑸ 识别。 A ．短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法 E 图灵机 F 有限自动机 G 下推自动机 4 ．一个文法所描述的语言是⑹ ；描述一个语言的文法是⑺ 。 A ．唯一的 B 不唯一的 C 可能唯一，好可能不唯一 5 ．数组的内情向量中肯定不含有数组的⑻ 的信息 A．维数 B.类型 C.维上下界 D.各维的界差 6 ．在下述的编译方法中，自底向上的方法有⑼ ，自顶向下的分析方法有⑽ 。 ①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析 ⑥ SLR（k）分析⑦ LL（k）分析⑧LALR（K）分析 A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧ 二、简答题（每小题 5 分，共 20 分） 1 ． LL （ 1 ）分析法对文法有哪些要求？ 2 ．常见的存储分配策略有几种？它们都适合于什么性质的语言？ 3 ．常见循环优化都有哪些项目？ 4 ．什么是活动记录？它主要由哪些内容构成？ 五、（ 12 分）已给文法 G[S] ：S → SaP | Sf | P P → qbP | q 将 G[S] 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。 七、（ 8 分）将下面的条件语句表示成逆波兰式和四元式序列： if a>b then x:=a+b*c else x:=b-a; 八、（ 8 分）给定基本块： A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。参考答案： 一、⑴ D ⑵ A ⑶ A ⑷ C ⑸ G. ⑹ A ⑺ B ⑻ A ⑼ F ⑽ A 二、 1 ．对于 G 中的每个产生式A →γ 1 | γ 2 | … | γ m ，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即 FIRST( γ i ) ∩ FIRST( γ j )= φ（1 ≤ i ，j ≤ m ；i ≠ j ）
参考答案 一、单项选择题(共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 ．L 0?L 1?L 2?L 3 B ．L 3?L 2?L 1?L 0 C ．L 3=L 2?L 1?L 0 D ．L 0?L 1?L 2=L 3 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中的一条产生式。
第一章引论 一.单项选择题 1. 如果一个编译程序能产生不同于其宿主机的机器代码，则称它为：___________________ 。 a. 诊断编译程序 b. 优化编译程序 c. 交叉编译程序 d. 可变目标编译程序 2. 编译程序将高级语言程序翻译成_________ 。 a. 机器语言程序或高级语言程序 b. 汇编语言或机器语言程序 c. 汇编语言程序或高级 语言程序d. 中间语言程序或高级语言程序 3. 下面的四个选项中，__________不是编译程序的组成部分。 a. 词法分析程序 b. 代码生成程序 c. 设备管理程序 d. 语法分析程序 4. 现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须借助于一个_______把各个目标模块，包括系统提供的库模块连接在一起，确定程序变量或常 数在主存中的位置，装入内存中制定的起始地址，使之成为一个可运行的绝对指令代码的程序。 a. 重定位程序； b. 解释程序； c. 连接装配程序； d. 诊断程序； 5. 从编译程序的角度说，源程序中的错误通常分为________两大类。 a. 词法错误和语法错误； b. 语法错误和语义错误； c. 编辑错误和诊断错误； d. 词法错误和语义错误； 6. 下面对编译原理的有关概念正确描述的是：____。 a. 目标语言只能是机器语言 b. 编译程序处理的对象是源语言。 c. Lex是语法分析自动生成器 d. 解释程序属于编译程序 7. 目标代码生成阶段所生成的目标代码的形式不可能是____。 a. 绝对指令代码 b. 可充定位的指令代码。 c. 汇编指令代码 d. 三地址代码 8. 语义错误是指源程序中不符合语义规则的错误，不包括：____ a. 非法字符错误 b. 类型不一致错误。 c. 作用域错误 d. 说明错误
《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个2分，共20分） 1．编译程序是对高级语言程序的解释执行。(× ) 2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 4．语法分析时必须先消除文法中的左递归。(×) 5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 6．逆波兰表示法表示表达式时无须使用括号。(√ ) 7．静态数组的存储空间可以在编译时确定。(×) 8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。(× ) 10．一个语义子程序描述了一个文法所对应的翻译工作。(×) 二、选择题(请在前括号选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值D．( ) 单词自身值 2．正规式 M 1 和 M 2 等价是指_____。 A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等
3．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。 A．( )最左推导和最右推导对应的语法树必定相同 B．( ) 最左推导和最右推导对应的语法树可能不同 C．( ) 最左推导和最右推导必定相同 D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。 A．( )源程序B．( ) 目标语言 C．( ) 编译方法 D．( ) 以上三项都是 6．四元式之间的联系是通过_____实现的。 A．( ) 指示器B．( ) 临时变量 C．( ) 符号表 D．( ) 程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。 A. ( ) ┐AB∨∧CD∨B．( ) A┐B∨CD∨∧ C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨ 8. 优化可生成_____的目标代码。 A．( ) 运行时间较短B．( ) 占用存储空间较小C．( ) 运行时间短但占用存空间大D．( ) 运行时间短且占用存储空间小 9．下列______优化方法不是针对循环优化进行的。 A. ( ) 强度削弱 B．( ) 删除归纳变量 C．( ) 删除多余运算 D．( ) 代码外提
一、回答下列问题：(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
编译原理试题及答案 <高级版> 一、对于文法 G[S] ： S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB ⑴ (3 分 ) 请写出三个关于 G[S] 的句子； ⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型？试证明你的结论。 ⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。 二、请构造一个文法，使其产生这样的表达式 E ：表达式中只含有双目运算符 + 、 * ，且 + 的优先级高于 * ， + 采用右结合， * 采用左结合，运算对象只有标识符 i ，可以用括号改变运算符优先级。要求给出该文法的形式化描述。 三、设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。 ⑴试写出描述 L 的正规表达式； ⑵构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。 四、给定文法 G[S] ： S → AB A → a B | bS | c B → AS | d ⑴ (6 分 ) 请给出每一个产生式右部的 First 集；
⑵ (3 分 ) 请给出每一个非终结符号的 Follow 集； ⑶ (8 分 ) 请构造该文法的 LL(1) 分析表； ⑷ (8 分 ) 什么是 LL(1) 文法？该文法是 LL(1) 文法吗？为什么？ 五、给定文法 G[S] ： S → SaA|a A → AbS|b ⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵请构造该文法的 LR(0) 分析表。 ⑶什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？ 六、给定下列语句： if a+b>c then x := a*(b-c) + (b*c-d)/e ⑴写出其等价的逆波兰表示； ⑵写出其等价的四元式序列。 七、已知下列 C 语言程序： int * f() { int a = 100; return &a; } main()
一． 填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静 态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址 计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一 7． 如果在文法G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导 C ． 该句子有两个不同的最右推导 D ． 该句子有两棵不同的语法树
编译原理试题A 一、单项选择题（每题1分，共20分） 1、哪个不是编译系统的组成部分（C ） A．词法分析器 B. 代码生成器 C．设备管理程序 D. 语法分析器 2. 设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是什么 （ B ） A．词法分析 B. 语法分析 C．语义分析 D. 代码生成 3. 下面不能用于对文法进行描述的是（A ） A．源语言 B. EBNF C．BNF D. 语法图 4. 设有文法G[S]: S→S1|S0|Sa|Sc|a|b|c，下列符号串中不是该文法的句子的是 （A ） A．ab0 B. a0c01 C．aaa D. bc10 5. 文法G[S]: S→aA A→bB B→a|aS ,则L(G)为（C ）A．{(ab)n a|n≥1} B. {a (ba)n|n≥1} C．{(aba)n|n≥1} D. {(aba)n|n≥0} 6. 哪个不是DFA的构成成分（B ） A．有穷字母表 B. 初始状态集合 C．终止状态集合 D. 有限状态集合 7.词法分析器的输入是（B ） A．单词符号串 B.源程序C．语法单位 D.目标程序 8.在词法分析阶段不能识别的是（C ）A．标识符 B. 运算符C．四元式 D. 常数 9.设有一段C语言程序 while(i&&++j) { c=2.19; j+=k;
i++; } ,经过词法分析后可以识别的单词个数是（B ）A．19 B.20 C．21 D.23 10．自上而下语法分析的主要动作是（B ）A．移进 B. 推导C．规约 D. 匹配 11.下面不属于LL(1)分析器的组成部分是（D ）A．LL(1)总控程序 B. LL(1)分析表 C．分析栈 D.源程序串 12.设有文法G[S]为 S→AB|bC，A→ε|b，B→ε|aD，C→AD|b，D→aS|c 则FOLLOW(A)为（A ）A．{a,c,#} B.{c,#} C．{a,#} D.{#} 13.设有文法G[S]: S→Ap|Bq，A→a|cA，B→b|dB，则FIRST(Ap)为（ C ）A．{p,q} B. {b,d} C．{a,c} D. 其他 14.自下而上语法分析的主要分析动作是（D ）A．推导 B. 规约C．匹配 D. 移进-规约 15.算法优先分析中，可规约串是（C ）A．句柄B．活前缀C．最左素短语D．素短语16. 设有文法G={{S},{a},{S→SaS|ε},S}，该文法是（B ） A．LL(1)文法B C．SLR(1)文法D．算法优先文法 17、中间代码生成时所以据的是（C ）A．语法规则B．词法规则C．语义规则 D．等价变换规则 18、给定文法G: E→E+T|T，T→T*F|F，F→i|(E) 则L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为（C）A．iii*i++B．ii+iii**+ C．ii+ii*i*+ D．其他 19．在编译程序中与生成中间代码的目的无关的是（B）A．便于目标代码优化B．便于存储空间的组织 C．便于目标代码的移植D．便于编译程序的移植
2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。 3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 4、已知文法G(S)及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么 5、已知文法G(S) S→bAa A→(B | a B→Aa) 写出句子b(aa)b的规范归约过程。 6、已知文法G[S] S→S*aF | aF | *aF F→+aF | +a 消除文法左递归。 1、设文法G(S): S→^ | a | (T) T→T,S | S ⑴消除左递归； ⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表 2.语句if E then S (1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 4.设某语言的for语句的形式为 for i:＝E(1) to E(2) do S 其语义解释为 i:＝E(1) LIMIT:＝E(2) again: if i＜＝LIMIT then Begin S; i:＝i＋1 goto again End; （1）写出适合语法制导翻译的产生式； （2）写出每个产生式对应的语义动作。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S (1) 给出句子(a,(a,a))的最左推导； (2) 给出句型((T,S),a)的短语, 直接短语，句柄。 8.对于C 语言do S while E语句 (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集合； ⑶构造预测分析表。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i (1) 给出句型(i+i)*i+i的最左推导及画出语法树； (2) 给出句型(E+T)*i+F 的短语，素短语和最左素短语。 答案： (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) C→if E then S→CS(1) (2) C→if E then {BACK, NXQ); :=} S→CS(1) {:=MERG, S(1). Chain)} 4. (1) F→for i:=E(1) to E(2) do S→FS(1) (2)F→for i:=E(1) to E(2) do {GEN(:=, E(1).place, _, entry(i)); :=entry(i);