《编译原理》期末考试复习题.docx

该【《编译原理》期末考试复习题 】是由【飞行的振中】上传分享，文档一共【35】页，该文档可以免费在线阅读，需要了解更多关于【《编译原理》期末考试复习题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。;.
《编译原理》期末考试复****题
一、是非题(请在括号内,正确的划√,错误的划×)(每个
2分,共20分)
×。()
×。()
√。()
×->a,A->Bb,A,B∈VN,a、b∈VT。()
√(1)文法。()
√。()
×。()
×。()
×。()
×。()
三、填空题(每空1分,共10分)
,语法解析,语义解析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_____和____。
表格管理出错办理_
,____是机器语言程序或汇编程序,则其翻译程序称为____。
_目标程序_编译程序
。
可否生成目标代码_
,输入数据是____,输出结果是_____。
_源程序目标程序
;.'
;.
。
_语法成分
。
自上而下_自下而上
四、简答题(20分)
什么是句子?什么是语言?
答:(1)设G是一个给定的文法,S是文法的开始符号,若是Sx(其中x∈VT*),则称x是文法的一个句子。
(2)设G[S]是给定文法,则由文法G所定义的语言L(G)可描述为:L(G)={x│Sx,x∈VT*}。
一、是非题(请在括号内,正确的划
√,错误的划×)(每个2分,共20分)
×,
FORTRAN
采用动向储藏分配策略。
()
×。
()
√3
.递归下降解析法是自顶向上解析方法。
()
×4
.产生式是用于定义词法成分
的一种书写规则。()
√。
()
√(1)解析法的名称中,
S的含义是简单的。()
×7
.综合属性是用于
“自上而下
”传达信息。()
×
属性和特色等有关信息
,如种类、种属、所占单元大小、地
址等等。()
×9
.程序语言的语言办理程序是一种应用软件。
()
×
COBOL
和FORTRAN语言。()
三、填空题(每空1分,共10分)

___句柄__。
;.'
;.
,称为__语义规则___。
,不但包括__词法解析___、__语法解析___、__中间代码生成___、代码优化、
目标代码生成等五个部分,还应包括表格办理和出错办理。
,程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。

__源程序___中鉴别出一个个___单词符号__。

__语法范围___的一种书写规则。
一、是非题(请在括号内,正确的划√,错误的划×)(每个
2分,共20分)
×。
()
×,有且仅有一个唯一的终态。
()
√。
()
×4
.语法解析时必定先除掉文法中的左递归
。()
√,但不能够正确地指出出错地点。
()
√6
.逆波兰表示法表示表达式时不用使用括号。
()
×7
.静态数组的储藏空间能够在编译时确定。
()
×8
.进行代码优化时应重视考虑循环的代码优化,这对提高目标代码的效率将起更大作用。
()
×。
()
×。
()
三、填空题(每空1分,共10分)
:____和_____。
讲解_编译
;.'
;.
,它接受输入的_____,对源程序进行_____并鉴别出一个个单词符号,其输出结果是
单词符号,供语法解析器使用。
词法解析器源程序词法解析
、归约、错误办理、_____等四种操作。
移进_接受
:一个总控程序和_____。
一张解析表
-/所代表的表达式是____。
_a/(b-c)
。
_基本块_
一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分)
,则有L(r|s)=L(r)L(s)。(×)
。(√)
。(×)
。(√)
。(×)
“移进”/归“约”矛盾。(×)
。(×)
,而三元式和间接三元式则便于优化。(×)
;.'
;.
。(√)
。(×)
三、填空题(每空1分,共10分)
,即识其余单词是该类文法的句子。
,即识其余是该类文法的句子。语法解析的有效工具是__语法
树___。
,应用算符优先解析技术时,每步被直接归约的是__最左素短语___,而应用LR解析技术
时,每步被直接归约的是___句柄__。
、___四无式表示__与___三元
式表示__等。
一、是非题(请在括号内,正确的划√,错误的划×)(每个
2分,共20分)
(l)文法必然是无二义的。(×)。(×)
。(×)
,其中有一个被认为是初态,最多只有一个终态。(√)
,应试虑怎样充分利用计算机的存放器的问题。(×)
。(√)
,则称这个文法是二义的。(√)
。(×)
。(×)
,FORTRAN采用动向储藏分配策略。(×)
三、填空题(每空1分,共10分)
;.'
;.
,中间代码产生是依照语言的__语义___规进行的。
,其输出是__语法单位___。
。
。
+c+d*e-所表达的表达式为__(a+b+c)*d-e___。
。
二、填空题(每空2分,共22分)
[S]:S→(A)|a,A→AcS|S|b;该文法的开始符号是S,非终结符号会集为
{S,A},终结符号会集为{a,b,c,(,)}。
:有穷自动机,正规式和正规文法。
(1)和递归下降方法。
[S]:S→Sa|a,构造它的拓广文法,引入一个产生式:Sˊ→S;则I。=Closure
({[Sˊ→·S,#]})={[Sˊ→·S,#],[S→·Sa,#/a],[S→·a,#/a]}。
(0)项目集规范族中,若有项目:AAbB,其中bVT,称该项目为移进项目。
LL(1)语法解析方法中应解决的主要问题是除掉回溯;LR语法解析方法中应解决的主要问题是项目矛盾。
三、判断题(判断以下各题的正错,若正确,在括号中写“正”;否则写“错”。每题2分,共
16分)
,则由它描述的语言必然拥有二义性。(错)
,则定义该语言的文法必然是递归的。(正)
*b,则与之等价的文法应该是G[A]:A→aA|b。(正)
[A]:A→aB,B→bB|b,则该文法是LL(1)文法。(错)
,称为文法G的句子。(错)
。(错)
。(正)
;.'
;.
,却不能够用正规式表示的语言。(错)
文法G的一个句子对应于多个推导,则G是二义性的。(×)
动向的储藏分配是指在运行阶段为源程序中的数据对象分配储藏单元。(√)
算符优先文法采用“移进-规约”技术,其规约过程是规范的。(×)
删除归纳变量是在强度削弱今后进行。(√)
在目标代码生成阶段,符号表用于目标代码生成。(×)
(每空2分,共20分)
,但大部分编译中采用的方案有两
种:静态储藏分配方案和动向储藏分配方案,此后者又分为(1)和(2)。
规范规约是最(3)规约。
编译程序的工作过程一般划分为5个阶段:词法解析、(4)、语义解析与中间代码生成,代码优化及(5)。别的还有(6)和出错办理。
+y*z/(a+b)的后缀式为(7)。
(8)。
,而且每个元素占用一个储藏单元,则数组a[1..15,1..20]某个元素a[i,j]
的地点计算公式为(9)。
(10)范围内的一种优化。
答案::
栈式动向储藏分配
堆式动向储藏分配
左
语法解析
目标代码生成
表格管理
xyz*ab+/+
继承属性
;.'
;.
a+(i-1)*20+j-1
基本块
一、
填空题(每空
2分,共20分)
1
目标程序(targetcode)
语法解析(syntaxanalyzer
)
代码优化器(code
optimizer)
代码产生器(codegenerator)
符号表管理(symboltable
manager)
2
继承属性(inheritedattribute
)
3
局部优化(localoptimization
)
4
四元式(quatriple
)
5E
+*()id
二、填空题(本大题共5小题,每题2分,共10分)
(单词),此后再解析每个(句子)并翻译其意义。
(自底向上)和(自顶向下)两种。
。词法、语法和语义解析是对源程序的(解析),中间
代码生成、代码优化与目标代码的生成则是对源程序的(综合)。
,主要分为两大类,即(静态储藏分配)方案
和(动向储藏分配)方案。
,输入数据是(源程序),输出结果是(目标程序)。
三、名词讲解题(共5小题,每题4分,共20分)

词法解析的主要任务是从左向右扫描每行源程序的符号,依照词法规则
从组成源程序的字符串中鉴别出一个个拥有独立意义的最小语法单位,
并变换成一致的内部表示(token),送给语法解析程序。
(1)文法
若文法的任何两个产生式A|都满足下面两个条件:
(1)FIRST()FIRST()=;
(2)若*,那么FIRST()FOLLOW(A)=。
我们把满足这两个条件的文法叫做LL(1)文法,其中的第一个L代表从左
向右扫描输入,第二个L表示产生最左推导,1代表在决定解析器的每步
动作时向前看一个输入符号。除了没有公共左因子外,LL(1)文法还有一
些明显的性质,它不是二义的,也不含左递归。

句子的树构造表示法称为语法树(语法解析树或语法推导树)。
给定文法G=(VN,VT,P,S),关于G的任何句型都能构造与之关系的
;.'
;.
语法树。这棵树拥有以下特色:
(1)根节点的标记是开始符号S。
每个节点的标记都是V中的一个符号。
若一棵子树的根节点为A,且其所有直接后辈的标记从左向右的排列次序为A1A2AR,那么AA1A2AR必然是P中的一条产生式。
(4)
若一标记为A的节点最少有一个除它以外的后辈,则
AVN。
(5)
若树的所有叶节点上的标记从左到右排列为字符串
w,则w是文法G
的句型;若w中仅含终结符号,则w为文法G所产生的句子。
(0)解析器
所谓LR(0)解析,是指从左至右扫描和自底向上的语法解析,且在解析的每一步,只须依照解析栈当前已移进和归约出的所有文法符号,并至多再
向前查察0个输入符号,就能确定有关于某一产生式左部符号的句柄可否
已在解析栈的顶部形成,从而也就可以确定当前所应采用的解析动作(是移进还是按某一产生式进行归约等)。

文法就是语言构造的定义和描述,是有穷非空的产生式会集。
文法G定义为四元组的形式:
G=(VN,VT,P,S)
其中:VN是非空有穷会集,称为非终结符号会集;
VT是非空有穷会集,
称为终结符号会集;P是产生式的会集(非空);S是开始符号(或鉴别符号)。
这里,VN∩VT=,SVN。V=VN∪VT,称为文法G的字母表,它是出现
文法产生式中的所有符号的会集。
文法G所描述的语言用L(G)表示,它由文法G所产生的所有句子组成,即
L(G)={x|S*x,其中S为文法开始符号,且xVT}
简单的说,文法描述的语言是该文法所有句子的会集。
四、简答题(共4小题,每题5分,共20分)
?
用汇编语言或高级语言编写的程序,必定先送入计算机,经过变换成用机器语言表示的目标程序(这个过程即编译),才能由计算机执行。执行变换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序变换过的叫目标程序,也就是机器语言。
编译程序的工作情况有三种:汇编型、讲解型和编译型。汇编型编译程序用来
将汇编语言编写的程序,依照一一对应的关系,变换成用机器语言表示的程序。讲解型编译程序将高级语言程序的一个语句,先讲解成为一组机器语言的指令,此后马上执行,执行完了,取下一组语句讲解和执行,这样连续到完成一个程序
止。用讲解型编译程序,执行速度很慢,但能够进行人和计算机的"对话",随时
能够更正高级语言的程序。BASIC语言就是讲解型高级语言。编译型编译程序将级语言编写的程序,一次就会部翻译成机器语言表示的程序,而且过程进行很快,
在过程中,不能够进行人机对话更正。FORTRAN语言就是编译型高级语言。
;.'
;.
?
词法解析、语法解析和语义解析是对源程序进行的解析(称为编译程序的前端),
而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为
编译程序的后端),它们从源程序的中间表示建立起和源程序等价的目标程序。
。
所谓自下而上解析法就是从输入串开始,渐渐进行“归约”,直至归约到文法的
开始符号;也许说从语法树的尾端开始,步步向上“归约”,直到根节点。
。
代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换,在保证变换前后辈码执行结果相同的前提下,尽量使目
标程序运行时所需要的时间短,同时所占用的储藏空间少。
一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分)
。(×)
,有且仅有一个唯一的终态。(×)
。(√)
。(×)
,但不能够正确地指出出错地点。(√)
。(√)
。(×)
,这对提高目标代码的效率将起更大作用。(×)
。(×)
。(×)
三、填空题(每空1分,共10分)
:___讲解__和__编译___。
;.'