编译原理期末复习
- 格式:doc
- 大小:2.89 MB
- 文档页数:21
《编译原理》期末试题(一)一、是非题(请在括号内,正确的划√,错误的划×)(每个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.构造编译程序应掌握______。
编译原理期末复习题(包含上一份N多答案)(总28页)--本页仅作为文档封面,使用时请直接删除即可----内页可以根据需求调整合适字体及大小--编译原理复习题一、填空题: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个输入符号)。
1.给出语言{a n b n a m b m | n,m≥0}的一个上下文无关文法。
(6分)解:G[S]:S—>ABA—>aAb |εB—>aBb |ε2.给出语言{1 n 0 m 1 m0 n | n,m≥0}的一个上下文无关文法。
解:G[S]:S—>1S0 | AA—>0A1 |ε3.P48 第6题(5)、(6).画语法树6、已知文法G:<表达式>::=<项>|<表达式>+<项><项>::=<因子>|<项>*<因子><因子>::=(<表达式>)|i(5)i+(i+i) (6)i+i*i解:(5)语法树:(6)语法树:4.P48第13题直接短语等13、一个上下文无关文法生成句子abbaa的推导树如下:(3)求直接短语解:直接短语有:a ε bP102例题6.1及其分析.( 后加画语法树)例6.1 设文法G[S]为:(1)S—>aAcBe(2)A—>b(3)A—>Ab(4)B—>d对输入串abbcde#进行分析,检查该符号串是否是G[S]的句子。
步骤符号栈输入符号串动作(1)# abbcde# 移进(2)#a bbcde# 移进(3)#ab bcde# 归约(A—>b)(4)#aA bcde#移进(5)#aAb cde# 归约(A—>Ab)(6)#aA cde# 移进(7)#aAc de# 移进(8)#aAcd e# 归约(B—>d)(9)#aAcB e# 移进(10)#aAcBe # 归约(S—>aAcBe)(11)#S # 接受一、计算分析题(60%)1、正规式→ NFA→ DFA→最简DFAP72第1题(1)、(4);第一题1、构造下列正规式相应的DFA.(1)1(0|1)*101解:先构造NFA0 1S AA A ABAB AC ABAC A ABZABZ AC AB除S,A外,重新命名其他状态,令AB为B、AC为C、ABZ为D,因为D含有Z(NFA的终态),所以0 1S AA A BB C BC A DD C B(4) b((ab)*|bb)*ab解:先构造NFA得到DFA如下所示:P72第4题(a)4、把下图确定化和最小化解:确定化:a b0 01 101 01 11 0、{1},其中A为初态,A,B为终态,因此有:a bA B CB B CC A最小化::初始分划得终态组{A,B},非终态组{C}Π0:{A,B},{C},对终态组进行审查,判断A和B是等价的,故这是最后的划分。
期末复习总结《编译原理》第一章:绪论一、填空问题①由于计算机只能认识机器语言,所以需要翻译程序将高级语言翻译成计算机可以识别的机器语言。
②编译程序的工作过程一般主要划分为词法分析,语法分析,中间代码生成,代码优化,目标代码生成等几个基本阶段,同时还会伴有表格管理和出错处理。
③如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两个阶段:编译阶段和运行阶段。
如果编译程序生成的目标程序是汇编语言的程序,则源程序的执行分为三个阶段:编译阶段,汇编阶段和运行阶段。
1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于是否生成目标代码 .1-05.对编译程序而言,输入数据是源程序,输出结果是目标程序 .1-10.一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括(1)c.其中, (2)b 和代码优化部分不是每个编译程序都必需的. 词法分析器用于识别 (3)c ,语法分析器则可以发现源程序中的 (4)d .(1) a.模拟执行器 b.解释器 c.表格处理和出错处理 d.符号执行器(2) a.语法分析 b.中间代码生成 c.词法分析 d.目标代码生成(3) a.字符串 b.语句 c.单词 d.标识符(4) a.语义错误 b.语法和语义错误 c.错误并校正 d.语法错误1-11.程序语言的语言处理程序是一种 (1)a . (2)b 是两类程序语言处理程序,他们的主要区别在于 (3)d .(1) a.系统软件 b.应用软件 c.实时系统 d.分布式系统(2) a.高级语言程序和低级语言程序 b.解释程序和编译程序c.编译程序和操作系统d.系统程序和应用程序(3) a.单用户与多用户的差别 b.对用户程序的查错能力c.机器执行效率d.是否生成目标代码1-12.汇编程序是将 a 翻译成 b ,编译程序是将 c 翻译成 d .a.汇编语言程序b.机器语言程序c.高级语言程序d. a 或者 be. a 或者 cf. b 或者 c1-13.下面关于解释程序的描述正确的是 b .(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和 FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的a. (1)(2)b. (1)c. (1)(2)(3)d.(2)(3)1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段,而解释程序通常缺少 (1)e 和 (1)b .其中, (1)e 的目的是使最后阶段产生的目标代码更为高效.与编译系统相比,解释系统 (2)d .解释程序处理语言时,大多数采用的是 (3)b 方法.(1): a. 中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化(2): a.比较简单,可移植性好,执行速度快b.比较复杂,可移植性好,执行速度快c.比较简单,可移植性差,执行速度慢d.比较简单,可移植性好,执行速度慢(3): a.源程序命令被逐个直接解释执行 b.先将源程序转化为之间代码,再解释执行c.先将源程序解释转化为目标程序,在执行d.以上方法都可以1-15.用高级语言编写的程序经编译后产生的程序叫 b .用不同语言编写的程序产生 a 后,可用 g 连接在一起生成机器可执行的程序.在机器中真正执行的是 e .a. 源程序b. 目标程序c. 函数d. 过程e. 机器指令代码f. 模块g. 连接程序h.程序库1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容: c , d , f .a. 汇编语言b. 高级语言c. 源语言d. 目标语言e. 程序设计方法f. 编译方法g. 测试方法h. 机器语言1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成(1)d ,诸阶段的工作往往是 (2)d 进行的.(1) a. 过程 b. 程序 c. 批量 d.遍(2) a. 顺序 b. 并行 c. 成批 d.穿插1-18.编译程序与具体的机器 a , 与具体的语言 a .a. 有关b.无关1-19.使用解释程序时,在程序未执行完的情况下, a 重新执行已执行过的部分.a. 也能b.不可能1-20.编译过程中,语法分析器的任务就是 b .(1) 分析单词是怎样构成的(2)分析单词串是如何构成语句和说明的(3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构a. (2)(3)b. (2)(3)(4)c. (1)(2)(3)d.(1)(2)(3)(4)1-21.编译程序是一种常用的 b 软件.a. 应用b. 系统1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前,一般要经过 b 这几步.(1) 编辑 (2) 编译 (3) 连接 (4) 运行a. (1)(2)(3)(4)b. (1)(2)(3)c. (1)(3)d.(1)(4)1-23.编译程序必须完成的工作有 a .(1) 词法分析 (2) 语法分析 (3) 语义分析(4) 代码生成 (5) 之间代码生成 (6) 代码优化a. (1)(2)(3)(4)b. (1)(2)(3)(4)(5)c. (1)(2)(3)(4)(5)(6)d. (1)(2)(3)(4)(6)e. (1)(2)(3)(5)(6)1-24.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法a .a. 不正确b.正确1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由 b 完成的.a. 编译器b. 汇编器c. 解释器d. 预处理器1-26.编译程序生成的目标程序 b 是机器语言的程序.a. 一定b. 不一定1-27.编译程序生成的目标程序 b 是可执行的程序.a. 一定b. 不一定1-28.编译程序是一种 B 。
编译原理期末总结复习(经典版)编制人:__________________审核人:__________________审批人:__________________编制单位:__________________编制时间:____年____月____日序言下载提示:该文档是本店铺精心编制而成的,希望大家下载后,能够帮助大家解决实际问题。
文档下载后可定制修改,请根据实际需要进行调整和使用,谢谢!并且,本店铺为大家提供各种类型的经典范文,如公文写作、报告体会、演讲致辞、党团资料、合同协议、条据文书、诗词歌赋、教学资料、作文大全、其他范文等等,想了解不同范文格式和写法,敬请关注!Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you!In addition, this shop provides you with various types of classic sample essays, such as official document writing, report experience, speeches, party and group materials, contracts and agreements, articles and documents, poems and songs, teaching materials, essay collections, other sample essays, etc. Learn about the different formats and writing styles of sample essays, so stay tuned!编译原理期末总结复习编译原理期末总结复习(精选3篇)编译原理期末总结复习篇1一、简答题1.什么是编译程序?答:编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。
《编译原理》期末考试复习题一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分)×1.计算机高级语言翻译成低级语言只有解释一种方式。
()×2.在编译中进行语法检查的目的是为了发觉程序中所有错误。
()√3.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。
()×4.正则文法其产生式为 A->a , A->Bb, A,B∈VN , a 、 b∈VT 。
()√5.每个文法都能改写为 LL(1) 文法。
()√6.递归下降法允许任一非终极符是直接左递归的。
()×7.算符优先关系表不一定存在对应的优先函数。
()×8.自底而上语法分析方法的要紧问题是候选式的抉择。
()×9.LR 法是自顶向下语法分析方法。
()×10.简单优先文法允许任意两个产生式具有相同右部。
()三、填空题(每空1分,共10分)1.编译程序的工作过程一般能够划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本时期,同时还会伴有__ ___和 ___ _。
表格治理出错处理_2.若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。
_目标程序 _编译程序3.编译方式与解释方式的全然区别在于__ __。
是否生成目标代码_4.对编译程序而言,输入数据是__ __, 输出结果是__ ___。
_源程序 目标程序5.产生式是用于定义__ __的一种书写规则。
_语法成分6.语法分析最常用的两类方法是___ __和__ __分析法。
自上而下 _自下而上四、简答题(20分)1. 什么是句子? 什么是语言 ?答:(1)设G是一个给定的文法,S是文法的开始符号,假如S x(其中x∈VT*),则称x是文法的一个句子。
(2)设G[S]是给定文法,则由文法G所定义的语言L(G)可描述为:L(G)={x│S x,x∈VT*} 。
《编译原理》期末复习资料【题1】1.(a|b)*(aa|bb)(a|b)*画出状态转换图。
Ia Ib①1,2,3 2,3,4 2,3,5②2,3,4 2,3,4,6,7,8 2,3,5③2,3,5 2,3,4 2,,3,5,6,7,8④2,3,4,6,7,8 2,3,4,6,7,8 2,3,5,7,8⑤2,3,5,6,7,8 2,3,4,7,8 2,3,5,6,7,8⑥2,3,5,7,8 2,3,4,7,8 2,3,5,6,7,8⑦2,3,4,7,8 2,3,4,6,7,8 2,3,5,7,8Ia Ib1 2 32 4 33 2 54 4 65 7 56 7 57 4 6新的状态转换图如下:(1)A={1,2,3},B={4,5,6,7} Aa={2,4} ×(2)A={1,3},B={2},C={4,5,6,7} Aa={2}⊂B,Ab={3,5} ×(3)A={1},B={2},C={3},D={4,5,6,7}(单元素可以不用看,必有,古先看D)Da={4,7}⊂D,Db={5,6}⊂D,Aa={2}⊂B,Ab={3}⊂C,Ba={4}⊂D,Bb={3}⊂C,Ca={2}⊂B,Cb={5}⊂C,则有baA B CB D CC B DD D D2.(a*|b*)b(ba)*的状态转换图。
Ia Ib①1,2,3,4 2,4 3,4,5,6,8②2,4 2,4 5,6,8③3,4,5,6,8 --- 3,4,5,6,7,8④5,6,8 --- 7⑤3,4,5,6,7,8 6,8 3,4,5,6,7,8⑥7 6,8 ---⑦6,8 --- 7Ia Ib1 2 32 2 43 --- 54 --- 65 7 56 7 ---7 --- 6新的状态转换图如下:化简:(用终结状态与非终结状态,然后输出状态一致分一类)。
(1)A={1,2,6},B={3,4,5,7} Aa={2} ×(2)A={1,2},B={6},C={3,4,7},D={5} Cb={5,6} ×(只要有一个不属于任何一个集合,就不行) (3)A={1,2},B={6},C={3},D={4,7},E={5} Ab={3,4} × (4) A={1},B={2},C={6},D={3},E={4,7},F={5} Aa={2}⊂B ,Ab={3}⊂D ,Ba={2}⊂B ,Bb={4}⊂E ,Ca={7}⊂E ,Db={5}⊂F ,Eb={6}⊂C ,Fa={7}⊂E ,Fb={5}⊂Fa b A B D B B E C E --- D --- F E --- C FEF[注意事项]:[知识要点]:正则表达式:******|,|,)|(,)|(,)(,,|,ab a b a a b a a b a ab ab b a a{}a a aaa aa a a ,,,,*ε⇔;{}b a a b a ,)b (|⇔或;{}ab b a ab ⇔)(和;(){},,,,*ababab abab ab ab ε⇔;()()()(){} ,,,,,,||||*baba aabb aab b a b a b a b a b a ε⇔⇔()*|b a a 是最左边一个字母一定是a ,其余字母为b a 、的任意组合,不包括ε。
编译原理一、单选题1、将编译程序分为若干个“遍”是为了()。
BA.提高程序的执行效率B.使程序的结构更加清晰C.利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握()。
DA.源程序B.目标语言C.编译方法D.以上三项都是3、变量应当()。
CA.持有左值B.持有右值C.既持有左值又持有右值D.既不持有左值也不持有右值4、编译程序绝大多数时间花在()上。
DA.出错处理B.词法分析C.目标代码生成D.管理表格5、()不可能是目标代码。
DA.汇编指令代码B.可重定位指令代码C.绝对指令代码D.中间代码6、编译程序是对()。
DA.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译7、正规式M1和M2等价是指()。
CA.M1和M2的状态数相等B.M1和M2的有象弧条数相等C.M1和M2所识别的语言集相等D.M1和M2状态数和有象弧条数相等8、如果文法G是无二义的,则它的任何句子()。
AA.最左推导和最右推导对应的语法树必定相同。
B.最左推导和最右推导对应的语法树可能相同。
C.最左推导和最右推导必定相同。
D.可能存在两个不同的最左推导,但它们对应的语法树相同。
9、文法G:S→S+T|TT→T*P|PP→(S)|i句型P+T+i的短语有()BA.i,P+TB. P,P+T,i,P+T +iB.P+T + i D. P,P+T,i10、产生正规语言的文法为()。
DA.0型B.1型C.2型D.3型11、文法G:S→b|˄|(T)T→T˅S|S则FIRSTVT(T)=() CA.{b,˄,(}B.{b,˄,)}C.{b,˄,(,˅}D.{b,˄,),˅}12、给定文法:A→bA | cc,下面的符号串中,为该文法句子的是()。
A①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc可选项有:A.①B.①③④⑤C.①④D.①④⑤13、采用自上而下分析,必须()。
第八节习题一、单项选择题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、编译程序各阶段的工作都涉及到bc 。
a.语法分析b.表格管理c.出错处理d.语义分析e.词法分析2、编译程序工作时,通常有abce 阶段。
<编译原理>历年试题及答案一.(每项选择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)构造预测分析表。
编译原理期末复习题⼀、单项选择题1.构造编译程序应掌握。
Da. 源程序b. ⽬标语⾔c. 编译⽅法d. 以上三项都是 2.编译程序绝⼤多数时间花在上。
Da. 出错处理b. 词法分析c. ⽬标代码⽣成d. 表格管理 3.DFA M(见图1-1)接受的字集为。
Da. 以0开头的⼆进制数组成的集合b. 以0结尾的⼆进制数组成的集合c. 含奇数个0的⼆进制数组成的集合d. 含偶数个0的⼆进制数组成的集合4. -a-(b*c/(c-d)+(-b)*a)的逆波兰表⽰是。
(@代表后缀式中的求负运算符) Ca. abc*cd-b@a*+/-@b. a@bc*cd-b@a*+/-c. a@bc*cd-/b@a*+-d. a@bc*/cd-b@a*+- 5.在规范归约中,⽤来刻画可归约串。
Ba. 直接短语b. 句柄c. 最左素短语d. 素短语6.若B 为⾮终结符,则A →α·B β为项⽬。
Da. 归约b. 移进c. 接受d. 待约 7.中间代码⽣成时所依据的是。
Ca. 语法规则b. 词法规则c. 语义规则d. 等价变换规则8.有⽂法G 及其语法制导翻译如下所⽰(语义规则中的*和+分别是常规意义下的算术运算符):E →E (1)∧ T {E.val = E (1).val * T.val} E →T {E.val = T.val}T →T (1)# n {T.val = T (1).val + n.val } T → n {T.val = n.val}则分析句⼦1 ∧ 2 ∧ 3 # 4其值为。
Ca. 10b. 34c. 14d.54 9.如果⽂法G 是⽆⼆义的,则它的任何句⼦α。
A1图1-1a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导,但它们对应的语法树相同10.下列动作中,不是⾃下⽽上分析动作的是:。
编译原理期末复习编译原理是计算机科学与技术专业的一门重要基础课程,它研究的是程序设计语言在计算机上的实现方式。
编译原理的学习主要涉及到词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等内容。
针对这些方面,下面将对编译原理的重要内容进行总结和复习。
一、词法分析词法分析是编译过程的第一步,其主要目的是将源程序中的字符序列划分成词法单位。
常用的词法单元有关键字、标识符、常数、运算符、界符等。
词法分析通过有限自动机或正则表达式来实现。
二、语法分析语法分析是将词法分析阶段生成的词法单元流转化为一个抽象语法树。
语法分析的主要工作是根据给定的语法规则,将输入串分析成语法树。
语法分析有两种主要方法:基于文法的自上而下的分析和基于文法的自下而上的分析,常用的算法包括LL(1)、LR(1)、SLR(1)和LALR(1)等。
三、语义分析语义分析是对语法分析的结果进行语义检查和语义动作的计算。
语义分析的主要任务是检查源程序是否符合语义规则,计算符号的类型和值,并生成中间代码。
语义分析常用的方法包括语义制导翻译和符号表的建立。
四、中间代码生成中间代码是指在编译过程中生成的一种可以被多次优化和被不同目标代码生成程序使用的代码。
中间代码生成的目的是将源程序翻译成其中一种中间形式,便于进一步优化和生成目标代码。
中间代码生成的方法有三地址码、四地址码和虚拟机代码等。
五、代码优化代码优化是编译过程中的重要环节,其主要目的是对中间代码进行优化,使得生成的目标代码更加高效和紧凑。
代码优化使用各种数据流分析、指令调度和寄存器分配等技术,常用的优化方法有常量传播、公共子表达式消除、代码移动和死代码消除等。
六、目标代码生成目标代码生成是将中间代码转化为目标机器代码的过程,目标代码生成需要考虑目标机器的特性和限制。
目标代码生成包括指令选择、寻址方式的选择和寄存器分配等步骤。
常用的技术有基于各种寻址方式的代码选择算法、寄存器分配算法和指令调度算法等。
编译原理期末考试复习题(含答案)一、选择题1.代码生成阶段的主要任务是(C)。
A.把高级语言翻译成汇编语言B.把高级语言翻译成机器语言C.把中间代码变换成依赖具体机器的目标代码D.把汇编语言翻译成机器语言2.文法G 所描述的语言是( C )的集合。
A.文法G 的字母表V 中所有符号组成的符号串B.文法G 的字母表V 的闭包V* 中的所有符号串C.由文法的开始符号推出的所有终结符串D.由文法的开始符号推出的所有符号串3.语言是(C)。
A.终结符与非终结符的符号串的集合B.非终结符符号串的集合C.终结符符号串的集合D.产生式的集合4.常用的中间代码形式不含(D)。
A.三元式B.四元式C.逆波兰式D.语法树5.四元式之间的联系是通过(B)实现的。
A.指示器B.临时变量C.符号表D.程序变量6.词法分析器的输出结果是( C )。
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.下推自动机识别的语言是( C )A.0型语言 B.1型语言C.2型语言 D.3型语言9. 在规范归约中,用(B)来刻画可归约串。
A.直接短语 B.句柄C.最左素短语 D.素短语10.词法分析器用于识别( C)。
A.字符串 B.语句 C.单词 D.标识符11.一个句型中称为句柄的是该句型的最左(D)A.非终结符号 B.短语 C.句子 D.直接短语12.文法 G[E] :E→T∣E+TT→F∣T * FF→a∣(E)该文法句型 E + F * (E + T) 的简单短语是下列符号串中的(B)。
①(E+T)②E+T ③F ④ F * (E+T)A.①和③B.②和③C.③和④D.③13.通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括(C)。
《编译原理》期末复习【题型】一、填空题:每空1分,共10分;二、单选题:每题2分,共20分;三、应用题:每小题6分,共48分;四、综合分析题:每小题11分,共22分。
【知识点】1.编译程序的整个过程从逻辑上依次分为哪6个阶段,其中还涉及哪2个重要工作。
2.语法分析有哪两大类方法?3.编译程序和解释程序的概念,二者最主要的区别是?4.句柄的定义。
5.什么是规范推导?6.语言、句型、句子的定义。
7.LR分析法中的项目类型定义(待约项目、移入项目、归约项目)。
8.中间代码和目标代码区别。
9.文法与正则表达式所描述的语言及句子。
10.如何判断自动机(状态转换图)所能识别的字符串。
11.中间代码生成时主要依据什么规则?12.根据给定文法,通过推导,画出指定句子的语法树。
13.自底向上的语法分析过程中,构造LR分析表时可能会面临的两种冲突。
14.判断源程序中出现的某类错误可能在编译的哪个阶段被发现。
15.词法分析及语法分析的输入输出是什么?16.0、1、2、3型文法的定义、别名及描述能力强弱排名。
17.证明给定文法是二义性的(参考第二章课后练习)。
18.消除文法的左递归及提取公共左因子。
19.给定一个文法和该文法的句型,要求写出句型的最左推导、画出语法分析树、指出短语、简单短语、句柄(参考第二章课后练习及课件中的例题)。
20.根据有限自动机的定义(五元组),给出其状态转换矩阵和状态转换图。
21.画出按照给定翻译模式分析某句子时所产生的分析树,分析其输出结果(参考第六章课后练习及课件中的例题)。
22.针对给定的语言构造一个文法G,然后判断该文法类型(0、1、2、3型)(参考第二章课后练习)。
23.根据有限自动机M的定义(五元组),画出M的状态转换图,并说明它所识别或接受的语言是什么(参考课件第三章例题)。
24.给出一个复合表达式,写出该表达式的三元式和四元式(如:-a*(b+c)/d)。
25.判断某语法制导定义在给定输入下的输出结果,分析文法产生的语言,指出语法制导定义功能。
编译原理期末考试复习题一、选择题1. 编译器的主要功能是什么?A. 代码优化B. 语法分析C. 代码生成D. 所有上述选项2. 词法分析器的主要任务是什么?A. 将源代码转换为汇编代码B. 识别源程序中的词法单元C. 检查源代码的语法正确性D. 生成中间代码3. 语法分析中使用最多的两种分析方法是?A. 自顶向下分析和自底向上分析B. 递归下降分析和自底向上分析C. 递归下降分析和自顶向下分析D. 正则表达式分析和递归下降分析4. 一个文法是递归的,它可能产生无限多的字符串。
这种文法被称为:A. 上下文无关文法B. 上下文相关文法C. 上下文自由文法D. 正则文法5. 语义分析的主要任务是什么?A. 识别词法单元B. 构建语法树C. 确定程序的语义D. 生成目标代码二、简答题1. 解释什么是词法分析,并简述其在编译过程中的作用。
2. 描述自顶向下分析和自底向上分析的区别,并给出各自的优点。
3. 什么是中间代码?它在编译过程中有什么作用?4. 什么是代码优化?请举例说明一个常见的代码优化技术。
5. 简述编译器的后端主要负责哪些工作?三、计算题1. 给定一个简单的文法,写出其产生的第一个词法单元序列,并解释其生成过程。
2. 给出一个程序的控制流图(CFG),并根据该图计算其活跃变量。
四、论述题1. 论述编译器设计中的一些常见问题以及解决这些问题的策略。
2. 讨论在现代编译器中,如何实现对并行计算的支持。
五、综合应用题1. 设计一个简单的词法分析器,能够识别以下词法单元:关键字、标识符、常量、运算符,并给出相应的正则表达式。
2. 给定一个简单的上下文无关文法,实现一个递归下降分析器,并给出分析过程。
六、开放性问题1. 考虑到现代编程语言的复杂性,你认为未来的编译器设计将面临哪些新的挑战?2. 描述一个你认为可以改进现有编译器性能或功能的想法或技术。
结束语:本复习题旨在帮助学生全面回顾编译原理课程的主要内容,包括编译器的各个阶段、关键技术和算法。
编译原理期末复习鉴于编译原理马上就要期末考试,我将手中集中的一些资料上的题目进行了整理归类,每种类型题目给出了所涉及到的基本知识,然后对每类题目中的第一道例题进行了做法进行了讲解,剩下的例题请给大家作为练习,答案也都给出,希望对大家复习有所帮助,最后由于时间很紧,整理的有些仓促,整理中难免有遗漏或错误,请大家见谅。
注:下面出现的字母中,若无特别说明,小写英文字母为终结符,大写英文字母为非终结符,希腊字母为终结符与非终结符的任意组合。
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:产生式集合(有限)。
(6)二义性文法:一个文法中存某个句子,它有两个不同的最左(或者最右推导),则称该文法是二义性的。
例子如文法G:S→if expr then S |otherS→if expr then S else S 句子if e1 then if e2 then s1 else s2是二义性的。
(7)文法的形式(注:文法的形式一定要牢记,特别是2型和3型文法一定要牢记,不仅在概念题中有用,在下面的根据语言写文法题中也有重要作用,如果所写的文法形式不对,一切都是无用功……)1)0型文法(短语文法,图灵机):产生式形式为:α→β,其中:α∈ (V T ⋃V N)*且至少含有一个非终结符;β∈ (V T ⋃V N)*2)1型(上下文有关文法,线性界限自动机):产生式形式为:α→β其中:|α| ≤ |β|,仅 S→ε例外但是S不得出现在任何产生式右部。
3)2型文法(上下文无关文法,非确定下推自动机):产生式形式为:P→α, P∈V N,α∈(V T ⋃V N)*。
4)3型文法(正规文法,有限自动机):右线性文法:产生式形如:A →αB 或 A →α其中:α∈ V T*;A,B∈V N 左线性文法:产生式形如:A → Bα或 A →α其中:α∈ V T*;A,B∈V N例题:设G=(V T,V N,S,P)是一个上下文无关文法,产生集合P中的任一个产生式应具有什么样的形式?若G是1型文法呢?若G是正则文法呢?上下文无关文法,产生式形式为:P→α, P∈V N,α∈ (V T ⋃V N)*。
1型文法:产生式形式为:α→β其中:|α| ≤ |β|,仅 S→ε例外。
正则文法:右线性文法:产生式形如:A →αB 或 A →α其中:α∈ V T*;A,B∈V N 左线性文法:产生式形如:A → Bα或 A →α其中:α∈ V T*;A,B∈V N(8)什么是PDA(下推自动机)?答:PDA是下推自动机,PDA M用一个七元组表示(K,Σ,f,H,h0,S,Z)K: 有穷状态集∑:输入字母表(有穷) H:下推栈符号的有穷字母表h0 :H中的初始符号 f: K ⨯(Σ⋃{ε}) ⨯ H –> K ⨯ H* S:属于K是初始状态。
Z:包含于K,是终结状态集合。
(9) 什么是DFA(有穷状态自动机)?自动机M是一个五元式M=(S, ∑, f, S0, F),其中:1)S: 有穷状态集, 2)∑:输入字母表(有穷),3) f: 状态转换函数,为S⨯∑→S的单值部分映射,f(s,a)=s’表示:当现行状态为s,输入字符为a时,将状态转换到下一状态s’。
我们把s’称为s的一个后继状态。
4) S0∈S是唯一的一个初态; 5) F⊆S :终态集(可空)。
(10)推导:所谓推导就是对于一个含非终结符A的符号串,利用规则A→α,把A替换成α得到新符号串的过程。
最左推导:在推导的每一步,选择符号串最左边的非终结符进行替换。
最右推导:在推导的每一步,选择符号串最右边的非终结符进行替换。
(11)归约:归约是推倒的逆过程,即用产生式的左部非终结符替换右部符号串。
(12)什么是句型?什么称为句子?什么是语言?句型:从文法的起始符号出发,经过有限步的推导能够推导出来的符号称为句子。
句子:只由终结符构成的句型称为句子。
语言:所有句子的集合构成该文法描述的语言。
(13)什么是短语?什么是直接短语(也称为简单短语)?什么是句柄?什么是素短语?什么是最左素短语?(以下几个概念一定要理解,考试中肯定会考哪些是短语,直接短语,句柄等,具体方法请参见后面的)短语:如果存在某个文法非终结符P,满足S*⇒βPγ,并且P+⇒α则称α为句型βαγ相对于非终结符P的短语。
直接短语:如果P⇒α,即从P出发一步推出α,则α称为直接短语。
句柄:一个句型的最左直接短语称为该句型的句柄。
素短语:至少含有一个终结符的短语,并且除了自身外,不包含更小的素短语。
最左素短语:句型中最左边的素短语。
(14)自顶向下的语法分析方法中需要解决的主要问题什么?如何表示?答:1)主要需要解决回溯和左递归问题。
2)表示方式,回溯:文法中存在形如A→α1|α2|…|αn,即产生式右部存在多个候选,导致推导时不能确定到底应该选择哪个候选式。
左递归:文法中存在形如P→Pα的形式,推导时会导致推导过程无休止的进行下去。
注:解决方法,对回溯采取的是提取左公因子,对左递归使消除左递归(包括直接左递归和间接左递归)。
(15)内情向量:一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做“内情向量”或“信息向量”的表格中,以便以后计算数组元素的地址时引用这些信息。
每个数组有一个内情向量。
其中的信息包括,数组的类型,维数,各维的上、下界,以及数组的首地址。
(16)C语言的活动记录:SP TOP2、最左最右推导,画语法树,找短语、直接短语、句柄等。
这种题目很简单,送分题,一定不能丢分!考题:1)文法G[S]为:S→SdT | T T→T<G | G G→(S) | a试给出句型(SdG)<a的推导过程及语法树,并找出(SdG)<a的短语,直接(简单)短语、句柄和最左素短语。
分析:(1)推导和画语法树这些都很简单,不再赘述。
(2)根据所画出的语法树,可以很快的找出短语,直接短语,句柄和最左素短语等,先讲一个简单子树的概念,所谓简单子树是指仅具有单层分支的子树。
具体方法如下:短语:任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语;直接短语:任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语;句柄:最左边的直接短语;素短语:至少含有一个终结符的短语,并且除了自身外,不包含更小的素短语。
最左素短语:最左边的素短语。
答:(1)S⇒T⇒ T<G ⇒G<G⇒(S)<G⇒(SdT)<G⇒(SdG)<G⇒(SdG)<a语法树:(2)短语:G,SdG, (SdG), a, (SdG)<a 直接短语:G,a 句柄:G 最左素短:a 注:还有一份试卷将句型改为adT<(S),与这个类似,大家自己做做,答案是短语:a,(S),T<(S),adT<(S) 直接短语:a,(S) 句柄:a 最左素短语:SdG下面两道例题大家看看,一定要会找短语,直接短语,句柄等.※短语、简单短语和句柄示例【例2.12】图2.3为一个算术表达式(型)的语法树:•句型: E+F-T/F*i•短语: E+F-T/F*i,E+F,F,T/F*i,T/F,i•简单短语: F,T/F,i•句柄: FEE - TE + T T * FF T / F i图2.3 E+F-T/F*i 的语法树※一类典型的综合例题:【例2.13】G(S): S->aAcBe ; A->Ab|b ; B->d※给定符号串: aAbcde⑴证明= aAbcde 是一个句型;⑵画出句型的语法树;⑶指出中的短语、简单短语和句柄。
【题解】⑴ S=>aAcBe=>aAbcBe=> aAbcde⑵语法树如右图:⑶短语、简单短语和句柄:Sa A c B eA b d•短语: aAbcde ,Ab , d•简单短语: Ab , d•句柄:Ab考题:2)文法G[E]的产生式为E→E+T|T T→T*F|F F→i|(E)①对于句型(i+i)*i,给出最左最右推导及相应的推导树②列出句型的所有短语、简单短语。
(还有一份试卷上是出句型F+T*F的所有短语、简单短语和句柄,大家自己做做)答:(1)最左推导:E⇒T⇒T*F⇒F*F⇒(E)*F⇒(E+T)*F⇒(T+T)*F⇒(F+T)*F⇒(i+T)*F⇒(i+F)*F⇒(i+i)*F⇒(i+i)*i最右推导E⇒T⇒T*F⇒T*i⇒F*i⇒(E)*i⇒(E+T)*i⇒(E+F)*i⇒(E+i)*i⇒(T+i)*i ⇒(F+i)*i⇒(i+i)*i推导树如下:(2)短语;i,i+i,(i+i),(i+i)*i 直接短语:i 句柄:i3、根据语言推文法这类题目首先要看清题目,指定的是什么文法,一般都是2型(上下无关文法)或者3型(正规文法),这两类文法形式一定要记住,具体请参见第2页的文法分类。
掌握几个基本形式{a n| n>0}对应文法S→aS| a 如果是n>=0则为S→a S|ε(ε是空字) {a n b n | n>0}对应文法S→aSb| ab下面这四道题目老是在试卷中重复出现,所以大家好好看看。