编译原理2006期末考试试卷A

试卷答题时限：120 分钟考试形式：闭卷笔试一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共20注意：须将本题答案写在下面的表格中，写在其它地方无效1. 编译程序是对（）A. 汇编程序的翻译B。

高级语言程序的解释执行C. 机器语言的执行D. 高级语言的翻译2。

词法分析器的输出结果是（）A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身值D．单词自身值3.在规范规约中,用（）来刻画可规约串.A．直接短语B．句柄C．最左素短语D．素短语4。

与正规式（a* ｜b）＊(c ｜d）等价的正规式是（）A．a＊(c ｜d）｜b(c ｜d) B．a＊(c ｜d） * | b（c ｜d）＊C．a*（c | d）| b*（c ｜d) D．（a | b） * c｜(a ｜b)＊d5. 若项目集I K含有A→α·，则在状态K时，仅当面临输入符号a∈FOLLOW(A)时,才采取A→α·动作的一定是（）A．LALR文法B．LR（0) 文法C．LR（1)文法D．SLR(1)文法6。

四元式之间的联系是通过（）实现的。

A. 指示器B。

临时变量C。

符号表D. 程序变量7．文法G：S → x Sx｜y所识别的语言是（)A．xyx B．(xyx)＊C．x n yx n(n≥0）D．x*yx*8.有一语法制导翻译如下所示:S → b Ab {print “1”}A→(B {print “2”}A→a {print “3"}B→Aa) ｛print “4”}若输入序列为b（（（aa)a）a）b，且采用自下而上的分析方法，则输出序列为（）A．32224441 B. 34242421 C．12424243 D。

344422129．关于必经结点的二元关系，下列叙述不正确的是（ )A．满足自反性B．满足传递性C．满足反对称型D．满足对称性10．错误的局部化是指（）。

A．把错误理解成局部的错误B．对错误在局部范围内进行纠正C．当发现错误时，跳过错误所在的语法单位继续分析下去D．当发现错误时立即停止编译，待用户改正错误后再继续编译1分,共5分）1.文法G的一个句子对应于多个推导，则G是二义性的。

编译原理期末考试试题及答案一、选择题（每题2分，共20分）1. 编译器的前端主要负责以下哪项工作？A. 代码优化B. 目标代码生成C. 词法分析和语法分析D. 运行时支持2. 词法分析器的主要任务是什么？A. 识别语法结构B. 识别词法单元C. 构建语法树D. 代码优化3. 语法分析中，使用哪种方法可以避免回溯？A. 递归下降分析B. LR分析C. LL分析D. 自顶向下分析4. 下列哪个选项不是中间代码的形式？A. 三地址代码B. 四元组C. 抽象语法树D. 汇编语言5. 代码优化的目标不包括以下哪项？A. 提高代码执行速度B. 减少程序占用的内存C. 增加程序的可读性D. 减少程序的执行时间二、简答题（每题10分，共30分）1. 简述编译器的主要组成部分及其功能。

2. 解释什么是语法制导翻译，并举例说明其在编译过程中的应用。

3. 描述静态作用域规则和动态作用域规则的区别。

三、计算题（每题15分，共30分）1. 给定一个简单的算术表达式 `3 + (4 * 5) - 2`，请使用逆波兰表示法表示，并说明其转换过程。

2. 假设有一个简单的文法如下：```S -> A BA -> a A | εB -> b B | ε```请写出使用该文法生成字符串 "ab" 的所有派生树。

四、论述题（每题20分，共20分）1. 论述编译器中代码优化的重要性，并举例说明常见的优化技术。

参考答案一、选择题1. C2. B3. B4. D5. C二、简答题1. 编译器的主要组成部分包括前端、中端和后端。

前端负责词法分析和语法分析，中端进行语义分析和中间代码生成，后端则负责代码优化和目标代码生成。

2. 语法制导翻译是一种基于文法规则的翻译技术，它将源程序的语法结构映射到相应的语义操作上。

例如，在编译过程中，语法制导翻译可以用于将源代码中的条件语句转换为中间代码中的跳转指令。

3. 静态作用域规则是指变量的作用域在编译时确定，而动态作用域规则是指变量的作用域在运行时确定。

2006～2007学年第1学期期末考试试卷《编译原理》答案一、单项选择题（共10分，每小题1分。

）A卷答案：二、简答题1.简要叙述语法分析的基本功能是什么？对于同一个文法，LALR(1)和SLR(1)的分析表状态个数相同，为什么前者的分析能力要比后者强？（简述要点即可）（10分）答：语法分析的基本功能是：a)语法分析处于词法分析和语义分析之间，它的输入是词法分析的输出，它的输出是语义分析的输入。

（1分）b)词法分析对输入的字符串进行分析，判断是否一个合法的输入。

其中合法是指输入的字符串是否符合程序设计语言的语法规定（或者文法的规定）。

（3分）c)对于不符合语法的字符串要设计错误处理机制。

其分析方法包括自顶向下和自底向上分析两种。

（1分）LALR(1)比SLR(1)分析能力强的原因：在构造分析表时，SLR(1)中的规约项填写的是全体FOLLOW(A)集合中的符号，这样就增加了移动-规约冲突的可能性。

（2分）而对于LALR(1)，虽然分析表状态和SLR(1)同样多，但是它采用了向前搜索符技术，使得规约项填写的只是FOLLOW(A)集合的子集，而且大部分时间下是真子集，这就使得产生移动-规约冲突的可能性减少，因此更加精确，所以分析能力更强。

（3分）2.在对运行时的内存空间进行存储组织时，过程一次执行所需的信息用一块连续的存储区来管理，这就是活动记录。

在活动记录中，有两个域分别保存了“可选的访问链”和“可选的控制链”。

请简要描述这两个域的区别，以及它们保存的数据在存储管理中都起到了什么作用。

（10分）答：区别：“可选的访问链”总是指向定义该过程的过程的活动记录。

因为它总是指向定义者，所以这个指针主要用来对非局部数据的访问。

（2.5分）“可选的控制链”总是指向调用该过程的过程的活动记录。

因为指针的指向顺序总是由上一个活动记录指向下一个活动记录，所以这个指针主要用于过程调用时参数的传递和数据返回。

（2.5分）数据的作用“可选的访问链”中的数据用于计算非局部数据的位置。

《编译原理》试卷A 参考答案注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。

2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。

3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。

4. 满分100分，考试时间为120分钟。

题号一二三四总分统分人得分一、单项选择题（每小题2分共20分）1．中间代码生成所依据的是语言的（C ）。

A: 词法规则B: 语法规则C: 语义规则D: 产生式规则2．词法分析器的加工对象是（C ）。

A: 中间代码B: 单词C: 源程序D: 元程序3．同正则表达式a*b*等价的文法是（C ）。

A: G1: S aS|bS|εB: G2: S aSb|εC: G3: S aS|Sb|εD: G4: S abS|ε4．文法G[A]：A→b A→bH H H →BA B→Ab H →a 不是(B )：A: 2型文法B: 正规文法C: 0型文法D: 1型文法5．算符优先分析每次都是对（算符优先分析每次都是对（ B B B ）进行规约。

）进行规约。

A: A: 短语短语短语 B: B: B: 最左素短语最左素短语最左素短语 C: C: C: 素短语素短语素短语 D: D: D: 句柄句柄6．一个LR （1）文法合并同心集后,如果不是LALR(1)文法必定存在(B )：A: 移进-归约冲突B: 归约-归约冲突C: 识别句型D: 收集类型信息7．下列不属于类型检查范畴的描述是（C ）。

A: 运算符的分量类型的相容性B: 形参和实参类型的相容性C ：形参和实参的个数的一致性D: 赋值语句的左右部类型的相容性8．（ B B ）不是）不是DFA 的成分。

A:A:有穷字母表有穷字母表有穷字母表 B: B: B:初始状态集合初始状态集合C:C:终止状态集合终止状态集合终止状态集合 D: D: D:有限状态集合有限状态集合9．若B 为非终结符，则A α.B β为（为（ B B B ）项目。

《编译原理》考试试卷A适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、填空题：（每空1分，共10分）1.解释系统与编译系统的区别在于和。

2.在编译过程中始终伴随着管理和出错处理过程。

3.语法分析的方法为和两大类。

4.LL(1)文法中不能有和。

5.词法分析器中单词的描述工具是 ,单词的识别工具。

6.算符优先语法分析，在符号栈栈顶出现时，进行规约处理。

二、单选题（每小题2分，共10分）1.词法分析器的加工对象是（）A.中间代码B.单词C.源程序D.元程序2.同正则表达式a*b*等价的文法是（）A. G1:S→aS|bS|εB. G2: S→aSb|εC. G3:S→aS|Sb|εD. G4: S→abS|ε3.文法G[A]:A→bH H→BA B→Ab H→a 不是（）A. 2型文法B. 3型文法C. 0型文法D.1型文法4.算符优先分析每次都是对（）进行规约。

A.短语B.最左素短语C.素短语D.句柄5.( )不是DFA的成分。

A.有穷字母表B. 初始状态集合C.终止状态集合D.有限状态集合三、问答题（第1,5小题每题15分，其余每小题10分，共80分）1. （15分）解释下列术语：（1）编译程序（2）句柄（3）上下文无关文法2.编译程序主要有哪些构成成分？（10分）3.给出描述语言L={a n b2n c m|n,m≥0}的cfg。

（10分）4.（10分）将下图中的DFA M最小化。

5. （15分）判断文法G[S]:S→aHH→aMd|dM→Ab|εA→aM|e是否为LL(1)文法？给出判断过程。

6. （10分）改写文法G[E]：E → E+T|TT →T*F|FF →(E)| a为无左递归文法。

7. （10分）已知文法G[S]为：S→VV→T|ViTT→F|T+FF→)V*|(请指出句型(+(i( 规范推到，并指出句型F+Fi( 中的短语、句柄和素短语。

《编译原理》考试试卷A参考答案适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、填空题：（每空1分，共10分）1. 边翻译边执行和不生成目标代码。

《编译原理》模拟试题一一、是非题(请在括号内，正确的划错误的划X)(每个2分，共20分)1•计算机高级语言翻译成低级语言只有解释一种方式。

(X)2.在编译中进行语法检查的目的是为了发现程序中所有错误。

(X)3.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。

(丁 )4.正则文法其产生式为A->a , A->Bb, A.BGVN , a、beVT o (X)5.每个文法都能改写为LL(1)文法。

(V)6.递归下降法允许任一非终极符是直接左递归的。

(V)7.算符优先关系表不一定存在对应的优先函数。

(X)8.自底而上语法分析方法的主要问题是候选式的选择。

(X)9.LR法是自顶向下语法分析方法。

(X)10.简单优先文法允许任意两个产生式具有相同右部。

(X)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1.一个编译程序中，不仅包含词法分析，_____ ,中间代码生成，代码优化，目标代码生成等五个部分。

A.()语法分析B.()文法分析C.()语言分析D.()解释分析2.词法分析器用于识别_____ oA.()字符串B.()语句C.()单词D.()标识符3 •语法分析器则可以发现源程序中的______ oA.()语义错误B.()语法和语义错误C.()错误并校正D.()语法错误4.下面关于解释程序的描述正确的是。

(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A. ( ) (1) (2)B. () (1)C. () (1)⑵(3)D.()⑵⑶5. _________________________________________ 解释程序处理语言时，大多数采用的是 ___________________________________ 方法。

2006年期末考试A 卷参考答案 一、．（12分）简答题：1． 简述编译程序分成哪几个阶段。

答： 编译过程通常需要经过词法分析、语法分析、中间代码生成、代码优化和目标代码生成五个阶段。

另外还包括表格管理和出错处理。

2． 为什么要将词法分析与语法分析分离？答：将编译过程的分析工作划分成词法分析和语法分析两个阶段的理由如下：（1）使整个编译程序的结构更简洁、清晰和条理化（2）编译程序的效率会改进 ；（3）增强编译程序的可移植性。

二、（6分）叙述由下列正规式描述的语言：1． (a|b)*(aa|bb)(a|b)*。

含有相继2个a 或b 的{a,b}上的任意串。

2． （0|1）（0|1）（0|1）0（0|1）* 第四位为0的{0，1}上的任意串。

三、（12分）构造一个DFA ，它接受∑={a ，b}上所有满足下面条件的字符串，其条件是字符串中的每个b 都有a 直接跟在右边。

解：正规式为V=(a|ba)*首先构造如下图所示的NFA M'再构造转换矩阵如下表、下图所示。

即：见下表a化简，先将状态分终态组J1={0,1}和非终态组J2={2}考察J1，{0,1}a ={1}⊂{0,1} {0,1}b ={2}⊂{3} 不能再分组。

重新命名上述状态子集将{0,1}用{1}代替 将{2}用{1}代替，见下表。

这样得到如图所示的简化后的DFA M 。

四、 （20分）对于文法G(E)E → E + T | T T → T *F | F F → P^F | P P → (E) | i1． 计算FIRSTVT 和LASTVT ； 2． 该文法是算符优先文法吗？ 3． 计算优先关系。

解：（1）构造FIRSTVT 集合的LASTVT 集合。

FIRSTVT(P)={(,i) ,FIRSTVT(F)={^,(,i), FIRSTVT(T)={*,^,(,i) ,FIRSTVT(E)={+,*,^,(,i); LASTVT(P)={},i} ,LASTVT(F)={ ^,},i} ,LASTVT(T)={*,^,} ,i} ,LASTVT(E)={+,^,*, ）} (2)是算符优先文法。

编译原理试题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. bc105. 文法G[S]:S→aAA→bBB→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.2310．自上而下语法分析的主要动作是（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．便于编译程序的移植20．中间代码是介于源语言程序和什么之间的一种代码 （D ）A ．源代码 B. 机器语言 C. 汇编语言 D. 目标代码二．简答（每题3分，共12分） 1. 什么是编译程序？编译程序是将源语言程序翻译为目标语言程序的程序。

编译原理期末试题及答案一、选择题（每题2分，共20分）1. 编译器的主要功能是将（）代码转换成（）代码。

A. 高级语言，低级语言B. 高级语言，机器语言C. 汇编语言，机器语言D. 机器语言，汇编语言答案：B2. 编译过程中，词法分析的输出是（）。

A. 语法树B. 语法分析表C. 词法单元D. 抽象语法树答案：C3. 在编译原理中，语法分析通常采用（）方法。

A. 递归下降分析B. 动态规划C. 贪心算法D. 回溯算法答案：A4. 语义分析的主要任务是（）。

A. 检查语法错误B. 生成中间代码C. 检查语义错误D. 优化代码答案：C5. 编译器的优化通常发生在（）阶段。

A. 词法分析B. 语法分析C. 语义分析D. 代码生成答案：D6. 编译器的前端主要负责（）。

A. 代码生成B. 代码优化C. 语法分析D. 目标代码生成答案：C7. 编译器的后端主要负责（）。

A. 代码生成B. 代码优化C. 语法分析D. 词法分析答案：A8. 编译原理中，LL(1)分析方法的特点是（）。

A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B9. 编译原理中，LR(1)分析方法的特点是（）。

A. 左到右，最右推导B. 左到右，最左推导C. 右到左，最右推导D. 右到左，最左推导答案：B10. 编译原理中，语法制导翻译的主要思想是（）。

A. 根据语法树的结构进行翻译B. 根据词法单元进行翻译C. 根据语法分析表进行翻译D. 根据语义分析表进行翻译答案：A二、填空题（每题2分，共20分）1. 编译器中，用于表示语法规则的产生式通常由非终结符、产生符号和（）组成。

答案：产生式右侧2. 在编译原理中，一个文法是（）的，如果它的任何两个产生式都不会导致相同的句柄。

答案：无二义性3. 编译器的词法分析阶段通常使用（）算法来识别和分类词法单元。

答案：有限自动机4. 语法分析阶段，如果一个文法是左递归的，编译器需要使用（）技术来消除左递归。