一、简答题 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.词法分析阶段的功能是什么 答：
天津理工大学考试试卷 ～2010学年度第二学期 《编译原理》期末考试试卷 课程代码： 0660116 试卷编号： 1-A 命题日期： 2010 年 6 月 15 日 答题时限： 120 分钟考试形式：闭卷笔试 大题号 一二三四 总分 一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分， 得 分 1 2 3 4 5 6 7 8 9 10 D C B D D B C B D C 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) * d 含有Aα·，则在状态K时，仅当面临输入符号a∈FOLLOW(A)时，才采 5. 若项目集I K 取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. 34442212 9．关于必经结点的二元关系，下列叙述不正确的是（ ） A ．满足自反性 B ．满足传递性 C ．满足反对称型 D ．满足对称性 10．错误的局部化是指（ ）。 A ．把错误理解成局部的错误 B ．对错误在局部范围内进行纠正 C ．当发现错误时，跳过错误所在的语法单位继续分析下去 D ．当发现错误时立即停止编译，待用户改正错误后再继续编译 二、判断题（每小题1分，共5分） 得 分 1. 文法G 的一个句子对应于多个推导，则G 是二义性的。（× ） 2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√ ） 3. 算符优先文法采用“移进－规约”技术，其规约过程是规范的。（ × ） 4. 删除归纳变量是在强度削弱以后进行。（ √ ） 5. 在目标代码生成阶段，符号表用于目标代码生成。（ × ） 5分，共15分） 得 分 1. 构造正规式(0∣1)* 00相应的正规式并化简。（共5分） （1）根据正规式，画出相应的NFA M （2分） I I 0 I 1 {x,1,2} {1,2,3} {1,2} {1,2,3} {1,2,3,4} {1,2} {1,2} {1,2,3} {1,2 } {1,2,3, {1,2,3,4} {1,2 } X 12 3 4 01
编译原理期中测试答案 三、单项选择题(每题3分，共15分) 1．设有文法G[S]: S→(AS)|(b) A→(SaA)|(a) 该文法的句型(((b)a(a))(b))有 C 个直接短语。 A.1 B. 2 C. 3 D. 4 2．如果一个文法满足 D ，则称该文法是二义性文法。 (1) 文法的某一个句子存在两个（包括两个）以上的语法树 (2) 文法的某一个句子存在两个（包括两个）以上的最左推导 (3) 文法的某一个句子存在两个（包括两个）以上的最右推导 (4) 在进行归约时，文法的某些规范句型的句柄不唯一 上述描述中的所有正确描述有： A. (1) B. (1)(2) C. (1)(2)(3) D. (1)(2)(3)(4) 3．构造一个不带回溯的自顶向下语法分析器，要求文法满足 E 。 A.对每个形如A→x1|x2|…|xn的产生式，要求FIRST(xi)与FIRST(xj)的交集为空集(i≠j) B.对每个形如A→x1|x2|…|xn的产生式，若xi* ε，则要求FIRST(xj)与FOLLOW(A)的交集为空集(i≠j) C. 不含左递归 D. A和B同时满足 E. A、B和C同时满足
4、给定文法A→bA|cc，下列符号串中，是该文法的句子的是 C 。 ① cc ② bcbc ③ bcbcc ④ bccbcc ⑤ bbbcc A① B. ①③④⑤ C. ①⑤ D. ①④⑤ 5、若一个句型中出现了某一产生式的右部，则此右部 B 是该句型的句柄。 A.一定 B. 不一定 C. 一定不 D. 无法判断 四、简述题(每题5分，共20分) 1、写一上下文无关文法,它能产生语言}0 n。 n a L m b , =m | {>= # S→A#B A→Aa|ε B→Bb|ε 2、将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe | bA A→Ab | d 答：文法G[S] 改写为等价的不含左递归和左公共因子的 G'[S]S→bB B→SAe | A A→d A' A' →bA' | ε 3、什么是文法的二义性？下面的文法是二义的吗？为什么？
编译原理考试题及答案汇总一、选择 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．( ) 产生式
编译原理期末复习 鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 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：产生式集合(有限)。
翻译程序:把一种语言程序转换成另一种语言程序，且在功能上是相同的这样的程序。 编译程序：把高级语言转换成低级语言，且在功能上是相同的这样的程序。 解释程序：边解释边执行源程序的程序。区别：编译程序有中间代码，而解释程序没有。编译过程的五个阶段： 1、词法分析任务：对构成源程序的字符串进行扫描和分解，识别出一个个单词。 2、语法分析任务：在词法分析的基础上，根据语言规则，把单词符号串分解成各类语法 单位。 3、语义分析和中间代码产生任务：对语法分析所识别出的各类语法范畴，分析其含义， 并进行初步翻译。 4、优化任务：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效 的目标代码。 5、目标代码生成任务：把中间代码变换成特定机器上的低级语言代码。 编译程序的七个部分词法分析器，语法分析器、语义分析与中间代码产生器、优化器、目标代码生成器、表格管理和出错处理。 编译程序生成的五个办法：机器语言、高级语言、移植、自编译方式和使用工具自动生成。词法规则：指单词符号的形成规则。（也就是正规式） 语法规则：规定了如何从单词符号形成更大的结构。就是语法单位的形成规则。 空字：不包含任何符号的序列。 闭包： 中所有的符号组成的集合。 上下文无关文法是指：所定义的语法范畴是完全独立于这种范畴可能出现的环境的文法。上下文无关文法的四个组成部分：一组终结符号、一组非终结符号、一个开始符号和一组产生式。 终结符号也就是不可再分的基本符号。 非终结符号是用来代表语法范畴，表示一定符号串的集合。 开始符号是语言中我们最感兴趣的语法范畴。 产生式是定义语法范畴的书写规则。 句子：文法中从开始符号推导的终结符号串。 句型：从开始符号推导的符号串。 语言：文法中所有句子的集合。 程序语言的单词符号分为五种：关键字、标识符、常数、运算符和界符。 二元式表示：（种类，属性） 正规式的运算符有三种：或，连接和闭包。优先顺序是：闭包，连接，或。 DFA怎么识别字：若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字是a，则称a可为DFA所识别。 DFA怎么识别空字：若DFA的初态结点同时又是终态结点，则空字可为DFA所识别。NFA怎么识别字：若存在一条从某一初态结点到终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于a，则称a可为NFA识别。 NFA怎么识别空字：若M的某些结点即是初态又是终态结点，或者存在一条从某个初态结点到某个终态结点的空通路，那么，空字可为M所识别。 语言的语法结构是用上下文无关文法描述的。 语法分析分为两类：自上而下分析法，自下而上分析法。 自上而下分析法面临的问题：1.文法的左递归问题。2.回溯3.成功可能是暂时的，产生虚假匹配。4.难于知道输入串中出错的确切位置。5.效率低，代价高。
河南科技大学电信科卷A 一． 填空题（每空2分，共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-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。
………密………封………线………以………内………答………题………无………效…… 电子科技大学2014 -2015学年第2学期期末考试 A 卷 课程名称：编译原理考试形式：闭卷考试日期：2015 年月日考试时长：120分钟 课程成绩构成：大班平时10 %，期中10 %，实验10 %，期末70 % 本试卷试题由___七_ _部分构成，共__8___页。 题号一二三四五六七合计 得分 得分 一、选择题（共20分，共10题，每题2分） 1.通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括（） A.模拟执行器 B.解释器 C.表格处理和出错处理 D.符号执行器 2.如果在推导过程中的任何一步α?β，都是对α中的最右非终结符进行替换，则称这种推导为（） A.直接推导 B.广义推导 C.最左推导 D.规范推导 3.设有文法G[S]=（{S，B}，{b},{S→bB | b,B→bS},S）,该文法所描述的语言是（） A．L(G[S]）={b n| n ≥0} B. L(G[S])={b2n| n ≥ 0} C. L(G[S])={b2n+1 | n ≥ 0} D. L(G[S])={b2n+1|n ≥ 1} 4.项目A α·称为（），其中A∈V N，A不是开始符。 A.移进项目 B.归约项目 C.待约项目 D.接受项目 5.编译程序生成的目标程序（）是机器语言的程序。 A．一定B．不一定C．某种情况下一定D．某种情况下不一定 6.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。 A．自左至右B．自顶向下C．自底向上D．自右向左 7.运行阶段的存储组织和管理的目的是（） （1）提高编译程序的运行速度 （2）提高目标程序的运行速度 （3）为运行阶段的存储分配做准备 A.(1)(2) B.(1)(3) C.(2) D.(1)(2)(3) 8.如果文法G 是无二义的，则它的任何句子α（） A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同
编译原理学习心得 编译原理学习心得1 编译程序在计算机科学与技术的发展历史中发挥了巨大作用，是计算机系统的核心支撑软件。而“编译原理”这门课程一直以来是国内外大学计算机相关专业的重要课程。因为它的知识结构贯穿程序设计语言、系统环境以及体系结构，能以相对的视角体现从软件到硬件以及软硬件协同的整机概念。其理论基础又涉及形式语言与自动机、数据结构与算法等计算机学科的许多重要方面，为联系计算机科学理论和计算机系统的典范。 虽然编译原理这门课程在大多数的人里认为枯燥无味，学起来就像看天书一样。然而学习这门课程还是有一定的好处的。比如可以更加容易的理解在一个语言种哪些写法是等价的，哪些是有差异的，可以更加客观的比较不同语言的差异，并且学习新的语言的效率也会更加高，语言转换也会更加游刃有余。 不学“编译原理”这门课程的话，自己的编程思想会很浅显。而且编程也只仅仅停留在编程上，无法深入理解其中的原理。 学习编译原理的话，从文法、正规式、NFA与DFA的定义，下手，要用心动脑去体会 编译原理学习心得2
从联系最紧密的操作系统来说吧，你写多线程/多进程的程序就得和操作系统的知识打交道。写多线程得加锁吧，临界区、死锁的四个条件之类的标准的操作系统的内容吧(不得不吐槽一下，某国内一线电商干了三年的程序猿，写多线程居然不知道加锁，也是醉了)。进程间通信的几种方式什么管道、socket、共享内存等，这也是操作系统的内容吧。文件系统，这也是经常要打交道的东西。还有内存什么的，你做Android 开发，这些里边有很多东西都在系统层面被封装好了，但是你要是不知道原理，一旦出了错根本无从调试，况且你该不会打算写一辈子写Android 就是填逻辑吧。 然后，是编译原理，普通的程序猿是接触不到编译器或者虚拟机的开发的。但是这并不意味着编译原理就用不到。说个最常见的读取配置文件，只要你的配置文件有自定义的语法，你就要用编译原理的东西。还有类似于自动生成代码啦、正则表达式啦这些都算是编译原理的内容。你既然是写Java 的不了解虚拟机怎么可以，最基本的字节码总是需要能看懂的吧，分析一些疑难杂症的时候字节码还是很有用的。 最后，是计算机原理，如果只是做应用开发的话计算机原理其实不必要掌握的多深入，但是一些基本的概念还是要清楚的。比如寄存器、缓存、中断什么的，关键的时候可以帮助你调试。在一些对性能要求非常高的场合，也是很有作用的。此外，学了
编译原理考试题及答案汇总 一、选择 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. 文法S→0S | S1 | 0的语言是( )。 A. { 0 m1m| m >=0 } B. { 0 m1m| m >=1 } C. { 0 m1n | m>=1,n>=0 } D. { 0 m1n | m>=0,n>=1 } 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. 在利用寄存器R生成T1:=C/B的目标代码同时,还应记录信息( )。 A. C/B在T1中 B. T1在C/B中 C. R含有T1, T1在R中 D. R含有C/B, C/B在R中 1.D 2.B 3.C 4.B 5.B 6.A 7.B 8.D 9.D 10.C
云南大学2009至2010学年上学期信息学院计算机科学与工程系计算机科学与技术专业2007级《编译技术》期中考试B卷（闭卷） 满分100分考试时间：120分钟任课教师：周小兵学院：_______专业：______学号：_______姓名：________ 一、选择题（本大题共4小题，每小题5分，共20分） 1．词法分析器的任务是从源程序中识别____B____。 A、句子 B、单词 C、字符 D、终结符号 2. 文法S→aSb|ab所产生的语言是什么____C____。 A、(ab)n B、a n b m C、a n b n D、a和b的个数相等的a、b串 3.在源程序中，使用的某个变量没有声明，在编译的____C____阶段会报错。 A、词法分析 B、语法分析 C、语义分析 D、代码生成 4．编译器在___C_____阶段进行表达式的类型检查及类型转换。 A、词法分析 B、语法分析 C、语义分析 D、目标代码生成 二、分析题（本大题共2小题，每小题10分，共20分） 1、一个上下文无关文法生成句子abbaa的推导树如下： (1)给出句子的最左推导。 (2)该文法的产生式集合P可能有哪些元素？
(3)找出该句子的所有短语、直接短语、句柄。 解答： （1）句子abbaa最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 注：应该用=>（表示推导），而不能用→（表示定义） （2）产生式集合P可能： S→ABS |Aa|εA→a B→SBB|b （3）把abbaa表示成a1b1b2a2a3 短语：a1, a2, ε, b1, b2, b1b2, a2a3 , a1b1b2a2a3 直接短语：a1, a2, ε, b1, b2, 句柄：a1 注：由于有多个a和b，所以应该加上下标以示区别。 2、将正规式r=a(b|c)*转换成相应的正规文法 解答： 令S是文法的开始符号，首先形成S→a(b|c)*，然后形成S→aA和A→(b|c)*，再变换成： S→aA A→(b|c)B A→ε B→(b|c)B B→ε 进而变换为全部符合正规文法产生式的形式： S→aA A→bB|c B|ε B→bB|c B|ε 注：也可分开写成7个产生式 三、设计题（本大题共2小题，每小题10分，共20分） 对文法G[A]: A → aABe|a B → Bb|d 1. 文法G[A]是LL(1)文法吗？为什么？如果不是，请改写。 2. 改写后的文法是LL(1)文法吗？请给出它的预测分析表。 解答： 1.文法G[S]不是LL(1)文法，因为存在左公因子（A → aABe|a）和左递归（B →
北方工业大学 《编译原理》课程期末复习题（答案） A 卷 2016年春季学期 开课学院 考试方式：闭卷 考试时间：120 分钟 班级 姓名 学号 一判断题（每个小题1分，共10分） 1. 程序语言主要由语法和语义两方面定义。 （ ） 2. 自上而下分析方法会遇到的主要问题有左递归和回溯。 （ ） 3. 已知文法G ：E →i | EAE ，A →+|* ，其中的终结符号集包括{i ，+}。（ ） 4. 编译程序是将高级语言程序翻译成机器语言程序。 （ ） 5. 只含有综合属性的属性文法称为S-属性文法。 （ ） 6. LL(1)文法中第一个L 的含义是从左到右扫描输入串。 （ ） 7. 在编译中进行语法检查的目的是为了发现程序中所有错误。 （ ） 8. 一个语义子程序描述了一个文法所对应的翻译工作。 （ ） 9. 一个句型的直接短语是唯一的。 （ ） 10. 确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ） 解：1.√ 2.√ 3.× 4.× 5.√ 6.√ 7.× 8.× 9.× 10.√ 二、选择题（每个小题1分，共20分） 1. 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是____。 A. 短语文法 B. 正规文法 C. 上下文有关文法 D. 上下文无关文法 2. 不可能是目标代码。 A. 汇编指令代码 B. 可重定位指令代码 C. 绝对指令代码 D. 中间代码 3. 将编译程序分成若干个“遍”是为了 。 A. 提高程序的执行效率 B. 利用有限的机器内存并提高机器的执行效率 C. 使程序的结构更加清晰 D. 利用有限机器内存但降低了机器的执行效率 4. 后缀式ab+cd+/可用表达式 来表示。 订 线 装
编译原理期中试卷(软件工程) 1．简答题（每题5分，共计15分） (1) 简述编译程序与解释程序的区别。 解释程序不生成目标代码，而编译程序生成目标代码 (2) 什么是句柄？ 令G[S]是一个文法，如果有S=>*αAδ且A=>*β则称β是一个关于非终结符号A 的，句型αβδ的短语。其次如果有S=>αAδ且A=>β则称β是直接短语。一个句型的最左直接短语称为该句型的句柄。 (3) 自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么？ 自顶向下的语法分析解决的核心问题是：（1）消除左递归 (2) 避免回溯 自底向上的语法分析解决的核心问题是：寻找句柄 2．文法G[S]: S∷=a｜b｜(T) T∷=T,S｜S 给出句型(a,(b,S))的短语与直接短语(简单短语)、句柄和最左素短语。（10分）短语：(a,(b,S))，a,(b,S)，a，(b,S)，b,S，b 直接短语(简单短语)：a，b 句柄：a 最左素短语：a 3．按指定类型给出下列语言的文法,并指出语言的类型。（每个5分，共10分） (1) L1={ a n b m| n≥0,m>0 } S::= aS|bS|b (2) L2={ 0n1n b m c m| n>0，m ≥0}S::=AB A::=0A1|01 B::=bBc|ε4．构造正则式ba*|(ab)*b对应的DFA并最小化。（要求步骤清楚，15分）
5. 请在划线处填空。（5分） BEGIN /* Start Algorithms */ (1) PUSH(‘#’),PUSH(‘S ’); 把第一个输入符号读进b; FLAG = TRUE ； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在X 中； IF X ∈ Vt THEN IF X==b THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X==‘#’ THEN FLAG = FALSE ELSE ERROR ELSE IF M [X,b]={X → X1X2…XK} THEN (2) 将XkXk-1…X1入栈 ELSE ERROR END /* End Of While */ END /* End of Algorithms */ 6．为文法G[P]：P ∷=begin S end S ∷=A ｜C A ∷=V:=E C ∷=if E then S E::=VE' E'::=+VE' | ε V ∷=i 构造递归下降识别程序（15分） 构造程序（略，注意判断预测的符号）
一、单项选择题 1、将编译程序分成若干个“遍”是为了( B ) A．提高程序的执行效率 B. 使程序的结构更加清晰 C．利用有限的机器内存并提高机器的执行效率 D．利用有限的机器内存但降低了机器的执行效率 2、不可能是目标代码的是( D ) A．汇编指令代码 B．可重定位指令代码 C．绝对指令代码 D．中间代码 3、词法分析器的输入是( B ) A．单词符号串 B．源程序 C．语法单位 D．目标程序 4、编译程序中的语法分析器接受以 c 为单位的输入，并产生有关信息供以后各阶段使用。 可选项有：a、表达式 b、产生式 c、单词 d、语句 5、高级语言编译程序常用的语法分析方法中，递归下降分析法属于 b 分析方法。 可选项有：a、自左至右 b、自顶向下 c、自底向上 d、自右向左 6、已知文法G[E]：E→TE’ E’ →+TE’∣ε T→FT’ T’ →*FT’∣ε F→（E）∣id 求：FOLLOW（F）=（1） d ， FIRST（T’）=（2） b 可选项有： a、｛*，+｝ b、｛*，ε｝ c、｛+,#，）｝ d、｛*，+，#，）｝ e、｛#，）｝ f、｛*，+，#，id｝ 7、中间代码生成时所遵循的是( C ) A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 8、编译程序是对( D ) A．汇编程序的翻译 B．高级语言程序的解释执行 C．机器语言的执行 D．高级语言的翻译 9、词法分析应遵循( C ) A．语义规则 B．语法规则 C．构词规则 D．等价变换规则 10、词法分析器的输出结果是( C ) A．单词的种别编码 B．单词在符号表中的位置 C．单词的种别编码和属性值 D．单词属性值 11、正规式M1和M2等价是指( C ) A．M1和M2的状态数相等 B．M1和M2的有向弧条数相等
第一章 引论 ? 为什么要用编译器 ? 与编译器相关的程序 ? 翻译步骤 ? 编译器中的主要数据结构 1、语言处理器 1、简单的说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。 2、编译器的重要任务之一就是报告它在翻译过程中发现的源程序中的错误。 3、使用编译器是为了提高编程的速度和准确度。 4、与编译器相关的程序：解释程序（interpreter ）、汇编程序（assembler ）、连接程序（linker ）、装入程序（loader ）、预处理器（preprocessor ）、编辑器（editor ）、调试程序（debugger ）、描述器（profiler ）、项目管理程序（project manager ）。 5、解释器是另一种常见的语言处理器。它并不通过翻译的方法生成目标程序。从用户的角度来看，解释器直接利用用户提供的输入执行源程序中指定的操作。 6、一个源程序可能被分割成多个模块，并存放于独立的文件中。把源程序聚合在 一起的任务有时会由一个被称为预处理器（preprocessor ）的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。 7、连接器（linker ）能够解决外部内存地址的问题。 8、加载器（loader ）把所有的可执行目标文件放到内存中执行。 2、一个编译器的结构 Output Source Program Front end Back end Object
1、将编译器看成黑盒，则源程序映射为在语义上等价的目标程序，而这个映射由两部分组成：分析部分和综合部分。 2、分析部分把源程序分解成多个组成要素，并在这些要素之上加上语法结构。 3、综合部分根据中间表示和符号表中的信息来构造用户期待的目标程序。 4、编译器的第一个步骤：词法分析（lexical）或扫描（scanning）。词法分析器读入组成源程序的字符流，并且将它们组成有意义的词素（lexeme）的序列。词法分析器产生词法单元（token）。 5、分隔词素的空格会被词法分析器忽略掉。 6、编译器的第二个步骤：语法分析（syntax）或解析（parsing）。语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。 7、语义分析（static semantic analysis）：语义分析器使用语法树和符号表中的信息 来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。语义分析的一个重要部分是类型检查（type checking）。编译器检查每个运算符是否具有匹配的运算分量。 8、总的说，编译器的翻译步骤是：扫描程序----语法分析程序----语义分析程序---- 源代码优化程序----代码生成器----目标代码优化程序。 3、编译器结构中的主要数据结构 1、记号（token） 2、语法树（syntax tree） 3、符号表（symbol table） 4、常数表（literal table） 5、中间代码（intermediate code） 6、临时文件（temporary file） 4、将编译器分成了只依赖于源语言（前端（ front end））的操作和只依赖于目 标语言（后端（ back end））的操作两部分。 第二章词法分析 ? 扫描处理 ? 正则表达式 ? 有穷自动机 ? 从正则表达式到D FA ? 利用L e x自动生成扫描程序 1、Tokens记号标记：identifiers、keywords、integers、floating-point、symbols、strings、comments 1、使用正则表达式去描述程序语言tokens 2、一个正则表达式是归纳确定 3、一个正则表达式R描述一组字符串集合L(R) 4、L(R) = the language defined by R 5、所有的token都能用正则表达式表示 2、正则表达式： 1、基本正则表达式：他们是字母比哦啊中的单个字符且自身匹配
词法分析： 1、根据正规式（a|b）*(aa|bb) （a|b）*构造NFA, 然后确定化成DFA 2、设计一个最小化的DFA，其输入字母表是{0,1}，接受从0开始以1结尾的所有序列 正规式为：0（0|1）*1 语法分析： 1、已知文法G[E]: E E+T|E-T|T，T T*F|T/F|F，F(E)|i 证明(F+i)-T*(E-T)是文法的句型，并给出该句型的短语、直接短语和句柄 3、文法：S Aa A BB B sb|c 消除左递归 4、文法：S Qd Q Rb|Se R Sa|Qf|a 消除左递归 5、判断文法S cA|BA A CB|ε B dB C a|bd 是否是LL（1）文法，说明理由。是的话构造预测分析表 6、已知文法G[A]: A(A)|a，构造该文法的LR(0)分析表 7、判断文法S Sab|bR R S|a 是不是SLR文法，若是，构造分析表，不是的话说明理由。 语法制导翻译和中间代码生成： 1、分别给出表达式-（a*（b-c））+d 的逆波兰式、四元式和三元式 逆波兰式：@(a*(b-c))+d到@(a*(bc-))+d到@(abc-*)+d到(abc-*@)+d到abc-*@d+ 注意：@为求负的运算符- 四元式： (-,b,c,T1) (*,a,T1,T2) (@,T2,-,T3) (+,T3,d,T4) 2、写出a*-(b+c)树形表示法 3、对布尔式X+Y>Z∨A∧(┐B∨C)进行翻译 4、把语句if A∨B 一、填空题（每空1分，共20分） 1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析, 中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理 ___和 ___出错处理__。 2．若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序称为 ___编译程序__ 。 3．编译方式与解释方式的根本区别在于__是否生成目标代码___。 4．对编译程序而言,输入数据是___源程序__, 输出结果是__目标程序___。 5．若两个正规式e1和e2所表示的正规集相同,则e1和e2等价,写作e1=e2。 6．一个句型中的最左简单短语称为该句型的___句柄__。 7．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。 二、是非题（请在括号内，正确的划√，错误的划×）（每个1分，共10分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙 机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B ∈V N ， a 、 b ∈V T 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√)（2班做） 6.有穷自动机接受的语言是正规语言。(√)（1班做） 7.对任何一个NFA M都存在一个DFA M’,使得L(M’)=L(M).( √ ) 8．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×) 9．确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 10．词法分析作为单独的一遍来处理较好。(× ) 11．有穷自动机接受的语言是正规语言。（√） 三、选择题（每小题2分，共20分） 1．文法G 产生的_____的全体是该文法描述的语言。 A．( ) 句型B．( ) 终结符集C．( ) 非终结符集D．( ) 句子 2．若文法G 定义的语言是无限集，则文法必然是_____。 A．( ) 递归的B．( ) 前后文无关的 C．( ) 二义性的D．( ) 无二义性的 3．四种形式语言文法中，1型文法又称为_____文法。 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．采用自上而下分析，必须_____。（2班做） A．( ) 消除左递归B．( ) 消除右递归 C．( ) 消除回溯D．( )提取公共左因子 9．在规范归约中，用_____来刻画可归约串。（2班做） A．( )直接短语B．( )句柄 C．( )最左素短语D．( )素短语编译原理半期考试答案
相关主题
文本预览