下载文档原格式
编译原理考试试题及答案 一、选择题（每题2分，共10分） 1. 编译器的主要功能是将高级语言源程序翻译成（ ）。 A. 机器语言程序 B. 汇编语言程序 C. 中间代码 D. 可执行文件 答案：A
2. 在编译原理中，词法分析的主要任务是（ ）。 A. 将源代码转换成中间代码 B. 识别源代码中的单词符号 C. 生成语法树 D. 优化代码 答案：B
3. 下列哪个选项不属于语法分析的范畴？（ ） A. 构建语法树 B. 词法分析 C. 消除左递归 D. 检测语法错误 答案：B
4. 在编译过程中，语义分析的主要任务是（ ）。 A. 检查语法结构的正确性 B. 检查标识符的声明和使用 C. 计算表达式的值 D. 代码优化 答案：B 5. 编译器的优化阶段主要关注（ ）。 A. 语法结构的检查 B. 代码的生成 C. 程序运行效率的提升 D. 错误信息的报告 答案：C
二、填空题（每题2分，共10分） 1. 编译器前端的主要工作包括词法分析、语法分析和________。 答案：语义分析
2. 编译器后端的主要工作包括代码生成和________。 答案：代码优化
3. 在编译原理中，________是指一个非终结符可以推导出空串。 答案：产生式
4. 编译过程中，________分析用于检测和报告语法错误。 答案：语法
5. 编译器中的________分析阶段负责将源代码中的标识符与它们的定义关联起来。 答案：语义
三、简答题（每题10分，共20分） 1. 简述编译器的主要组成及其功能。 答案：编译器主要由前端和后端组成。前端包括词法分析、语法分析和语义分析，负责将源代码转换为中间代码，并进行错误检测和类型检查。后端包括代码生成和代码优化，负责将中间代码转换为目标代码，并优化代码以提高程序的运行效率。 2. 描述编译过程中词法分析器的主要任务。 答案：词法分析器的主要任务是将源代码分解成一系列的标记（token），这些标记包括关键字、标识符、常量、运算符等。它还负责识别和报告源代码中的词法错误，如拼写错误和不匹配的括号等。
地大《编译原理(新)》在线作业二
一、单选题（共15 道试题，共60 分。
）
1. 正则文法（）二义性的。
A. 可以是
B. 一定不是
C. 一定是
D. 可以不是
正确答案：B
2. 由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成（）。
A. 过程
B. 程序
C. 批量
D. 遍
正确答案：D
3. 简单优先分析每次规约的是（）。
A. 最左短语
B. 直接短语
C. 句柄
D. 最左素短语
正确答案：C
4. 词法分析器的输出是（）。
A. 字符串
B. 二元式
C. 三元式
D. 四元式
正确答案：A
5. Chomsky 定义的四种形式语言文法中，0 型文法又称为（）文法。
A. 短语文法
B. 上下文无关文法
C. 上下文有关文法
D. 正规文法
正确答案：A
6. NFA M=（Σ，S，s0，F，δ）中的δ表示（）的函数。
A. S×Σ?S
B. S×Σ?2S
C. S×Σ?F。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
编译原理习题参考答案第⼆章2.构造产⽣下列语⾔的⽂法（2）{a n b m c p|n,m,p≥0}解： G(S) ：S→aS|X,X→bX|Y,Y→cY|ε（3）{a n # b n|n≥0}∪{cn # dn|n≥0}解： G(S)：S→X,S→Y,X→aXb|#, Y→cYd|# }（5）任何不是以0 打头的所有奇整数所组成的集合解：G(S)：S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8, J→1|3|5|7|9}（6）（思考题）所有偶数个0 和偶数个1 所组成的符号串集合解：对应⽂法为 S→0A|1B|ε，A→0S|1C B→0C|1S C→1A|0B3.描述语⾔特点（2）S→SS S→1A0 A→1A0 A→ε解：L(G)={1n10n11n20n2… 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm 不全为零}该语⾔特点是：产⽣的句⼦中，0、1 个数相同，并且若⼲相接的1 后必然紧接数量相同连续的0。
（5）S→aSS S→a解：L(G)={a(2n-1)|n≥1}可知：奇数个a5. (1) 解：由于此⽂法包含以下规则：AA→ε，所以此⽂法是0 型⽂法。
7.解：(1)aacb 是⽂法G[S]中的句⼦，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（3）aacbccb 不是⽂法G[S]中的句⼦aacbccb 不能从S推导得到时，它仅是⽂法G[S]的⼀个句型的⼀部分，⽽不是⼀个句⼦。
11.解：最右推导:(1) S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上⾯推导中，下划线部分为当前句型的句柄。
对应的语法树为：3 假设M:⼈ W:载狐狸过河，G:载⼭⽺过河，C:载⽩菜过河6 根据⽂法知其产⽣的语⾔是L={a m b n c i| m,n,i≧1}可以构造如下的⽂法VN={S,A,B,C}, VT={a,b,c}P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c} 其状态转换图如下:7 (1) 其对应的右线性⽂法是:A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2) 最短输⼊串011(3) 任意接受的四个串： 011,0110,0011,000011(4) 任意以1 打头的串.9．对于矩阵(iii)(1) 状态转换图：(2) 3型⽂法（正规⽂法）S→aA|a|bB A→bA|b|aC|a B→aB|bC|b C→aC|a|bC|b(3)⽤⾃然语⾔描述输⼊串的特征以a 打头，中间有任意个（包括0个）b,再跟a,最后由⼀个a,b 所组成的任意串结尾或者以b 打头，中间有任意个（包括0个）a,再跟b,最后由⼀个a,b 所组成的任意串结尾。
编译原理考试题及答案一、选择题（每题2分，共10分）1. 在编译原理中，词法分析器的主要任务是什么？A. 将源代码转换为中间代码B. 识别源代码中的词法单元C. 进行语法分析D. 优化代码答案：B2. 下列哪个选项不是编译器的组成部分？A. 词法分析器B. 语法分析器C. 运行时环境D. 语义分析器答案：C3. 编译器的哪个阶段负责检查变量是否已经声明？A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：C4. 在编译原理中，哪些技术常用于错误恢复？A. 预测分析表和LR分析B. 递归下降分析和LR分析C. 预测分析表和递归下降分析D. 预测分析表和错误恢复算法答案：D5. 编译器中用于优化代码的阶段是哪一个？A. 词法分析B. 语法分析C. 语义分析D. 代码优化答案：D二、填空题（每题2分，共10分）1. 编译器的前端包括词法分析、语法分析和________。
答案：语义分析2. 在编译过程中，________分析器负责将源代码的逻辑结构转换为一种内部表示形式。
答案：语法3. 编译器的后端包括________、寄存器分配和代码生成。
答案：中间代码生成4. 编译器中的________分析用于检查程序中的类型错误。
答案：语义5. 编译器的________阶段负责将高级语言代码转换为目标机器代码。
答案：代码生成三、简答题（每题10分，共20分）1. 简述编译器的主要功能。
答案：编译器的主要功能包括将高级语言编写的源代码转换成目标机器可以执行的机器代码，同时进行错误检测、代码优化等。
它通常包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等阶段。
2. 描述编译过程中的语法分析阶段的主要任务。
答案：语法分析阶段的主要任务是检查源代码是否符合语言的语法规则，构建抽象语法树（AST），并进行语法制导的语义分析。
这一阶段使用诸如自顶向下的递归下降分析、自底向上的移进-规约分析等技术来识别语言结构，并为后续的语义分析和代码生成打下基础。
编译原理第二章-课后题答案本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March第二章3.何谓“标志符”，何谓“名字”，两者的区别是什么答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。
4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值。
（1）优先顺序（从高到低）为+、*和↑，同级优先采用左结合。
（2）优先顺序为↑、+、*，同级优先采用右结合。
答：（1）1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256（2）1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=86.令文法G6为N-〉D|NDD-〉0|1|2|3|4|5|6|7|8|9（1）G6的语言L（G6）是什么（2）给出句子0127、34、568的最左推导和最右推导。
答：（1）由0到9的数字所组成的长度至少为1的字符串。
即：L（G6）={d n|n≧1,d∈{0,1,…,9}}（2）0127的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>01270127的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127（其他略）7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。
答：G（S）：S->+N|-NN->ABC|CC->1|3|5|7|9A->C|2|4|6|8B->BB|0|A|ε［注］：可以有其他答案。
［常见的错误］：N->2N+1原因在于没有理解形式语言的表示法，而使用了数学表达式。
8.令文法为E->T|E+T|E-TT->F|T*F|T/FF->(E)|i(1)给出i+i*i、i*(i+i)的最左推导和最右推导。
编译原理试题及答案一、单项选择题（每题2分，共20分）1. 编译器的主要功能是将（）转换成目标代码。
A. 汇编语言B. 高级语言C. 机器语言D. 伪代码答案：B2. 语法分析阶段的任务是（）。
A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：B3. 下列哪个算法是用于构建语法分析树的？（）A. LL(1)分析B. LR(1)分析C. 语法制导翻译D. 语法制导翻译方案答案：A4. 在编译原理中，一个文法的产生式A→α表示（）。
A. A可以被α替换B. A可以被α推导C. A可以被α翻译D. A可以被α解释答案：B5. 一个语言的语法分析树的根节点对应于（）。
A. 程序B. 程序的输入C. 程序的输出D. 程序的语法答案：D6. 编译器的语义分析阶段主要处理（）。
A. 词法分析B. 语法分析C. 类型检查D. 代码优化答案：C7. 编译器的代码优化阶段主要进行（）。
A. 词法分析B. 语法分析C. 类型检查D. 指令选择答案：D8. 编译器的代码生成阶段主要进行（）。
A. 词法分析B. 语法分析C. 类型检查D. 指令序列生成答案：D9. 编译器的哪个阶段负责处理变量的存储分配？（）A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D10. 编译器的哪个阶段负责处理宏展开？（）A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：A二、多项选择题（每题3分，共15分）1. 编译器的前端包括（）。
A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：ABC2. 编译器的后端包括（）。
A. 词法分析B. 语法分析C. 代码优化D. 代码生成答案：CD3. 编译器的语义分析阶段可能包括（）。
A. 类型检查B. 作用域解析C. 存储分配D. 代码优化答案：ABC4. 编译器的代码优化阶段可能包括（）。
A. 常量折叠B. 死代码消除C. 循环不变代码外提D. 词法分析答案：ABC5. 编译器的代码生成阶段可能包括（）。
编译原理考试题及答案一、选择题（每题2分，共20分）1. 编译器的主要功能是将高级语言源程序转换成机器语言目标程序。
（对/错）答案：对2. 编译过程中，词法分析器的主要任务是识别源程序中的各种词法单位。
（对/错）答案：对3. 在语法分析阶段，编译器使用的数据结构是栈。
（对/错）答案：错4. 语义分析的主要目的是检查程序的语法结构是否正确。
（对/错）答案：错5. 编译器的优化阶段可以提高目标程序的执行效率。
（对/错）答案：对6. 编译器的代码生成阶段负责将中间代码转换为目标代码。
（对/错）答案：对7. 编译器的运行时系统包括内存管理、输入输出处理等功能。
（对/错）答案：对8. 编译器的前端主要负责源程序的分析，后端负责目标代码的生成。
（对/错）答案：对9. 编译器的词法分析阶段不涉及对标识符的识别。
（对/错）答案：错10. 编译器的语法分析阶段可以识别出所有的语法错误。
（对/错）答案：对二、填空题（每题2分，共20分）1. 编译器在进行语法分析时，通常采用________算法。
答案：LL(1)或LR(1)2. 编译器在语义分析阶段，需要对变量的________进行检查。
答案：作用域和生命周期3. 编译器在代码优化阶段，常用的优化技术包括________和循环优化。
答案：常量传播4. 编译器在目标代码生成阶段，需要考虑________的约束。
答案：目标机器5. 编译器的运行时系统包括________、内存管理、输入输出处理等。
答案：程序启动和异常处理6. 编译器在词法分析阶段，需要识别的词法单位包括________、标识符、常量等。
答案：关键字7. 编译器在语法分析阶段，使用的分析表可以是________表或ACTION 表。
答案：GOTO8. 编译器在语义分析阶段，需要对表达式的________进行计算。
答案：类型9. 编译器的代码生成阶段，需要将中间代码转换为________代码。
答案：目标机器10. 编译器的运行时系统在内存管理中，需要处理________和垃圾收集。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。
(×)2．一个有限状态自动机中，有且仅有一个唯一的终态。
(×)3．一个算符优先文法可能不存在算符优先函数与之对应。
(√)4．语法分析时必须先消除文法中的左递归。
(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
(√)6．逆波兰表示法表示表达式时无须使用括号。
(√)7．静态数组的存储空间可以在编译时确定。
(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。
(×)10．一个语义子程序描述了一个文法所对应的翻译工作。
(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。
A．()单词的种别编码B．()单词在符号表中的位置C．()单词的种别编码和自身值D．()单词自身值2．正规式M1和M2等价是指_____。
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．四元式之间的联系是通过_____实现的。
第二章 词法分析2.1 完成下列选择题： (1) 词法分析器的输出结果是 。
a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M 2等价是指 。
a. M1和M2的状态数相等b. M1和M2的有向边条数相等c. M1和M2所识别的语言集相等d. M1和M2状态数和有向边条数相等 (3) DFA M(见图2-1)接受的字集为 。
a. 以0开头的二进制数组成的集合b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合d. 含偶数个0的二进制数组成的集合 【解答】(1) c (2) c (3) d图2-1 习题2.1的DFA M2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。
通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。
每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。
2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下： f(x,a)={x,y} f{x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M ′。
【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y ,b)均为多值函数，因此M 是一非确定有限自动机。
先画出NFA M 相应的状态图，如图2-2所示。
图2-2 习题2.3的NFA M用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。
华南理工大学-编译原理习题参考答案-21.(1)A: ScannerB:=id (b)+id (a)*id (i)2C: Semantic analyzerD: IR GenerationE: Code generator(2)R.E.: ((ab*a)|b)*(3) the rewritten grammerA → bAbB | bABb | aBB → BaA | ab | baA → bA A’ | aBA’→bB|BbB →ab B’ | ba B’B’→aAB’|ε(4)E→T+E| T-E|T, T→1|2|3|4|5|6|7|8|9|0E ? T+E ? T+T-E? T+T- T? T+T- 4? T+3- 4? 2+3-4(5)T*F2(1)turn the regular expression to NFA12a34εε56a78bε9ε10bε11εε12εεε(2) turn this NFA into DFA using the tableI I a I b {1} 0 {2,3,4,5,9,12}{2,3,4,5,9,12}1 {6,7} {4,5,9,10,11,12} {6,7}2{4,5,8,9,11,12} {4,5,9,10,11,12} 3 {6,7} {4,5,9,10,11,12}{4,5,8,9,11,12}4{6,7}{4,5,9,10,11,12}a2ba aab34b 1b(3) minimize the DFA and give the reason0a2abb{1,3,4}3 Solution:(1)The attribute grammar isS’→while E do SS’.begin=newlabel;E.true=newlabel;E.false=S’.next;S.next=S’.begin;S’.code=Label S’.begin || E.code || Label E.true || S.code ||goto S’.b egin(2)The Three Code is (符合逻辑的三地址码算正确)参考：t1=1t2=10if t1 ≤ t2 goto L1 goto L2label L1v=t1 t3=x+1 x=t3 label L4 if v ≠ t2 goto L3goto L2Label L3v=v+1 t4=x+1 x=t4 goto L4label L2halt4(1)Please explain the rewritten grammar is LL(1) grammar.●S→(L)|aS’●S’→S|ε●L→SL’●L’→SL’|εNullable nonterminal：{S’, L’}Productions First sets First(α) sets Follow setsFirst(S)={(, a} First(S’)={(,a,ε} First(L)={ (, a } First(L’)={(,a,ε} First(() = {(} First(a) ={a}First((L))={(}First(aS’)={a}First(S) ={(,a}First(SL’)={ (,a }Follow(S)={$,(,a}Follow(S’)={$,(,a}Follow(L)={ ) }Follow(L’)={ ) }Reason:S’→S|ε : ε in First(S’), and First(S’) ∩ Follow(S’)≠Φ, So the grammar is not LL(1)(2)Construct the LL(1) parsing table( ) a $S S→(L)S→aS’S’S’→SS’→εS’→SS’→εS’→εL L→SL’L→SL’L’L’→SL’L’→εL’→SL’5.1) Rewrite the grammar and Draw the DFA: G ’[A]:(1) S ’ → A (2) A → a Ad (3) A → aAb (4) A → εI 0:S ’→·A A →·aAd A →·aAb A →·I 1:S ’→A·A I 2:A →a·Ad A →a·Ab A →·aAd A →·aAb A →·aI 3:A →a·Ad A →a·AbAabI 5:A →aAb·I 4:A →aAd·d2) : Is it LR(0) or SLR(1), why?In I 0 and I 2, there exist shift-reduce confliction.Follow(A) ∩ {a} = {d,b,$} ∩ {a} =Φ, so G[A] is a SLR(1) grammar.ACTION GOTO a d b $ A 0 S 2 r3 r3 r3 1 1 acc 2 S 2 r3 r3 r3 33 S4 S5 4r1r1r15 r2 r2 r23) Solution:Stack Input ACTION GOTO1 $0 abd$ Shift 22 $0a2 bd$ r3 33 $0aA3 bd$ Shift 54 $0aA3b5 d$ r2 15 $0A1 d$ err。
