中南大学软件工程2005年《编译原理》试卷及参考答案

《编译原理》软件工程2005级期终考卷学号：姓名：说明:1.本考卷中大写字母∈VN，其他符号∈VT；2、试卷中一、二两题请作在考卷上一、概念题（15分）1、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？2、对下列状态转换图，写出状态0的处理过程：其中：状态2的过程为proc2.3、文法G为：SaABAaB||则判断G为LL（1）文法的条件是：二、判断题（10分。注：每答对一题得+2分；答错一题得-2分；不答者得0分）1、设∑为{a，b}，则a，ba，{∑}，Ø都是∑上的正规式。（）2、对于上下文无关文法G[S]，若SαABαβγ则A一定是一条产生式规则，其中α,β,γ∈（VT∨VN）*（）3、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。（）4、LR（0）分析法是一种规范归约法。（）5、算符优先分析法只能用来分析算符优先文法。（）三、（10分）设文法G3为：SAaBcAAa|aBb求句型AaBc的最左素语。四、（20分）设文法G[S]为SaAcB问：1、该文法是否为算符文法，为什么？AAb|b2、构造算符优先关系表。Bd3、该文法是否可改造为LL（1）文法，为什么？012字母其他数字字母五、（本题20分）设文法G为：EeAf|eBgAaA|aBBb|a对于输入串eaaaf，采用LR（0）、LL（1）、SLR（1）等方法中合适的一种进行分析。六、（25分）有作控制用的布尔表达式文法G[E]及其语义动作如下：1、构造SLR（1）分析表（若不是SLR(1)）的，则说明理由）2、分析布尔式a∨bc的四元式生成过程，并画出最后的真假链表。3、给出语句IFa∨bcTHENI:=m*nELSEI:=m+n的完整四元式序列。文法G[E]：(1)Ei1i2{E.TC:=NXQ;E.FC=NXQ+1;GEN(J,ENTRY(i1),ENTRY(i2),O);GEN(J,,,0)}(2)EAE1{E.FC:=E1.FC;E.FC:=MERGE(A.TC,E1.TC)}(3)AB∨{BACKPATCH(B.FC,NXQ);A.TC:=B.TC}(4)Bi{B.TC:=NXQ;B.FC:=NXQ+1;GEN(Jnz,ENTRY(i),,0);GEN(J,,,0)}软件0501班编译原理考试答案及评分细则词法分析语法分析语义分析与中间代码产生优化目标代码生成源程序单词符号语法单位中间代码中间代码目标代码Proc0:getchar();CASEcharOF‘a’,’b’,…,’z’:‘A’,’B’,…,’Z’:proc1elseerrorENDCASE2、(5分)3、(5分)条件：（1）文法G不含左递归；（2）对于每个非终结符，First(α)、First(β)、First(γ)两两不相交；（3）对于每个非终结符，不含能推出ε的产生式，故不考虑非终结符的First集和Follow集相交的情况。二、（每小题2分）1、×；2、×；3、√；4、√；5、√。三、（10分）方法一：句型AaBc的语法树为：SAaBc故AaBc即为所求最左素短语。方法二：FIRSTVT(S)={a},LASTVT(S)={c},FIRSTVT(A)={a},LASTVT(A)={a},FIRSTVT(B)={b},LASTVT(B)={b}。则有：abc#a=bc#=对于#AaBc#，#a，a=c，c#，则最左素短语为AaBc。四、（20分）1、该文法是算符文法。因为其任一产生式的右部都不含相继（并列）的非终结符，即不含如下形式…QR…的产生式右部。（4分）2、FIRST(S)={a},LAST(S)={c},FIRST(A)={b},LAST(A)={b},FIRST(B)={d},LAST(B)={d}。（3分）构造算符优先关系表如下：（5分）abcd#a=bcd#=3、该文法可以改造为LL（1）文法。（8分）原因：①消除左递归：S→aAcBA→bA’A’→bA’|εB→d；②FIRST(A)={a},FOLLOW(A)={c},FIRST(A’)={b,ε},FOLLOW(A’)={c},FIRST(B)={d},FOLLOW(B)={#},FIRST(S)={a},FOLLOW(S)={#},对于每个非终结符的各个产生式的FIRST集两两不相交；③对于A’，FIRST（A）∩FOLLOW（A）=Φ。综上所述，原文法可以改造成LL（1）文法。五、（20分）原文法不是LL（1）文法，故不能直接使用LL（1）分析法进行分析。步骤如下：1、拓广文法：①E’→E②E→eAf③E→eBg④A→aA⑤A→a⑥B→Bb⑦B→a（2分）2、项目集规范族：E’→.EE→.eAfE→.eBgE’→E.E→e.AfA→.aAA→.aE→e.BgB→.BbB→.aE→eA.fA→a.AA→a.A→.aAA→.aB→B.bE→eAf.A→aA.A→a.AA→a.A→.aAA→.aE→eBg.B→Bb.E→eB.gB→B.b0Ee123A4aB5f6A7a8g9b10Aa（6分）由此项目集规范族可判断，原文法非LR（0）文法，故不能直接使用LR（0）分析法进行分析。因此，使用SLR（1）分析法分析原文法。3、构造SLR（1）分析表如下：FOLLOW(A)={f}；FOLLOW(B)={b,g}；FOLLOW(E)={#}。ACTIONGOTO状态abefg#ABE0S211acc2S4353S64S8r7r5r775S10S96r27r48S8r579r310r6r6（6分）4、分析输入串eaaaf如下：步骤状态符号输入串动作10#eaaaf#预备202#eaaaf#移进3024#eaaaf#移进40248#eaaaf#移进502488#eaaaf#移进602487#eaaAf#归约70247#eaAf#归约8023#eAf#归约90236#eAf#移进1001#E#归约11acc接受（6分）六、（25分）1、步骤：（1）拓广文法：①E’→E②E→i(1)i(2)③E→AE(1)④A→B∨⑤B→i（2分）（2）项目集规范族：E’→.EE→.i(1)i(2)E→.AE(1)A→.B∨B→.iE’→E.E→i.(1)i(2)B→i.E→A.E(1)E→.i(1)i(2)E→.AE(1)A→.B∨B→.iE→i(1).i(2)E→AE.(1)E→i(1)i.(2)A→B.∨A→B∨.01E2iA3B∨45A67EiB248i（6分）（3）SLR（1）分析表如下：FOLLOW(E)={#}；FOLLOW(A)={i}；FOLLOW(B)={∨}。ACTIONGOTO状态i∨#EAB0S21341acc2S6r43S27344S55r36S87r28r1（6分）2、分析输入串a∨bc如下：步骤状态栈符号输入串动作四元式10#a∨bc#预备202#i∨bc#移进304#B∨bc#归约B.TC=1,B.FC=2;Gen(Jnz,a,_,0);Gen(J,_,_,3);4045#B∨bc#移进503#Abc#归约A.TC=B.TC=1;BackPatch(2,3);6032#Aic#移进70326#AiC#移进803268#Aii#移进9037#AE#归约E.TC=3,E.FC=4;Gen(J,b,c,0);Gen(J,_,_,0);1001#E#归约E.FC=4;E.TC=MERG(1,3);11acc接受（6分）整理：真出口为3；假出口为4。（2分）1、Gen(Jnz,a,_,0)2、Gen(J,_,_,3)3、Gen(J,b,c,1)4、Gen(J,_,_,0)3、四元式：1、（Jnz,a,_,5）2、(J,_,_,3)3、(J,b,c,5)4、(J,_,_,8)5、(*,m,n,T1)6、(:=,T1,_,I)7、(J,_,_,10)8、(+,m,n,T2)9、(:=,T2,_,I)10、……（1）引论编译程序，编译过程，编译程序的结构。（2）高级语言及其语法描述上下文无关文法，语法分析树，二义性。（3）词法分析正规表达式，NFA，DFA，词法分析器设计。（4）语法分析-自上而下分析清除左递归，提左因子，递归下降子程序，预测分析表构造，LL（1）方法。（5）语法分析-自下而上分析算符优先表构造，符符优先函数构造，LR（0）分析表构造，SLR分析表构造，以及规范LR分析表构造。（6）属性文法和语法引导翻译S属性文法，S-属性文法的自下而上计算，L-属性文法和自顶而下的翻译。（7）语文分析和中间代即产生各种语句到四元式的翻译方法，包括说明语句，赋值语句，布尔表达式，控制语句，数组引用，过程调用。（8）符号表符号表的组织和使用方法。（9）运行时存储空间组织静态存储分配，动态存储分配，活动记录，Display表运行时的组织。（10）优化优化概述，局部优化，基本块的DAG表示及其应用。（11）代码生成简单代码生成器，寄存器分配，DAG目标代码。本课程的重点内容词法分析、语法分析、语义分析及中间代码生成优化。本课程的难点内容正规表达式、NFA、DFA、LL（1）分析、算符优先分析、LR（0）、SLR（1）、LR（1）分析。