编译原理考试试题1

编译原理试题及答案一、选择题1. 编译器的主要功能是什么？A. 程序设计B. 程序翻译C. 程序调试D. 数据处理答案：B2. 下列哪一项不是编译器的前端处理过程？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，词法分析器的主要作用是什么？A. 识别程序中的关键字和标识符B. 将源代码转换为中间代码C. 检查程序的语法结构D. 确定程序的运行环境答案：A4. 语法分析通常采用哪种方法？A. 自顶向下分析B. 自底向上分析C. 正则表达式匹配D. 直接解释执行答案：B5. 语义分析的主要任务是什么？A. 检查程序的语法结构B. 检查程序的类型安全C. 识别程序中的变量和常量D. 将源代码转换为机器代码答案：B二、简答题1. 简述编译器的工作原理。

答案：编译器的工作原理主要包括以下几个步骤：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

词法分析器将源代码分解成一系列的词素；语法分析器根据语法规则检查词素序列是否合法；语义分析器检查程序的语义正确性；中间代码生成器将源代码转换为中间代码；代码优化器对中间代码进行优化；最后，目标代码生成器将优化后的中间代码转换为目标机器代码。

2. 什么是词法分析器，它在编译过程中的作用是什么？答案：词法分析器是编译器前端的一个组成部分，负责将源代码分解成一个个的词素（tokens），如关键字、标识符、常量、运算符等。

它在编译过程中的作用是为语法分析器提供输入，是编译过程的基础。

三、论述题1. 论述编译器中的代码优化技术及其重要性。

答案：代码优化是编译过程中的一个重要环节，它旨在提高程序的执行效率，减少资源消耗。

常见的代码优化技术包括：常量折叠、死代码消除、公共子表达式消除、循环不变代码外提、数组边界检查消除等。

代码优化的重要性在于，它可以显著提高程序的运行速度和性能，同时降低程序对内存和处理器资源的需求。

四、计算题1. 给定一个简单的四则运算表达式，请写出其对应的逆波兰表达式。

《编译原理》考试试题及答案（附录）一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。

( X )2.一个句型的直接短语是唯一的。

( X )3.已经证明文法的二义性是可判定的。

（ X ）4.每个基本块可用一个DAG表示。

（√）5.每个过程的活动记录的体积在编译时可静态确定。

（√）6.2型文法一定是3型文法。

（ x ）7.一个句型一定句子。

( X )8.算符优先分析法每次都是对句柄进行归约。

(应是最左素短语) ( X )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。

（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。

( x )11.一个优先表一定存在相应的优先函数。

( x )12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )13.递归下降分析法是一种自下而上分析法。

( )14.并不是每个文法都能改写成LL(1)文法。

( )15.每个基本块只有一个入口和一个出口。

( )16.一个LL(1)文法一定是无二义的。

( )17.逆波兰法表示的表达试亦称前缀式。

( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )19.正规文法产生的语言都可以用上下文无关文法来描述。

( )20.一个优先表一定存在相应的优先函数。

( )21.3型文法一定是2型文法。

( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。

( )二、填空题：1.( 最右推导 )称为规范推导。

2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。

4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

5.语法分析器的输入是（），其输出是（）。

6.扫描器的任务是从（）中识别出一个个（）。

<编译原理>历年试题及答案一．（每项选择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/d9．程序所需的数据空间在程序运行前就可确定，称为____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^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b) *a(a|b)构造一个确定的有限自动机。

4．设文法G(S)：S→(L)|a S|aL→L，S|S(1) 消除左递归和回溯；(2) 计算每个非终结符的FIRST和FOLLOW；(3) 构造预测分析表。

编译原理考试试卷一、选择题（每题2分，共20分）1. 编译器的主要功能是将源代码转换成目标代码，以下哪个不是编译器的基本组成部分？A. 词法分析器B. 语法分析器C. 代码优化器D. 运行时环境2. 词法分析器通常不负责以下哪项任务？A. 识别关键字B. 识别标识符C. 进行语义分析D. 去除空白字符3. 语法分析中，递归下降分析是一种：A. 确定性分析方法B. 非确定性分析方法C. 基于语法制导的分析方法D. 基于语法树的分析方法4. LR分析器是用于处理：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. 所有选项都是二、简答题（每题10分，共30分）1. 简述编译原理中词法分析器的作用及其实现方式。

2. 描述语法分析中自顶向下分析和自底向上分析的区别。

3. 解释编译优化的重要性，并给出一个优化的例子。

三、计算题（每题25分，共50分）1. 给定一个简单的算术表达式 "3 + 4 * 2 - 1"，请说明如何使用递归下降分析器来解析这个表达式，并给出相应的语法树。

2. 假设你有一个简单的编译器后端，需要将四元式 "(a, b, +, 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/d6． 一个编译程序中，不仅包含词法分析， _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． 编译过程中 , 语法分析器的任务就是 (1) 分析单词是怎样构成的 (2) (3) 分析语句和说明是如何构成程序的 A ．( ) (2)(3) B ．( ) (2)(3)(4)C ．( ) (1)(2)(3) D ．( ) (1)(2)(3)(4) 12． 编译程序是一种 ___C__。

编译原理一、(5×6分)回答下列问题：1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 2．什么是句柄？什么是素短语？3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 4．运行时的DISPLAY 表的内容是什么？它的作用是什么？ 5．对下列四元式序列生成目标代码：A:=B*C D:=E+F G:=A+D H:=G*2其中，H 是基本块出口的活跃变量， R0和R1是可用寄存器二、(8分)设∑={0，1}上的正规集S 由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA 。

三、(6分)写一个文法使其语言为L(G)={ a n b m a m b n | m,n ≥1}。

四、(8分)对于文法G(E):E →T|E+T T →F|T*F F →(E)|i1. 写出句型(T*F+i)的最右推导并画出语法树。

2. 写出上述句型的短语，直接短语、句柄和素短语。

五、(12分)设文法G(S)：(|*)B B |B A A A |SiA S A →+→→ 1．构造各非终结符的FIRSTVT 和LASTVT 集合； 2．构造优先关系表和优先函数。

六、(9分)设某语言的do-while 语句的语法形式为 S → do S (1) While E其语义解释为：真 假S (1)的代码 E 的代码针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作。

七、(8分)将语句if (A<X) ∧ (B>0) then while C>0 do C:=C+D; 翻译成四元式。

八、(10分) 设有基本块如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)画出DAG图；(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。

一、单选题（每题2分，共20分）1. 编译器的（）阶段可将源程序的字符流收集到若干记号中。

A. 语法分析B. 语义分析C. 代码生成D. 词法分析2. 文法A aA | b属于正则文法，正则文法在乔姆斯基层次中对应于（）文法。

A. 1型B. 2型C. 3型D. 0型3. 某C语言源代码文件包含#include <stdio.h>，（）将对源代码进行处理，把文件stdio.h 包含进去。

A.编译器B.解释器C.汇编器D.预处理器4. LL(1)文法的充要条件是（）。

A.对于文法中的每条产生式Uα1|α2|…|αn，要求FIRST(αi)∩FIRST(αj)＝Φ（i≠j）B.该文法对应的LL(1)分析表中每个项目最多只有一条产生式。

C.A和BD.都不是5. 以下说法中正确的是（）。

A.任何语言都可以描述为一个正则表达式。

B.对于任何一个NFA M，都存在一个DFA M’，满足L(M)= L(M’)。

C.任何一个DFA只有一个终态。

D.NFA的弧上标记只含输入字母表中的元素。

6.合成属性的计算可以通过对语法树进行（）遍历进行。

A. 前序B.中序C.后序D.任意7.乔姆斯基的2型文法是这样一种语言，其产生式限制为（）。

A. α->βB. P->βC. P->a或P->aβD. αPγ->αβγ8. 正则式的“*”读作（）。

A. 并且B.连接C.正则闭包D.闭包9. 编译程序中的语义分析器接受以（）为单位的输入，并产生信息供以后各阶段使用。

A. 语法树B.子程序C.单词D.语句10.文法A->aAb|ab生成的语言是（）。

A. {ab}B.{aAb}C. {anbn|n≥1}D.{anbn|n≥0}二、判断题（每题2分，共10分，对的打√，错的打×）1. 一个LR(0)文法一定是SLR(1)文法。

（）2. 在类型声明文法中，类型属性type是继承属性。

第一章练习题（绪论）一、选择题1．编译程序是一种常用的软件。

A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序是可执行程序。

A) 一定B) 不一定3．编译程序的大多数时间是花在上。

A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。

A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。

5．编译程序各个阶段都涉及到的工作有。

A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。

A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。

A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于。

A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于。

A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。

10．编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题1．文法 G 产生的 (1) 的全体是该文法描述的语言。

A.句型B. 终结符集C. 非终结符集D. 句子2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C)文法；2 型语言可由(G) 识别。

A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。

编译原理考试题及答案一、选择题（每题5分，共20分）1. 编译器的主要功能是什么？A. 代码优化B. 代码翻译C. 代码调试D. 代码运行答案：B2. 下列哪个选项不属于编译器的前端部分？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D3. 在编译原理中，文法的产生式通常表示为：A. A -> αB. A -> βC. A -> γD. A -> δ答案：A4. 下列哪个算法用于构建语法分析树？A. LL(1)分析B. LR(1)分析C. SLR(1)分析D. LALR(1)分析答案：A二、填空题（每空5分，共20分）1. 编译器的前端通常包括词法分析、语法分析和________。

答案：语义分析2. 编译器的后端主要负责________和目标代码生成。

答案：代码优化3. 编译器中的词法分析器通常使用________算法来识别单词。

答案：有限自动机4. 语法分析中，________分析是一种自顶向下的分析方法。

答案：递归下降三、简答题（每题10分，共30分）1. 简述编译器的作用。

答案：编译器的主要作用是将高级语言编写的源代码转换成计算机能够理解的低级语言或机器代码，以便执行。

2. 解释一下什么是语法制导翻译。

答案：语法制导翻译是一种翻译技术，它利用源语言的语法信息来指导翻译过程，使得翻译过程能够更好地理解源代码的语义。

3. 什么是词法分析器？答案：词法分析器是编译器前端的一部分，它的任务是将源代码文本分解成一系列的标记（tokens），这些标记是源代码的最小有意义的单位。

四、计算题（每题10分，共30分）1. 给定一个简单的文法G(E)：E → E + T | TT → T * F | FF → (E) | id请计算文法的非终结符号E的FIRST集和FOLLOW集。

答案：E的FIRST集为{(, id}，FOLLOW集为{), +, $}。

2. 假设编译器在进行语法分析时，遇到一个语法错误的代码片段，请简述编译器如何处理这种情况。

编译原理试题及答案一、选择题1. 编译器的主要功能是什么？A. 将高级语言代码翻译成机器语言代码B. 进行程序调试C. 进行代码优化D. 管理程序运行时的内存分配答案：A2. 词法分析器的主要任务是什么？A. 将源代码分解成多个语句B. 将源代码分解成多个词素C. 检查源代码的语法正确性D. 将词素转换为相应的语法单位答案：B3. 下列哪个是自顶向下的语法分析方法？A. LL(1)分析法B. LR(1)分析法C. LALR(1)分析法D. GLR分析法答案：A4. 语义分析的主要任务是什么？A. 检查程序的语法正确性B. 检查程序的类型正确性C. 将源代码转换为目标代码D. 进行程序的优化答案：B5. 代码生成阶段的主要任务是什么？A. 将语法树转换为目标代码B. 进行程序的优化C. 检查程序的类型正确性D. 将源代码分解成多个词素答案：A二、简答题1. 简述编译过程的主要阶段。

答案：编译过程主要分为四个阶段：词法分析、语法分析、语义分析和代码生成。

词法分析将源代码分解成词素，语法分析检查源代码的语法结构，语义分析检查源代码的语义正确性，代码生成将源代码转换为目标代码。

2. 什么是中间代码？它在编译过程中起到什么作用？答案：中间代码是一种介于源代码和目标代码之间的代码形式，它通常具有更接近于机器语言的特性，但仍然保持一定的抽象级别。

中间代码在编译过程中起到桥梁的作用，它使得代码优化和目标代码生成更加方便和高效。

三、论述题1. 论述编译器优化的几种常见方法。

答案：编译器优化主要包括以下几种方法：常量折叠、死代码消除、公共子表达式消除、循环优化、代码内联、寄存器分配等。

这些优化方法可以提高程序的执行效率，减少资源消耗，提高程序的运行速度。

结束语：本试题涵盖了编译原理的基本知识点，包括编译器的功能、编译过程的主要阶段、中间代码的作用以及编译器优化的方法。

希望考生能够通过本试题加深对编译原理的理解和掌握。

编译原理试题及答案1. 选择题（每题4分，共40分）1) 当编译器在词法分析阶段遇到无法识别的字符时，应该采取的动作是：A. 直接忽略该字符并继续进行词法分析B. 输出错误信息并终止词法分析过程C. 将该字符标记为非法字符并继续词法分析D. 转交给语法分析器进行处理答案：B2) 下列关于语法分析器的描述中，错误的是：A. 语法分析器使用文法规则将输入的记号流转化为推导树B. 语法分析器可以通过自上而下或自下而上的方式进行解析C. LL(1)文法是一种常用于自上而下语法分析的文法形式D. 语法分析器的输入是词法分析器输出的记号流答案：A3) 以下关于语法制导翻译的说法，正确的是：A. 语法制导翻译是在语义分析阶段完成的B. 语法制导翻译通过产生式的属性传递进行信息的传递和计算C. 语法制导翻译只能用于自上而下的语法分析D. 语法制导翻译是在语法分析阶段完成的答案：B4) 在SLR分析算法中，项目集簇的构造过程中需要进行的操作是：A. 闭包操作和移进操作B. 移进操作和规约操作C. 闭包操作和规约操作D. 闭包操作、移进操作和规约操作答案：D5) 下列关于中间代码生成的叙述中，错误的是：A. 中间代码是一种类似于汇编代码的表示形式B. 中间代码可以直接被目标代码生成器所使用C. 中间代码的生成可以采用三地址码的形式D. 中间代码的生成在语法分析和语义分析之后进行答案：B2. 简答题（每题10分，共30分）1) 请简要描述编译器的主要工作流程。

答案：编译器的主要工作流程包括词法分析、语法分析、语义分析、中间代码生成、优化和目标代码生成等阶段。

在词法分析阶段，编译器将输入的源代码转化为一个个记号流。

接下来，在语法分析阶段，编译器使用文法规则对记号流进行分析，并生成语法树或推导树。

在语义分析阶段，编译器对语法树进行语义检查，并进行类型推导和符号表管理等操作。

中间代码生成阶段将经过语义分析的源代码转化为一种中间表示形式，通常是三地址码。

编译原理课程测试第一套卷（附解析）1．（20分）写出字母表∑ = {a, b}上语言L = {w | w中a的个数是偶数}的正规式，并画出接受该语言的最简DFA。

2．（15分）考虑下面的表达式文法，它包括数组访问、加和赋值：E → E[E] | E + E | E = E | (E) | id该文法是二义的。

请写一个接受同样语言的LR(1)文法，其优先级从高到低依次是数组访问、加和赋值，并且加运算是左结合，赋值是右结合。

3．（10分）下面是产生字母表∑ = { 0, 1, 2}上数字串的一个文法：S → D S D | 2D → 0 | 1写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和从右向左读都一样时，称它为回文数）。

4．（10分）教材上7.2.1节的翻译方案P →{offset := 0}DD →D ; DD →id : T { enter(, T.type, offset); offset := offset + T.width }T →integer {T.type := integer; T.width := 4 }T→real{T.type := real; T.width := 8 }使用了变量offset。

请重写该翻译方案，它完成同样的事情，但只使用文法符号的属性，而不使用变量。

5．（5分）一个C语言程序如下：void fun(struct {int x; double r;} val) { }main(){struct {int x; double r;} val;fun(val);}该程序在X86/Linux机器上的用cc命令编译时，报告的错误信息如下：1: warning: structure defined inside parms1: warning: anonymous struct declared inside parameter list1: warning: its scope is only this definition or declaration,1: warning: which is probably not what you want.7: inco mpatible type for argument 1 of ‘fun’请问，报告最后一行的错误的原因是什么？如何修改程序，使得编译时不再出现这个错误信息。

《编译原理》训练题第一章一．填空题1．一个编译程序是一个①，编译程序完成从②语言所写的源程序到③语言所写的目标程序的翻译工作。

2．编译程序的整个工作划分成阶段进行的,典型的划分方法，将编译过程分成六个阶段：①，②，③，④，⑤，⑥。

3．对编译程序而言，输入数据是①，输出结果是②。

4．编译方式与解释方式的根本区别在于。

二判断题（）1．汇编程序是一个编译程序，它把汇编语言程序翻译成机器语言执行。

（） 2．编译程序是一个语言翻译程序，它把汇编语言程序翻译成机器语言执行。

三．选择题1．汇编程序是将（1）翻译成（2）；编译程序是将（3）翻译成（4）。

可选项有：a.汇编语言程序b.机器语言程序c.高级语言程序d.汇编语言程序或机器语言程序e.汇编语言程序或高级语言程序f.机器语言程序或高级语言程序2．用高级语言编写的程序经编译后产生的程序叫（1）。

用不同语言编写的程序产生（1）后，可用（2）连接在一起生成机器可执行的程序。

在机器中真正执行的是（3）。

可选项有：a.源程序b.目标程序c.函数d.过程e.机器指令代码f.模块g.连接程序h..程序库3．编译程序与具体的机器（1），与具体的语言（2）。

可选项有：a.有关b.无关4．编译程序是一种常用的软件。

可选项有：a.应用b.系统5．编译程序生成的目标程序是机器语言的程序。

可选项有：a.一定b.不一定四、思考题1．给出一个典型的编译程序的结构框图。

2．什么是前端和后端？设想相同的前端不同的后端，相同的后端不同的前端生成的编译程序分别有何特征？第二章一．填空题1. INT O A在每个过程目标程序的入口都有这样一条指令，用以完成①的工作，A域的值为②。

2. OPR O O在每个过程目标程序的①都有这样一条指令，用以完成②的工作。

3．PL/0编译程序运行时的存储分配策略采用栈式动态分配，用①链和②链的方式解决递归调用和非局部变量的引用问题。

4. 是构成语言文法的单词，是语法成分的最小单位。

编译原理试卷一窗体顶端一、选择1.一个正规语言只能对应()？A 一个正规文法；B 一个最小有限状态自动机；2.文法G[A]：A→ε A→aB B→Ab B→a是()：A 正规文法B 二型文法3.下面说法正确的是()：A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的()：A 必要条件B 充分必要条件窗体底端窗体顶端二、多项选择1.PL/0语言的目标程序解释执行时用到的数据对象有()：A 目标代码CODEB 符号表TABLEC 数据栈SD 关键字表WORD2.PL/0语言编译时产生或使用的数据对象有()：A 目标代码CODEB 符号表TABLEC 数据栈SD 关键字表WORD窗体底端窗体顶端三、问答题问答第1题(5分)将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。

G[S]：S→bSAe | bAA→Ab | d问答第2题(10分) 判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。

S→aHH→aMd | dM→Ab | εA→aM | e问答第3题给出与正规式R＝（ab）*（a|b*）ba等价的NFA。

问答第4题将下图的NFA确定化为DFA。

问答第5题(7分)（1）给出下列PL/0示意程序中当程序执行到X过程调用Z过程后（即执行Z过程体时）的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容。

（2）说明Display表和DL（老SP）,RA,TOP及全局Display的作用。

PL/0示意程序为：const a=80;var b,c;procedure X;var d;procedure Z;var e,g;begin (* Z *)c:=b*a；end ；(* Z *)begin (* X *)call Z;end ；(* X *)procedure Y;var f;begin (* Y *)call X;end ；(* y *)begin (* main *)call Y;end. (* main *)问答第6题(5分)给出问答第5题PL/0示意程序编译到Y过程体时TABLE表的内容。

考试科目:《编译原理》第1章至第4章（总分100分）一、选择与填充（30）1. 一个正则语言只能对应( B )？A. 一个正则文法B. 一个最小有限状态自动机C. 一个自然语言D. 一个上下文有关文法2. 对于编译程序而言，输入数据是源程序，输出数据是____目标程序____。

3. 给出在字母表{0,1}上的“所有以00结尾的符号串的集合”的语言的正则表达式：_____(0|1)*00_____。

4. 一个句型中最左的（ A ）称为该句型的句柄。

A. 简单短语B. 短语C. 非终结符号D. 终结符号5. Micro语言只有三种语句：（ B ）、输入语句和输出语句。

A. GOTO语句B.赋值语句C. 条件语句D.循环语句6. 描述高级语言语法的常用方法有_____语法图_____和BNF范式。

二、给出与正规式R＝（ab）*（a|b*）ab等价的NFA。

（16）答：三、简述 DFA 与 NFA 有何区别。

（14）答：DFA与NFA的区别主要有两点：1是NFA可以若干个开始状态，而DFA仅只一个开始状态2是DFA的映像M是从到K，而NFA的映像M是从到K的子集，即映像M将产生一个状态集合（可能为空集），而不是单个状态。

四、判断下列文法是否具有二义性：G[P]: P→PaP|PbP|cP|Pe|f(18)答：五、对于下面的文法G[Z]，构造句子(i*i+i)*i的最左和最右推导及相应的语法树。

（22）(1) Z::=E (2) E::=T+E (3) E::=T (4) T::=F*T(5) T::=F (6) F::=(E) (7) F::=i答：。

《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。