编译原理A卷答案

1、编译原理A卷答案 第5页，共9页得分评卷人1 词法分析程序是逐个识别（字符）,形成单词级别的（字符）串，词法分析程序输出湖北第二师范学院2014- 2015学年度第二学期编译原理课程考试答案（A卷）院系:计算机学院专业班级：学生姓名：学号：考试方式:闭卷题号-一-二二三四五总分签名分数、填空题（每空1分，共10分）的数据是（2）个，它们分别是（种别编码）和（自身值）。2语法分析程序是逐个识别（单词），形成语句级别的（单词）串。3遍扫描的编译方法，是以语法分析程序为主，调用（词法分析）程序、语义分析程序，再由语义程序调用中间代码生成、中间代码优化等。4程序设计语言的发展带来了日渐多变的运行时存储

2、管理方案，主要分为两大类，即（静态存储 分配 ）方案和（动态存储分配）方案。得分评卷人、综合题（共90 分）1. ( 5分)将下面文法改写成3型文法：G=( S,A,B ,a,b,c,d,e,P,S)其中：P=SabcA|edB,AbeB,B d答案：改写后的3型文法是(5分)G=( S,A,B,C,D,E,F ,a,b,c,d,e,P,S)其中：P=SaC|eF, C bD,DcA,AbE,EeB,FdB,B d2. ( 5分)给出下面表达式的四元式形式：a*b+(c-d)/e答案：四元式形式(5分)(* , a, b, t1 )(-,c, d, t2 )(/, t2 , e, t3 )(+

3、, t1 , t3 , t4 )3(30 分)给定文法 GE ：E t E+T | E-T | TT t T*F | T/F | FF t (E) | i该文法是 LL(1) 文法吗？为什么？不是的能否改造为LL( 1)文法，如果能够改造，给出改造后的文法，并给出改造后文法是LL (1 )文法的证明过程。无论改造前还是改造后的文法，如果是LL( 1)文法，则给出(i+i)*i的分析过程(要求给出详细过程，并给出LL( 1)的分析表)答案：( 1)该文法不是 LL( 1)文法，因为文法的产生式含有左递归( 2 分)(2)该文法可改造为 LL (1)文法，即消除左递归，改造后的文法是( 3 分)E

4、 t TE 'E' t +TE'| -TE '|£T t FT'T' t *FT '|/FT '| £F t (E) | i证明改造后的文法是 LL (1)文法的过程A.求可达£的非终结符可达的是 E' ,T'( 1 分)B.求每个非终结符的 First 集合First(E)= (,iFirst(E ' )=+,-First(T)= (,iFirst(T' )=*,/First(F)= (,i( 3 分)C.求每个产生式右部字符串的 First First(TE 

5、9; )= (,i First(+TE')=+First(-TE')=-First(FT ' )= (,i First(*FT')=*First(/FT')=/First(E)= ( First(i)= i First( £ )=£ 集合( 3 分)D.求每个非终结符的 Follow 集合 Follow(E)=$,)Follow(E ' )= Follow(E)=$,)( 3 分)Follow(T)=First(E' ) U Follow(E)=$,+,-,)Follow(T ' )= Follow(T)=$,

6、+,-,)Follow(F)= First(T' ) U Follow(T)=$,+,-, *,/,)E.求每个非终结符的 Select 集合Select(E t TE' )=First(TE ')= (,i ( 5 分)Select(E ' t +TE' )=First(+TE' )= + Select(E ' t -TE ' )=First(-TE' )= - Select(E'£ )=First( £ )-£ U Follow(E')= $,) Select(T FT &

7、#39; )=First(FT ' )= (,i Select(T'*FT ' )=First(*FT' )= * Select(T'/FT ' )=First(/FT' )= / Select(T'£ )=First( £ )-£ U Follow(T')= $,+,-,)Select(F (E)=First(E)= ( Select(F i)=First(TE ' )= i F.求有多个产生式的非终结符Select集合的交集(2分)显然有Select(E '宀 +TE

8、9;)n Select(E 't -TE ')n Select(E ' t £ )=Select(T '宀 *FT ')n Select(T 't /FT ')n Select(T ' t £)=Select(F 宀(E)=n Select(Fi)：= 所以改造后的文法是LL (1)文法（3）、根据E给出预测分析表（4分）非终 结符终结符+-*/()$Et TE't TE'E'T +TE't -TE'T £T £TT FT 'T FT'

9、T'T £T £t *FT 't *FT 'T £T £FT (E)t i符号串（i+i ） *i的分析过程（4分）步骤符号栈Si输入符号串产生式1$E(i+i)*i$Et TE'2$E' T(i+i)*i$Tt ft '3$E' T' F(i+i)*i$Ft( E)4$E' T') E (i+i)*i$E' T') Ei+i)*i$Et TE'$E' T') E' Ti+i)*i$Tt ft '$E' T

10、9;) E' T' Fi+i)*i$Ft i$E' T') E' T' ii+i)*i$E' T') E' T'+i)*i$T' T £$E' T') E'+i)*i$E' t +TE'$E' T') E' T+i)*i$E' T') E' Ti)*i$Tt ft'$E' T') E' T' Fi)*i$Ft i$E' T') E' T'

11、ii)*i$E' T') E' T')*i$T' T £$E' T') E')*i$E'T £$E' T')*i$E' T'*i$Tt *FT '$E' T' F*i$E' T' Fi$Ft i$E' T'$T't £$E'E' t £$4. （10分）对下面的 NFA进行确定化编译原理A卷答案 第7页，共9页答题：第1步：确定化过程（5分）第2步：确定化的 DFAy新状态

12、lxly0qO0q11q22 丁1q11q2,q332q22q1,q343q2,q33q3,q45q1,q344q1,q34q2,q3,q46q375q3,q45q3,q45q376q2,q3,q4 6q3,q45q1,q347q37q3,q45q375. （15分）给定文法GEE t E+T | E-T | TT t T*F | T/F | FF t （E） | ii+i ） *i的分析该文法是算符优先文法吗？是，则构造该文法的算符优先关系矩阵，并给出（ 过程（要求给出详细过程）答案：（1）该文法是算符优先文法（1分）（2）构造该文法的算符优先矩阵A.求各非终结符的FirstVT集合(3 分

13、)FirstVT(E)=FirstVT (T)=FirstVT (F)=： +,-,：* , / ,:(, i * , /, ( , i (,i B.求各非终结符的LasttVT集合(3 分)LastVT(E)= +*,-, ,/, ), i LastVT(T)= *,/,),i LastVT(F)=),i C.构造优先关系表（4分）+-*/()$+>><<<><>->><<<><>*>>>><><>/>>>><>&

14、lt;>(<<<<<=<)>>>>>>i>>>>>>$<<<<<<=分析（i+i ） *过程（4分）步骤符号栈S关系输入符号串最左素短语$<(i+i)*i$(<i+i)*i$(i>+i)*i$i$(V<+i)*i$(V+<i)*i$(V+i>)*i$i$(V+V>)*i$V+V$(V=)*i$(V)>*i$(V)$V<*i$V*<i$V*i<$i$V*V>$V*V$V=$6.

15、 （25分）给定文法GEE t E+T | TT t T*F | FF t (E) | i该文法是LR (0)文法吗？是，则构造该文法的 LR( 0)分析表，并给出(i+i ) *i的分析过 程，不是的，是 SLR( 1)文法吗，是，则构造该文法的 SLR( 1)分析表，并给出( i+i ) *i 的分 析过程。(要求给出详细过程)答案：( 1)拓广文法( 2 分)0、 E't E1、 EtE+T2、 EtT3、TtT*F4、 TtF5、Ft(E)6、 Fti2)构造LR( 0)项目集规范簇( 10分)(3) 在下图的DFA中，11、12、19均发生了规约一一移进冲突，所以该文法不是L

16、R ( 0)文法。( 2 分)(4) 在11规范项目集中规约项目E' tE.的Follow ( E') = $,而移进项目的移进符号 集= +, Follow ( E)A +=在 I2 规范项目集中规约项目 E tT. 的 Follow (E) =$，+，)，而移进项目的移进符号集=*, Follow ( E)A *=在 I9 规范项目集中规约项目 E tE+T. 的 Follow (E) =$，+，)，而移进项目的移进符号集=* , Follow ( E)A * =所以，在3个发生冲突的项目集中可解决冲突，因此该文法是 SLR( 1)文法(5分)编译原理 A 卷答案 第 6页

17、，共 9页1619+Et e+.tEt e+t.Tt .t*fTt t.*fTt .F14Ft .(E)(*15itFt .iI5(I3T t f.e JtA.(di14F t i.Tt .T*FTt .FFt .(E)Ft .i13Ft (.E)Et .E+tEt .t1I+18Ft (E.)Et E.+TFt .i111ft（ E）17Tt T*.FFt .(E)110Tt T*F.编译原理A卷答案 第9页，共9页(4分)(5)根据上面的 DFA建立SLR( 1 )的分析表状态Actio nGotoi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r4r4r44S5S48235r6r6r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r3r3r311r5r5r5r5r5r5(6)分析(i+i ) *i的过程(4 分)栈内容输入符