编译原理期末试题(二)含答案.pdf

第 1 页 共 12 页编译原理期末试题（二）一、是非题：一、是非题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。()2.一个句型的直接短语是唯一的。（）3.已经证明文法的二义性是可判定的。（）4.每个基本块可用一个 DAG 表示。（）5.每个过程的活动记录的体积在编译时可静态确定。（）6.2 型文法一定是 3 型文法。（）7.一个句型一定句子。()8.算符优先分析法每次都是对句柄进行归约。X ()9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。()11.一个优先表一定存在相应的优先函数。X ()12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()13.递归下降分析法是一种自下而上分析法。()14.并不是每个文法都能改写成 LL(1)文法。()15.每个基本块只有一个入口和一个出口。()16.一个 LL(1)文法一定是无二义的。()17.逆波兰法表示的表达试亦称前缀式。()18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()19.正规文法产生的语言都可以用上下文无关文法来描述。()20.一个优先表一定存在相应的优先函数。()21.3 型文法一定是 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.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标代码生成）五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的 ）。4.从功能上说，程序语言的语句大体可分为（执行性 ）语句和（说明性 ）语句两大类。5.语法分析器的输入是（单词符号 ），其输出是（语法单位 ）。6.扫描器的任务是从（源程序中 ）中识别出一个个（单词符号 ）。7.符号表中的信息栏中登记了每个名字的有关的性质，如(类型、种属、所占单元大小、地址）等等。8.一个过程相应的 DISPLAY 表的内容为(现行活动记录地址和所有外层最新活动记录的地址)10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。11.一个名字的属性包括(类型)和(作用域 )。12.常用的参数传递方式有(传地址），（传值），（传名）13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。第 2 页 共 12 页14.语法分析的方法大致可分为两类，一类是（自上而下 ）分析法，另一类是（自下而上）分析法。15.预测分析程序是使用一张（分析表 ）和一个（符号栈）进行联合控制的。17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。21.一个文法 G，若它的预测分析表 M 不含多重定义，则该文法是（LL(1)文法）文法。22.对于数据空间的存贮分配，FORTRAN 采用(静态策略，PASCAL 采用(动态)策略。24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。26.对于文法 G，仅含终结符号的句型称为(句子)。27.所谓自上而下分析法是指(从开始符号出发，向下推导，推出句子）29.局限于基本块范围的优化称（局部优化 ）。31.2 型文法又称为（上下文无关）文法；3 型文法又称为（正则）文法。32.每条指令的执行代价定义为(指令访问主存次数加 1）33.算符优先分析法每次都是对(最左素短语）进行归约。三、名词解释题：三、名词解释题：1.局部优化-局限于基本块范围的优化称。2.二义性文法-如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3.DISPLAY 表-过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。5.最左推导-任何一步=都是对 中的最右非终结符替换。6.语法-一组规则，用它可形成和产生一组合式的程序。7.文法-描述语言的语法结构的形式规则。8.基本块-指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语-令 G 是一个文法，S 划文法的开始符号，假定 是文法 G 的一个句型，如果有 SA 且 A，则称 是句型 相对非终结符 A 的短语。11.待用信息-如果在一个基本块中，四元式 i 对 A 定值，四元式 j 要引用 A 值，而从 i 到 j 之间没有 A 的其它定值，则称 j 是四元式 i 的变量 A 的待用信息。12.规范句型-由规范推导所得到的句型。13.扫描器-执行词法分析的程序。14.超前搜索-在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15.句柄-一个句型的最左直接短语。16.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。17.规范句型-由规范推导所得到的句型。18.素短语-素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法-是组规则，用它可形成和产生一个合式的程序。20.待用信息-如果在一个基本块中，四元式 i 对 A 定值，四元式 j 要引用 A 值，而从 i 到 j 之间没有 A 的其它定值，则称 j 是四元式 i 的变量 A 的待用信息。21.语义-定义程序的意义的一组规则。四、简答题：四、简答题：1.写一个文法 G,使其语言为 不以 0 开头的偶数集。2.已知文法 G(S)及相应翻译方案SaAb print“1”Sa print“2”AAS print“3”第 3 页 共 12 页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;end beginA:=2;B:=A*2;P(A,A,B);Print A,B end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A,B 的值是什么?5文法 G(S)SdABAaA|aBBb|描述的语言是什么？6.证明文法 G(S)SSaS|是二义性的。7.已知文法 G(S)SBAABS|dBaA|bS|c的预测分析表如下 a b c d#SSBASBASBA AABSABSABSAd BBaA BbS Bc给出句子 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.考虑下面的程序：procedure p(x,y,z);begin y:=y+z;z:=y*z+xend;begin a:=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 begina:=5;b:=2;p(a+b,a-b,a);print a end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 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|+a消除文法左递归和提公共左因子。第 5 页 共 12 页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=45.L(G)=danbm|n0,m06.证明：因为文法 GS存在句子 aa 有两个不同的最左推导，所以文法 GS是是二义性的。S=SaS=SaSaS=aSaS=aaS=aa S=SaS=aS=aSaS=aaS=aa7.句子 adccd 的分析过程：步骤符号栈输入串产生式0#Sadccd#1#ABadccd#SBA2#AAaadccd#BaA3#AAdccd#4#Addccd#Ad5#Accd#6#SBccd#ABS7#Scccd#Bc8#S cd#9#ABcd#Bc10#Acd#11#A d#12#dd#Ad第 6 页 共 12 页13#8.所求文法是 GS:SAB AaAc|D DbD|bBaBb|aabb9.函数a(),f4244g552310.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指令系统的特点。12.正规式 a(a|b)*。13.删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。14.文法 GS:SaB|a Bbc|bBc15.传值 a=2 传地址 a=1516.逆波兰式:abcd-*e/+三元序列:op arg1 arg2 (1)-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,bba19.Display 表:嵌套层次显示表由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，display 表就是用于登记每个外层过程的最新活动记录起始地址。20.传地址 a=12传值 a=521.所求文法是 GS:SAC AaaAbb|ab CccC|cc22.逆波兰式 abc+e*bc+f/+:=三元序列 op arg1 arg2第 7 页 共 12 页 (1)+b c (2)*(1)e (3)+b c (4)/(3)f (5)+(2)(4)(6):=a (5)23.一个文法 G 别是 LL(1)文法的充要条件是:(1)FIRST()FIRST()=(2)如果=*,FIRST()FOLLOW(A)=24.消除左递归SaFS|*aFSS*aFS|F+aF|+a提公共左因子,文法 G(S)SaFS|*aFSS*aFS|F+aFFF|25.作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。主要技术：线性表，对折查找，杂奏技术。五、计算题：五、计算题：1.设文法 G(S):S|a|(T)TT,S|S 消除左递归；构造相应的 FIRST 和 FOLLOW 集合；构造预测分析表 2.语句 if E then S(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。3.设文法 G（S）：S(T)|aTT+S|S(1）计算 FIRSTVT 和 LASTVT；（2）构造优先关系表。4.设某语言的 for 语句的形式为for i:E(1)to E(2)do S其语义解释为i:E(1)LIMIT:E(2)again:if iLIMIT thenBeginS;i:i1goto againEnd;（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。5.把语句第 8 页 共 12 页while a0 then a:=a+1else a:=a*3-1;翻译成四元式序列。6.设有基本块D:=A-CE:=A*CF:=D*ES:=2T:=A-C Q:=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 语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。9.已知文法 G(S)SaAcBe AAb|b Bd(1)给出句子 abbcde 的最左推导及画出语法树；(2)给出句型 aAbcde 的短语、素短语。10.设文法 G(S):S(T)|aS|a TT,S|S 消除左递归和提公共左因子；构造相应的 FIRST 和 FOLLOW 集合；构造预测分析表。11.把语句 if X0 Y0 do X:=A*3 else Y:=B+3;翻译成四元式序列。12.已知文法 G(S)EE+T|T TT*F|F F(E)|i(1)给出句型(i+i)*i+i 的最左推导及画出语法树；(2)给出句型(E+T)*i+F 的短语，素短语和最左素短语。13.设文法 G（S）：第 9 页 共 12 页ST|STTU|TUUi|-U（1）计算 FIRSTVT 和 LASTVT；（2）构造优先关系表。第 10 页 共 12 页答案：答案：(1)消除左递，文法变为 GS：S|a|(T)TST|ST,ST|此文法无左公共左因子。(2)构造相应的 FIRST 和 FOLLOW 集合：FIRST(S)=a,(，FOLLOW(S)=#,)FIRST(T)=a,(，FOLLOW(T)=FIRST(T)=,，FOLLOW(F)=)(3)构造预测分析表：a(),#SSaSS(T)TTSTTSTTSTTTT,ST2.(1)Cif E thenSCS(1)(2)Cif E then BACK(E.TC,NXQ);C.chain:=E.FC SCS(1)S.chain:=MERG(C.Chain,S(1).Chain)3.(1)FIRSTVT(S)=a,(FIRSTVT(T)=+,aa,(LASTVT(S)=a,)LASTVT(T)=+,a,)(2)a +()a .+(.4.(1)Ffor i:=E(1)to E(2)do SFS(1)(2)Ffor i:=E(1)to E(2)doGEN(:=,E(1).place,_,entry(i);F.place:=entry(i);LIMIT:=Newtemp;GEN(:=,E(2).place,_,LIMIT);Q:=NXQ;F.QUAD:=q;GEN(j,entry(i),LIMIT,q+2)F.chain:=NXQ;GEN(j,_,_,0)SFS(1)BACKPATCH(S(1).chain,NXQ);GEN(+,F.place,1,F.place);GEN(j,_,_,F.QUAD);S.chain:=F.chain5.(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)(10)(:=,T3,_,a)(11)(j,_,_,(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,S a直接短语 T,S a句柄 T,S8.(1)Sdo M1 S1 while M2 EM (2)M M.quad=nestquad;Sdo M1 S1 while M2 E backpatch(s1.nextlist,M2.quad);backpatch(E.truelist,M1.quad);S.nextlist=E.falelist;9.(1)S=aAcBe=AAbcBe=abbcBe=abbcde(2)短语:aAbcde,Ab,d 素短语:Ab,d10.(1)S(L)|aS SS|LSL L,SL|(2)FIRST(S)=a,(FIRST(S)=a,(,FIRST(L)=a,(FIRST(L)=,FOLLOW(S)=,),#FOLLOW(S)=,),#FOLLOW(L)=)FOLLOW(L)=)第 12 页 共 12 页(3)()a ,#SS(L)S aSSSSSSSSSLLSLLSLL,SL LL11.(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)(12)(:=,T2,_,Y)12.(1)E=E+T=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+T13.(1)FIRSTVT(S)=,i,-FIRSTVT(T)=,i,-FIRSTVT(U)=i,-LASTVT(S)=,i,-LASTVT(T)=,i,-LASTVT(U)=i,-(2)i -S .-.