郑州大学编译原理试卷及答案(往年试题整合)(1)

1、精品资料二填空题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的地址计算公式为(9)。

2、7 局部优化是局限于一个(10 )范围内的一种优化。答案(1) 栈式动态存储分配(2) 堆式动态存储分配(3) 左 (4) 语法分析 (5) 目标代码生成(6) 表格管理(7) xyz*ab+/+ (8) 继承属性 (9) a+(i-1)*20+j-1 (10)基本块8 词法规则通常可以用 正规式 ， 正规文法、 自动机描述；语法规则通常用_2 型文法_来描述；语义规则通常用_属性文法 来描述。9编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段1 .（）称为规范推导。2 .编译过程可分为（），（），（），（）和（）五个阶段。3 .如果一个文法存在某个句子对

3、应两棵不同的语法树，则称这个文法是（）。4 .从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。5 .语法分析器的输入是（），其输出是（）。6 .扫描器的任务是从（）中识别出一个个（）。7 .符号表中的信息栏中登记了每个名字的有关的性质，如）等等。8 . 一个过程相应的 DISPLAY 表的内容为9 .一个句型的最左直接短语称为句型的（）。10 .常用的两种动态存贮分配办法是（）动态分配和（）动态分配。11 .一个名字的属性包括（）和（）。12 .常用的参数传递方式有（），（）和（）。13 .根据优化所涉及的程序范围，可将优化分成为（），（）可编辑修改和（ ）三个级别。14. 语法

4、分析的方法大致可分为两类，一类是（一类是（ ）分析法。15. 预测分析程序是使用一张（合控制的。16. 常用的参数传递方式有（17. 一张转换图只包含有限个状态实际上至少要有一个（ ）态。18. 根据优化所涉及的程序范围，和（ ）三个级别。19. 语法分析是依据语言的 （语言的（ ）规则进行的。）和一个（ ）进行联） ， （ ）和（ ） 。,其中有一个被认为是（ ） 态;而且可将优化分成为 （） ，（）规则进行。 中间代码产生是依据）分析法，另20. 一个句型的最左直接短语称为句型的（ ） 。21. 一个文法 G ，若它的预测分析表M 不含多重定义，则该文法是 （ ）文法。22. 对 于 数

5、据 空 间 的 存 贮 分 配 ， FORTRAN 采 用 （） 策略，PASCAL 采用 （） 策略。23. 如果一个文法存在某个句子对应两棵不同的语法树， 则称这个文法是 （） 。24. 最右推导亦称为 （） ， 由此得到的句型称为 （） 句型。25. 语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法。26. 对于文法 G ，仅含终结符号的句型称为 （）27. 所谓自上而下分析法是指（28. 语法分析器的输入是（29. 局限于基本块范围的优化称（30. 预测分析程序是使用一张（控制的。 31.2 型文法又称为（） 文 法 。 32. 每（对（ ）进行归约。答案） ，其

6、输出是（ ） 。）。）和一个（ ）进行联合）文法； 3 型文法又称为条指令的执行代价定义为） 。 33. 算符优先分析法每次都是参考答案 ：1.（最右推导） 2.（词法分析） ， （语法分析） ， （中间代码生成） ， （代码优化）， （目标代码生成）3.（ 二义性的） 4.（执行性） ，（说明性） 5.（单词符号） ， （语法单位） 。 6.（源程序） ， （单词符号）7 .（类型、种属、所占单元大小、地址）8 .（现行活动记录地址和所有外层最新活动记录的地址） 9.（ 句柄） 10.（ 栈式 ），（堆式） 11.（ 类型 ），（作用域） 12.（ 传地址）， （传值），（传名） 13.（

7、局部优化）， （循环优化）， （全局优化）14.（ 自上而下） ，（自下而上） 15.（ 分析表） ， （符号栈） 16.（ 传地址） ， （传值） ， （传名） 17.（ 初） ，（终） 18.（ 局部优化） ，（循环优化） ，（全局优化） 19.（ 语法） ， （语义） 20.（ 句柄）21.（LL（1） 文法） 22.（ 静态）， （动态）23.（ 二义性文法） 24.（ 规范推导） ， （规范） 25.（ 自上而下） ， （自下而上） 26.（ 句子 ）27.（ 从开始符号出发，向下推导，推出句子） 28.（ 单词符号） ， （语法单位） 29.（ 局部优化） 30.（ 分析表） ，

8、（符号栈） 31.（ 上下文无关文法） ， （正规） 32.（ 指令访问主存次数加 1 ） 33.（ 最左素短语）三 解答题（共60 分）1 （共 15 分）已知文法GE:E ETE|（E） |i T 7*|+（1 ） 将文法 G 改造成 LL （1 ）文法； （5 分）（ 2 ） 构造文法 G 中每个非终结符的 FIRST 集合及 FOLLOW 集合；（5 分）（3） 构造 LL （1 ）分析表。 （5 分）2 .（共 12 分）给定文法 GS: S-S（S）| &（ 1 ） 给出句子（）（）（）（）的规范推导过程；（ 4 分）（ 2 ） 指出每步推导所得句型的句柄； （ 4 分）（

9、 3 ） 画出该句子的语法推导树。 （ 4 分）答案1 （1）文法存在左递归，消除左递归后的文法为：E-（E）E' |i E ' （2 分）E' -TEE ' | e （2 分）T-*|+（1 分）（ 2 ） （5 分）没考虑#扣 0.5 分，其它错或少写一个扣 0.5 分FIRST（E尸（,iFIRST（E '尸口+, e FIRST（T尸口+FOLLOW(E)=),*,+,#FOWLLOW(E )= ),*,+,# FOLLOW(T)=(,i1. 写一个文法G, 使其语言为 不以 0 开头的偶数集。2. 已知文法G(S)及相应翻译方案SaAb pri

10、nt"1” Saprint "2” AAS print "3” Afc print "4” 输入acab,输出是什么？3. 已知文法 G(S)SbAaA 7 (B | a B Aa)写出句子 b(aa)b 的规范归约过程。4. 考虑下面的程序：procedure p(x, y, z) ； begin y:=x+y; z:=z*z; end beginA:=2; B:=A*2; P(A, A, B); Print A, B end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A, B 的值是什么 ?5. 文法 G(S) SdAB A aA

11、| a B Bb| £描述的语言是什么？6. 证明文法G(S) S -SaS| £ 是二义性的。7. 已知文法 G(S) SBA ABS| dB aA| bS | c的预测分析表如下a b c d # S S BA SBA SBA A A -BS ABS ABS Ad B BaA B bS B c给出句子 adccd 的分析过程。8. 写一个文法G, 使其语言为 L(G)=albmclanbn| l>=0, m>=1, n>=29. 已知文法 G(S): S -a| (T) T -T,S|S的优先关系表如下：关系 a ( ) , a - - .> .

12、> ( <. <. =. <. ) - - .> .> , <. <. .> .>请计算出该优先关系表所对应的优先函数表。10. 何谓优化？按所涉及的程序范围可分为哪几级优化？11. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？12. 一字母表2=a, b,试写出2上所有以a为首的字组成的正规集相对应的正规式13. 基本的优化方法有哪几种？14. 写一个文法G, 使其语言为 L(G)=abncn| n >0 15.考虑下面的程序：，procedure p(x, y, z); begin y:=y+z; z:=y*z

13、+x end; begin a:=2; b:=3;p(a+b, b, a); print a end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a 的值是什么 ?16. 写出表达式 a b*(c-d)/e 的逆波兰式和三元序列。17. 证明文法G(A) A-AA | (A)|£是二义性的。18. 令2=a,b,则正规式 a*b|b*a表示的正规集是什么？19. 何谓 DISPLAY 表？其作用是什么？20. 考虑下面的程序：procedure p(x, y, z) ； begin y:=y+2; z:=z+x; end begina:=5; b:=2;p(a+b,

14、 a-b, a); print a end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a 的值是什么?21. 写一个文法G, 使其语言为 L(G)=anbncm| n>0 为奇数， m>0 为偶数 22. 写出表达式a:=(b+c)*e+(b+c)/f 的逆波兰式和三元序列。23. 一个文法G 别是LL(1) 文法的充要条件是什么？24. 已知文法GSSS*aF | aF | *aF F -+aF | +a消除文法左递归和提公共左因子。25. 符号表的作用是什么？符号表查找和整理技术有哪几种？答案：.1所求文法是GS:SAB |B A0 A AD |CB -2

15、|4 |6 |8C-1 |3 |5 |7 |9 |B D-0 |C2.输出是42314 .传地址 A=6, B=16传值 A=2, B=45 .L(G尸danbm|n>0, m >06 .证明：因为文法GS存在句子aa有两个不同的最左推导，所以文法 GS 是是二义性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa8.所求文法是GS: S -ABA aAc | D D bD | b B aBb | aabb10 .优化：对程序进行各种等价变换，使得从变换后的程序

16、出发，能 产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化11 .目标代码通常采用三种形式：机器语言，汇编语言，待装配机器 语言模块。应着重考虑的问题:(1) 如何使生成的目标代码较短；(2) 如何充分利用寄存器，以减少访问内存次数； (3) 如何充分利用指令系统的特点。12. 正规式 a ( a | b )* 。13. 删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。14. 文法 GS:SaB | a B bc |bBc15. 传值 a=2 传地址 a=1516. 逆波兰式 : abcd-*e/+三元序列 : op arg1 arg2 (1

17、) - c d (2) * b (1)(3) /(2) e (4) +a (3)17. 证明：因为文法 GS 存在句子 () 有两个不同的最左推导，所以文法GS是是二义性的。A=>AA=>(A)A=>()A=>()A=>AA=>A=>(A)=>()18. (a*b|b*a)=a,b,ab,ba,aab,bba , 19. Display 表: 嵌套层次显示表当一个由于过程嵌套允许内层过程引用外层过程定义的数据，过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display 表就是用于登记每个外层过程的最新活动记录起始地址。20. 传地

18、址 a=12 传值 a=521. 所求文法是 GS: S -ACA aaAbb | ab C ccC | cc23.一个文法 G别是LL(1)文法的充要条件是：(1) FIRST( %) AFIRST(份=(2)如果户*>工FIRST(喻A FOLLOW(A)= 24.消除左递归SaFS' | *aFS ' S'f*aFS' | £ F+aF|+a提公共左因子，文法 G' (S) S-aFS' | *aFS ' S' -*aFS ' | £ F7+aF ' F ' F | &25. 作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。主要技术：线性表，对折查找，杂奏技术。三、简答题： (每题 7 分，共 28 分)(说明：将答案写在试卷后面的答题纸上)1 、已知文法GEE->E+T|E-T|T T->T*F|T/F|F F->(E)|i证明( F+T ) -