编译技术命题指导意见教学内容知识点及题型
第一章编译器概述A （1）编译的阶段划分[选择题2分]
[1] 编译程序绝大多数时间花在( )上。
A. 出错处理
B. 词法分析
C. 目标代码生成
D. 符号表管理
答案：D
[2] ( ) 和代码优化部分不是每个编译程序都必需的。
A. 语法分析
B. 中间代码生成
C. 词法分析
D. 代码生成
答案：B
[3] 编译程序前三个阶段完成的工作是( )。
A. 词法分析、语法分析和代码优化
B. 代码生成、代码优化和词法分析
C. 词法分析、语法分析和语义分析
D. 词法分析、语法分析和代码生成
答案：C
（2）遍的概念[填空题2分]
[1] 编译阶段的活动常用一遍扫描来实现，一遍扫描包括和。
答案：读一个输入文件写一个输出文件
[2] 将编译程序分成若干个“遍”是为了________。
答案：使程序的结构更加清晰
[3] 编译器从逻辑上可以分为7个阶段，其中，可以作为一个后端遍的是___________阶段。答案：代码生成
（3）前端和后端的划分[简答题5分]
[1] 什么是前端？[5分]
答案：编译器分成分析和综合两大部分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。[2] 什么是后端？[5分]
答案：编译器分成分析和综合两大部分。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。
[3] 什么是前端？什么是后端？[5分]
答案：编译器分成分析和综合两大部分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。
第二章2.1 2.2 词法记号的定义及描述B （1）词法分析器的功能[选择题2分]
[1] 词法分析程序的输出结果是（）。
A. 单词的种别编码
B. 单词在符号表中的位置
C. 单词的种别编码和单词属性值
D. 单词的单词属性值
答案：C
[2] 词法分析器用于识别_____。
A. 字符串
B．语句
C．单词
D．标识符
答案：C
[3] 扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即（）。
A．字符B．单词C．句子D．句型
答案：B
（2）词法记号概念及属性[填空题2分]
[1] 词法记号是由和构成的二元组。
答案：记号名属性值
[2] 词法单元是源程序中匹配一个的字符序列。
答案：记号模式
[3] 影响语法分析的决策，影响记号的翻译。
答案：记号名属性
（3）正规式与语言的对应关系[选择题2分]
[1] 下面文法（）和正规表达式a*b描述的语言相同。
A. S→ab | aSb
B. S→b | aS
C. S→a | aSb
D. S→a | Sb
答案：B
[2] 最多包含两个a的{a,b}上的语言（）。
A. (a|ε)b*(a|ε)
B. b*ab*ab*|b*ab*
C. b*(a|b*)(a|b*)b*
D. b*(a|ε)b*(a|b*)b*
答案：D
[3] 与(a|b)*等价的正规式是（）。
A. (a*|b*)*
B. (a|b)+
C. (ab)*
D. a*|b*
答案：A
第二章2.3.1,2.3.2 NFA,DFA C （1）NFA与DFA的概念[选择题2分]
[1] 有如图所示的有穷自动机，与之等价的正规式为（）。
A. (0|1)*(000|111)(0|1)
B. (0|1) (000|111)(0|1)
C. (0|1)*(000|111)(0|1) *
D. Ａ，B ，C选项都不正确
答案：C
[2] 对于NFA和DFA模型说法错误的是（）。
A. DFA是NFA的特殊形式
B. DFA与NFA的状态转换完全相同
C. 都有唯一的开始状态
D. 都可以有多个接受状态
答案：B
[3] 对于DFA模型，说法错误的是（）。
A. DFA从任何状态出发，对于任何输入符号，可有多个转换
B. 任何状态都没有ε转换
C. DFA有唯一的开始状态
D. DFA 可以有多个接受状态 答案：A
（2）NFA 的构造 [简答题 10分]
[1] 设有非确定的有自限动机NFA M=({A ，B ，C}，{0，1}，δ，{A}，{C})，其中： δ (A ，0)={C} δ (A ，1)={A ，B} δ (B ，1)={C} δ (C ，1)={C}。请画出状态转换距阵和状态转换图。 答案：
状态转换距阵为：
δ 0 1 A C A ，B B ? C C
?
C
状态转换图为：
[2] 构造正规式相应的 NFA : 1(0|1)*101。 答案：
A B 1
C 1
1 0
1
1
[3] 为（（ε|a）b*）* 构造非确定的有限自动机，给出它们处理输入串ababbab的转换序列。答案：
输入串ababbab的转换序列：
0 1456789 145678 789 1456789 10 或者0 1456789 1456789 1236789 1456789 10
（3）NFA转化为DFA [简答题10分]
[1] 设 ={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。
答案：构造相应的正规式：(0|1)*1(0|1)
NFA:
确定化：
I 0I
1I
{0,1,2} {1,2} {1,2,3} {1,2} {1,2} {1,2,3} {1,2,3} {1,2,4} {1,2,3,4} {1,2,4} {1,2} {1,2,3} {1,2,3,4}
{1,2,4}
{1,2,3,4} 、
[2] 构造正规式 1(0|1)*101 相应的DFA 。 答案：先构造NFA ：
确定化：
重新命名，令AB为B、AC为C、ABY为D得：所以，可得DFA为：
[3] 对于下图所示NFA，回答下列问题：
（1）用正规式描述该有限自动机所表示的语言。（2）由NFA转为DFA。
（3）构造最简DFA。
答案：
（1）(a|b)*a(a|b)*
（2）
（3）
（4）DFA的化简[简答题10分]
[1] 已知NFA= （{x,y,z},{0,1},M,{x},{z} ），其中：
M(x,0)={z}, M(y,0)={x,y}, M(z,0)={x,z}, M(x,1)={x}, M(y,1)= φ ,M(z,1)={y}, 构造相应的DFA并最小化。
答案：根据题意有NFA图:
下表由子集法将NFA转换为DFA：
面将该DFA最小化：
(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}
(2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。
(3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。
(4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。
(5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA 如下：
[2] 给定下列自动机：
把此自动机转换为确定自动机DFA。
答案：
有状态矩阵如图：
从而可得DFA 如图：
[3] （1）将下图中的NFA M 确定化为DFA M ’。 （2）将DFA M ’化简。
01
a
a b
a
答案： 确定化:
a b {0} {0,1} {1} {1}
{0}
---
{0，1}
{0,1} {1}
状态编号 a b 0 1 2 2 0 --- 1
1
2
a -->
a a
b b
未简化的DFA
最小化：
分为：终态集{0,1} 非终态集{2} {0,1}a ={1} {0,1}b = {2}
所以：{0,1} = ｛0｝ ｛2｝ = ｛1｝
a -->
b a
0 1
2
1
第二章2.4,2.5 词法分析器的生成器; 第二章习题D （1）直接从语言构造DFA [简答题5分]
[1] 写出能产生字母表{x,y}上的不含两个相邻的x,且不含两个相邻的ｙ的全体符号串的有
限状态自动机。
答案：
2
1
x
y
x
y
[2] 处于/* 和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转
换图。
答案：
[3] 有语言L={w|w ∈(0,1)+，并且w 中至少有两个1 ，又在任何两个1之间有偶数个
0 }，试构造接受该语言的确定有限状态自动机。
答案：
1 2 4
start
5
2
others
others
/ * *
*
/
（2）Lex 的功能[填空题2分]
[1] Lex是从基于正规式的描述来构造。
答案：词法分析器
[2] Lex程序包含三部分：、和辅助函数。
答案：声明翻译规则
[3] 由Lex建立的分析器通常作为分析器的一个子程序。答案：词法语法
第三章 3.1上下文无关文法E （1）上下文无关文法定义[选择题2分]；
[1] 一个上下文无关文法G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，
一个开始符号，以及一组（）。
A. 句子
B. 句型
C. 单词
D. 产生式
答案：D
[2] 文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（）。
A. 短语文法
B. 正则文法
C. 上下文有关文法
D. 上下文无关文法
答案：D
[3] 文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。
A. 短语文法
B. 正则文法
C. 上下文有关文法
D. 上下文无关文法
答案：A
（2）最左推导、最右推导[简答题5分]；
[1] 文法
S->a|^|(T)
T->T,S|S
对(a,(a,a) 和(((a,a),^,(a)),a) 的最左推导。
答案：
对(a,(a,a)的最左推导为：
S=>(T) =>(T,S) =>(S,S) =>(a,S)
=>(a,(T)) =>(a,(T,S)) =>(a,(S,S))
=>(a,(a,S)) =>(a,(a,a))
对(((a,a),^,(a)),a) 的最左推导为：
S=>(T) =>(T,S) =>(S,S) =>((T),S)
=>((T,S),S) =>((T,S,S),S) =>((S,S,S),S)
=>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S)
=>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S)
=>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S)
=>(((a,a),^,(a)),a)
[2] 设文法G[E]:
E →RP|P
P →(E)|i
R →RP+| RP* |P+|P*
对i+i*(i+i)的最右推导。
答案：E? RP ? R(E) ? R(RP) ? R(Ri) ? R(P+i) ? R(i+i) ? RP*(i+i) ? Ri*(i+i)
? P+i*(i+i) ? i+i*(i+i
[3] 考虑文法S->aSbS | bSaS |ε
（a）为句abab构造两个不同的最左推导，以此说明该文法是二义的。（b）为abab构造对应的最右推导。
答案：
（3）分析树[简答题5分]；
[1] 考虑文法S->aSbS | bSaS |ε
（1）为abab构造对应的分析树。
（2）这个文法产生的语言是什么？
答案：
（1）
（2）该文法产生a、b 个数相等的ab 串（含空串）
[2] 对于文法G(E):
E→T|E+T
T→F|T*F
F→(E)|i
写出句型(T*F+i)的最右推导并画出语法树。
答案：
（1）E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i) （2）语法树如右图。
[3] 令文法G[S]为：
S→AB
A→aAb | ab
B→b,
（1）G[S]定义的语言L(G)是什么？
（2）给出句子aabbb的最左推导，并给出其语法分析树。
答案：
（1）S→abB→abb
S→aAbB→aabbB→aabbb
S→aAbB→aaAbbB→aaabbbB→aaabbbb
E
T
F
( E )
E + T
F
i
T
T * F
……
S→a n b m(n>=0,m>=1)
（2）s →AB→aAbB→aabbB→aabbbb
/.
（4）二义性概念[选择题2分]
[1] 如果文法G是无二义的，则它的任何句子α（）。
A. 最左推导和最右推导对应的语法树必定相同
B. 最左推导和最右推导对应的语法树可能不同
C. 最左推导和最右推导必定相同
D. 可能存在两个不同的最左推导，但它们对应的语法树相同
答案：A
[2] 如果一个文法G是无二义性文法，对于任何一个句子，该句子（）。
A. 可能存在两个不同的最左推导
B. 可能存在两个不同的最右推导
C. 最左推导和最右推导不同
D. 仅存在一个最左推导和一个最右推导
答案：D
[3] 若文法G 定义的语言是无限集，则文法必然是（）。
A. 递归的
B. 前后文无关的
C. 二义性的
D. 无二义性的
答案：A
第三章 3.2 语言和文法F （1）消除左递归[填空题2分]；
[1] 一个文法是左递归的，如果它有非终结符A，对某个串a，存在推导。
答案：A=>+Aa
[2] 的分析方法不能用于左递归文法，因此需要消除左递归。
答案：自上而下
[3] 由形式为A->Aa的产生式引起的左递归称为。
答案：直接左递归
（2）提取左因子[填空题2分]；
[1] 提取左因子用于产生适合于的文法。
答案：自上而下
[2] A->aB|aC，经过提取左因子，原来的产生式成为和。
答案：A->aA’A’->B|C
[3] 对于悬空else的文法
stmt->if expr then stmt else stmt
| if expr then stmt
| other
提取左因子后的文法成为和。
一、填空题|（每题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____。
一、填空题（每空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
致谢： 2005级周朝丽、丛志环、张云华、周娇、陈亮、陶锌、张世强等同学不仅对讲义的进一步完善提出了宝贵的意见和建议，而且提出的许多富有探讨性的问题，不仅令我进一步思考，同时也令讲义的许多内容进一步丰富，在此，本人、现在已经看到、未来将会看到该讲义的人对各位的“答疑解惑”表示由衷的谢意！ 参考书目： 1.编译原理，Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman著，李建中，姜守旭译。机械工 业出版社，2003 Compilers Principles, Techniques, and Tools（英文版名字） 2.编译原理及实践，（美）Kenneth C. Louden著，冯博琴等译。机械工业出版社，2000 Compiler Construction: Principles and Practice （英文版名字） 3.编译原理习题与解析(第2版)/伍春香编著-.--北京:清华大学出版社,2006 4.编译原理=Compiling Principle/周经野，张继福主编-.--武汉:武汉理工大学出版社,2003 5.程序设计语言编译方法. 肖军模编著. 大连理工大学出版社，2000。 6.程序设计语言编译原理/陈火旺等编.--北京:国防工业出版社,1984 7.编译方法/金成植编.--北京:高等教育出版社,1984 8.编译原理/蒋立源主编.--西安:西北工业大学出版社,1993.8 9.编译原理和技术/陈意云, 马万里编译.--安徽:中国科学技术大学出版社,1989.12 10.编译原理及其习题解答/何炎祥...[等]编著-.--武汉:武汉大学出版社,2004。 11.形式语言与自动机理论 12.FORTRAN语言程序设计，谭浩强、田淑清编著，高等教育出版社，1987年5月。 13.PASCAL程序设计，郗曼丽编著，陕西科学技术出版社。 14.讲义的一些部分来源于互联网上的多种资源，其链接难以一一提供，在此，谨向大家 致以真诚地敬意和诚挚的谢意，感谢大家通过互联网提供的极为有益的帮助和指导。 1
编译原理复习题 一、填空题： 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.根据优化所涉及的程序范围，可将优化分成为（），（）
编译原理课程设计 自顶向下语法分析器 学院（系）：计算机科学与技术学院学生姓名：xxxxxxxxx 学号：xxxxxxxxx 班级：电计1102 大连理工大学 Dalian University of Technology
目录
1 系统概论 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示： 图1 语法分析器在编译程序中的地位 语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。 自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。 自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。 2 需求分析 以前，人们对语法的分析都建立在人工的基础上，人工分析虽然能够做到侧类旁推，但终究人力有限，再精密的分析都会出现或多或少的错误。为减少因人为产生的错误，并加快
网络高等教育 本科生毕业论文（设计） 题目：我国中小企业内部控制研究 学习中心：江苏徐州沛县学院奥鹏学习中心[17] 层次：专科起点本科 专业：会计学 年级： 2013年春季 学号： 131376322745 学生：刘雪 指导教师：钟建勋 完成日期： 2015年 01月24日
内容摘要 目录 1.1 基本要求 (2) 1.2 封面格式 (2)
1.3 内容摘要 (3) 1.4 目录 (3) 1.5 论文正文 (3) 1.6 定义章节标题格式 (3) 1.7 参考文献 (4) 1.7.1 标题：“参考文献” (4) 1.7.2 参考文献说明 (4) 1.7.3 参考文献示例 (4) 1.8 其它 (5) 1.8.1 量和单位的使用 (5) 1.8.1 图表及公式的使用 (5) 2 毕业论文的写作规格 (6) 2.1 毕业论文（设计）装订要求 (6) 2.2 毕业论文（设计）内容简述 (7) 参考文献 (7) 附录 (8)
引言 我国的中小企业发迹于二十世纪八十年代的短缺经济，发展于九十年代国有经济的调整时期，近几年来获得了较快的发展。大多数中小企业具有规模较小、业务单一、经营灵活、效率较高等特点。然而，或许正是这些优势导致了它们的诸多劣势：组织结构简单、规章制度缺失、人才缺乏、管理水平不高等，这些特征决定了中小企业内部控制的特征。 ①在经营权和所有权未分离的状况下，中小型企业内部控制结构的建立还有待时日。尽管部分中小企业形式上建立了董事会、监事会，但真正的法人治理结构并未到位，谈不上授权和监管，更谈不上内部控制。②中小企业由于难以获取充分的资源以实现恰当的职责分离，导致一个员工可能同时兼任几个岗位，而这些岗位可能存在不相容性。③管理层控制业务的能力会导致其不恰当地越过控制过程的可能性增大。 内部控制制度是社会生产力发展到一定时期的产物。是当今现代化企业管理十分重要的手段。企业内部控制作为企业生产经营活动的自我调节、自我约束的内在的机制，在企业管理中发挥着举足轻重的作用。企业内部控制机制的建立、健全以及日后实施情况的好坏，足企业能否走上现代化企业的关键。因此，应该在企业内部建立并健全内控制度，并且严格强化实施。下面就是本人对企业内部控制有关问题的思考。
参考答案 一、单项选择题(共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.本实习报告填写的内容要求学生手写，不得打印。 2.封面标题填写生产实习或认识实习等实习类型。 3.实习内容和时间安排是对实习整体安排的记录。 4.实习日记是在实习过程中记录现场所观察到的内容和学习到的知识，必须反映当天的工 作内容。需要填写当天的实习日期、项目、实习内容摘要、工艺流程图、心得体会，重点突出，条理清楚。 5.实习报告是对整个实习内容的回顾和总结，也是考核对实习内容掌握的程度，作为评定 实习成绩的依据之一。包括下列内容：实习时间、地点，实习单位概况，实习目的、内容，工艺流程，生产中存在的问题的分析与合理化建议等，实习体会。 1
表1实习内容和时间安排序号实习内容训练目的实习场所时间安排备注1 2 3 4 5 6 7 8 2 实习日记 地点：日期： 3 实习日记 地点：日期： 4 实习日记 地点：日期： 5 实习日记
6 实习日记 地点：日期：7 实习日记 地点：日期：8 实习日记 地点：日期：9 实习日记 地点：日期：10 实习日记 地点：日期：11 实习日记
12 实习日记 地点：日期：13 实习日记 地点：日期：14 实习日记 地点：日期：15 实习日记 地点：日期：16 实习日记 地点：日期：17 实习日记
18 实习日记 地点：日期：19 实习日记 地点：日期：20 实习日记 地点：日期：21 实习日记 地点：日期：22 实习日记 地点：日期：23 实习日记
24 实习日记 地点：日期：25 实习日记 地点：日期：26 实习日记 地点：日期：27 实习日记 地点：日期：28 实习报告 29 30
《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个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．( ) 代码外提
编译原理试题及答案 <高级版> 一、对于文法 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()
机密★启用前 大连理工大学网络教育学院 2019年秋《编译原理基础》 期末考试复习题 ☆注意事项：本复习题满分共：200分。 一、单项选择题 1、以010结尾的二进制串的正规式为（）。 A．(1|0)*01 B．0*01* C．(1|0)*010 D．0(1|0)*01 2、与(s|t)* (s|t)等价的正规式是（）。 A．s*| t* B．(st)*(s|t) C．(s|t)(s|t)* D．(s|t)* 3、对正规式(a*|b*)+所描述的语言，下列说法准确的是（）。 A．连续个a再加连续个b所组成的串的集合 B．a和b个数相等的串的集合 C．a和b组成的所有串（不含空串）的集合 D．a和b组成的所有串（包含空串）的集合 4、对于DFA模型，说法错误的是（）。 A．DFA从任何状态出发，对于任何输入符号，可有多个转换 B．任何状态都没有ε转换 C．DFA有唯一的开始状态 D．DFA可以有多个接受状态 5、以下说法错误的是（）。 A. NFA的状态集合是无限的 B. NFA的输入符号可能有多个 C. DFA的状态集合是有限的 D. DFA的输入符号可能有多个 6、符号串ab1b2是文法G[A]：A→aB B→bB|b的句子，该句子的句柄是（）。
A．b1B．b2 C．a D．b1b2 7、移进-归约分析为输入串构造分析树是从（）开始的。 A．根结点B．叶结点 C．中间结点D．任一结点 8、下列叙述正确的是（）。 A．任何LL(1)文法都是LR(1)文法 B．任何LL(1)文法都是SLR(1)文法 C．任何SLR(1)文法肯定是LR(1)文法 D．任何LR(1)文法肯定是LALR(1)文法 9、下列叙述正确的是（）。 A．S属性定义属于L属性定义 B．变量类型声明的语法制导定义不是一个L属性定义 C．L属性定义只包含综合属性 D．L属性定义只包含继承属性 10、中间代码生成时所依据的为（）。 A．语法规则B．语法规则 C．语义规则D．等价变换规则 单选题答案 1． A 2． B 3． D 4． A 5． A 6． B 7． B 8． C 9． A 10．C 二、填空题 1、对编译程序而言，输入数据是，输出结果是。 答案：源程序目标程序 2、对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同的那么该文法就称为是二义的。 答案：语法树 3、编译器常用的语法分析方法有和两种。 答案：自底向上、自顶向下 4、程序设计语言的发展带来日渐多变的运行时存储管理方案，主要分为两大类
编译原理试题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．便于编译程序的移植
1.NFA可以用带标记的有向图表示，即状态转换图，结点表示状态，有标记的边代表转换函数。() A.正确 B.错误 答案：A 2.确定的有限自动机从任何状态出发，对于任何输入符号，最多只有一个转换。() A.正确 B.错误 答案：A 3.每一个正规集都可以由一个状态数最少的DFA识别，这个DFA是唯一的。() A.正确 B.错误 答案：A 4.自下而上分析器按从根结点到叶结点的次序来建立分析树。() A.正确 B.错误 答案：B 5.最有效的自上而下和自下而上的分析法都只能处理上下文无关文法的子类。() A.正确 B.错误 答案：A 6.正规式只能表示给定结构的固定次数的重复或者不指定次数的重复。() A.正确 B.错误 答案：A
7.推导的意思是把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。() A.正确 B.错误 答案：A 8.最左推导又称规范推导。() A.正确 B.错误 答案：B 9.分析树是推导的图形表示。() A.正确 B.错误 答案：A 10.分析树的叶结点由非终结符或终结符标记，所有这些标记从左到右构成一个句型。() A.正确 B.错误 答案：A 11.一个文法，如果存在某个句子有不止一棵分析树与之对应，那么称这个文法是二义的。() A.正确 B.错误 答案：A 12.二义文法是至少存在一个句子有不止一个最左(最右)推导的文法。() A.正确 B.错误
答案：A 13.文法二义代表语言一定是二义的。() A.正确 B.错误 答案：B 14.提左因子也是一种文法变换，它用于产生适合于自上而下分析的文法。() A.正确 B.错误 答案：A 15.自上而下分析的文法是为输入串寻找最左推导。() A.正确 B.错误 答案：A 16.正规式M1和M2等价是指()。 A.M1和M2的状态数相等 B.M1和M2的有向边条数相等 C.M1和M2所识别的语言集相等 D.M1和M2状态数和有向边条数相等 答案：C 17.设有文法G[S]:S→S1|S0|Sa|Sc|a|b|c，下列符号串中()不是该文法的句子。 A.ab0 B.a0c01 C.aaa D.bc10 答案：A 18.形式语言中，不包含()。
华中科技大学武昌分校 《编译原理》试卷A 专业班级：_________学号：_________姓名：__________总分 一、单项选择题(共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．词法分析 2．LL(1)文法 3．语法树 4．LR(0)分析器 5．语言和文法 四、简答题(共4小题，每小题5分) （题分 20分） 1．编译程序和高级语言有什么区别? 2．编译程序的工作分为那几个阶段? 3．简述自下而上的分析方法。 4．简述代码优化的目的和意义。 五、综合应用题(共3小题，每小题10分) （题分 30分） 得分 得分 得分
模拟习题1 一、单项选择题 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．产生规则d．词法规则 7、词法分析器的输入是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 解答 1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。 2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。 3、对编译而言，变量既持有左值又持有右值，故选c。 4、编译程序打交道最多的就是各种表格，因此选d。 5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。 6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。 7、b 8、c 9、d 10、c