编译原理(A卷)答案.doc

湖北第二师范学院20142015学年度第二学期编译原理课程考试答案(A卷)院 系： 计算机学院 专业班级： 学生姓名： 学 号： 考试方式 ： 闭卷 题号一二三四五总分签名分数得分评卷人一、填空题（每空1分，共10分）1词法分析程序是逐个识别（字符 ），形成单词级别的（字符 ）串，词法分析程序输出的数据是（2 ）个，它们分别是（种别编码 ）和（自身值 ）。 2语法分析程序是逐个识别（单词 ），形成语句级别的（单词 ）串。3一遍扫描的编译方法，是以语法分析程序为主，调用（词法分析 ）程序、语义分析程序，再由语义程序调用中间代码生成、中间代码优化等。4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即（静态存储分配 ）方案和（动态存储分配 ）方案。得分评卷人二、综合题（共90分）1（5分）将下面文法改写成3型文法： G=（S,A,B,a,b,c,d,e,P,S）其中：P=SabcA|edB,AbeB,Bd答案：改写后的3型文法是（5分）G=（S,A,B,C,D,E,F,a,b,c,d,e,P,S）其中：P=SaC|eF, CbD,DcA,AbE,EeB,FdB,Bd2（5分）给出下面表达式的四元式形式： a*b+(c-d)/e答案：四元式形式（5分）（*，a，b，t1）（-，c，d，t2）（/，t2，e，t3）（+，t1，t3，t4）3（30分）给定文法 GE ： E E+T | E-T | T T T*F | T/F | FF (E) | i 该文法是 LL(1) 文法吗？为什么？不是的能否改造为LL（1）文法，如果能够改造，给出改造后的文法，并给出改造后文法是LL（1）文法的证明过程。无论改造前还是改造后的文法，如果是LL（1）文法，则给出（i+i）*i的分析过程（要求给出详细过程，并给出LL（1）的分析表）答案：（1）该文法不是LL（1）文法，因为文法的产生式含有左递归 （2分）（2）该文法可改造为LL（1）文法，即消除左递归，改造后的文法是 （3分）E TEE +TE | -TE | T FTT *FT | /FT |F (E) | i 证明改造后的文法是LL（1）文法的过程A. 求可达的非终结符 （1分）可达的是E,TB. 求每个非终结符的First集合 （3分）First(E)= (,iFirst(E)=+,-First(T)= (,iFirst(T)=*,/First(F)= (,iC. 求每个产生式右部字符串的First集合 （3分）First(TE)= (,iFirst(+TE)=+First(-TE)=-First(FT)= (,iFirst(*FT)=*First(/FT)=/First(E)= ( First(i)= i First()= D. 求每个非终结符的Follow集合 （3分）Follow(E)=$,)Follow(E)= Follow(E)=$,)Follow(T)=First(E) Follow(E)=$,+,-,)Follow(T)= Follow(T)=$,+,-,)Follow(F)= First(T) Follow(T)=$,+,-, *,/,)E. 求每个非终结符的Select集合 （5分）Select(E TE)=First(TE)= (,i Select(E +TE)=First(+TE)= + Select(E -TE)=First(-TE)= - Select(E )=First()- Follow(E)= $,) Select(T FT)=First(FT)= (,i Select(T *FT)=First(*FT)= * Select(T /FT)=First(/FT)= / Select(T )=First()- Follow(T)= $,+,-,) Select(F (E)=First(E)= ( Select(F i)=First(TE)= i F. 求有多个产生式的非终结符Select集合的交集 （2分）显然有Select(E +TE)Select(E -TE) Select(E )=Select(T *FT) Select(T /FT) Select(T )= Select(F (E)= Select(F i)= 所以改造后的文法是LL（1）文法（3）、根据E给出预测分析表 （4分）非终结符终结符+-*/()i$ETETEE+TE-TET FTFTT *FT *FTF(E)i符号串（i+i）*i的分析过程 （4分）步骤符号栈Si输入符号串产生式1$E(i+i)*i$ETE2$ET(i+i)*i$T FT3$ETF(i+i)*i$F（E）4$ET）E（(i+i)*i$ET）Ei+i)*i$ETE$ET）ETi+i)*i$T FT$ET）ETFi+i)*i$Fi$ET）ETii+i)*i$ET）ET+i)*i$T $ET）E+i)*i$E +TE$ET）ET+i)*i$ET）ETi)*i$TFT$ET）ETFi)*i$Fi$ET）ETii)*i$ET）ET)*i$T $ET）E)*i$E $ET）)*i$ET*i$T *FT$ETF*i$ETFi$Fi$ET$T $EE $4（10分）对下面的NFA进行确定化xxxx,yyyxyq0q1q2q3q4答题：第1步：确定化过程（5分）新状态IxIy0q0 0q1 1q2 21q1 1q2,q3 32q2 2q1,q3 43q2,q3 3q3,q4 5q1,q3 44q1,q3 4q2,q3,q4 6q3 75q3,q4 5q3,q4 5q3 76q2,q3,q4 6q3,q4 5q1,q3 47q3 7q3,q4 5q3 7第2步：确定化的DFAxyyyxxyxyq0q1q2q3q5q4q7xyxq6yx5（15分）给定文法 GE ： E E+T | E-T | T T T*F | T/F | FF (E) | i 该文法是算符优先文法吗？是，则构造该文法的算符优先关系矩阵，并给出（i+i）*i的分析过程（要求给出详细过程）答案：（1）该文法是算符优先文法 （1分）（2）构造该文法的算符优先矩阵A. 求各非终结符的FirstVT集合 （3分）FirstVT（E）=+，-，*，/，（，iFirstVT（T）=*，/，（，iFirstVT（F）=（，iB. 求各非终结符的LasttVT集合 （3分）LastVT(E)= +，-，*，/，)，i LastVT(T)= *，/，)，i LastVT(F)= )，i C. 构造优先关系表 （4分）+-*/()i$+-*/(=i$=(3)分析（i+i）*过程 （4分）步骤符号栈S关系输入符号串最左素短语$(i+i)*i$(+i)*i$i$(V+i)*i$(V+)*i$i$(V+V)*i$V+V$(V=)*i$(V)*i$(V)$V*i$V*i$V*i$V*V$V=$6（25分）给定文法 GE ： E E+T | T T T*F | FF (E) | i 该文法是LR（0）文法吗？是，则构造该文法的LR（0）分析表，并给出（i+i）*i的分析过程，不是的，是SLR（1）文法吗，是，则构造该文法的SLR（1）分析表，并给出（i+i）*i的分析过程。（要求给出详细过程）答案：（1）拓广文法 （2分）0、E E1、 E E+T 2、 E T 3、T T*F 4、T F 5、F (E) 6、F i （2）构造LR（0）项目集规范簇 （10分）（3）在下图的DFA中，I1、I2、I9均发生了规约移进冲突，所以该文法不是LR（0）文法。 （2分）（4）在I1规范项目集中规约项目E E. 的Follow（E）=$，而移进项目的移进符号集=+，Follow（E）+= 在I2规范项目集中规约项目E T. 的Follow（E）=$，+，），而移进项目的移进符号集=*，Follow（E）*= 在I9规范项目集中规约项目E E+T. 的Follow（E）=$，+，），而移进项目的移进符号集=*，Follow（E）*= 所以，在3个发生冲突的项目集中可解决冲突，因此该文法是SLR（1）文法 （5分）iI5(I4FI3）I9EE+T.TT.*FF(iI0E .EE.E+TE.TT.T*FT.FF.(E)F.iI1E E.EE.+TEI2ET.TT.*FTI3T F.FI5Fi.iI4F(.E)E.E+TE.TT.T*FT.FF.(E)F.i(I6EE+.TT.T*FT.FF.(E)F.i+I7TT*.FF.(E)F.i*+FTI8F(E.)EE.+TE+I10TT*F.*(iI11F（E）.（5）根据上面的DFA建立SLR（1）的分析表 （4分）状态ActionGotoi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r4r4r44S5S48235r6r6r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r3r3r311r5r5r5r5r5r5（6）分析（i+i）*i的过程 （4分）栈内容输入符号串动作0（i+i）*i$移进0(4i+i）*i$移进0(4i5+i）*i$r6规约0(4F3+i）*i