2022年编译原理期末试题及答案.pdf-淘文阁

资源描述

《2022年编译原理期末试题及答案.pdf》由会员分享，可在线阅读，更多相关《2022年编译原理期末试题及答案.pdf（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、编译原理期末试题（一）一、是非题（请在括号内，正确的划，错误的划）（每个 2 分，共 20 分）1编译程序是对高级语言程序的解释执行。( )2一个有限状态自动机中，有且仅有一个唯一的终态。( )3一个算符优先文法可能不存在算符优先函数与之对应。( )4语法分析时必须先消除文法中的左递归。 ( )5LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。( )6逆波兰表示法表示表达式时无须使用括号。( )7静态数组的存储空间可以在编译时确定。( )8进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。( )9两个正规集相等的必要条件是他们对应的正规式等

2、价。( )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：SxSx|y所识别的语言是_。A( ) xyx B( ) (xyx)

3、* C( ) xnyxn(n0) D ( ) x*yx* 4如果文法G 是无二义的，则它的任何句子 _ 。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 1 页，共 37 页 - - - - - - - - - - A( )最左推导和最右推导对应的语法树必定相同B( ) 最左推导和最右推导对应的语法树可能不同C( ) 最左推导和最右推导必定相同D( )可能存在两个不同的最左推导，但它们对应的语法树相同5构造编译程序应掌握_。A( )源程序B( ) 目标语言 C ( ) 编译方法D( ) 以上三项都是6四元

4、式之间的联系是通过_实现的。A( ) 指示器B( ) 临时变量C( ) 符号表D( ) 程序变量7表达式 ( A B)(CD)的逆波兰表示为_。A. ( ) AB CDB( ) A B CD C ( ) AB CD D( ) AB CD8. 优化可生成 _的目标代码。A( ) 运行时间较短 B ( ) 占用存储空间较小C( ) 运行时间短但占用内存空间大D( ) 运行时间短且占用存储空间小9下列 _优化方法不是针对循环优化进行的。A. ( ) 强度削弱B( ) 删除归纳变量C( ) 删除多余运算D( ) 代码外提10编译程序使用_区别标识符的作用域。A. ( ) 说明标识符的过程或函数名B(

5、) 说明标识符的过程或函数的静态层次C( ) 说明标识符的过程或函数的动态层次D. ( ) 标识符的行号精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 2 页，共 37 页 - - - - - - - - - - 三、填空题 (每空 1 分，共 10 分)1计算机执行用高级语言编写的程序主要有两种途径：_解释 _和_编译 _。2扫描器是 _词法分析器 _，它接受输入的_源程序 _，对源程序进行_词法分析 _并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3自上而下分析法采用_移进 _、归约

7、ST | 3. 试为表达式w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。解： w a b + c d e 10 - / + 8 + * +5. 已知文法GS 为 S aSb|Sb|b ，试证明文法GS 为二义文法。证明：由文法 GS：SaSb|Sb|b ，对句子aabbbb 对应的两棵语法树为：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 3 页，共 37 页 - - - - - - - - - - 因此，文法GS为二义文法。五.计算题（ 10 分）已知文法A-aAd|aAb| 判

8、断该文法是否是SLR(1) 文法，若是构造相应分析表，并对输入串ab# 给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有：S-A A-aAd|aAb| 下面构造它的LR(0)项目集规范族为：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 4 页，共 37 页 - - - - - - - - - - 从上表可看出 ,状态 I0 和 I2 存在移进 -归约冲突，该文法不是LR(0)文法。对于I0 来说有：FOLLOW( A) a=b,d,#a= ，所以在 I0 状态下面临输入符号为a时移进，

9、为b,d,#时归约，为其他时报错。对于I2 来说有也有与I0 完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1) 文法。其 SLR(1) 分析表为：对输入串 ab#给出分析过程为：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 5 页，共 37 页 - - - - - - - - - - 编译原理期末试题（二）一、是非题：1. 一个上下文无关文法的开始符，可以是终结符或非终结符。( )2.一个句型的直接短语是唯一的。（）

10、3.已经证明文法的二义性是可判定的。（）4.每个基本块可用一个DAG表示。（）5. 每个过程的活动记录的体积在编译时可静态确定。（）型文法一定是3型文法。（）7.一个句型一定句子。( )8.算符优先分析法每次都是对句柄进行归约。X ( )9. 采用三元式实现三地址代码时，不利于对中间代码进行优化。（）10. 编译过程中，语法分析器的任务是分析单词是怎样构成的。( )11. 一个优先表一定存在相应的优先函数。X ( )12. 目标代码生成时，应

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

12、 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 6 页，共 37 页 - - - - - - - - - - 型文法一定是2型文法。( )22. 如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。( )答案： 1. 2. 3. 4. 5. 6. 7. 8. 9.10. 11. 12.13. 14.15.16.17. 18.19. 20. 21. 22. 二、填空题：2.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码

13、生成），（优化）和（目标代码生成）五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。4.从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。5.语法分析器的输入是（单词符号），其输出是（语法单位）。6.扫描器的任务是从（源程序中）中识别出一个个（单词符号）。7.符号表中的信息栏中登记了每个名字的有关的性质，如(类型、种属、所占单元大小、地址）等等。8.一个过程相应的DISPLAY表的内容为 (现行活动记录地址和所有外层最新活动记录的地址 )10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。11.一个名

14、字的属性包括( 类型 )和 (作用域)。12.常用的参数传递方式有(传地址），（传值），（传名）13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上）分析法。15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。21.一个文法 G，若它的预测分析表M 不含多重定义

15、，则该文法是（LL(1) 文法）文法。22.对于数据空间的存贮分配，FORTRAN采用( 静态策略，PASCAL 采用 ( 动态 )策略。24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。26.对于文法 G，仅含终结符号的句型称为( 句子)。27.所谓自上而下分析法是指(从开始符号出发，向下推导，推出句子）29.局限于基本块范围的优化称（局部优化）。型文法又称为（上下文无关）文法；3 型文法又称为（正则）文法。32.每条指令的执行代价定义为(指令访问主存次数加1）33.算符优先分析法每次都是对(最左素短语）进行归约。四、简答题：1.写一个文法G, 使其语言为不以 0 开头的偶数

16、集。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 7 页，共 37 页 - - - - - - - - - - 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:=

17、A*2;P(A, A, B);Print A, Bend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出A, B的值是什么5文法 G(S)SdABAaA| aBBb| 描述的语言是什么6. 证明文法 G(S)S SaS| 是二义性的。7. 已知文法 G(S)S BAABS| dBaA| bS | c的预测分析表如下abcd#SSBASBAS BAAABSABSA BSAdBBaABbSBc精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 8 页，共 37 页 - - - - - - - - -

18、 - 给出句子adccd 的分析过程。8. 写一个文法G, 使其语言为L(G)=albmclanbn| l=0, m=1, n=2 9. 已知文法 G(S):Sa| (T)TT,S|S的优先关系表如下：关系a(),a-.(.=.,.请计算出该优先关系表所对应的优先函数表。10. 何谓优化按所涉及的程序范围可分为哪几级优化11. 目标代码有哪几种形式生成目标代码时通常应考虑哪几个问题12. 一字母表 =a, b ，试写出上所有以a 为首的字组成的正规集相对应的正规式。13. 基本的优化方法有哪几种14. 写一个文法G, 使其语言为L(G)=abncn| n015. 考虑下面的程序：proced

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

20、 - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 9 页，共 37 页 - - - - - - - - - - begina:=5;b:=2;p(a+b, a-b, a);print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出a 的值是什么21.写一个文法G, 使其语言为L(G)=anbncm| n0 为奇数，m0 为偶数 22.写出表达式a:=(b+c)*e+(b+c)/f 的逆波兰式和三元序列。23.一个文法 G 别是 LL(1)文法的充要条件是什么24.已知文法 GSSS*aF | aF | *aFF+aF | +

21、a消除文法左递归和提公共左因子。25.符号表的作用是什么符号表查找和整理技术有哪几种答案： 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(Aa)b#归约5 #b(Ma)b#移进6#b(Ma)b#移进7#b(B b# 归约8#bAb#归约9#bAb#移进10#S#接受4.传地址A=6, B=16传值A=2, B=4(G)=danbm|n0, m06

22、.证明：因为文法 GS存在句子 aa 有两个不同的最左推导，所以文法GS是是二义性的。S=SaS=SaSaS=aSaS=aaS=aaS=SaS=aS=aSaS=aaS=aa7.句子 adccd 的分析过程：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 10 页，共 37 页 - - - - - - - - - - 步骤符号栈输入串产生式0#Sadccd#1#ABadccd#S BA2#AAaadccd#B aA3#AAdccd#4#Addccd#Ad5#Accd#6#SBccd#A BS7#Scccd#

23、 Bc8#S cd# 9#ABcd#Bc10#Acd#11#A d#12#dd#Ad13# 8.所求文法是GS: SABAaAc | DD bD | bB aBb | aabb9.函数a(),f4244g552310.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指令系统的特点。12.正规式a ( a | b )* 。13.删除多余运算，代码

24、外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。14.文法 GS:S aB | aBbc |bBc15.传值a=2传地址a=1516.逆波兰式 : abcd-*e/+三元序列 : op arg1 arg2(1) - c d精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 11 页，共 37 页 - - - - - - - - - - (2) * b (1)(3) / (2) e(4) + a (3)17.证明：因为文法 GS存在句子() 有两个不同的最左推导，所以文法GS是是二义性的。

25、A=AA=(A)A=()A=()A=AA=A=(A)=()18.(a*b|b*a)=a,b,ab,ba,aab,bba表: 嵌套层次显示表由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，display 表就是用于登记每个外层过程的最新活动记录起始地址。20.传地址a=12传值a=521.所求文法是GS: S ACA aaAbb | abC ccC | cc22.逆波兰式abc+e*bc+f/+:=三元序列op arg1 arg2(1) + b c(2) * (1) e(3) + b c(4) / (3) f(5) + (2)

27、 - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 12 页，共 37 页 - - - - - - - - - - 消除左递归；构造相应的FIRST和 FOLLOW集合；构造预测分析表2.语句 if E then S(1) 改写文法，使之适合语法制导翻译；(2) 写出改写后产生式的语义动作。4.设某语言的for 语句的形式为for i:E(1) to E(2) do S其语义解释为i:E(1)LIMIT:E(2)again: if i LIMIT thenBeginS;i:i1goto againEnd;（1）写出适合语法制导翻译的产生式；（2）写出每个产生

28、式对应的语义动作。5.把语句while a0 then a:=a+1else a:=a*3-1;翻译成四元式序列。6.设有基本块D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有M 还被引用，请写出优化后的四元序列。7.已知文法 G(S)Sa | | (T)TT,S | S(1) 给出句子 (a,(a,a)的最左推导；(2) 给出句型 (T,S),a) 的短语 , 直接短语，句柄。8.对于 C 语言 do S while E 语句精品资料 - - - 欢迎下载 - - - - - - - - - -

30、a, ( FIRST(S )=a, (, FIRST(L)=a, ( FIRST(L )=, FOLLOW(S)=, ), # FOLLOW(S )=, ), #FOLLOW(L)= ) FOLLOW(L )= )(3)()a,#SS (L)S aSSS SS S SSSLLSLLSLL,SL LL11.把语句if X0 Y0 do X:=A*3else Y:=B+3;翻译成四元式序列。12.已知文法 G(S)EE+T | TTT*F| FF(E)| i(1) 给出句型(i+i)*i+i 的最左推导及画出语法树；(2) 给出句型(E+T)*i+F 的短语，素短语和最左素短语。解 (1)消除左递

31、，文法变为G S ：S | a | (T)TST | S精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 14 页，共 37 页 - - - - - - - - - - T ,ST | 此文法无左公共左因子。(2)构造相应的FIRST 和 FOLLOW集合：FIRST(S)=a, , ( ， FOLLOW(S)=#, , )FIRST(T)=a, , ( ，FOLLOW(T)=FIRST(T )=, ，FOLLOW(F)=)(3)构造预测分析表：a(),#SSaSS(T)TTSTTSTTSTTTT ,ST

32、2. (1)Cif E thenSCS(1)(2)Cif E then BACK, NXQ); :=SCS(1) :=MERG, S(1). Chain)4. (1) Ffor i:=E(1) to E(2) doSFS(1)(2)Ffor i:=E(1) to E(2) doGEN(:=, E(1).place, _, entry(i);:=entry(i);LIMIT:=Newtemp;GEN(:=, E(2).place, _, LIMIT);Q:=NXQ;:=q;GEN(j , entry(i), LIMIT, q+2):=NXQ;GEN(j, _, _, 0)SFS(1)BACKPA

33、TCH(S(1).chain, NXQ);GEN(+, , 1, ;GEN(j, _, _, ;:=5.(1) (j, c, 0, (5)(4)(j, _, _, (8)(5)(+, a, 1, T1)(6)(:=, T1, _, a)(7)(j, _, _, (1)(8)(*, a, 13, T2)(9)(-, T2, 1, T3)精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 15 页，共 37 页 - - - - - - - - - - (10) (:=, T3, _, a)(11) (j, _,

34、_, (1)6.优化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+207. 最左推导S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)短语(T,S),a)(T,S),a(T,S)T,Sa直接短语T,Sa句柄T,S8.(1)S do M1 S1while M2 EM(2)M=nestquad;S do M1 S1while M2 E backpatch, ;backpatch, ;=;9.(1) S=aAcBe=AAbcBe=abbcBe=abbcde(2) 短语 : aAbcde, Ab, d素短语

35、: Ab, d11.(1) (j, X, 0, (5)(2) (j, _, _, (3)(3) (j0, X, 0, (7)(6) (j, _, _, (7)(7) (*, A, 3, T1)(8) (:=, T1, _, N)(9) (j, _, _, (5)(10) (j, _, _, (13)(11) (+, B, 3, T2)精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 16 页，共 37 页 - - - - - - - - - - (12) (:=, T2, _, Y)12.(1) E=E+T

36、=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+T=(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T=(i+i)*i+F=(i+i)*i+i (2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F素短语i, E+T最左素短语E+T编译原理期末试题（二）1、描述由正规式b*(abb*)*(a| )定义的语言，并画出接受该语言的最简DFA 。2、证明文法E E + id | id 是 SLR(1) 文法。3、下面是表达式和赋值语句的文法，其中 and 的类型是 bool bool

37、 bool，+的类型是 int int int，=的类型是 int int bool，:= 要求 id 和 E的类型都是int 或者都是 bool。为该文法写一个语法制导定义或翻译方案，它完成类型检查。S id := EE E and E | E + E | E = E |id4、对于下面C 语言文件f1(int x)long x;x = 1;f2(int x)long x;x = 1;某编译器编译时报错如下：: In function f1 :3: warning: declaration of x shadows a parameter请回答，对函数f2 为什么没有类似的警告错误。5、下面

38、 C语言程序经非优化编译后，若运行时输入2，则结果是area=, addr=-76经优化编译后，若运行时输入2，则结果是area=, addr=-68请解释为什么输出结果有区别。main()float s, pi, r;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 17 页，共 37 页 - - - - - - - - - - pi=;scanf(%f, &r);printf(area=%f, addr=%dn, s=pi*r*r, &r);6、描述由正规式ba(bb a)b定义的语言，并画出接受该语言

39、的最简DFA 。7、下面的文法产生代表正二进制数的0 和 1 的串集：B B 0 | B 1 | 1下面的翻译方案计算这种正二进制数的十进制值：B B1 0 := 2 | B1 1 := 2 +1| 1 := 1 请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。8、在 C 语言中，如果变量i 和 j 都是 long 类型，请写出表达式&i 和表达式 &i&j 的类型表达式。为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。main() long i, j;printf( “ %dn” , &i&j);9、一个 C语言的函数如下：func(i) lo

42、母表a, b上不含子串aa 的所有串的集合。最简 DFA如下：2、先给出接受该文法活前缀的DFA如下：I0和 I3都只有移进项目，肯定不会引起冲突；I2和 I4都无移进项目并仅含一个归约项目，也肯定不会引起冲突；在I1中， E的后继符号只有$，同第 2 个项目的展望符号“+”不一样，因此 I1也肯定不会引起冲突。由此可以断定该文法是SLR(1) 的。3、语法制导定义如下。S id := E := if= bool and= bool) or= int and= int) then type_ok else type_error E E1and E2 := if= bool and= bool

43、 then bool else type_error E E1 + E2 := if= int and= int then int else type_error E E1 = E2 := if= int and= int then bool else type_error E id := lookup 4、对于函数f1，局部变量x 声明的作用域是整个函数体，导致在函数体中不可能访问形式参数 x。由于这是一个合法的C 语言函数，因此编译器给出警告错误。对于函数 f2，由于局部变量x 的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。5、使用非优化编译时，变量 s, pi, r 在

44、局部数据区都分配4 个字节的空间。使用优化编译时，由于复写传播，pi*r*r 变成*r*r ，pi=成为无用赋值而删去，函数中不再有pi 的引用，因此不必为 pi 分配空间。类似地， s=*r*r 也是一个无用赋值（表达式要计算，但赋值是无用的），也不必为 s 分配空间。这样，和非优化情况相比，局部数据区少了8 个字节，因此 r 的地址向高地址方向移动了8 个字节。6、正规式 b a(bba)b 体现的特点是，每个a 的左边都有若干b，除非 a 是第一个字母。该正规式定义的语言是：至少含一个a，但不含子串aa 的所有 a 和 b 的串集。最简DFA 如下：EEE E + idE idI0

45、EEE E+ idI1E idI2Eid+E E +idI3E E + idI4idstart1abb2start2abb10ab精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 19 页，共 37 页 - - - - - - - - - - 7、消除左递归后的文法：B 1 BB 0 B | 1 B | 相应的翻译方案如下：B 1 B.i := 1 B := B.val B0 B := B.i 2 B1 B.val := B| 1 B:= B.i 2 +1 B1 B.val := B| B.val :=

46、B.i8、表达式 &i 的类型表达式是pointer(long) ，表达式 &i&j 的类型表达式是long。按照 C 语言的规定，指向同一个类型的两个指针可以相加减，它们值的差是它们之间的元素个数。9、左边的编译器版本：一般只为局部变量分配空间。调用函数前，用若干次pushl 指令将参数压栈，返回后用 addl $n, %esp 一次将所有参数退栈（常数 n 根据调用前做了多少次pushl来决定）。右边的编译器版本：除了为局部变量分配空间外，同时还为本函数中出现的函数调用的参数分配空间，并且参数所用空间靠近栈顶。调用函数前，用movl 指令将参数移入栈顶，调用结束后无需参数退栈指令。优点是

47、每次函数调用结束后不需要执行addl $n, %esp 指令，另外增加优化的可能性。编译原理期末试题（三）1、从优化的范围的角度，优化可以分哪两类对循环的优化可以有哪三种答：从优化的范围的角度，优化可以分为局部优化和全局优化两类；对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。2、写出表达式 a=b*c+b*d 对应的逆波兰式、四元式序列和三元式序列。答：逆波兰式：abc*bd*+:= 四元式序列：三元式序列 : OP ARG1 ARG2(1) (*，b，c， t1) (1) (* b，c )(2) (*，b，d， t2) (2) (* b，d )(3) (+， t1，t

48、2，t3) (3) (+ (1)，(2)(4) (:=， t3，/， a) (4) (:= (3)，a)3、对于文法 G(S): ）MaLa|(LMbMbS答：1）bMabLbbbMbS)(2）短语: Ma)，(Ma)， b(Ma)bSbM(TMabL)精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载名师归纳 - - - - - - - - - -第 20 页，共 37 页 - - - - - - - - - - 直接短语 : Ma) 句柄: Ma)三、设有字母表 a，b上的正规式 R=(ab|a)*。解：（1）（2）将（ 1）所得的非确定有限自动机确

49、定化ab-01131221+3（3）对（ 2）得到的 DFA化简，合并状态 0 和 2 为状态 2：（4）令状态 1 和 2 分别对应非终结符B和 AG: AaB|a| ； BaB|bA|a|b| ；可化简为： G: A aB|；BaB|bA| 四、设将文法 G改写成等价的 LL(1) 文法，并构造预测分析表。G：SS*a T|aT|*aT ； T+a T|+a解：消除左递归后的文法G : SaTS |*aTSS *aTS |T+aT|+a 提取左公因子得文法G:SaTS |*aTS12aab-+012aaba-+0123baa-+精品资料 - - - 欢迎下载 - - - - - - - -

50、 - - - 欢迎下载名师归纳 - - - - - - - - - -第 21 页，共 37 页 - - - - - - - - - - S *aTS | T+aTT T|Select(S aTS )=aSelect(S *aTS )=*Select(S aTS )Select(S *aTS )=Select(S *aTS )=*Select(S )=Follow(s )=#Select(S *aTS )Select(S )= Select(T +aT )=+Select(T T)=First(T) =+Select(T )=Follow(T )=*,#Select(T T)Select(T

展开阅读全文