编译原理答案解析

1、湖北第二师范学院2014-2015学年度第二学期编译原理课程考试答案（B卷）院 系：计算机学院学生姓名：考试方式:闭卷专业班级： 学 号： 得分评卷人题号-二三四五总分签名分数一.填空题（每空1分，共10分）1. 从编译系统的方式看，有两种编译方式，一种是（解释 ）方式，另一种是（编译 ）。2. 编译的过程一般讲，有（词法分析 ）,（语法分析）,（语义分析），（中间代码生成），（中间代码优化）和（目标代码生成）。3. 程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即（静态存储分配 ）方案和（动态存储分配）方案。得分评卷人二、综合题（共90分）1. （5分）构造语言a3n

2、|nl的文法答案：苴文法是（5分）P （A）： A-*aaa aaaA2. （5分）给出下面表达式的逆波兰表示：a*b+（cd）/e答案：ab*cde/+（5 分）3. （30分）给左文法GE:E - E+T TT - T*F FF - （E） | i该文法是LL（1）文法吗？为什么？不是的能否改造为LL （1）文法，如果能够改造，给岀改 造后的文法，并给出改造后文法是LL （1）文法的证明过程。无论改造前还是改造后的文法，如果 是LL （1）文法，则给出（i+i） *i的分析过程（要求给出详细过程，并给出LL （1）的分析表） 答案：（1）该文法不是LL （1）文法，因为文法的产生式含有左递

3、归（2分）（2）该文法可改造为LL （1）文法，即消除左递归，改造后的文法是（3分）E _ TE，E' - +TE' £T _ FT， 一 *FT £F - （E） i证明改造后的文法是LL （1）文法的过程A.求可达£的非终结符 可达的是E' ,T'（1分）B.求每个非终结符的First集合 First (E) = (, iFirst (Ef ) = +First (T) = (, iFirst (Tf ) = *First (F) = (, i（3分）C.求每个产生式右部字符串的First集合First (TE ) = (, i

4、First (+TE, ) = +First (FTJ ) = (, iFirst (*FT, ) = *First(E)= ( First (i) = i First ( e ) = £ （3分）D.求每个非终结符的Follow集合Fol low (E) = $,)Fol low (E )= Follow (E) = $,)（3分）Follow(T)=First(E, ) U Follow(E) = $,+,)Follow(T' )= Follow(T)=$,+,)Follow(F)= First(T, ) U Follow(T) = $,+, *,)E.求每个非终结符的S

5、elect集合（5分）Select (E » TE )=First(TE, )=Ci Select(E*-+TE' ) hirst (+TE)= +Select(E*f £ )=First( e )- e ，U Follow(E, ) = $,) Select(T - FT )=First(FT, ) = Ci Select(T*-*FT, )=First(*FTr)= *Select(T 一 £ )二First仁)- e U Follow(T, ) = $,+,) Select(F 一 (E)=First(E)= ( Select(F 一 i)二Firs

6、t(TE )= i F.求有多个产生式的非终结符Select集合的交集(2分)显然有Select(E - +TE' ) nSelect(Ef - £)二0>Select(T - *FV ) ASelect(T, - £)二Select(F - (E)= nSelect(F - i)=所以改造后的文法是LL (1)文法(3)、根据E给出预测分析表(4分)非终 结符终结符+()1sE_TE'_TEE，-+TE'f E-* eT-* FT'T，f *FTf E-* eF-(E)f 1符号串(i+i) *i的分析过程(4分)步骤符号栈Si输入符

7、号串产生式1SE(i+i)*i$E TE，2SE' T(i+i)*i$T- FT'3SE'F(i+i)*i$F- (E)4SE， T ) E (i+i)*i$SE， T ) Ei+i)*i$E_TE，SE' r ) E Ti+i)*i$T- FT't ) e T Fi+i)*i$F-iSE' T ) E T ii+i)*i$SE' T ) E T+i)*iST* £SE， r ) E+i)*iSE' -+TE'SE' T ) E T+i)*iSSE' T ) E Ti)*iST_FVt ) E V

8、 Fi)*iSF-iSE， r ) e T ii)*iSSE， t ) E T)*i$T* -* eSE， V ) E)*i$E* _ eSE')*i$SE' V*i$T- *FTSE' V F*i$SE'Fi$F-iSE，$T' -* £SE，E* -* £S4. （10分）对下面的DFA进行最简化答题：第1步：确左化过程（5分）将7个状态分成两个状态集,终态集q5, q6,非终态集q0, ql, q2, q3, q4, q7分割前状态集lxIy分割后状态集IqO, ql, q2, q3, q4, q7ql, q3q5, q6q0,

9、 ql, q2, q3, q4, q7q0, qlqO, ql, lq3, q4, q7Jq0, qllq3, q4, q7qo, q6q3, q4, q7Eq3, q4, q7qo, q6q5, q6q3, q4, q7q5, q6根据上表命名不可分割的终态集，及到达状态分割前状态集lxIyq00ql1q22ql1lq3, q4, q7J3q22q3, q4, q73lq3, q4, q73lq5, q64q3, q4, q73lq5, q64lq5, q64q3, q4, q735. （15分）给定文法GE：T - T*FF - (E)该文法是算符优先文法吗？是，则构造该文法的算符优先关系

10、矩阵，并给出（i+i）心的分析 过程（要求给出详细过程）答案：（1）该文法是算符优先文法（1分）（2）构造该文法的算符优先矩阵扎 求各非终结符的FirstVT集合（3分）FirstVT （E）二+,*,（, iFirstVT （T）二*, （, iFirstVT （F） = （, iB.求各非终结符的LasttVT集合(3分)LastVT(E) = +, *, ), i LastVT(T) = LastVT(F) = ), i C.构造优先关系表（4分）()1S-><<><>*>><><>(<<<二<

11、;)>>>>1>>>>S<<<<二（3）分析（i+i） *过程（4分）步骤符号栈S关系输入符号串最左素短语$<(i+i)*iS$(<i+i)*iS$(i>+i)*i$1$(V<+i)*i$(V+<i)*i$ (V+i>)*i$1$(v+v>)*i$v+v$(V二)*i$(V)>*i$(V)$v<*i$v-<i$V*i<$1$v*v>$v*v$v二s6. (25分)给左文法GE:E - E+T TT - T*F FF - (E) | i该文法是LR (0

12、)文法吗？是，则构造该文法的LR (0)分析表，并给岀(i+i) *i的分析过 程，不是的，是SLR (1)文法吗，是，则构造该文法的SLR (1)分析表，并给出(i+i) *i的分 析过程。(要求给出详细过程)答案：(1)拓广文法(2分)0、E'-E1、E-E+T2、E-T3、T-T*F4. T-F5、F-(E)6、F f 1(2) 构造LR (0)项目集规范簇(10分)(3) 在下图的DFA中，II、12、19均发生了规约一一移进冲突，所以该文法不是LR (0)文法。(2分)(4) 在II规范项目集中规约项目E' -E.的Follow (E')二$,而移进项目的移进

13、符号 集二 + , Follow (E) C + 二在12规范项目集中规约项目E -T.的Follow (E) = $, +,),而移进项目的移进符号集二 *, Follow (E) n * = 0)在19规范项目集中规约项目E -E+T.的Follow (E) = $, +,),而移进项目的移进符号集 =*, Follow (E) A * = 0)所以，在3个发生冲突的项目集中可解决冲突，因此该文法是SLR(1)文法(5分)10EIIE' f.EE，_EE-.E+TE-E +TE-.TT-T*FT-FT12Ff (E)E7F-iT-*T. *FT16E-E+ TT-.T*FT-.FF

14、-(E)Fi19131415FE-E+T.T7 *F7+.1E-E. +TT-T*F13T -F.18F- (E.)TT* FF-(E)14F- (. E)E-E+TE_TT_T*FT 一F F-(E)110IllF一 (E).状态ActionGoto1+*()$ETF0S5SI1231S6acc2r2S7r2r23rlr 1rlrlrlrl4S5SiS235r6r6r6r6r6r66S5Si937S5Si108S6SU9rlS7rlrl10r3r3r3r3r3r311r5r5r5ror5r5（5）根据上面的DFA建立SLR （1）的分析表（4分）（6）分析（i+i）相的过程（4分）栈内容输入符号串动作0(i+i) *i$移进0(4ii) *i$移