编译原理期末考试试卷及答案.doc

资源描述

1、第 0 页共 14 页一填空题（每空 2 分，共 20 分）1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。2. 规范规约是最（3）规约。3. 编译程序的工作过程一般划分为 5 个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。另外还有（6）和出错处理。4表达式 x+y*z/(a+b)的后缀式为（7）。5文法符号的属性有综合属性和（8）。6假设二位数组按行存放，而且每个元素占用一个存储单元，则数组 a1.15,1.20某个元素 ai，j的地址计算公式

2、为（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在通常的语法分析方法中

3、，（）特别适用于表达式的分析。A 算符优先分析法 B LR 分析法C 递归下降分析法 D LL（1）分析法5经过编译所得到的目标程序是（）。A 四元式序列 B 间接三元式序列C 二元式序列 D 机器语言程序或汇编语言程序6 一个文法所描述的语言是（）；描述一个语言的文法是（）。A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一7 如果在文法 G 中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。A 其最左推导和最右推导相同 B 该句子有两个不同的最左推导得分得分第 1 页共 14 页C 该句子有两个不同的最右推导 D 该句子有两棵不同的语法树E 该句子对应

4、的语法树唯一8 下面（）语法制导翻译中，采用拉链回填技术。A. 赋值语句 B. 布尔表达式的计算 C. 条件语句 D. 循环语句三解答题（共 60 分）1 （共 15 分）已知文法 GE: EETE|（E）|i T*|+（1（将文法 G 改造成 LL（1）文法；（5 分）（2（构造文法 G 中每个非终结符的 FIRST 集合及 FOLLOW 集合；（5 分）（3（构造 LL（1）分析表。（5 分）2 （共 12 分）给定文法 GS：SS(S)|（1）给出句子()()()()的规范推导过程；（4 分）（2）指出每步推导所得句型的句柄；（4 分）（3）画出该句子的语法推导树。（

5、4 分）3 （共 8 分）在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。AaB print “0” ；Ac print “1” ；BAb print “2” ；（1（当分析器的输入为 aacbb 时，打印的字符串是什么？（3 分）（2（写出分析过程。（5 分）5 （共 15 分）设有表格构造文法 GS：Sa|(T)TT,S|S(1) 计算文法 GS的 FIRSTVT 集和 LASTVT 集。（5 分）(2) 构造 GS的优先关系表，并判断 GS是否为算符优先文法。（5 分）(3) 计算 GS的优先函数。（5 分）得分第 2 页共

6、 14 页二单项选择题（每题 2 分，共 10 分）1. 设有文法 GI： II1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（）。 ab0 a0c01 aaa bc10可选项有：A B C D2.程序的基本块是指（）。A 一个子程序 B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段 D 一组顺序执行的程序段，仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。A 自左向右 B 自顶向下 C 自底向上 D 自右向左4经过编译所得到的目标程序是（）。A 四元式序列 B 间接三元式序列C 二元式序列 D 机器语

7、言程序或汇编语言程序5 运行阶段的存储组织与管理的目的是（）。提高编译程序的运行速度节省编译程序的存储空间提高目标程序的运行速度为运行阶段的存储分配做准备可选项有：A. B. C. D. 2. （10 分）已知文法 GS: SaBc|bABAaAb|bBb|（4（构造其 LL（1）分析表；（5（判断符号串 baabbb 是否为该文法的句子（写出含有符号栈、输入串和规则的分析过程）。答案：(1) 栈式动态存储分配(2) 堆式动态存储分配(3) 左得分得分第 3 页共 14 页(4) 语法分析(5) 目标代码生成(6) 表格管理(7)xyz*ab+/+(8) 继承属性(9)a

8、+(i-1)*20+j-1(10) 基本块一、选择题（每问 2 分，共 20 分）1.C B 2.D 3.B 4.A 5.D 6.A,C7.BCD,选对一个得 1 分且不超过满分，选错一个扣一分，扣完为止。8.BCD，选对一个得 1 分且不超过满分，选错一个扣一分，扣完为止。二、解答题1 （1）文法存在左递归，消除左递归后的文法为：E(E)E|i E （2 分）ETEE| （2 分）T*|+ （1 分）（2）(5 分)没考虑#扣 0.5 分，其它错或少写一个扣 0.5 分FIRST(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+ FOLLOW(E)=),*,+,# FOWL

9、LOW(E)= ),*,+,# FOLLOW(T)=(,i（3）每错一个扣 0.5 分，全错或不写不得分，扣完为止，共 5 分( ) i * + #E E(E)E EiEE E ETEEE ETEEE E T T* T+2 （1）规范推导过程如下。写错推导符号扣 0.5 分,错写或少写一步推导扣 0.5 分，扣完为止，最左推导扣 2分，共 4 分。 ()()( ()()() SS SSSS（2）（1）中加下划线的部分是句柄，标识如（1）。每少写一个句柄扣 0.5 分，扣完为止，共 4 分。（3）每少写步扣 0.5 分，扣完为止，共 4 分。SS ( S )S ( S ) )第 4 页共 1

10、4 页3 （1）打印的字符串是：12020（错一个扣 0.5 分，共 3 分）（2）归约过程中错一步扣 0.5 分，扣完为止。（共 5 分）5 （1）少写一个扣 1 分，全错或不写不得分，共 5 分。FIRSTVT(S)=a,(FIRSTVT(T)=, a,(LASTVT(S)= a,)LASTVT(T)= a,), ,三、单项选择题（每题 2 分，共 10 分）1.B 2.D 3.B 4.D 5.C四、解答题（共 70 分）1 （1） L(G)=0 m1m|M1 共 2 分，写成扣 1 分（2） S=0S1=00S11=000111，共 3 分， =写成-扣 1 分（3）共 3 分，错处

11、扣 0.5 分，扣完为止一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( )2.一个句型的直接短语是唯一的。 ( )3.已经证明文法的二义性是可判定的。（）4.每个基本块可用一个 DAG 表示。（）5.每个过程的活动记录的体积在编译时可静态确定。（）6.2 型文法一定是 3 型文法。（）7.一个句型一定句子。 ( )8.算符优先分析法每次都是对句柄进行归约。 ( )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( )11.一个优先表一定存在相应的优先函数。 ( )12.目标代

12、码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( )13.递归下降分析法是一种自下而上分析法。 ( )14.并不是每个文法都能改写成 LL(1)文法。 ( )15.每个基本块只有一个入口和一个出口。 ( )16.一个 LL(1)文法一定是无二义的。 ( )S ( S ) ) S ( S ) )S ( S ) ) )第 5 页共 14 页17.逆波兰法表示的表达试亦称前缀式。 ( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( )19.正规文法产生的语言都可以用上下文无关文法来描述。 ( )20.一个优先表一定存在相应的优先函数。 ( )21.3 型文法一定是 2

13、型文法。 ( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( )二、填空题：1.( )称为规范推导。2.编译过程可分为（），（），（），（）和（）五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。5.语法分析器的输入是（），其输出是（）。6.扫描器的任务是从（）中识别出一个个（）。7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。8.一个过程相应的 DISPLAY 表的内容为（）。9.一个句型的最左直接短

14、语称为句型的（）。10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。11.一个名字的属性包括( )和( )。12.常用的参数传递方式有（），（）和（）。13.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。14.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。15.预测分析程序是使用一张（）和一个（）进行联合控制的。16.常用的参数传递方式有（），（）和（）。17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。18.根据优化所涉及的程序范围，可将优化分成

15、为（），（）和（）三个级别。19.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。20.一个句型的最左直接短语称为句型的（）。21.一个文法 G，若它的预测分析表 M 不含多重定义，则该文法是（）文法。22.对于数据空间的存贮分配， FORTRAN 采用( )策略， PASCAL 采用( )策略。23.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是( )。24.最右推导亦称为（），由此得到的句型称为（）句型。25.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。26.对于文法 G，仅含终结符号的句型称为

16、 ( )。27.所谓自上而下分析法是指（）。28.语法分析器的输入是（），其输出是（）。29.局限于基本块范围的优化称（）。30.预测分析程序是使用一张（）和一个（）进行联合控制的。31.2 型文法又称为（）文法；3 型文法又称为（）文法。32.每条指令的执行代价定义为（）。33.算符优先分析法每次都是对（）进行归约。三、名词解释题：1.局部优化2.二义性文法3.DISPLAY 表4.词法分析器5.最左推导6.语法7.文法8.基本块9.语法制导翻译10.短语11.待用信息12.规范句型第 6 页共 14 页13.扫描器14.超前搜索15.句柄16.语法制导翻译1

17、7.规范句型18.素短语19.语法20.待用信息21.语义四、简答题：1.写一个文法 G, 使其语言为不以 0 开头的偶数集。2.已知文法 G(S)及相应翻译方案SaAb print “1”Sa print “2”AAS print “3”Ac print “4”输入 acab, 输出是什么？3. 已知文法 G(S)SbAaA(B | aBAa)写出句子 b(aa)b 的规范归约过程。4. 考虑下面的程序：procedure p(x, y, z)；beginy:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A, A, B);Print A, Bend.试问，若参数传递的

19、,a - - . .( ., .请计算出该优先关系表所对应的优先函数表。10.何谓优化？按所涉及的程序范围可分为哪几级优化？11.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？12.一字母表 =a, b，试写出上所有以 a 为首的字组成的正规集相对应的正规式。13.基本的优化方法有哪几种？14.写一个文法 G, 使其语言为 L(G)=ab ncn| n015.考虑下面的程序：procedure p(x, y, z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b, b, a);print aend.试问，若参数传递的方式分别采用传地址和传

21、(a,a)的最左推导；(2) 给出句型(T,S),a)的短语, 直接短语，句柄。9.已知文法 G(S)SaAcBeAAb| bBd(1)给出句子 abbcde 的最左推导及画出语法树；(2)给出句型 aAbcde 的短语、素短语。 10.设文法 G(S): S(T) | aS | aTT,S | S消除左递归和提公共左因子；构造相应的 FIRST 和 FOLLOW 集合；构造预测分析表。参考答案一、是非题：1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.二、填空题：1.(最右推导）2.(词

22、法分析），（语法分析），（中间代码生成），（代码优化），（目标代码生成）3.(二义性的）4.(执行性），（说明性）5.(单词符号），（语法单位）。6.(源程序），（单词符号）7.(类型、种属、所占单元大小、地址）8.(现行活动记录地址和所有外层最新活动记录的地址)9.(句柄）10.(栈式)，（堆式）11.(类型)，（作用域）12.(传地址），（传值），（传名）13.(局部优化），（循环优化），（全局优化）14.(自上而下），（自下而上）15.(分析表），（符号栈）16.(传地址），（传值），（传名）17.(初），（终）18.

23、(局部优化），（循环优化），（全局优化）19.(语法），（语义）20.(句柄）21.(LL(1) 文法）22.(静态），（动态）23.(二义性文法）24.(规范推导），（规范）25.(自上而下），（自下而上）26.(句子)27.(从开始符号出发，向下推导，推出句子）28.(单词符号），（语法单位）29.(局部优化）30.(分析表），（符号栈）31.(上下文无关文法），（正规）第 9 页共 14 页32.(指令访问主存次数加 1）33.(最左素短语）三、名词解释题： 1.局部优化-局限于基本块范围的优化称。2.二义性文法-如果一个文法存在某个句子对应两棵不同

24、的语法树，则称这个文法是二义性文法。3.DISPLAY 表-过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。4.词法分析器-执行词法分析的程序。5.最左推导-任何一步 = 都是对中的最右非终结符替换。6.语法-一组规则，用它可形成和产生一组合式的程序。7.文法-描述语言的语法结构的形式规则。8.基本块-指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语-令 G 是一个文法，S 划文法的开始符号，假定

25、是文法 G 的一个句型，如果有 S A且 A ，则称是句型相对非终结符 A 的短语。11.待用信息-如果在一个基本块中，四元式 i 对 A 定值，四元式 j 要引用 A 值，而从 i 到 j 之间没有 A 的其它定值，则称 j 是四元式 i 的变量 A 的待用信息。12.规范句型-由规范推导所得到的句型。13.扫描器-执行词法分析的程序。14.超前搜索-在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15.句柄-一个句型的最左直接短语。16.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法叫做语法制导翻译。17.规范句型-由规范推导所得到的句型。18

26、.素短语-素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法-是组规则，用它可形成和产生一个合式的程序。 20.待用信息-如果在一个基本块中，四元式 i 对 A 定值，四元式 j 要引用 A 值，而从 i 到 j 之间没有 A 的其它定值，则称 j 是四元式 i 的变量 A 的待用信息。21.语义-定义程序的意义的一组规则。四、简答题： 1.所求文法是 GS:SAB |B A0AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2.输出是 42313.句子 b(aa)b 的规范归约过程：步骤符号栈输入串动作0 # b(aa)b# 预备1 #b (aa)b# 移进2 #b( aa)b# 移进3 #b(a a)b# 移进4 #b(A a)b# 归约5 #b(Ma )b# 移进6 #b(Ma) b# 移进7 #b(B b# 归约8 #bA b# 归约

展开阅读全文