《编译原理》考试试题及答案(汇总).doc 62页

'《编译原理》考试试题及答案（汇总）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。(×)2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)3．一个算符优先文法可能不存在算符优先函数与之对应。(√)4．语法分析时必须先消除文法中的左递归。(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√)6．逆波兰表示法表示表达式时无须使用括号。(√)7．静态数组的存储空间可以在编译时确定。(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×)9．两个正规集相等的必要条件是他们对应的正规式等价。(×)10．一个语义子程序描述了一个文法所对应的翻译工作。(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1．词法分析器的输出结果是_____。　A．()单词的种别编码　　　　　　B．()单词在符号表中的位置　C．()单词的种别编码和自身值　　D．()单词自身值2．正规式M1和M2等价是指_____。 　A．()M1和M2的状态数相等 　　      B．()M1和M2的有向边条数相等　C．()M1和M2所识别的语言集相等　　D．()M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_____。　A．()xyx 　B．()(xyx)*C．()xnyxn(n≥0)   D．()x*yx*4．如果文法G是无二义的，则它的任何句子α_____。　A．()最左推导和最右推导对应的语法树必定相同　　　B．()最左推导和最右推导对应的语法树可能不同　　　C．()最左推导和最右推导必定相同 　　　D．()可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。　A．()源程序   　　　B．()目标语言     C．()编译方法    D．()以上三项都是6．四元式之间的联系是通过_____实现的。　A．()指示器       　　B．()临时变量　C．()符号表           D．()程序变量7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。　A.()┐AB∨∧CD∨　　　　B．()A┐B∨CD∨∧       C．()AB∨┐CD∨∧       D．()A┐B∨∧CD∨8.优化可生成_____的目标代码。　A．()运行时间较短　　　              B．()占用存储空间较小　C．()运行时间短但占用内存空间大　　　D．()运行时间短且占用存储空间小9．下列______优化方法不是针对循环优化进行的。　A.()强度削弱   　　　B．()删除归纳变量   　C．()删除多余运算　  　D．()代码外提 10．编译程序使用_____区别标识符的作用域。　A.()说明标识符的过程或函数名　B．()说明标识符的过程或函数的静态层次　C．()说明标识符的过程或函数的动态层次　D.()标识符的行号三、填空题(每空1分，共10分)1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。5．后缀式abc-/所代表的表达式是___a/(b-c)__。6．局部优化是在__基本块___范围内进行的一种优化。四、简答题（20分）1.简要说明语义分析的基本功能。答：语义分析的基本功能包括:确定类型、类型检查、语义处理和某些静态语义检查。2.考虑文法G[S]:S→(T)|a+S|aT→T,S|S消除文法的左递归及提取公共左因子。解：消除文法G[S]的左递归：S→(T)|a+S|a T→ST′T′→,ST′|ε提取公共左因子：S→(T)|aS′S′→+S|εT→ST′T′→,ST′|ε3.试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。解：wab+cde10-/+8+*+4.按照三种基本控制结构文法将下面的语句翻译成四元式序列：while(AaAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有：S"->AA->aAd|aAb|ε下面构造它的LR(0)项目集规范族为： 从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。其SLR(1)分析表为：对输入串ab#给出分析过程为： 一、是非题：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.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。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的一个句型，如果有SαAδ且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)及相应翻译方案S→aAb{print“1”}S→a{print“2”}A→AS{print“3”}A→c{print“4”}输入acab,输出是什么？3.已知文法G(S)S→bAa　　A→(B|aB→Aa)　写出句子b(aa)b的规范归约过程。4.考虑下面的程序：…procedure p(x,y,z)；begin y:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A,A,B);PrintA,Bend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出A,B的值是什么?5．文法G(S)S→dABA→aA|aB→Bb|ε描述的语言是什么？6.证明文法G(S)S→SaS|ε是二义性的。7.已知文法G(S)S→BAA→BS|dB→aA|bS|c的预测分析表如下abcd#SS→BAS→BAS→BAAA→BSA→BSA→BSA→dBB→aAB→bSB→c给出句子adccd的分析过程。8.写一个文法G,使其语言为L(G)={albmclanbn|l>=0,m>=1,n>=2}9.已知文法G(S):S→a|(T)T→T,S|S的优先关系表如下：关系a(),a--.>.>(<.<.=.<.)--.>.>,<.<..>.>请计算出该优先关系表所对应的优先函数表。10.何谓优化？按所涉及的程序范围可分为哪几级优化？11.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？12.一字母表Σ={a,b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。13.基本的优化方法有哪几种？14.写一个文法G,使其语言为L(G)={abncn|n≥0}15.考虑下面的程序：…procedurep(x,y,z); beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b,b,a);printaend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么?16.写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。17.证明文法G(A)A→AA|(A)|ε是二义性的。18.令Σ={a,b}，则正规式a*b|b*a表示的正规集是什么？19.何谓DISPLAY表？其作用是什么？20.考虑下面的程序：…procedure p(x,y,z)；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b,a-b,a);printaend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么?21.写一个文法G,使其语言为L(G)={anbncm|n>0为奇数，m>0为偶数}22.写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。23.一个文法G别是LL(1)文法的充要条件是什么？24.已知文法G[S]S→S*aF|aF|*aFF→+aF|+a消除文法左递归和提公共左因子。25.符号表的作用是什么？符号表查找和整理技术有哪几种？答案：1.所求文法是G[S]:S→AB|BA0A→AD|CB→2|4|6|8C→1|3|5|7|9|BD→0|C2.输出是42313.句子b(aa)b的规范归约过程：步骤符号栈输入串动作0#b(aa)b#预备 1#b(aa)b#移进2#b(aa)b#移进3#b(aa)b#移进4#b(Aa)b#归约5#b(Ma)b#移进6#b(Ma)b#移进7#b(Bb#归约8#bAb#归约9#bAb#移进10#S#接受4.传地址A=6,B=16传值A=2,B=45.L(G)={danbm|n>0,m≥0}6.证明：因为文法G[S]存在句子aa有两个不同的最左推导，所以文法G[S]是是二义性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aaS=>SaS=>aS=>aSaS=>aaS=>aa7.句子adccd的分析过程：步骤符号栈输入串产生式0#Sadccd#1#ABadccd#S→BA2#AAaadccd#B→aA3#AAdccd#4#Addccd#A→d5#Accd#6#SBccd#A→BS7#Scccd#B→c8#Scd#9#ABcd#B→c10#Acd#11#Ad#12#dd#A→d13##8.所求文法是G[S]:S→ABA→aAc|DD→bD|bB→aBb|aabb9.函数a(),f4244 g552310.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。　　三种级别：局部优化、循环优化、全局优化11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题：　　(1)如何使生成的目标代码较短；　　　(2)如何充分利用寄存器，以减少访问内存次数；　　　(3)如何充分利用指令系统的特点。12.正规式a(a|b)*。13.删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。14.文法G[S]:S→aB|aB→bc|bBc15.传值a=2传地址a=1516.逆波兰式:abcd-*e/+三元序列:oparg1arg2(1)-cd(2)*b(1)(3)/(2)e(4)+a(3)17.证明：因为文法G[S]存在句子()有两个不同的最左推导，所以文法G[S]是是二义性的。A=>AA=>(A)A=>()A=>()A=>AA=>A=>(A)=>()18.(a*b|b*a)={a,b,ab,ba,aab,bba……}19.Display表:嵌套层次显示表由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，display表就是用于登记每个外层过程的最新活动记录起始地址。20.传地址a=12传值a=521.所求文法是G[S]:S→ACA→aaAbb|abC→ccC|cc22.逆波兰式abc+e*bc+f/+:=三元序列oparg1arg2(1)+bc(2)*(1)e(3)+bc(4)/(3)f(5)+(2)(4)(6):=a(5)23.一个文法G别是LL(1)文法的充要条件是:(1)FIRST(α)∩FIRST(β)=Ф(2)如果β=*>ε,FIRST(α)∩FOLLOW(A)=Ф24.消除左递归S→aFS’|*aFS’S’→*aFS’|ε F→+aF|+a提公共左因子,文法G’(S)S→aFS’|*aFS’S’→*aFS’|εF→+aF’F’→F|ε25.作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。主要技术：线性表，对折查找，杂奏技术。五、计算题：1.设文法G(S):S→^|a|(T)T→T,S|S⑴消除左递归；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表2.语句ifEthenS　　(1)改写文法，使之适合语法制导翻译；　　(2)写出改写后产生式的语义动作。3.设文法G（S）：S→(T)|aT→T+S|S(1）计算FIRSTVT和LASTVT；（2）构造优先关系表。4.设某语言的for语句的形式为fori:＝E(1)toE(2)doS其语义解释为i:＝E(1)LIMIT:＝E(2)again:ifi＜＝LIMITthenBeginS;i:＝i＋1gotoagainEnd;（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。5.把语句whilea<10doifc>0thena:=a+1elsea:=a*3-1;翻译成四元式序列。6.设有基本块　　D:=A-C　　E:=A*C　　F:=D*E　　S:=2　　T:=A-CQ:=A*C　　G:=2*S 　　J:=T*QK:=G*5　　L:=K+JM:=L　　假设基本块出口时只有M还被引用，请写出优化后的四元序列。7.已知文法G(S)S→a|^|(T)T→T,S|S(1)给出句子(a,(a,a))的最左推导；(2)给出句型((T,S),a)的短语,直接短语，句柄。8.对于C语言doSwhileE语句　　(1)改写文法，使之适合语法制导翻译；　　(2)写出改写后产生式的语义动作。9.已知文法G(S)　　S→aAcBe　　A→Ab|b　　B→d　　(1)给出句子abbcde的最左推导及画出语法树；　　(2)给出句型aAbcde的短语、素短语。10.设文法G(S):S→(T)|aS|aT→T,S|S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。11.把语句ifX>0∨Y<0thenwhileX>0doX:=A*3elseY:=B+3;翻译成四元式序列。12.已知文法G(S)　E→E+T|T　T→T*F|F　F→(E)|i　(1)给出句型(i+i)*i+i的最左推导及画出语法树；　(2)给出句型(E+T)*i+F的短语，素短语和最左素短语。13.设文法G（S）：S→T|S∨TT→U|T∧UU→i|-U（1）计算FIRSTVT和LASTVT；（2）构造优先关系表。 答案：(1)消除左递，文法变为G’[S]：S→^|a|(T)"T→ST’|ST’→,ST’|ε此文法无左公共左因子。(2)构造相应的FIRST和FOLLOW集合：FIRST(S)={a,^,(}，FOLLOW(S)={#,,,)}FIRST(T)={a,^,(}，FOLLOW(T)={}}FIRST(T’)={,,ε}，FOLLOW(F)={)}(3)构造预测分析表：a^(),#SS→aS→^S→(T)"TT→ST’T→ST’T→ST’T’T’→εT’→,ST’2.(1)C→ifEthenS→CS(1)(2)C→ifEthen{BACK(E.TC,NXQ);C.chain:=E.FC}S→CS(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)F→fori:=E(1)toE(2)doS→FS(1)(2)F→fori:=E(1)toE(2)do{GEN(:=,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)}S→FS(1){BACKPATCH(S(1).chain,NXQ);GEN(+,F.place,1,F.place);GEN(j,_,_,F.QUAD);S.chain:=F.chain}5.(1)(j<,a,‘10’,(3)) (2)(j,_,_,(12))(3)(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,Sa直接短语T,Sa句柄T,S8.(1)S→doM1S1whileM2EM→ε(2)M→ε{M.quad=nestquad;}S→doM1S1whileM2E{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’S’→S|εL→SL’L’→,SL’|ε(2)FIRST(S)={a,(}FIRST(S’)={a,(,ε}FIRST(L)={a,(}FIRST(L’)={,,ε}FOLLOW(S)={,,),#}FOLLOW(S’)={,,),#}FOLLOW(L)={)}FOLLOW(L’)={)} (3)()a,#SS→(L)S→aS’S’S’→SS’→εS’→SS’→εS’→εLL→SL’L→SL’L’→,SL’L’L’→ε11.(1)(j>,X,0,(5))(2)(j,_,_,(3))(3)(j<,Y,0,(5))(4)(j,_,_,(11))(5)(j>0,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.>.>∨<..><.<.∧<..>.><.-<..>.><.1、描述由正规式b*(abb*)*(a|e)定义的语言，并画出接受该语言的最简DFA。2、证明文法E®E+id|id是SLR(1)文法。 3、下面是表达式和赋值语句的文法，其中and的类型是bool´bool®bool，+的类型是int´int®int，=的类型是int´int®bool，:=要求id和E的类型都是int或者都是bool。为该文法写一个语法制导定义或翻译方案，它完成类型检查。S®id:=EE®EandE|E+E|E=E|id4、对于下面C语言文件s.cf1(intx){longx;x=1;}f2(intx){{longx;x=1;}}某编译器编译时报错如下：s.c:Infunction‘f1’:s.c:3:warning:declarationof‘x’shadowsaparameter请回答，对函数f2为什么没有类似的警告错误。5、下面C语言程序经非优化编译后，若运行时输入2，则结果是area=12.566360,addr=-1073743076经优化编译后，若运行时输入2，则结果是area=12.566360,addr=-1073743068请解释为什么输出结果有区别。main(){floats,pi,r;pi=3.14159;scanf("%f",&r);printf("area=%f,addr=%dn",s=pi*r*r,&r);}6、描述由正规式b*a(bb*a)*b*定义的语言，并画出接受该语言的最简DFA。7、下面的文法产生代表正二进制数的0和1的串集：B®B0|B1|1下面的翻译方案计算这种正二进制数的十进制值：B®B10{B.val:=B1.val´2}|B11{B.val:=B1.val´2+1}|1{B.val:=1}请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。8、在C语言中，如果变量i和j都是long类型，请写出表达式&i和表达式&i-&j的类型表达式。为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。main(){longi,j;printf(“%dn”,&i-&j);}9、一个C语言的函数如下：func(i)longi;{ longj;j=i–1;func(j);}下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。左边的代码在调用func之前将参数压栈，调用结束后将参数退栈。右边代码对参数传递的处理方式没有实质区别。请叙述右边代码对参数传递的处理方式并推测它带来的优点。func:|func:pushl%ebp|pushl%ebpmovl%esp,%ebp|movl%esp,%ebpsubl$4,%esp|subl$8,%espmovl8(%ebp),%edx|movl8(%ebp),%eaxdecl%edx|decl%eaxmovl%edx,-4(%ebp)|movl%eax,-4(%ebp)movl-4(%ebp),%eax|movl-4(%ebp),%eaxpushl%eax|movl%eax,(%esp)callfunc|callfuncaddl$4,%esp|leaveleave|retret|编译原理试卷八答案start1abb21、由正规式b*(abb*)*(a|e)定义的语言是字母表{a,b}上不含子串aa的所有串的集合。最简DFA如下：2、先给出接受该文法活前缀的DFA如下：E¢®·EE®·E+idE®·idI0E¢®E·E®E·+idI1E®id·I2Eid+E®E+·idI3E®E+id·I4idI0和I3都只有移进项目，肯定不会引起冲突；I2和I4都无移进项目并仅含一个归约项目，也肯定不会引起冲突；在I1中，E¢的后继符号只有$，同第2个项目的展望符号“+”不一样，因此I1也肯定不会引起冲突。由此可以断定该文法是SLR(1)的。3、语法制导定义如下。S®id:=E{S.type:=if(id.type=boolandE.type=bool)or(id.type=intandE.type=int)thentype_okelsetype_error}E®E1andE2{E.type:=ifE1.type=boolandE2.type=boolthenboolelsetype_error}E®E1+E2{E.type:=ifE1.type=intandE2.type=intthenintelsetype_error}E®E1=E2{E.type:=ifE1.type=intandE2.type=intthenboolelsetype_error} E®id{E.type:=lookup(id.entry)}4、对于函数f1，局部变量x声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。由于这是一个合法的C语言函数，因此编译器给出警告错误。对于函数f2，由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。5、使用非优化编译时，变量s,pi,r在局部数据区都分配4个字节的空间。使用优化编译时，由于复写传播，pi*r*r变成3.14159*r*r，pi=3.14159成为无用赋值而删去，函数中不再有pi的引用，因此不必为pi分配空间。类似地，s=3.14159*r*r也是一个无用赋值（表达式要计算，但赋值是无用的），也不必为s分配空间。这样，和非优化情况相比，局部数据区少了8个字节，因此r的地址向高地址方向移动了8个字节。6、正规式b*a(bb*a)*b*体现的特点是，每个a的左边都有若干b，除非a是第一个字母。该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：start2abb10ab7、消除左递归后的文法：B®1B¢B¢®0B¢|1B¢|e相应的翻译方案如下：B®1{B¢.i:=1}B¢{B.val:=B¢.val}B¢®0{B¢1.i:=B¢.i´2}B¢1{B¢.val:=B¢1.val}|1{B¢1.i:=B¢.i´2+1}B¢1{B¢.val:=B¢1.val}|e{B¢.val:=B¢.i}8、表达式&i的类型表达式是pointer(long)，表达式&i-&j的类型表达式是long。按照C语言的规定，指向同一个类型的两个指针可以相加减，它们值的差是它们之间的元素个数。9、左边的编译器版本：一般只为局部变量分配空间。调用函数前，用若干次pushl指令将参数压栈，返回后用addl$n,%esp一次将所有参数退栈（常数n根据调用前做了多少次pushl来决定）。右边的编译器版本：除了为局部变量分配空间外，同时还为本函数中出现的函数调用的参数分配空间，并且参数所用空间靠近栈顶。调用函数前，用movl指令将参数移入栈顶，调用结束后无需参数退栈指令。优点是每次函数调用结束后不需要执行addl$n,%esp指令，另外增加优化的可能性。 《编译原理》期末试题（三）1、从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？答：从优化的范围的角度，优化可以分为局部优化和全局优化两类；对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。答：逆波兰式：abc*bd*+:=四元式序列：三元式序列:OPARG1ARG2(1)(*，b，c，t1)(1)(*b，c)(2)(*，b，d，t2)(2)(*b，d)(3)(+，t1，t2，t3)(3)(+(1)，(2))(4)(:=，t3，/，a)(4)(:=(3)，a)3、对于文法G(S):SbM(TMabL)答：1）2）短语:Ma)，(Ma)，b(Ma)b直接短语:Ma)句柄:Ma)三、设有字母表{a，b}上的正规式R=(ab|a)*。解：（1） 0123baaεε-+（2）将（1）所得的非确定有限自动机确定化εab-01131221+3ab-+013123+12312313+13123012aaba-+++（3）对（2）得到的DFA化简，合并状态0和2为状态2：12aab-++（4）令状态1和2分别对应非终结符B和AG:A→aB|a|ε；B→aB|bA|a|b|ε；可化简为：G:A→aB|ε；B→aB|bA|ε三、设将文法G改写成等价的LL(1)文法，并构造预测分析表。G：S→S*aT|aT|*aT；T→+aT|+a解：消除左递归后的文法G’:S→aTS’|*aTS’S’→*aTS’|εT→+aT|+a提取左公因子得文法G’’:S→aTS’|*aTS’S’→*aTS’|εT→+aT’T’→T|εSelect(S→aTS’)={a}Select(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’→ε)=Ф所以该文法是LL(1)文法。预测分析表：*+a#S→*aTS’→aTS’S’→*aTS’→εT→+aT’T’→ε→T→ε6设文法G为：S→A；A→BA|ε；B→aB|b解：（1）拓广文法G’：(0)S’→S(1)S→A(2)A→BA(3)A→ε(4)B→aB(5)B→b；FIRST(A)={ε,a,b}；FIRST(B)={a,b}构造的DFA如下:项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。（2）LR(1)分析表如下： (3)输入串abab的分析过程为：简答题3、设有文法G[S]:S→S(S)S|ε，该文法是否为二义文法？说明理由。答：是二义的，因为对于（）（）可以构造两棵不同的语法树。SSS(S)SS(S)SεεS(S)SS(S)Sεεεεεεεε三、给定文法G[S]：S→aA|bQ；A→aA|bB|b；B→bD|aQ；Q→aQ|bD|b；D→bB|aA；E→aB|bFF→bD|aE|b构造相应的最小的DFA。解：先构造其NFA：用子集法将NFA确定化：abSAQAABZQQDZBZQDDZABDABBQD将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。ab 012113224325416516625令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割：P1＝（｛0,5,6｝,｛1,2｝,｛3,4｝）再用b进行分割：P2＝（｛0｝,｛5,6｝,｛1,2｝,｛3,4｝）再用a、b进行分割，仍不变。再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。最小化为右上图。三、对文法G(S)：S→a|^|(T)；T→T，S|S答：(1)a^(),#a>>>^>>>(<<<=<)>>>,<<<>>#<<<=(2)是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。（2分）(3)给出输入串(a,a)#的算符优先分析过程。步骤栈当前输入字符剩余输入串动作1#(a,a##<(移进2#(a,a)#(,归约4#(N,a)#(<,移进5#(N,a)#,)归约7#(N,N）#,>)归约8#(N)#(=)移进9#(N)# )>#归约10#N#接受一、简述编译程序的工作过程。（10） 编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；④代码优化，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。二、构造下列正规式相应的DFA（用状态转换图表示）（15）（1）1（0|1）*10,1（2）0*10*10*10*1（3）letter（letter|digit）*03121（1）0051（2）112304011letter(3)1letter2digit三、给出下面语言的相应文法：（15）L1={anbn|n≥1}L2={anbm+nam|n≥1，m≥0}G1：A→aAb|abG1：S→ABA→aAb|abB→bBa|ε四、对下面的文法G：S→a|b|（T）T→T，S|S(1)消去文法的左递归，得到等价的文法G2；(2)判断文法G2是否LL（1）文法，如果是，给出其预测分析表。（15）G2：S→a|b|（T）T→ST’ T’→，ST’|εG2是LL（1）文法。ab（），#SS→aS→bS→（T）TT→ST’T→ST’T→ST’T’T’→εT’→，ST’五、设有文法G[A]：A→BCc|gDBB→bCDE|εC→DaB|caD→dD|εE→gAf|c(1)计算该文法的每一个非终结符的FIRST集和FOLLOW集；(2)试判断该文法是否为LL（1）文法。（15）FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g是LL（1）文法。六、对表达式文法G：E→E+T|TT→T*F|FF→(E)|I（1）造各非终结符的FIRSTVT和LASTVT集合；（2）构造文法的算符优先关系表。（15）FIRSTVTLASTVTETF*，+，（，i*，（，i（，i*，+，），i*，），i），i算符优先关系表+*I（）#+*I（）#>>><><<>><><<<<<<<<<>>>=>>>>>=七、有定义二进制整数的文法如下：L→LB|B B→0|1构造一个翻译模式，计算该二进制数的值（十进制的值）。（15）引入L、B的综合属性val，翻译模式为：S→L{print(L.val)}L→L1B{L.val=L1.val*2+B.val}L→B{L.val=B.val}B→0{B.val=0}B→1{B.val=1}《编译原理》期末试题（五）一、单项选择题(共10小题，每小题2分，共20分)1．语言是A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合2．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化3．一个句型中称为句柄的是该句型的最左A．非终结符号B．短语C．句子D．直接短语4．下推自动机识别的语言是A．0型语言B．1型语言C．2型语言D．3型语言5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A．字符B．单词C．句子D．句型6．对应Chomsky四种文法的四种语言之间的关系是A．L0ÌL1ÌL2ÌL3B．L3ÌL2ÌL1ÌL0C．L3=L2ÌL1ÌL0D．L0ÌL1ÌL2=L3 7．词法分析的任务是A．识别单词B．分析句子的含义C．识别句子D．生成目标代码8．常用的中间代码形式不含A．三元式B．四元式C．逆波兰式D．语法树9．代码优化的目的是A．节省时间B．节省空间C．节省时间和空间D．把编译程序进行等价交换10．代码生成阶段的主要任务是A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体机器的目标代码D．把汇编语言翻译成机器语言二、填空题（本大题共5小题，每小题2分，共10分）1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。三、名词解释题(共5小题，每小题4分，共20分)1．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2．LL(1)文法若文法的任何两个产生式A®a|b都满足下面两个条件：（1）FIRST(a)ÇFIRST(b)=f；（2）若bÞ*e，那么FIRST(a)ÇFOLLOW(A)=f。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。3．语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么A®A1A2…AR一定是P中的一条产生式。 (4)若一标记为A的节点至少有一个除它以外的子孙，则AVN。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。4．LR(0)分析器所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。5．语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法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为文法开始符号，且}简单的说，文法描述的语言是该文法一切句子的集合。四、简答题(共4小题，每小题5分，共20分)1．编译程序和高级语言有什么区别?用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的"对话"，随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。2．编译程序的工作分为那几个阶段?词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。3．简述自下而上的分析方法。所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。4．简述代码优化的目的和意义。代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目 标程序运行时所需要的时间短，同时所占用的存储空间少。五、综合应用题(共3小题，每小题10分，共30分)1．证明下述文法G：S®aSbS|aS|d是二义性文法。解：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。句子aadbd有两棵语法树。如下图：dSSabSSadSaSSabSdd(1)(2)由此可知，S®aSbS|aS|d定义的文法是二义性文法。ASBbBSab2．对于文法G[S]：S®AB，A®Aa|bB，B®a|Sb求句型baSb的全部短语、直接短语和句柄？句型baSb的语法树如图五(2)所示。解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。3．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，d，{A}，{C})，其中：d(A，0)={C}d(A，1)={A，B}d(B，1)={C}d(C，1)={C}。请画出状态转换距阵和状态转换图。解：状态转换距阵为：d01ACA，BBÆCCÆC状态转换图为11011 《编译原理》期末试题（六）编译原理样题【】1．____型文法也称为正规文法。　　　[A]0[B]1[C]2[D]3【】2．____文法不是LL(1)的。　　[A]递归[B]右递归[C]2型[D]含有公共左因子的【】3．文法E→E+E|E*E|i的句子i*i+i*i的不同语法分析树的总数为______。　　　[A]1[B]3[C]5[D]7【】4．四元式之间的联系是通过实现。[A]临时变量[B]指示器[C]符号表[D]程序变量【】5．同心集合并可能会产生的新冲突为。[A]二义[B]移进/移进[C]移进/归约[D]归约/归约【】6．代码优化时所依据的是。[A]语法规则[B]词法规则[C]等价变换规则[D]语义规则【】7．表达式a-(-b)*c的逆波兰表示为。[A]a-b@c*[B]ab@c*-[C]ab@-[D]ab@c-*（注：@为单目减运算符）【】8．过程的DISPLAY表记录了。[A]过程的连接数据[B]过程的嵌套层次[C]过程的返回地址[D]过程的入口地址二填空题3．对于文法G1和G2，若有L(G1)=L(G2)（或G1和G2的语言相同），则称文法G1和G2是等价的。4．对于文法G[E]：E→T|E+TT→F|T*FF→P^F|PP→(E)|i，句型T+T*F+i的句柄是T，最左素短语是T*F。5．最右推导的逆过程称为规范归约，也称为最左归约。6．规范规约中的可规约串是句柄，算符优先分析中的可规约串是最左素短语7．（A∨B）∧（C∨¬D∧E）的逆波兰式是ＡＢ∨ＣＤ¬Ｅ∧∨∧。8．在属性文法中文法符号的两种属性分别称为继承属性和综合属性（次序可换）。 9．符号表的每一项是由名字栏和地址分配两个栏目组成。在目标代码生成阶段，符号表是地址分配的依据。10．一个过程的DISPLAY表的内容是它的　直接外层的DISPLAY表的内容加上本过程的SP的地址三有穷自动机M接受字母表S＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的DFAM及和M等价的正规式。【】【】四证明正规式(ab)*a与正规式a(ba)*等价（用构造他们的最小的DFA方法）。【答案：】 五写一个文法，使其语言是：L＝{1n0m1m0n|m,n≥0}【】【】五文法G：S→1S0|AA→0A1|ε六对文法G[S]　S→aSb|PP→bPc|bQcQ→Qa|a(1)它是否是算符优先文法？请构造算符优先关系表(2)文法G[S]消除左递归、提取左公因子后是否是LL（1）文法？请证实。【】【】1.求出G[S]的FIRSTVT集和LASTVT集：FIERSTVT（S）={a,b}LASTBVT（S）={b,c}FIERSTVT(P)={b}LASTBVT（P）={c}FIERSTVT(Q)={a}LASTBVT（Q）={a}构造优先关系表为：abca<><>b<>c>>由于在优先关系中同时出现了aa以及bb，所以该文法不是算符优先文法。2.消除左递归和提取左公因子后的文法为：S→aSb|PP→bP’P’→Pc|QcQ→aQ’Q’→aQ’|ε求具有相同左部的两个产生式的Select集的交集：Select(S→aSb)∩Select(S→P)={a}∩First(P)={a}∩{b}=ФSelect(P’→Pc)∩Select(P’→Qc)=First(P)∩First(Q)={b}∩{a}=ФSelect(Q’→aQ’)∩Select(Q’→ε)={a}∩Follow(Q)={a}∩{c}=Ф所以修改后的文法是LL（1）文法。七已知文法G为:（0）S′→S（1）S→aAd（2）S→bAc（3）S→aec（4）S→bed（5）A→e试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。【】【答案：】ecAdI0:S′→·S,#S→·aAd,#S→·bAc,#S→·aec,#S→·bed,#I2：S→a·Ad,#S→a·ec,#A→·e,daI1：S′→S·,#SI3:S→b·Ac,#S→b·ed,#A→·e,cbI6:S→bA·c,#AI7：S→be·d,#A→e·,cI11：S→bed·,#dI10：S→bAc·,#I4：S→aA·d,#I5：S→ae·c,#　A→e·,deI8：S→aAd·,#I9：S→aec·,#c 构造LR(1)分析表如下：r411S106r210r39r18S11r57r5S95S846S734S52acc1A#S3bedc1SgotoaS2action0状态八已知源程序如下：prod:=0;i:=1;whilei≤20dobeginprod:=prod+a[i]*b[i];i:=i+1end;试按语法制导翻译法将源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。【答案：】 九设有以下程序段procedureP(x,y,z)beginY:=y*3;Z:=X+z;end;begina:=5;b:=2;p(a*b,a,a);print(a);end若参数传递的方法分别为（1）传值、（2）传地址、（3）传名，试问结果分别什么？【】【】十（1）传值5；（2）传地址25；（3）传名45十对以下文法，请写出关于括号嵌套层数的属性文法。(为S,L引入属性h,用来记录输出配对的括号个数)文法规则语义规则S→(T)S→iT→T,ST→S 答案：十一对PL/0语言的while语句while条件BDO语句S的编译程序，请在空缺处填空，完成该语句的编译算法：switch(SYM){……caseWHILESYM:CX1=CX;GetSym();CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);CX2=CX;GEN(JPC,0,0);if(SYM==DOSYM)GetSym();elseError(18);STATEMENT(FSYS,LEV,TX);GEN(JMP,0,CX1);CODE[CX2].A=CX；break;……}《编译原理》期末试题（七）一、回答下列问题：(30分)1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？解答：S-属性文法是只含有综合属性的属性文法。（2分）L-属性文法要求对于每个产生式AàX1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于： （1）产生式Xj的左边符号X1,X2…Xj-1的属性；（2）A的继承属性。（2分）S-属性文法是L-属性文法的特例。（2分）2．什么是句柄？什么是素短语？一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分）3．划分程序的基本块时，确定基本块的入口语句的条件是什么？解答：（1）程序第一个语句，或（2）能由条件转移语句或无条件转移语句转移到的语句，或（3）紧跟在条件转移语句后面的语句。4．(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。5．(6分)对下列四元式序列生成目标代码：A:=B*CD:=E+FG:=A+DH:=G*2其中，H是基本块出口的活跃变量，R0和R1是可用寄存器答：LDR0，BMULR0，CLDR1，EADDR1，FADDR0，R1MULR0，2STR0，H二、设S={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)答：构造相应的正规式：(0|1)*1(0|1)(3分)NFA:(2分)11 10432eeee100确定化：(3分)I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}014321001000111三、写一个文法使其语言为L(G)={anbmambn|m,n≥1}。(6分)答：文法G(S):S®aSb|BB®bBa|ba四、对于文法G(E):(8分)E®T|E+TT®F|T*FF®(E)|iETF(E)E+TFiTT*F1.写出句型(T*F+i)的最右推导并画出语法树。2.写出上述句型的短语，直接短语、句柄和素短语。答：1.(4分)EÞTÞFÞ(E)Þ(E+T)Þ(E+F)Þ(E+i)Þ(T+i)Þ(T*F+i)2.(4分)短语：(T*F+i),T*F+i,T*F,i直接短语：T*F,i句柄：T*F 素短语：T*F,i五、设文法G(S)：(12分)1．构造各非终结符的FIRSTVT和LASTVT集合；2．构造优先关系表和优先函数。(12分)答：(6分)FIRSTVT(S)={i，+，)，(}FIRSTVT(A)={+，)，(}FIRSTVT(B)={)，(}LASTVT(S)={i，+，*，(}LASTVT(A)={+，*，(}LASTVT(B)={*，(}优先关系表:(3分)i+()*i><<<+>><<>(>>>)<<<*>>>优先函数:(3分)i+()*f26616g14661六、设某语言的do-while语句的语法形式为(9分)S®doS(1)WhileE其语义解释为：真假S(1)的代码E的代码针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1)写出适合语法制导翻译的产生式； (2)写出每个产生式对应的语义动作。答：(1).适合语法制导翻译的文法(3分)G(S):R®doU®RS(1)WhileS®UE(2).(6分)R®do{R.QUAD:=NXQ}U®RS(1)While{U.QUAD:=R.QUAD;BACKPATCH(S.CHAIN,NXQ)}S®UE{BACKPATCH(E.TC,U.QUAD);S.CHAIN:=E.FC}答案二：(1)S®doM1S(1)WhileM2EM®ε(3分)(2)M®ε{M.QUAD:=NXQ}(6分)S®doM1S(1)WhileM2E{BACKPATCH(S(1).CHAIN,M2.QUAD);BACKPATCH(E.TC,M1.QUAD);S.CHAIN:=E.FC}七、(8分)将语句if(A0)thenwhileC>0doC:=C+D翻译成四元式。(8分)答：100(j<，A，X，102)101(j，-，-，109)102(j>，B，0，104) 103(j，-，-，109)104(j>，C，0，106)105(j，-，-，109)106(+，C，D，T1)107(:=，T1，-，C)108(j，-，-，104)109(控制结构3分，其他5分)八、(10分)设有基本块如下：T1:=S+RT2:=3T3:=12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)画出DAG图；(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。T1,T5,B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n7答：(1)DAG如右图：(6分)(2)四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4九、(9分)设已构造出文法G(S)：(1)S®BB(2)B®aB(3)B®b的LR分析表如下 ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。答：步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#acc《编译原理》期末试题（八）1．（10分）处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。2．为语言L＝{ambn|0£m£2n}（即a的个数不超过b的个数的两倍）写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。）3．（10分）构造下面文法的LL（1）分析表。D®TLT®int|realL®idRR®,idR|e4．（15分）就下面文法 S®(L)|aL®L,S|S·给出一个语法制导定义，它输出配对括号的个数。·给出一个翻译方案，它输出每个a的嵌套深度。如句子(a,(a,a))，第一小题的输出是2，第二小题的输出是122。5．（10分）Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。6．（5分）一个C语言程序如下：func(i1,i2,i3)longi1,i2,i3;{longj1,j2,j3;printf("Addressesofi1,i2,i3=%o,%o,%on",&i1,&i2,&i3);printf("Addressesofj1,j2,j3=%o,%o,%on",&j1,&j2,&j3);}main(){longi1,i2,i3;func(i1,i2,i3);}该程序在某种机器的Linux上的运行结果如下：Addressesofi1,i2,i3=27777775460,27777775464,27777775470Addressesofj1,j2,j3=27777775444,27777775440,27777775434从上面的结果可以看出，func函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。7．（15分）一个C语言程序及其在某种机器linux操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40; }.file"static.c".version"01.01"gcc2_compiled.:.data.align4.typeaa,@object.sizeaa,4aa:.long10.globlbb.align2.typebb,@object.sizebb,2bb:.value20.align4.typecc.2,@object.sizecc.2,4cc.2:.long30.text.align4.globlfunc.typefunc,@functionfunc:pushl%ebpmovl%esp,%ebpsubl$4,%espmovw$40,-2(%ebp).L1:leaveret.Lfe1:.sizefunc,.Lfe1-func.ident"GCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)"8．（10分）C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型语言。 9．（10分）如果在A机器上我们有C语言编译器CCA，也有它的源码SA（用C语言写成）。如何利用它通过尽量少的工作来得到B机器的C语言编译器CCB。10．（5分）表达式(lx.(lyz.(x+y)+z)3)45和(lx.(lyz.(x+y)+z)35)4有同样的结果。在抽象机FAM上，哪一个表达式对应的目标代码的执行效率高？为什么？参考答案1．124start52othersothers/***/2．LR（1）文法LR（1）文法二义文法S®AB|aABbS®ABS®AASb|eA®aaAb|eA®aaAb|ab|eA®a|eB®Bb|eB®Bb|e3．intrealid,$DD®TLD®TLTT®intT®realLL®idRRR®,idRR®e4．S¢®Sprint(S.num)S®(L)S.num:=L.num+1S®aS.num:=0L®L1,SL.num:=L1.num+S.numL®SL.num:=S.numS¢®{S.depth:=0}SS®{L.depth:=S.depth+1}(L)S®a{print(S.depth)}L®{L1.depth:=L.depth}L1,{S.depth:=L.depth}SL®{S.depth:=L.depth}S5．t1:=initialt2:=finalift1>t2gotoL1v:=t1L2:stmtifv=t2gotoL1v:=v+1gotoL2L1: 6．由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。7．aa是静态外部变量，而bb是外部变量，它们都分配在静态数据区（由.data伪指令开始），但是bb由伪指令.globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。cc是静态局部变量，同aa和bb一样，它的生存期是整个程序并分配在静态数据区。由于cc在源程序中的作用域是函数func的体，而在目标文件中，它的作用域至少已是整个文件了，为避免同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了cc.2。由于cc不是全局的，因此cc.2前面没有伪指令.globl。dd是自动变量，其作用域是函数func的体，其生存期是该函数激活期间，因此它分配在栈区，并且置初值是用运行时的赋值来实现。8．例如联合体的类型检查一般也不可能在编译时完成，虽然下面例子是可静态判断类型错误的。unionU{intu1;int*u2;}u;int*p;u.u1=10;p=u.u2;*p=0;9．·修改源码SA的代码生成部分，让它产生B机器的代码，称结果程序为SB。·将SB提交给CCA进行编译，得到一个可执行程序。·将SB提交给上述可执行程序进行编译，得到所需的编译器CCB。10．第一个表达式在执行lyz.(x+y)+z)3时出现参数个数不足的情况，因此有FUNVAL的值进入栈顶，然后发现参数个数不足，又把它做成FANVAL的情况。而第二个表达式执行的是(lyz.(x+y)+z)35，不会出现参数个数不足的情况。因此第二个表达式的执行效率比第一个表达式的高。《编译原理》期末大题1.设有如下文法G（S），试消除其左递归。G（S）：S—>Ac|cA—>Bb|bB—>Sa|a解：S→abcS′|bcS′|cS′,S′→abcS′|2.试构造与下面G（S）等价的无左递归的文法。G（S）：S—>Sa|Nb|cN—>Sd|Ne|f解：S→fN′bS′|cS′,S′→aS′|dN′bS′|,N′→eN′|3.设有文法G（S）：S—>aBc|bABA—>aAb|bB—>b|ε①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。②构造LL(1)分析表，并分析符号串baabbb是否是。 解：（1）FIRST(aBc)={a},FIRST(bAB)={b}FIRST(aAb)={a},A→b:FIRST(A→b)={b},B→b:FIRST(b)={b},FIRST(ε)={ε}FOLLOW(A)={b,#},FOOLOW(B)={c,#}SELECT(S→aBc)={a},SELECT(S→bAB)={b},SELECT(A→aAb)={a},SELECT(A→b)={b},SELECT(B→b)={b},SELECT(B→)={c,#}因此，所得的LL(1)分析表如表A-4所示。表A-4LL(1)分析表输入VN输入符号abc#SS→aBcS→bABAA→aAbA→bBB→bB→B→（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。图A-16识别串baabbb的过程1.对下列文法G(S)：S—>D(R)R—>R;P|PP—>S|ID—>i①计算文法G中每个非终结符的FIRSTVT集和LASTVT集。②构造文法G的算符优先关系矩阵。解：（1）FIRSTVT(S)={(,i}，FIRSTVT(D)={i}，FIRSTVT(R)={;,(,i}，FIRSTVT(P)={i,(}，LASTVT(S)={)}，LASTVT(D)={i}，LASTVT(R)={;,),i}，LASTVT(P)={i,)}（2）算符优先矩阵，如表A-5所示。表A-5优先矩阵();i#( );i#1.已知文法G(S)：S—>a|(T)T—>T,S|S①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。解：（1）最左推导：S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))语法树：如图A-16所示。图A-16(a,(a,a))的语法树（2）句型(T,a,(T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。短语：a||T,a||(T)||T,a,(T)||(T,a,(T))直接短语：a||(T)素短语：a||(T)最左素短语：a句柄：a活前缀：||(||(T||(T,||(T,a图A-17(T,a,(T))的语法树2.设文法Ｇ（Ｓ）为：Ｓ—＞ａ｜ａＡｂ　　　　　Ｓ—＞ｂ｜ｂＢａＡ—＞１Ａ０｜ε　　　　　　Ｂ—＞１Ｂ０｜ε求①ＬＲ（０）项目集族；②构造识别文法Ｇ（Ｅ）的ＤＦＡ；　③构造文法Ｇ（Ｅ）的SLR（１）的分析表；　④分析句子ａ１１００ｂ的识别过程。 解：（1）、（2）LR(0)项目集族和识别活前缀的DFA，如图A-19所示。图A-19LR(0)项目集族和DFA（3）、（4）略。一、选择1．将编译程序分成若干个“遍”是为了_B__。A.提高程序的执行效率B.使程序的结构更加清晰C.利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率2．正规式MI和M2等价是指__C__。A.MI和M2的状态数相等B.Ml和M2的有向弧条数相等。C.M1和M2所识别的语言集相等D.Ml和M2状态数和有向弧条数相等3．中间代码生成时所依据的是_C_。A．语法规则B．词法规则C．语义规则D．等价变换规则4．后缀式ab+cd+/可用表达式__B_来表示。A．a+b/c+dB．(a+b)/(c+d)C．a+b/(c+d)D．a+b+c/d6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化， 目标代码生成等五个部分。A．()语法分析B．()文法分析C．()语言分析D．()解释分析7．词法分析器用于识别__C___。A．()字符串B．()语句C．()单词D．()标识符8．语法分析器则可以发现源程序中的___D__。A．()语义错误B．()语法和语义错误C．()错误并校正D．()语法错误9．下面关于解释程序的描述正确的是__B___。(1)解释程序的特点是处理程序时不产生目标代码(2)解释程序适用于COBOL和FORTRAN语言(3)解释程序是为打开编译程序技术的僵局而开发的A．()(1)(2)B．()(1)C．()(1)(2)(3)D．()(2)(3)10．解释程序处理语言时,大多数采用的是__B___方法。A．()源程序命令被逐个直接解释执行B．()先将源程序转化为中间代码,再解释执行C．()先将源程序解释转化为目标程序,再执行D．()以上方法都可以11．编译过程中,语法分析器的任务就是__B___。(1)分析单词是怎样构成的(2)分析单词串是如何构成语句和说明的(3)分析语句和说明是如何构成程序的(4)分析程序的结构A．()(2)(3)B．()(2)(3)(4)C．()(1)(2)(3)D．()(1)(2)(3)(4)12．编译程序是一种___C__。A.()汇编程序B．()翻译程序C．()解释程序D．()目标程序13．文法G所描述的语言是_C____的集合。A.()文法G的字母表V中所有符号组成的符号串B．()文法G的字母表V的闭包V*中的所有符号串C．()由文法的开始符号推出的所有终极符串D.()由文法的开始符号推出的所有符号串14．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是___B__。A.()短语文法B．()正则文法C．()上下文有关文法D．()上下文无关文法15．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组__D___。A．()句子B．()句型C．()单词D．()产生式16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_C____。A．()模拟执行器B．()解释器C．()表格处理和出错处理D．()符号执行器17．文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是CA．()L(G[N])={bi│i≥0}B．()L(G[N])={b2i│i≥0}C．()L(G[N])={b2i+1│i≥0}D．()L(G[N])={b2i+1│i≥1}18．一个句型中的最左_B____称为该句型的句柄。A．()短语B．()简单短语C．()素短语D．()终结符号19．设G是一个给定的文法，S是文法的开始符号，如果S->x(其中x∈V*),则称x是文法G的一个___B__。A．()候选式B．()句型C．()单词D．()产生式20．文法G[E]：E→T∣E＋TT→F∣T﹡FF→a∣（E）该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的_____。 ①（E＋T）②E＋T③F④F﹡(E＋T)A．()①和③B．()②和③C．()③和④D．()③21．若一个文法是递归的，则它所产生的语言的句子__A___。A．()是无穷多个B．()是有穷多个C．()是可枚举的D．()个数是常量22．词法分析器用于识别___C__。A．()句子B．()句型C．()单词D．()产生式23．在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是_B____。A.()非终极符集B．()终极符集C．()字母表D.()状态集24．在自底向上的语法分析方法中，分析的关键是__A___。A.()寻找句柄B.()寻找句型C.()消除递归D.()选择候选式25．在LR分析法中，分析栈中存放的状态是识别规范句型___C__的DFA状态。A.()句柄B.()前缀C.()活前缀D.()LR(0)项目26．文法G产生的__D___的全体是该文法描述的语言。A．()句型B．()终结符集C．()非终结符集D．()句子27．若文法G定义的语言是无限集，则文法必然是___A__A．()递归的B．()前后文无关的C．()二义性的D．()无二义性的28．四种形式语言文法中，1型文法又称为__A___文法。A．()短语结构文法B．()前后文无关文法C．()前后文有关文法D．()正规文法29．一个文法所描述的语言是__A___。A．()唯一的B．()不唯一的C．()可能唯一，好可能不唯一D．()都不对30．__B___和代码优化部分不是每个编译程序都必需的。A．()语法分析B．()中间代码生成C．()词法分析D．()目标代码生成31．_B____是两类程序语言处理程序。A．()高级语言程序和低级语言程序B．()解释程序和编译程序C．()编译程序和操作系统D．()系统程序和应用程序32．数组的内情向量中肯定不含有数组的_A____的信息。A.()维数B．()类型C．()维上下界D．()各维的界差33.一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组__D___。A．()句子B．()句型C．()单词D．()产生式34．文法分为四种类型，即0型、1型、2型、3型。其中2型文法是___D__。A.()短语文法B．()正则文法C．()上下文有关文法D．()上下文无关文法35．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组__D___。A．()句子B．()句型C．()单词D．()产生式36．__A___是一种典型的解释型语言。A．()BASICB．()CC．()FORTRAND．()PASCAL37．与编译系统相比，解释系统___D__。A．()比较简单,可移植性好,执行速度快B．()比较复杂,可移植性好,执行速度快C．()比较简单,可移植性差,执行速度慢D．()比较简单,可移植性好,执行速度慢38．用高级语言编写的程序经编译后产生的程序叫__B___。A．()源程序B．()目标程序C．()连接程序D．()解释程序 39．编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过___B__这几步:(1)编辑(2)编译(3)连接(4)运行A.()(1)(2)(3)(4)B．()(1)(2)(3)C．()(1)(3)D．()(1)(4)40．把汇编语言程序翻译成机器可执行的目标程序的工作是由__A___完成的。A．()编译器B．()汇编器C．()解释器D．()预处理器41．词法分析器的输出结果是__C___。A．()单词的种别编码B．()单词在符号表中的位置C．()单词的种别编码和自身值D．()单词自身值42．文法G：S→xSx|y所识别的语言是__C___。A．()xyxB．()(xyx)*C．()xnyxn(n≥0)D．()x*yx*43．如果文法G是无二义的，则它的任何句子α___A__。A．()最左推导和最右推导对应的语法树必定相同B．()最左推导和最右推导对应的语法树可能不同C．()最左推导和最右推导必定相同D．()可能存在两个不同的最左推导，但它们对应的语法树相同44．构造编译程序应掌握___D___。A．()源程序B．()目标语言C．()编译方法D．()以上三项都是45．四元式之间的联系是通过__B___实现的。A．()指示器B．()临时变量C．()符号表D．()程序变量46．表达式(┐A∨B)∧(C∨D)的逆波兰表示为___B__。A.()┐AB∨∧CD∨B．()A┐B∨CD∨∧C．()AB∨┐CD∨∧D．()A┐B∨∧CD∨47.优化可生成__D___的目标代码。A．()运行时间较短B．()占用存储空间较小C．()运行时间短但占用内存空间大D．()运行时间短且占用存储空间小48．下列__C____优化方法不是针对循环优化进行的。A.()强度削弱B．()删除归纳变量C．()删除多余运算D．()代码外提49．编译程序使用__B___区别标识符的作用域。A.()说明标识符的过程或函数名B．()说明标识符的过程或函数的静态层次C．()说明标识符的过程或函数的动态层次D.()标识符的行号50．编译程序绝大多数时间花在___D__上。A．()出错处理B．()词法分析C．()目标代码生成D．()表格管理51．编译程序是对__D___。A．()汇编程序的翻译B．()高级语言程序的解释执行C．()机器语言的执行D．()高级语言的翻译52．采用自上而下分析，必须__C___。A．()消除左递归B．()消除右递归C．()消除回溯D．()提取公共左因子53．在规范归约中，用__B___来刻画可归约串。A．()直接短语B．()句柄C．()最左素短语D．()素短语54．若a为终结符，则A->α•aβ为__B___项目。A．()归约B．()移进C．()接受D．()待约55．间接三元式表示法的优点为__A___。A．()采用间接码表，便于优化处理B．()节省存储空间，不便于表的修改 C．()便于优化处理，节省存储空间D．()节省存储空间，不便于优化处理56．基本块内的优化为___B__。A.()代码外提，删除归纳变量B．()删除多余运算，删除无用赋值C．()强度削弱，代码外提D．()循环展开，循环合并57．在目标代码生成阶段，符号表用___D__。A．()目标代码生成B．()语义检查C．()语法检查D．()地址分配58．若项目集Ik含有A->α•，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A->α•”动作的一定是__D___。A.()LALR文法B．()LR(0)文法C．()LR(1)文法D．()SLR(1)文法59．堆式动态分配申请和释放存储空间遵守__D___原则。A.()先请先放B．()先请后放C．()后请先放D.()任意二、判断1．计算机高级语言翻译成低级语言只有解释一种方式。(×)2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×)3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(√)4．正则文法其产生式为A->a，A->Bb,A,B∈VN，a、b∈VT。(×)5．每个文法都能改写为LL(1)文法。(√)6．递归下降法不允许任一非终极符是直接左递归的。(√)7．算符优先关系表不一定存在对应的优先函数。(×)8．自底而上语法分析方法的主要问题是候选式的选择。(×)9．LR法是自顶向下语法分析方法。(×)10．简单优先文法允许任意两个产生式具有相同右部。(×)11．“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(×)12．若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。(×)13．一个句型的句柄一定是文法某产生式的右部。(√)14．在程序中标识符的出现仅为使用性的。(×)15．仅考虑一个基本块，不能确定一个赋值是否真是无用的。(√)16．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。(√)17．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。(×)18．数组元素的地址计算与数组的存储方式有关。(×)19．编译程序与具体的机器有关,与具体的语言无关。(×)20．递归下降分析法是自顶向上分析方法。(√)21．产生式是用于定义词法成分的一种书写规则。(×)22．LR法是自顶向下语法分析方法。(×)23．在SLR（1）分析法的名称中，S的含义是简单的。(√)24．综合属性是用于“自上而下”传递信息。(×)25．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×)26．程序语言的语言处理程序是一种应用软件。(×)27．一个LL(l)文法一定是无二义的。(×)28．正规文法产生的语言都可以用上下文无关文法来描述。(×)29．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。(√)30．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(×)31．逆波兰法表示的表达式亦称后缀式。(√) 32．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。(√)33．数组元素的地址计算与数组的存储方式有关。(×)34．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×)35．编译程序是对高级语言程序的解释执行。(×)36．一个有限状态自动机中，有且仅有一个唯一的终态。(×)37．语法分析时必须先消除文法中的左递归。(×)38．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√)39．逆波兰表示法表示表达式时无须使用括号。(√)40．静态数组的存储空间可以在编译时确定。(×)41．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×)42．两个正规集相等的必要条件是他们对应的正规式等价。(×)43．一个语义子程序描述了一个文法所对应的翻译工作。(×)44．r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×)45．确定的的自动机以及不确定的自动机都能正确地识别正集(√)46．分析作为单独的一遍来处理较好。(×)47．LR分析器的任务就是产生LR分析表。(√)48．归约和规范推导是互逆的两个过程。(√)49．同心集的合并有可能产生新的“移进”/“归约”冲突(×)50.lR分析技术无法适用二义文法。(×)51树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。(×)52序中的表达式语句在语义翻译时不需要回填技术。(√)三、填空1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和___出错处理__。2．若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序称为___编译程序__。3．编译方式与解释方式的根本区别在于__是否生成目标代码___。4．对编译程序而言,输入数据是___源程序__,输出结果是__目标程序___。5．产生式是用于定义___语法成分__的一种书写规则。6．语法分析最常用的两类方法是___自上而下__和___自下而上__分析法7．设G是一个给定的文法，S是文法的开始符号，如果S->x(其中x∈VT*),则称x是文法的一个__句子___。8．递归下降法不允许任一非终极符是直接__左___递归的。9．自顶向下的语法分析方法的基本思想是：从文法的__开始符号____开始，根据给定的输入串并按照文法的产生式一步一步的向下进行__直接推导____，试图推导出文法的__句子____，使之与给定的输入串___匹配___。10．自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行___直接归约__，力求归约到文法的__开始符号___。11常用的参数传递方式有___传地址__，传值和传名。12．在使用高级语言编程时,首先可通过编译程序发现源程序的全部__语法___错误和语义的部分错误。13．一个句型中的最左简单短语称为该句型的___句柄_。14．对于文法的每个产生式都配备了一组属性的计算规则，称为__语义规则___。 15．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。16．从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。17．产生式是用于定义__语法范畴___的一种书写规则。18．语法分析是依据语言的__语法___规则进行的，中间代码产生是依据语言的__语义___规进行的。19．语法分析器的输入是__单词符号串___，其输出是__语法单位___。20．产生式是用于定义___语法成分__的一种书写规则。21．逆波兰式ab+c+d*e-所表达的表达式为__(a+b+c)*d-e___。22．语法分析最常用的两类方法是__自上而下___和__自下而上___分析法。23．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。24．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。25．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。26．一个LR分析器包括两部分：一个总控程序和___一张分析表_。27．后缀式abc-/所代表的表达式是___a/(b-c)__。28．局部优化是在__基本块___范围内进行的一种优化。29．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。30．语法分析基于__上下文无关___文法进行，即识别的是该类文法的句子。语法分析的有效工具是__语法树___。31．分析句型时，应用算符优先分析技术时，每步被直接归约的是__最左素短语___，而应用LR分析技术时，每步被直接归约的是___句柄__。32．语义分析阶段所生成的与源程序等价的中间表示形式可以有__逆波兰___、___三元式表示__与___四元式表示__等。33．按Chomsky分类法，文法按照___规则定义的形式__进行分类。34．一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有___递归__定义的规则。35．一个名字的属性包括__类型___和__作用域___。四、综合题1.已知文法G(E)E→T|E＋TT→F|T*FF→(E)|i(1)给出句型(T*F＋i)的最右推导；(2)给出句型(T*F＋i)的短语、简单短语、句柄、素短语、最左素短语。解：(1)最右推导：E->T->F->(E)->(E＋T)->(E＋F)->(E＋i)->(T＋i)->(T*F＋i)(2)短语：(T*F＋i)，T*F＋i，T*F，i简单短语：T*F,i句柄：T*F素短语：T*F,i最左素短语：T*F2.构造正规式1(0|1)*101相应的DFA。解：先构造NFA： 确定化：重新命名，令AB为B、AC为C、ABY为D得： 所以，可得DFA为：3.文法：S->MH|aH->LSo|εK->dML|εL->eHfM->K|bLM判断G是否为LL(1)文法，如果是，构造LL(1)分析表。解：各符号的FIRST集和FOLLOW集为：各产生式SELECT集为：SELECTS->MH{d,b,e,#,o}S->a{a}H->LSo{e}H->ε{#,f,o}K->dML{d}K->ε{e,#,o}L->eHf{e}M->K{d,e,#,o}M->bLM{b}预测分析表 由于预测分析表中无多重入口，所以可判定文法是LL(1)的。4.对下面的文法G：E->TE"E"->+E|εT->FT"T"->T|εF->PF"F"->*F"|εP->(E)|a|b|^(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。(4分)(2)证明这个方法是LL(1)的。(4分)(3)构造它的预测分析表。(2分)解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(E")={+,ε}FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(T")=FIRST(T)U{ε}={(,a,b,^,ε};FIRST(F)=FIRST(P)={(,a,b,^};FIRST(F")=FIRST(P)={*,ε};FIRST(P)={(,a,b,^};FOLLOW集合有：FOLLOW(E)={),#};FOLLOW(E")=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E")UFOLLOW(E)={+,),#};//不包含εFOLLOW(T")=FOLLOW(T)=FIRST(E")UFOLLOW(E)={+,),#};FOLLOW(F)=FIRST(T")UFOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F")=FOLLOW(F)=FIRST(T")UFOLLOW(T)={(,a,b,^,+,),#};FOLLOW(P)=FIRST(F")UFOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε(2)证明这个方法是LL(1)的。各产生式的SELECT集合有：SELECT(E->TE")=FIRST(T)={(,a,b,^};SELECT(E"->+E)={+};SELECT(E"->ε)=FOLLOW(E/)={),#}SELECT(T->FT")=FIRST(F)={(,a,b,^};SELECT(T"->T)=FIRST(T)={(,a,b,^};SELECT(T"->ε)=FOLLOW(T/)={+,),#};SELECT(F->PF")=FIRST(P)={(,a,b,^};SELECT(F"->*F")={*};SELECT(F"->ε)=FOLLOW(F")={(,a,b,^,+,),#};SELECT(P->(E))={(}SELECT(P->a)={a}SELECT(P->b)={b}SELECT(P->^)={^}可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。 (3)构造它的预测分析表。文法G[E]的预测分析表如下：5.已知文法G[S]为：S->a|^|(T)T->T,S|S(1)计算G[S]的FIRSTVT和LASTVT。(2)构造G[S]的算符优先关系表并说明G[S]是否未算符优先文法。(3)给出输入串(a,a)#的算符优先分析过程。解：（1）各符号的FIRSTVT和LASTVT：（2）算符优先关系表：（3）句子(a,a)#分析过程如下： 6.已知文法为：S->a|^|(T)T->T,S|S构造它的LR(0)分析表。解：加入非终结符S"，方法的增广文法为：S"->SS->aS->^S->(T)T->T,ST->S下面构造它的LR(0)项目集规范族为：从上表可看出,不存在移进-归约冲突以及归约归约冲突，该文法是LR(0)文法。从而有下面的LR(0)分析表：7.已知文法为：A->aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解： 增加一个非终结符S/后，产生原文法的增广文法有：S"->AA->aAd|aAb|ε下面构造它的LR(0)项目集规范族为：从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。其SLR(1)分析表为：对输入串ab#给出分析过程为：'