编译原理(B卷)答案解析.doc

湖北第二师范学院2014－2015学年度第二学期 《编译原理》课程考试答案(B卷) 院 系： 计算机学院 专业班级： 学生姓名： 学 号： 考试方式 ： 闭卷 ……………………………………………………………………………………………………………… 题号 一 二 三 四 五 总分 签名 分数 得分 评卷人 一、填空题（每空1分，共10分） 1．，。 2．。．｝ 3．（30分）给定文法 G[E] ： 　　E → E+T | T 　　T → T*F | F 　　F → (E) | i 　　该文法是 LL(1) 文法吗？为什么？不是的能否改造为LL（1）文法，如果能够改造，给出改造后的文法，并给出改造后文法是LL（1）文法的证明过程。无论改造前还是改造后的文法，如果是LL（1）文法，则给出（i+i） 答案：（1）该文法不是LL（1）文法，因为文法的产生式含有左递归 （2分） （2）该文法可改造为LL（1）文法，即消除左递归，改造后的文法是 （3分） 　　E → TE’ E’ → +TE’ | ε 　　 T → FT’ T’ → *FT’ |ε 　　F → (E) | i 证明改造后的文法是LL（1）文法的过程 求可达ε的非终结符 （1分） 可达的是E’,T’ 求每个非终结符的First集合 （3分） First(E)={ (,i} First(E’)={+} First(T)={ (,i} First(T’)={*} First(F)={ (,i} 求每个产生式右部字符串的First集合 （3分） First(TE’)={ (,i} First(+TE’)={+} First(FT’)={ (,i} First(*FT’)={*} First((E))={ ( } First(i)={ i } First(ε)={ ε} 求每个非终结符的Follow集合 （3分） Follow(E)={$,)} Follow(E’)= Follow(E)={$,)} Follow(T)=First(E’) ∪ Follow(E)={$,+,)} Follow(T’)= Follow(T)={$,+,)} Follow(F)= First(T’) ∪ Follow(T)={$,+, *,)} 求每个非终结符的Select集合 （5分） Select(E → TE’)=First(TE’)={ (,i } Select(E’ → +TE’)=First(+TE’)={ + } Select(E’ →ε)=First(ε)-{ ε} ∪ Follow(E’)={ $,) } Select(T → FT’)=First(FT’)={ (,i } Select(T’ → *FT’)=First(*FT’)={ * } Select(T’ →ε)=First(ε)-{ ε} ∪ Follow(T’)={ $,+,) } Select(F → (E))=First((E))={ ( } Select(F → i)=First(TE’)={ i } 求有多个产生式的非终结符Select集合的交集 （2分） 显然有 Select(E’ → +TE’) ∩Select(E’ →ε)=Φ Select(T’ → *FT’) ∩Select(T’ →ε)= Φ Select(F → (E))= ∩Select(F → i)= Φ 所以改造后的文法是LL（1）文法 （3）、根据E给出预测分析表 （4分） 非终结符 终结符 + * ( ) i $ E →TE’ →TE’ E’ →+TE’ →ε →ε T → FT’ →FT’ T’ →ε → *FT’ →ε →ε F →(E) →i 符号串（i+i）’ 2 $E’T (i+i)*i$ T→ FT’ 3 $E’T’F (i+i)*i$ F→（E） 4 $E’T’）E（ (i+i)*i$ $E’T’）E i+i)*i$ E→TE’ $E’