编译原理复习题目集答案

第4章词法分析

重点内容：正规式转化为DFA

a、正规式->NFA

b、NFA -> DFA（子集法）

c、DFA化简（分割法）

题目1：课件例题：

a、为R=(a|b)*(aa|bb)(a|b)*构造NFA

b、从NFA构造DFA的算法

c、化简

题目2：

4.7 例1：构造正规式相应的DFA：1(0|1)*101

按照以下三步：

（1）由正规表达式构造转换系统（NFA）

（2）由转换系统（NFA）构造确定的有穷自动机DFA

（3）DFA的最小化

答：（1）构造与1(0|1)*101等价的NFA

（2）将NFA转换成DFA：采用子集法，即DFA的每个状态对应NFA的一个状态集合：

除X，A外，重新命名其他状态：

1、将M 的状态分成非终态和终态集{X,A,B,C}和{D}。

2、寻找子集中不等价状态{X,A,B,C}=>{X}，{A,B}{C}=>{X}{A}{B}{C}，无需合并。 最后生成

DFA ：

题目3：自习、书本练习4.7，参考答案见《z4 书本练习4.7.doc 》 已知文法G[S]：

S →aA|bQ A →aA|bB|b B →bD|aQ Q →aQ|bD|b E →aB|bF F →bD|aE|b 1、 构由于不可到达，去除E 、F 相关的多余产生式 2、 由新的G[S]构造NFA 如下

5、使用分割法化简以上DFA G：

5.1 令G={(0,1,3,4,6),(2,5)}// 分别为非终态和终态集

5.2 由{0,1,3,4,6}a={1,3}，{0,1,3,4,6}b={3,2,5,6,4}

将{0,1,3,4,6}划分为 {0,4,6}{1,3}，得G={(0,4,6),(1,3),(2,5)}

5.3 由{0,4,6}b={3,6,4}，将之划分为{0},{4,6}，得G={(0),(4,6),(1,3),(2,5)}

5.4 观察后，G中状态不可再分，为最小化DFA。

6、分别用 0，4，1，2代表各状态，DFA状态转换图如下：

造相应的最小的DFA

第5章自顶向下的语法分析

重点内容：LL（1）文法

a、去除左递归

b、LL（1）文法的判定（first、follow、select集）

c、预测分析表

d、使用栈和预测分析表对输入串的分析

题目1：课件例题：消除左递归+判定+分析

算术表达式文法G

E→E+T│T

T→T*F│F

F→(E)│I

d、分析输入串i+i*i#

（1）消除G的左递归得到文法G‘

E→TE '

E'→+TE'│ε

T→FT '

T'→*FT'│ε

F→(E)│i

（2）求出每个产生式的select集,G’是LL(1)文法

SELECT(E→TE' ) = { (,i }SELECT(E'→+TE' ) = { + } SELECT(E'→ε ) = { ),# }SELECT(T→FT' ) = { (,i } SELECT(T'→*FT' ) = { * }SELECT(T'→ε ) = { +,),# } SELECT(F→(E) ) = { ( }SELECT(F→ i ) = { i }

（3）依照选择集合把产生式填入分析表

注：表中空白处为出错

题目2：作业、习题5.1：消除左递归+判定+分析

G[S]:S->a|^|(T) T->T,S|S

d、分析输入串（a,a）#

文法G[S]:S->a|^|(T)，T->T,S|S

(1)给出对(a,(a,a))的最左推导

(2)改写文法，去除左递归

(3)判断新文法是否LL1文法，如是，给出其预测分析表

(4)给出输入串（a,a）#的分析过程，判断其是否文法G的句子。答：（1）对(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))

（2）改写文法为：

FIRST (→,S N) = {, }

FIRST (→ε) ={ε}

FOLLOW (N) ={)}

由于SELECT(N→,S N)∩SELECT(N→ε)={, }∩{)}=?

所以文法是LL(1)的。

（3）预测分析表：

可见输入串（a,a）#是文法的句子。

题目3：复习、书本5.6例1：判定+分析

G[S]：S→aH，H→aMd|d，M→Ab|ε，A→aM|e d、分析输入串aaabd#

（1）判断G[S]是否为LL（1）文法；若是，构造其预测分析表；

Select(H→aMd)={a} , Select(H→d)= {d} ；

Select(M→Ab)= {a,e}, Select(M→ε)= {d,b}；

Select(A→aM)= {a} , Select(A→e)= {e}

相同左部产生式的select集的交集均为空，所以G[S]是LL（1）文法。预测分析表：

（2）分析aaabd#是否G[S]的句子。

使用栈和预测分析表对输入串的分析：

第6章自底向上的语法分析

重点内容：算符优先文法

a、非终结符的firstvt集和lastvt集的计算

b、算符优先关系表

c、使用栈和算符优先关系表对输入串的归约题目1：课件例题：

文法：E→E+T|T

T→T×F|F

F→(E)|I

c、算符优先归约输入串i+i#

（1）求各非终结符的FIRSTVT集与LASTVT集

（2）计算算符优先关系表并说明此文法是否算符优先文法

（3）给出输入串i+i#的算符优先分析过程

优先关系表中无多重定义，此文法是算符优先文法

（3）对输入串i+i#的算符优先分析过程为：

题目2：作业、习题6.1、复习：

文法G[S]:S->a|^|(T) T->T,S|S

c、算符优先归约输入串（a,a）#

文法G[S]:S->a|^|(T)，T->T,S|S

(1)计算G[S]的FIRSTVT、LASTVT

(2)改造算符优先关系表并说明G[S]是否算符优先文法

(3)给出输入串（a,a）#的算符优先分析过程，判断其是否文法G的句子。答：文法展开为：S→a

S→?

S→(T)

T→T,S

T→S

（2）算符优先关系表：

表中无多重入口，所以是算符优先（OPG）文法。

（3）对输入串（a,a）#的算符优先分析过程为：

题目3：自习、书本练习6.4，参考答案见《z6 书本练习6.4.doc》已知文法G[S]：

S→S;G S→G G→G(T) G→H H→a H→(S) T→T+S T→S

c、算符优先归约输入串a;(a+a)#

（1）构造算符优先关系表

FIRSTVT(S)={;}∪FIRSTVT(G) = {; , a , ( }

FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( }

FIRSTCT(H)={a , ( }

FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , ; , a , ( }

LASTVT(S) = {;} ∪LASTVT(G) = { ; , a , )}

LASTVT(G) = { )} ∪ LASTVT(H) = { a , )}

LASTVT(H) = {a, }}

LASTVT(T) = {+ } ∪LASTVT(S) = {+ , ; , a ,} }

LASTVT（S）> ;

; < FIRSTVT（G）

由G→G(T…

LASTVT（G）> (

( < FIRSTVT（T）

由G→…T)

LASTVT（T）> )

由G→…(T)

( = )

由T→T+S

LASTVT（T）> +

+ < FIRSTVT（S）

由H→(S)

( < FIRSTVT（S）

LASTVT（S）> )

( = )

由S-> #S#

#< FIRSTVT（S）

LASTVT（S）> #

# = #

编译原理期末考试习题及答案

一、填空题|（每题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)

编译原理复习题2017(含试卷)

* 编译原理复习题 一．简答题： 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）语法分析的任务是什么？

编译原理试题(卷)汇总-编译原理期末试题(卷)(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____。

四川大学编译原理期末复习总结

一、简答题 1.什么是编译程序 答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义 答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么 答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术 答：优化技术1—删除公共子表达式 优化技术2—复写传播 优化技术3—删除无用代码 优化技术4—对程序进行代数恒等变换（降低运算强度） 优化技术5—代码外提 优化技术6—强度削弱 优化技术7—删除归纳变量 优化技术简介——对程序进行代数恒等变换（代数简化） 优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段 答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 6. 什么是文法 答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么 答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)； 并对静态语义进行审查。 8.代码优化须遵循哪些原则 答：等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么 答：

编译原理期末考试题目及答案

一、填空题（每空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、简答题（或者名词解释） 下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。 注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。（1）简述编译程序的概念及其构成 答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成： （2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。 语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合） 答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序 3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。 6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别： 1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。 （5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符号，S?V N P：产生式集合(有限)。

编译原理试题及答案(期末复习版).pdf

<编译原理>历年试题及答案 一．（每项选择 2 分，共 20 分）选择题 1．将 编译程序分成若干个“遍”是为了_b__。 a.提 高程序的执行效率 b.使程序的结构更加清晰 c. 利用有限的机器内存并提高机器的执行效率 d. 利用有限的机器内存但降低了机器的执行效率 2．构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译方 法 d.以上三项都是 3．变量应 当 c＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持 有左值也不持有右值 4．编译程序绝大多数时间花在 _d___上。 a.出错处理 b.词法分析 c.目标代码 生成 d.管理表格 5．词法分析器的输 出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c.单词 的种别编码和自身值 d.单词自身值 6．正规式 MI 和 M2 等价是指__c__。 a. MI 和 M2 的状态数相等 b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等 d. Ml 和 M2 状态数和有向弧条数相等7．中间代码生成时所依据的是—c。 a．语法规则 b．词法规则c．语义规则 d．等价变换规则 8．后缀式 ab+cd+/可用表达式__b_来表示。 a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 9．程序所需 的数据空间在程序运行前就可确定，称为____c_＿管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10.堆式 动态分配申请和释放存储空间遵守___d____＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 二（每小题 10 分，共 80 分）简答题 1.画出编译程序的 总体结构图，简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.

编译原理复习题--有答案版

1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 答案：S→AB|B A→a|aA B→bBc|bc 2．给出下面语言的相应文法 L1={a n b n c m d m| m,n≥1，n为奇数，m为偶数}。 答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化） (一)相应的正规式为(a|b)*ab(a|b)* (二)①与此正规式对应的NFA为 答案；在自己写的纸上 4、对下面的文法G: E→TE’E’→+E|εT→FT’T’→T|ε F→PF’F’→*F’|εP→(E)|a|b|∧ （1）证明这个文法是LL(1)的。 考虑下列产生式: E’->E|ε T’->T|ε F’->*F’ |ε P->(E) |∧a|b FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法.

计算这个文法的每个非终结符的FIRST和FOLLOW。（8分） 答案：FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#} FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} （3）构造它的预测分析表。（6分） 答案；在手机上 写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。 答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 给出下面语言的相应文法 L1={a n b n a m b m|n,m≥0} 给出下面语言的相应文法 答案：S→AB|A|B|∑ A→aAb|ab B→aBb|ab

编译原理试题及答案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、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。

郑州大学编译原理试卷及答案(往年试题整合)(2)

二填空题 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.根据优化所涉及的程序范围，可将优化分成为（），（）

编译原理期末复习题

3.2是非判断，对下面的述，正确的在述后的括号写T，否则写F。 (1)有穷自动机接受的语言是正则语言。（） (2)若r1和r2是Σ上的正规式，则r1|r2也是。（） (3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。（） (4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a|b)*。（） (5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（） (6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（） 答案 (1) T (2) T (3) F (4) F (5) T (6) T 3.3描述下列各正规表达式所表示的语言。 (1) 0(0|1)*0 (2) ((ε|0)1*)* (3) (0|1)*0(0|1)(0|1) (4) 0*10*10*10* (5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 答案 (1) 以0开头并且以0结尾的，由0和1组成的符号串。 (2) {α|α∈{0,1}*} (3) 由0和1组成的符号串，且从右边开始数第3位为0。 (4) 含3个1的由0和1组成的符号串。{α|α∈{0,1}+，且α中含有3个1 } (5) {α|α∈{0,1}*,α中0和1为偶数} 3.4对于下列语言分别写出它们的正规表达式。 (1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。 (2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 (3) Σ={0,1}上的含偶数个1的所有串。 (4) Σ={0,1}上的含奇数个1的所有串。 (5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。 (6) 不包含子串011的由0和1组成的符号串的全体。 (7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。 答案 (1) 令Letter表示除这五个元音外的其它字母。 ((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))* (2) A*B*....Z* (3) (0|10*1)* (4) (0|10*1)*1

编译原理复习例题

编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。但要求至少要按照作业题的范围复习。) 一选择题 1．编译的各阶段工作都涉及。 [A]词法分析[B]表格管理 [C]语法分析 [D]语义分析 2．型文法也称为正规文法。 [A] 0 [B] 1 [C] 2 [D] 3 3．文法不是LL(1)的。 [A]递归 [B]右递归 [C]2型 [D]含有公共左因子的 4．文法E→E+E|E*E|i的句子i*i+i*i有棵不同的语 法树。 [A] 1 [B] 3 [C] 5 [D] 7 5．文法 S→aaS|abc 定义的语言是。 [A]{a2k bc|k>0} [B]{a k bc|k>0} [C]{a2k-1bc|k>0} [D]{a k a k bc|k>0} 6．若B为非终结符，则 A→.B为。 [A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目 7．同心集合并可能会产生新的冲突。 [A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约 8．代码优化时所依据的是。 [A]语法规则 [B]词法规则 [C]等价变换规则 [D]语义规则 9．表达式a-(-b)*c的逆波兰表示（@为单目减）为。 [A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-* 10．过程的DISPLAY表是用于存取过程的。 [A]非局部变量[B]嵌套层次 [C]返回地址 [D]入口地址

二填空题 1．词法分析阶段的任务式从左到右扫描字符流，从而逐个识别一个个的单词。 2．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是。 3．最右推导的逆过程称为规范归约，也称为最左归约。 4．符号表的每一项是由名字栏和两个栏目组成。 在目标代码生成阶段，符号表是的依据。 三判断题（认为正确的填“T”，错的填“F”） 【】1．同心集的合并有可能产生“归约/归约”冲突。 【】2．一个文法所有句子的集合构成该文法定义的语言。【】3．非终结符可以有综合属性，但不能有继承属性。 【】4．逆波兰表示法表示表达式时无需使用括号。 【】5．一个有穷自动机有且只有一个终态。 【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。 四解答题 1．给定文法G和句型(T+F)*i+T, G: E→E+T|T T→T*F|F F→(E)|i （1）画出句型的语法树； （2）写出句型的全部短语、简单短语和句柄。 解：（略） 2．设有文法G：S→S+S|S*S|i|(S)。 （1）对于输入串i+i*i 给出一个最左推导； （2）该文法是否是二义性文法？请证明你的结论。 解：（1）i+i*i的最左推导： S => S+S => i+S => i+S*S => i+i*S => i+i*i （2）该文法是二义性的。因为对于句子i+i*i可以画出两棵语法树（语法树略）。 3．给出语言{a m b m c n|m≥1,n≥0}的上下文无关文法（2型）。

编译原理试题及答案

参考答案 一、单项选择题(共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中的一条产生式。

(2020年整理)编译原理期末总复习题(含答案).doc

第八节习题一、单项选择题 1、将编译程序分成若干个“遍”是为了 b 。 a．提高程序的执行效率 b．使程序的结构更加清晰 c．利用有限的机器内存并提高机器的执行效率 d．利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握 d 。 a．源程序b．目标语言 c．编译方法d．以上三项都是 3、变量应当 c 。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在 b 上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、 d 不可能是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用 a 可以定义一个程序的意义。 a．语义规则b．词法规则 c．产生规则d．词法规则 7、词法分析器的输入是 a 。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- d 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对 d 。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循 b 。 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 二、多项选择题

编译原理复习题及答案

编译原理复习题及答案一、选择题 1．一个正规语言只能对应( B ) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是( A ) A 正规文法 B 二型文法 3．下面说法正确的是( A ) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A ) A 必要条件 B 充分必要条件 5．下面说法正确的是( B ) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是( A ) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法( B ) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是( A ) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是( A ) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行

11．(A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序?B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序? C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器?C．表格处理和出错处理 ??? D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n(n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C)

编译原理考试试题与答案(汇总)

《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个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．( ) 代码外提