资源描述：
《编译原理(A卷)答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、湖北第二师范学院2014－2015学年度第二学期《编译原理》课程考试答案(A卷)院系：计算机学院专业班级：学生姓名：学号：考试方式：闭卷………………………………………………………………………………………………………………题号一二三四五总分签名分数得分评卷人一、填空题（每空1分，共10分）1．词法分析程序是逐个识别（字符），形成单词级别的（字符）串，词法分析程序输出的数据是（2）个，它们分别是（种别编码）和（自身值）。2．语法分析程序是逐个识别（单词），形成语句级别的（单词）串。3．一遍扫描的编译方法，是以语法分析程序为主，调用（
2、词法分析）程序、语义分析程序，再由语义程序调用中间代码生成、中间代码优化等。4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即（静态存储分配）方案和（动态存储分配）方案。得分评卷人二、综合题（共90分）1．（5分）将下面文法改写成3型文法：G=（｛S,A,B｝,{a,b,c,d,e},P,S）其中：P={S→abcA
3、edB,A→beB,B→d} 答案：改写后的3型文法是（5分）G=（｛S,A,B,C,D,E,F｝,{a,b,c,d,e},P,S）其中：P={S→aC
4、eF,C→bD,D→cA,A→bE
5、,E→eB,F→dB,B→d}2．（5分）给出下面表达式的四元式形式：a*b+(c-d)/e答案：四元式形式（5分）（*，a，b，t1）（-，c，d，t2）（/，t2，e，t3）（+，t1，t3，t4）《编译原理》A卷答案第9页，共9页3．（30分）给定文法G[E]： E→E+T
6、E-T
7、T T→T*F
8、T/F
9、F F→(E)
10、i 该文法是LL(1)文法吗？为什么？不是的能否改造为LL（1）文法，如果能够改造，给出改造后的文法，并给出改造后文法是LL（1）文法的证明过程。无论改造前还是改造后的文法，如果是LL（1）文法，
11、则给出（i+i）*i的分析过程（要求给出详细过程，并给出LL（1）的分析表）答案：（1）该文法不是LL（1）文法，因为文法的产生式含有左递归（2分）（2）该文法可改造为LL（1）文法，即消除左递归，改造后的文法是（3分） E→TE’E’→+TE’
12、-TE’
13、ε T→FT’T’→*FT’
14、/FT’
15、ε F→(E)
16、i证明改造后的文法是LL（1）文法的过程A.求可达ε的非终结符（1分）可达的是E’,T’B.求每个非终结符的First集合（3分）First(E)={(,i}First(E’)={+,-}First(T)={(,i
17、}First(T’)={*,/}First(F)={(,i}C.求每个产生式右部字符串的First集合（3分）First(TE’)={(,i}First(+TE’)={+}First(-TE’)={-}First(FT’)={(,i}First(*FT’)={*}First(/FT’)={/}First((E))={(}First(i)={i}First(ε)={ε}D.求每个非终结符的Follow集合（3分）Follow(E)={$,)}Follow(E’)=Follow(E)={$,)}Follow(T)=First(E’)
18、∪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’)={-}《编译原理》A卷答案第9页，共9页Select(E’→ε)=First(ε)-{ε}∪Follow(E’)={$,)}S
19、elect(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}A.求有多个产生式的非终结符Select集合的交集（2分）显然有Select(E’→+TE’)∩Select(E’→-TE’)∩Select(E’→ε)
20、=ΦSelect(T’→*FT’)∩Select(T’→/FT’)∩Select(T’→ε)=ΦSelect(F→(E))=∩Select(F→i)=Φ所以改造后的文法是LL（1）文法（3）、根据E给出预测分析表（4分）非终结符终结符+-*/()i$E→TE’→
