编译原理练习题
“编译原理”练习题
一、选择题
1、汇编程序是将 a 翻译成 b ,编译程序是将 c 翻译成 d .
a.汇编语言程序
b.机器语言程序
c.高级语言程序
d. a 或者 b
e. a 或者 c
f. b 或者 c
2、下面关于解释程序的描述正确的是 b .
(1) 解释程序的特点是处理程序时不产生目标代码
(2) 解释程序适用于COBOL 和 FORTRAN 语言
(3) 解释程序是为打开编译程序技术的僵局而开发的
a. (1)(2)
b. (1)
c. (1)(2)(3)
d.(2)(3)
3、高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少 (1)e 和 (1)b .其中， (1)e 的目的是使最后阶段产生的目标代码更为高效. 与编译系统相比，解释系统 (2)d .解释程序处理语言时,大多数采用的是 (3)b 方法. (4)a 就是一种典型的解释型语言.
(1): a. 中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化
(2): a.比较简单,可移植性好,执行速度快
b.比较复杂,可移植性好,执行速度快
c.比较简单,可移植性差,执行速度慢
d.比较简单,可移植性好,执行速度慢
(3): a.源程序命令被逐个直接解释执行 b.先将源程序转化为之间代码,再解释执行
c.先将源程序解释转化为目标程序,在执行
d.以上方法都可以
(4) : a. BASIC b. C c. FORTRAN d. PASCAL
4、用高级语言编写的程序经编译后产生的程序叫 b .用不同语言编写的程序产生 b 后,可用 g 连接在一起生成机器可执行的程序.在机器中真正执行的是 e .
a. 源程序
b. 目标程序
c. 函数
d. 过程
e. 机器指令代码
f. 模块
g. 连接程序
h.程序库
5、要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容: c ,
d , f .
a. 汇编语言
b. 高级语言
c. 源语言
d. 目标语言
e. 程序设计方法
f. 编译方法
g. 测试方法
h. 机器语言
6、由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成
(1)d ,
诸阶段的工作往往是 (2)d 进行的.
(1) a. 过程 b. 程序 c. 批量 d.遍
(2) a. 顺序 b. 并行 c. 成批 d.穿插
7、编译过程中,语法分析器的任务就是 b .
(1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的
(3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构
8、编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过 b 这几步.
(1) 编辑 (2) 编译 (3) 连接 (4) 运行
9、编译程序必须完成的工作有 a .
(1) 词法分析 (2) 语法分析 (3) 语义分析
(4) 代码生成 (5) 之间代码生成 (6) 代码优化
a. (1)(2)(3)(4)
b. (1)(2)(3)(4)(5)
c. (1)(2)(3)(4)(5)(6)
d. (1)(2)(3)(4)(6)
e. (1)(2)(3)(5)(6)
10、编译程序是一种 B 。
A. 汇编程序
B. 翻译程序
C. 解释程序
D. 目标程序
11、按逻辑上划分，编译程序第二步工作是 C 。
A. 语义分析
B. 词法分析
C. 语法分析
D. 代码优化
12、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标
代码生成等五个部分，还应包括 C 。
A.模拟执行器
B.解释器
C.表格处理和出错处理
D.符号执行器
13、文法G所描述的语言是 C 的集合。
A.文法G的字母表V中所有符号组成的符号串
B.文法G的字母表V的闭包V*中的所有符号串
C.由文法的开始符号推出的所有终极符串
D.由文法的开始符号推出的所有符号串
14、乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法
是 B 。
A.短语文法
B.正则文法
C.上下文有关文法
D.上下文无关文法
15、文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是
C 。
A. L(G[N])={b i│i≥0}
B. L(G[N])={b2i│i≥0}
C. L(G[N])={b2i+1│i≥0}
D. L(G[N])={b2i+1│i≥1}
16、一个句型中的最左 B 称为该句型的句柄。
可选项有：
A. 短语
B. 简单短语
C. 素短语
D. 终结符号
17、设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V*),则称x是文法G 的一个 B 。
A. 候选式
B. 句型
C. 单词
D. 产生式
18、一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，
一个开始符号，以及一组 D 。
A. 句子
B. 句型
C. 单词
D. 产生式
19、文法G[E]：
E→T∣E＋T
T→F∣T﹡F
F→a∣（E）
该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的 B 。
①（E＋T）②E＋T ③F ④ F﹡(E＋T)
可选项有：
A) ①和③ B) ②和③ C) ③和④ D) ③
20、若一个文法是递归的，则它所产生的语言的句子 A 。
A.是无穷多个
B.是有穷多个
C.是可枚举的
D.个数是常量
21、词法分析器用于识别 C 。
A. 句子
B. 句型
C. 单词
D. 产生式
22、在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是 B 。
A. 非终极符集
B.终极符集
C. 字母表
D. 状态集
23、编译程序中语法分析器接收以 A 为单位的输入。
A. 单词
B. 表达式
C. 产生式
D. 句子
24、在自底向上的语法分析方法中，分析的关键是 A 。
A. 寻找句柄
B. 寻找句型
C. 消除递归
D. 选择候选式
25、在LR分析法中，分析栈中存放的状态是识别规范句型 C 的DFA状态。
A.句柄
B. 前缀
C. 活前缀
D. LR(0)项目
26、词法分析的任务是（A）
A．识别单词 B.分析句子的含义 C.识别句子 D.生成目代码
27、代码优分的目的是（C）
A.节省时间
B.节省空间
C.节省时间和空间
D.把编译程序进行等价交换
28、代码生成阶段的主要任务是（C）
A.把高级语言翻译成汇编语言
B.把高级语言翻译成机器语言
C.把中间代码变换成依赖具体机器的目标代码
D.把汇编语言翻译成机器语言
29、在LR分析法中，分析栈中存放的状态是识别规范句型 C 的DFA状态。
A.句柄
B. 前缀
C. 活前缀
D. LR(0)项目
30、一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 D 。
A. 句子
B. 句型
C. 单词
D. 产生式
二、是非判断题
1、正规文法产生的语言都可以用上下文无关文法来描述。（×）
2、如果一个文法是递归的，则其产生的语言的句子是无穷个。（√）
3、文法的二义性和语言的二义性是两个不同的概念。（√）
4、一个LL( l)文法一定是无二义的。（√）
5、在规范规约中用最左素短语来刻划可归约串。（×）
6、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。（√）
7、编译程序是对汇编程序的翻
译。（×）
8、计算机高级语言翻译成低级语言只有解释一种方式。（×）
9、在编译中进行语法检查的目的是为了发现程序中所有错误。（×）
10、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完
全相同。（×）
11、正则文法其产生式为A→a，A→Bb, A,B∈V N，a、b∈V T。（√）
12、每个文法都能改写为LL(1)文法。（×）
13、递归下降法允许任一非终极符是直接左递归的。（×）
14、算符优先关系表不一定存在对应的优先函数。（√）
15、自底而上语法分析方法的主要问题是候选式的选择。（×）
16、LR法是自顶向下语法分析方法。（×）
18、若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。（×）
19、一个句型的句柄一定是文法某产生式的右部。（√）
20、在程序中标识符的出现仅为使用性的。（×）
21、在程序中标识符的出现仅为使用性的。（×）
三、名词解释题
1、扫描遍：
指编译程序对源程序或中间代码程序从头到尾扫描一次。
2、短语：
设G[Z]是给定文法, w=xuy∈V+，为该文法的句型,如果满足下面两个条件:
① Z xUy；
② U u；
则称句型xuy 中的子串u是句型xuy的短语。
3、简单短语：
设G[Z]是给定文法, w=xuy∈V+，为该文法的句型,如果满足下面两个条件:
① Z xUy；
② U u；
则称句型xuy 中的子串u是句型xuy的简单短语（或直接短语）。
4、句柄：
R
一个句型中的最左简单短语称为该句型的句柄。 5、语法分析：
按文法的产生式识别输入的符号串是否为一个句子的分析过程。
6、活前缀：若S′ αA ω αβω是文法G′中的一个规范推导，G′是G 的拓广文法，符号串γ是αβ的前缀，则称γ是G 的，也是G′的一个活前缀。其中 S'为文法开
始符号。或：可归前缀的任意首部。 7、可归前缀：
是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。 8、LR(0)项目：
把产生式右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。 9、语义规则：
对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。 10、翻译方案：
将属性文法中的语义规则用花括号{ }括起来，插在产生式右部的合适地方，指明语义规则的计算次序，陈述一些细节，得到一种语义动作与语法分析交错的表示方法，以表述语义动作在语法分析过程中的执行时刻，称之为翻译方案。 11、后缀式：
一种把运算量（操作数）写在前面把算符写在后面（后缀）的表示法。即 一个表达式E 的后缀形式可以如下定义：
(1) 如果E 是一个变量或常量，则E 的后缀式是E 自身。
(2) 如果E 是E 1 op E 2形式的表达式，这里op 是任何二元操作符，则E 的后缀式为E 1’
E 2’op，这里E 1’和E 2’分别为E 1和E 2的后缀式。
(3) 如果E 是（E 1）形式的表达式，则E 1的后缀式就是E 的后缀式。
12、过程活动：
一个过程的活动指的是该过程的一次执行。就是说，每次执行一个过程体，产生该过程体的一个活动。 13、活动记录：
为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样一个连续的存储块称为活动记录。 14、活动的生存期：
指的是从执行某过程体第一步操作到最后一步操作之间的操作序，包括执行过程时调用其它过程花费的时间。 15、 基本块的DAG ：
一个基本块的DAG 是一种其结点带有下述标记或附加信息的DAG 。
(1)图的叶结点（没有后继的结点）以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A 的地址，则用addr （A ）作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。
R
(2)图的内部结点（有后继的结点）以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。
(3)图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。
16、S-属性文法：？什么是L-属性文法？它们之间有什么关系？
S-属性文法是只含有综合属性的属性文法。
17、L-属性文法：
L-属性文法要求对于每个产生式A X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：
（1）产生式Xj的左边符号X1,X2…Xj-1的属性；
（2）A的继承属性。
18、语法制导翻译：
语法制导翻译是对前后文无关文法的扩充，即对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序，完成相应的语义分析和翻译工作。
19、词法分析
词法分析的主要任务是从左向右扫描每行源程序的符号，按照记法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示，送给语法分析程序。
四、简答计算题
1、已知文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→（E）|i
①该文法的开始符号（识别符号）是什么？
②请给出该文法的终结符号集合V T和非终结符号集合V N。
③找出句型T+T*F+i的所有短语、简单短语和句柄。
答：①该文法的开始符号（识别符号）是E。
②该文法的终结符号集合V T={+、-、*、/、（、）、i}。
非终结符号集合V N={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;
简单短语为i、T*F、第一个T;句柄为第一个T。
2、已知文法G[S]为：
S→dAB
A→aA|a
B→Bb|ε
① G[S]产生的语言是什么？
② G[S]能否改写为等价的正规文法？
答：① G[S]产生的语言是L(G[S])={da n b m
│n ≥1,m ≥0}。
② G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[S ˊ]为： S ˊ→dA A →aA|aB|a B →bB|b
3、简述DFA 与NFA 有何区别
答：DFA 与NFA 的区别表现为两个方面:一是NFA 可以若干个开始状态，而DFA 仅只一个开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 4、试给出非确定自动机的定义。
答：一个非确定的有穷自动机（NFA ）M 是一个五元组：M=（K ，Σ，S ，P ）。
其中:
1. K 是一个有穷集，它的每个元素称为一个状态；
2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
3. S ﹙K 是一个非空初态集；
4. P 是状态转换函数，是在K ×Σ*→K 的子集的映射，即，P: K ×Σ*→2K ；表明在某状态下对于某输入符号可能有多个后继状态。
5、为正规式（a|b ）*
a(a|b) 构造一个等价的确定的有限自动机。
答：
6、给定下列自动机，将其转换为确定的自动机。
答：(1)消除ε边，得到NFA ：
带―号的结点为终止状态
―
― 带―号的结点为终止状态
其中：开始状态：0
终止状态：2
b
7、 给定下列自动机：
(1)把此自动机转换为确定自动机DFA 。 (2)给出此DFA 的正则表达式。 答：（1）： 有状态矩阵如图：
― ＋ 注：带＋号的结点为初始状态； 带―号的结点为终止状态
a b ?0 01 2 01 01 2 －2 1 2 1 2
a b
?0 0,1 2 1 2 －2 1 2
?
从而可得DFA如图：
极小化后：
（2）此DFA或 a*b（b∣
4-13.消除下列文法
E→E-T∣T
T→T/F∣F
F→( E )∣i
答：
消除文法G[E]的左递归后得到：
E→TE’
E’→ -T E’∣ε
T→FT’
T’→/FT’∣ε
F→( E )∣i
8、在LL(1)分析法中,LL分别代表什么含义?
答:第一个L代表从左到右的扫描，第二个L代表每次进行最左推导。
9、自顶向下分析思想是什么？
答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。
10、自顶向下的缺点是什么？
答：在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。
11、LL（1）文法的定义是什么？
答：一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A的两个不同产生式，A→α,A→β；满足SELECT(A →α)∩SELECT(A →β)=Ф。其中，α、β不能同时ε。
12、什么是文法的左递归？
答：一个文法含有下列形式的产生式之一时：
1)A→Aβ，A∈VN，β∈V*
2)A→Bβ，B→Aα，A、B∈VN，α、β∈V*
则称该文法是左递归的。
13、递归下降法的主要思想是什么？
答：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。
1． Z →C S
2． C →if E then 3． S →A ＝E 4． E →E ∨A 5． E →A 6． A →i
其中：Z 、C 、S 、A 、E ∈V N ； if 、then 、＝、∨、i ∈V T
14、自底向上分析法的原理是什么？
答：在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通
过反复查找当前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。
15、给定文法G[Z]：
a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA 。 b) 构造其SLR （1）分析表。
答：1.首先拓广文法：在G 中加入产生式0．Z ′→Z ，然后得到新的文法G ′，再求G ′的
识别全部活前缀的DFA ：
2． Follow(Z)＝{#}
Follow(C)＝{i} Follow(S)＝{#}
Follow(E)＝{#,∨,then} Follow(A)＝{＝,# ,∨,then }
I 0：Z ′→.Z
Z →.C S
C →.if E then I 1：Z ′→Z . I 2：Z →C .S
S →.A ＝E A →.i
I 3：C →if .E then
E →.E ∨A E →.A A →.i I 4：Z →C S . I 5：S →A .＝E
I 7：C →if E .then
E →E .∨A I 9：S →A ＝.E
E →.E ∨A E →.A A →.i
I 10：C →if E then . I 11：E →E ∨.A
A →.i I 12：S →A ＝E .
E →E .∨A I 13：E →E ∨A .
S →a A A →Ab A →b
0.S ′→S 1.S →aA 2.A →Ab 3.A →b
16、 设有文法G[S]：
求识别该文法所有活前缀的DFA 。 答：
(1).首先拓广文法： 在G 中加入产生式0.S ′→S ，然后得到新的文法G ′
(2).再求G ′的识别全部活前缀的DFA ： 17、语法制导翻译方法的基本思想是什么?
答：在语法分析过程中，每当使用一条产生式进行推导或归约时，就执行该产生式所对应的
语义动作进行属性计算，完成对输入符号串的翻译。
18、在一个属性文法中，对应于每个产生式A →a 都有一套与之相关联的语义规则，每条规则的形式为
b ：＝f （c1,c2…，ck ），其中对于b 的要求是什么？ 答：语义规则中的左部属性变量b 被规定为只能是下述两种变量：
① 对应产生式左部符号的综合属性变量；
②对应产生式右部符号的继承属性变量。
19、对于文法G(E):
E→T|E+T
T→F|T*F
F→(E)|i
1）写出句型(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
20、构造下面文法的LL(1)分析表。
S → a B S | b A S | ε
A → b A A | a
B → a B B | b
答：
五、综合题
1、通过构造识别活前缀的DFA和构造分析表，来证明文法E → E + id | id是SLR(1)文法。
答：先给出接受该文法活前缀的DFA如下：
表中没有多重定义的条目，因此该文法是SLR(1)的。
2、为下面文法构造规范LR(1)分析表，画出像教材上图3.20这样的状态转换图就可以了。
S →V = E | E
V →*E | id
E →V
（2）上述状态转换图有同心项目集吗？若有，合并同心项目集后是否会出现动作冲突？答：
（1）状态转换图如下：
411512713810
3、给定文法：
E → E + id | id
要求：
(a)构造识别活前缀的DFA；
(b)构造分析表,并说明该文法是否为SLR(1)文法；
(c) 假定输入串为id+id+id，请给出分析过程。
答：先给出接受该文法活前缀的DFA如下：
(a):
(b):
构造SLR分析表如下：
表中没有多重定义的条目，因此该文法是SLR(1)的。
编译原理期末考试习题及答案
一、填空题|（每题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、设有文法G[S]： S→N N→D|ND D→0|1|2|…|9 试写出028和4321的最左推导和最右推导过程。 2、证明文法G[S]是二义性文法： S→if E then S else S |if E then S |s E→0|1 3、设有文法G[E]： E→E-T|T T→T/F|F F→i|(E) （1）试写出i/(i-i-i)的推导树。 （2）试写出（F-i）/F的短语、简单短语和句柄。 4、设∑={0,1}，请给出∑上下列语言的文法（1）所有以0开头的串 （2）所有以0开头，以1结尾的串 5、证明文法G1和G2等价 G1：S→0S1，S→01 G2：A→0R，A→01，R→A1 第三章有限状态自动机和词法分析 1、请用中文描述下列正规式表示的正规集 （1）0(0|1)*0 （2）0*10*10*10* 2、试写出∑＝{0，1}上下列集合的正则表达式：（1）所有以1开始和结束的符号串。 （2）恰含有3个1的所有符号所组成的集合。（3）集合{01，1}。
（4）所有以111结束的符号串。 3、试写出∑＝{0，1}上下述集合的正则表达式： （1）试写出非负整数集的正则表达式。 （2）试写出以非5数字为头的所有非负整数集的正则表达式。 4、试将图3.1中所示的有限状态自动机M 最小化。 图3.1 M 的状态转换图 5、设∑＝{a,b}，试构造下述正则表达式的确定性有限状态自动机： （1）a(a|b)*baa （2）(a|b)*bbb * 6、对于下列的状态转换矩阵： （1）分别画出相应的状态转换图。 （2）用自然语言分别描述它们所识别的输入串的特征 7、将图3.2所示的非确定的有限状态自动机确定化和最小化。 图3.2 非确定的有限状态自动机M 第四章 自顶向下语法分析 1、从下列文法中消去左递归。
编译原理第1阶段练习题及答案,这是其中一个阶段共3个阶段。答案在后面
江南大学网络教育第一阶段练习题及答案，这是其中一个阶段共3个阶段。答案在后面 考试科目:《编译原理》第章至第章（总分100分） __________学习中心（教学点）批次：层次： 专业：学号：身份证号： 姓名：得分： 一单选题 (共4题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。) 1. 若一个文法是递归的，则它所产生的语言的句子是（）。（5 分） A. 无穷多个 B. 有穷多个 C. 可枚举的 D. 个数是常量 2. 文法G[A]：A→ε A→aB B→Ab B→a是（）。（5 分） A. 0型文法 B. 1型文法 C. 2型文法 D. 3型文法 3. 词法分析器的输入是（）。（5 分） A. 单词符号串 B. 源程序 C. 语法单位 D. 目标程序 4. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一 个开始符号，以及一组（）。（5 分） A. 句子 B. 句型 C. 单词 D. 产生式 二填空题 (共2题，总分值10分 ) 5. 编译程序的功能可以分解为词法分析、语法分析、__________、中间代码生成、中间代码优 化、目标代码生成。（5 分） 6. 微小语言Micro的单词有下面的几种：标识符、__________、实常数、保留字、__________、 换行符。（5 分）
三简答题 (共2题，总分值20分 ) 7. 给出与正规式R＝1(0|1)*101等价的NFA。（10 分） 8. 写出下面程序经词法分析后的TOKEN表示。 begin var X:real; var J:integer; read(J); J:=J+(J*20); X:=J-1; Write(2*J+X) End（10 分） 四综合计算题 (共2题，总分值50分 ) 9. 已知文法G(S) S→a| (T) T→T，S|S 写出句子((a，a)，a)的规范归约过程及每一步的归约规则和句柄。（25 分）10. 已知文法 G[E] 为： E→T|E+T|E-T T→F|T*F|T/F F→（E）|i ①该文法的开始符号（识别符号）是什么？ ②请给出该文法的终结符号集合 Vt 和非终结符号集合 Vn 。 ③找出句型 T+T*F+i 的所有短语、简单短语和句柄。（25 分）
编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)
编译原理考试题及答案汇总 一、选择 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____。
编译原理期末考试题目及答案
一、填空题（每空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分，共15分) 1．设有文法G[S]: S→(AS)|(b) A→(SaA)|(a) 该文法的句型(((b)a(a))(b))有 C 个直接短语。 A.1 B. 2 C. 3 D. 4 2．如果一个文法满足 D ，则称该文法是二义性文法。 (1) 文法的某一个句子存在两个（包括两个）以上的语法树 (2) 文法的某一个句子存在两个（包括两个）以上的最左推导 (3) 文法的某一个句子存在两个（包括两个）以上的最右推导 (4) 在进行归约时，文法的某些规范句型的句柄不唯一 上述描述中的所有正确描述有： A. (1) B. (1)(2) C. (1)(2)(3) D. (1)(2)(3)(4) 3．构造一个不带回溯的自顶向下语法分析器，要求文法满足 E 。 A.对每个形如A→x1|x2|…|xn的产生式，要求FIRST(xi)与FIRST(xj)的交集为空集(i≠j) B.对每个形如A→x1|x2|…|xn的产生式，若xi* ε，则要求FIRST(xj)与FOLLOW(A)的交集为空集(i≠j) C. 不含左递归 D. A和B同时满足 E. A、B和C同时满足
4、给定文法A→bA|cc，下列符号串中，是该文法的句子的是 C 。 ① cc ② bcbc ③ bcbcc ④ bccbcc ⑤ bbbcc A① B. ①③④⑤ C. ①⑤ D. ①④⑤ 5、若一个句型中出现了某一产生式的右部，则此右部 B 是该句型的句柄。 A.一定 B. 不一定 C. 一定不 D. 无法判断 四、简述题(每题5分，共20分) 1、写一上下文无关文法,它能产生语言}0 n。 n a L m b , =m | {>= # S→A#B A→Aa|ε B→Bb|ε 2、将文法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' | ε 3、什么是文法的二义性？下面的文法是二义的吗？为什么？
编译原理试题及答案3
编译原理复习题 一、填空题： 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.文法与语言的对应关系 思路要点：注意结构拆分 技巧：如何将表示语言的通用字符串形式作适当的“切割”？ 例：已知语言：L1 = {a x b2x c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。 提示：该题实际上要求为相应语言设计上下文无关文法。 一个文法设计好后，严格来说应当证明此文法是否对应于该语言。 解：G[S]：S →AB A →ε | aAbb B →ε | cB 推导过程： S ? AB +? a x Ab2x B /*使用A →aAbb x次*/ ? a x b2x B /*使用A →ε一次*/ ? a x b2x c x B /*使用B →cB x次*/ ? a x b2x c x/*使用B →ε一次*/ 举一反三：已知语言L2 = {a x b2y c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。 解：G[S]：S →AB A →ε | aA B →ε | bBcc 练习：14：写出下列语言对应的文法 (1).{a n b n a m b m|n,m≥0}
2. {1n 0m 0m 0n |n,m ≥0} 3. {1n 0m 0m 0n |n ≥0,m>0} 4. { a n b m c k |n,m,k ≥0} G1: S —>AA G2: S —>AB A —>aAb|ε A —>aAb|ε B —>aBb|ε G: S —>1S0 S —>A A —>0A1 A —>ε G: S →1S0|A S →1S0|0A1 A →0A1|01 A →0A1|ε 2. 给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。 1. 令文法G ［E ］为： Z →bMb M →a|(L L →Ma ） ① 符号串b(Ma)b 是否为该文法的一个句型，并证明。 ② 若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。 1）（5分）证明：S=> bMb=>b(Lb=>b(Ma)b 所以，符号串b(Ma)b 是该文法的一个句型。 （2）（5分）短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma) 练习： （10分）已知文法G[T]： T →T*F | F ；F →F ↑P | P ； P →(T) | i （1）用最右推导法证明β：T*P ↑(T*F) 是G[T]的一个句型； （2）画出β的语法树； （3）写出β的全部短语、直接短语和句柄。 (1) T=>T*F=>T*F ↑P=>T*F ↑(T)=> T*F ↑(T*F) =>T*P ↑(T*F) 证毕。 (2) 如图 T T * F F ↑ P P T * T F ( ) 第3题 语法树 （3）短语：T*P ↑(T*F) ；P ↑(T*F) ；(T*F) ；T*F ；P 直接短语：T*F ；P
期末考试编译原理试卷及答案
一． 填空题（每空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 ． 该句子有两棵不同的语法树
编译原理第七章练习题
第7节习题 一、单项选择题 1、中间代码生成所依据的是。 a.语法规则 b.词法规则 c.语义规则 d.等价变换规则 2、四元式之间的联系是通过实现的。 a.指示器 b.临时变量 c.符号表 d.程序变量 3、后缀式ab+cd+/可用表达式来表示。 a.a+b/c+d b.(a+b)/(c+d) c.a+b/(c+d) d.a+b+c/d 4、表达式（┓A∨B）∧（C∨D）的逆波兰表示为。 a. ┓AB∨∧CD∨ b. A┓B∨CD∨∧ c. AB∨┓CD∨∧ d. A┓B∨∧CD∨ 5 所对应的表达式为。 a.A+B+C+D b.A+(B+C)+D c.(A+B)+C+D d.(A+B)+(C+D) 6、四元式表示法的优点为。 a.不便于优化处理，但便于表的更动 b.不便于优化处理，但节省存储空间 c.便于优化处理，也便于表的更动 d.便于表的更动，也节省存储空间 7、终结符具有属性。 a.传递 b.继承 c.抽象 d.综合 解答 1、选c。 2、四元式之间的联系是通过临时变量实现的，故选b。 3、选b。 4、选b。 5、选d。 6、四元式表示法的优点与间接三元式相同，故选c。 7、选d。 二、多顶选择题 1、中间代码主要有。 a．四元式b．二元式c．三元式d．后缀式e．间接
三元式 2、下面中间代码形式中，能正确表示算术表达式a+b+c 的有 。 a ．ab+c+ b ．abc++ e ．a+b+c 3、在下面的 语法制导翻译中，采用拉链-回填技术。 a ．赋值语句 b ．goto 语句 c ．条件语句 d ．循环语句 4、下列 中间代码形式有益于优化处理。 a ．三元式 b ．四元式 c ．间接三元式 d ．逆波兰表示法 e ．树形表示 法 5、在编译程序中安排中间代码生成的目的是 。 a ．便于进行存储空间的组织 b ．利于目标代码的优化 c ．利于编译程序的移植 d ．利于目标代码的移植 e ．利于提高目标代码的质量 6、下面的中间代码形式中， 能正确表示算术表达式 a ．ab+c* b ．abc*+ c ．a+b*c 7、三地址代码语句具体实现通常有 表示方法。 a ．逆波兰表示 b ．三元式 c ．间接三元式 d ．树形表示 e ．四元式 解答 1、选a 、c 、d 、e 。 2、b 、d 的中间代码不能正确表示a+b+c ，而e 不是中间代码：故选a 、c 。 3、凡涉及到跳转的语句都需要采用拉链——回填技术，故选 b 、c 、d 。 4、选b 、c 。 5、选b 、d 。 6、选b 、e 。 7、选b 、c 、e 。
编译原理期末考试试卷及答案
期末考试试卷（A）卷 一、填空题（每小题2分，共20分） 1、字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的①。 2、设z=abc，则z的固有头是①。 3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫 ①。 4、设∑＝{a,b}，∑上的正规式(a|b)(a|b) 相应的正规集为① 5、NFA的映象f是从"状态×字"映射到"状态子集"，f为①值函数。 6、LR分析是按规范句型的①为可归约串。 7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。 8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规 则的计算必须在定义属性c的语义规则的计算①。 9、对于栈式符号表，引入一个显示嵌套层次关系表- ①表，该表总是 指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。 10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk 的一条通路。如果n1=nk，则称该通路为①。 二、单项选择（每小题2分，共14分） 1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。其中3型文法也称 为（）。 A．上下无关文法 B.正规文法 C．上下文有关文法 D.无限制文法 2、生成非0开头的正偶数集的文法是（）。 A． Z::=ABC B. Z::=ABC C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0 A::=1|2|3|…|9 A::=1|2|3|…|9 C. Z::=ABC|2|4|6|8 D. Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|…|9 A::=1|2|3|…|9 3、简单优先分析法从左到右扫描输入串,当栈顶出现（）时进归约。
编译原理试题及答案
参考答案 一、单项选择题(共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中的一条产生式。
编译原理试题B及答案
编译原理试题B 一、单项选择题（每题1分，共20分） 1、对编译系统有关概念描述正确的是（ B） 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→0S|1A|0，A→1|1S|0B，B→1A|0B，下列符号串中是该文法的句子的是 （）？A．1010001001101 B.0101001110010010 C．1101010011110111 D.1010011101101010 (可画出DFA验证) 5. 文法G[S]: S→aA|bC|a A→aS|bB B→aC|bA|b C→aB|bS ,则不是L(G)句子的是（ B ） A．a100b50ab100 B. a1000b500aba C．a500b60aab2a D. a100b40ab10aa （画出DFA） 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．其他
编译原理考试试题与答案(汇总)
《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个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．( ) 代码外提
编译原理习题及答案(整理后)
第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。
一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a) 例1设有文法G[S]: S →a|（T ）| T →T,S|S （1） 试给出句子(a,a,a)的最左推导。 （2） 试给出句子(a,a,a)的分析树 （3） 试给出句子(a,a,a)的最右推导和最右推导的逆过程(即最左规约)的每一步的句柄。 【解】(1) (a,a,a)的最左推导 S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a) （2）(a,a,a)的分析树 S ( T ) T ， S S T ， S a a (3) (a,a,a)最右推导 最左规约每一步的句柄 S=>(T) 句柄为：(T) =>(T,S) 句柄为：T,S =>(T,a) 句柄为：a =>(T,S,a) 句柄为：T,S =>(T,a,a) 句柄为：第一个a =>(S,a,a) 句柄为：S =>(a,a,a) 句柄为：第一个a 例2已知文法G[Z]: Z →0U|1V U →1Z|1 V →0Z|0 （1） 请写出此文法描述的只含有４个符号的全部句子。 （2） G [Z]产生的语言是什么？ （3） 该文法在Chomsky 文法分类中属于几型文法？ 【解】（1）0101，0110，1010， 1001 （2）分析G[Z]所推导出的句子的特点：由Z 开始的推导不外乎图1所示的四种情形。 图 1文法G[Z]可能的几种推导 Z 1 U Z U Z 1 Z 1 Z 1 V 由Z 推导出10或01后就终止或进入递归，而Z 的每次递归将推导出相同的符号串：10或 01。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01)+ } (3)该文法属于3型文法。 例3 已知文法G=({A,B,C}，{a,b,c}，P，A), P由以下产生式组成: A→abc A→aBbc Bb→bB Bc→Cbcc bC→Cb aC→aaB aC→aa 此文法所表示的语言是什么？ 【解】 分析文法的规则： 每使用一次Bc→Cbcc，b、c的个数各增加一个； 每使用一次aC→aaB或aC→aa, a的个数就增加一个； 产生式Bb→bB、 bC→Cb起连接转换作用。 由于A是开始符号，由产生式A→abc推导得到终结符号串abc；由产生式A→aBbc推导得到B后，每当使用产生式Bb→bB、Bc→Cbcc、bC→Cb、aC→aaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、aaabbbccc、…所以文法描述的语言为{ a n b n c n|n>0}. 例4 构造描述语言L(G[S])={（n）n|n≥0} 的文法。 【解】(1)找出语言的一些典型句子: n=0 ε n=1 ( ) n=2 (()) … 所以, L(G[S])={ ε、( ) (())、((()))、…} (2)分析句子的特点: 只含有(和),(和)的个数相同且对称, 句子中所含的符号数可无限, 句子的个数可无限。 (3)凑规则:由 S→ε|() 得到ε|()，由 A→ (S) 得到 (())，(()) 是在（）的两边再加上一对（）得到，((()))是在(())的两边再加上一对（）得到，…所以将上述产生式合并为S→(S) |ε。 (4)得到文法 G[S]: S→(S) |ε (5)检验:语言所有的句子均可由文法G[S]推导出来, 文法G[S]推导出来的所有终结符号串均为语言的句子. 例5 构造描述语言L(G[S])={a m b n |n>m>0} 的文法。 【解】找出语言的一些典型句子:abb、abbb、…、aabbb、aabbbb、…,语言的句子的特点是仅含有a、b, a在b的左边，b的个数大于a的个数，a的个数至少是1。 单独生成c k, k>1 可用产生式 C→c |Cc 句子中要求b的个数大于a的个数，所以得到文法：编译原理第一章练习和答案