资源描述：
《编译原理期末考试习题集与答案解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、填空题
2、（每题4分，共20分）1.乔母斯基定义的3型文法（线性文法）产生式形式AàBa
3、a,或AàaB
4、a，A，B∈Vn,a,b∈Vt。2.语法分析程序的输入是单词符号，其输出是语法单位。3型为Bà.aB的LR（0）项目被称为移进项目，型为Bàa.B的LR（0）项目被称为待约项目，4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。二.已知文法G(S)(1)EàT
5、E+T(2)TàF
6、F*F(3)Fà（E）
7、i（1）写出句型（T*F+i）的最右推到并画出语法树。（4分）（2）写出上述句型
8、的短语，直接短语和句柄。（4分）答：（1）最右推到（2分）E==>T==>F==>(E)==>(E+T)==>(E+F)==>(E+i)==>(T+i)==>(T*F+i)(2)语法树（2分）（3）（4分）短语：（T*F+i），T*F+i，T*F，i直接短语：T*F，i句柄：T*F三.证明文法G(S)：SàSaS
9、ε是二义的。（6分）答：句子aaa对应的两颗语法树为：因此，文法是二义文法四.给定正规文法G（S）：(1)SàSa
10、Ab
11、b(2)AàSa请构造与之等价的DFA。（6分）答：对应的NFA为：（6分）状态转换表：ab{F}Φ{S}{S}{S,A}Φ{S,A}{S
12、,A}{S}五.构造识别正规语言b*a(bb*a)*b*最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分）（2）将（1）所得的NFA确定化：（5分）ab{0}{1，3}{0}{1,3}Φ{2，3}{2,3}{1,3}{2,3}（5分）六.已知文法 G(S):(1)Sà^
13、a
14、(T)(2)TàT,S
15、S试：（1）消除文法的左递归；（4分）（2）构造相应的first和follow集合。（6分）答：（1）消除文法的左递归后文法G’（S）为：(1)Sà^
16、a
17、(T)(2)TàST’
18、S(3)T’à,ST’
19、ε（4分）（2）（6分）firstfollowS
20、a^(#,)Ta^()T’,ε)七.已知文法 G(S):(1)SàSiA
21、A(2)AàA+B
22、B(3)BàA*
23、（试构造非终止符的firstVT和lastVT集合。（10分）答：（10分）firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(FollowS#Ba,b,#八.已知文法 G(S):(1)SàBB(2)BàaB(3)Bàb的follow集合如表：试：（1）给出该文法的LR（0）项目集规范族划分；（2）填写相应的SLR（1）的分析表。（15分）答：（1）LR（0）项目集规范族划分(8分)I0S’à.SSà.BBBà.aBBà
24、.b---àI1---àI2--àI3--àI4SBabI1S’àS.I2SàB.BBà.aBBà.b---àI5--àI3--àI4BabI3Bàa.BBà.aBBà.b---àI6--àI3--àI4BabI4Bàb.I5SàBB.I6BàaB.(2)SLR(1)分析表（7分）状态ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九．设某语言的not-then-else语句的语法形式为：SànotEthenS1其语义解释为：针对自上而下的语法分析器，(1)分段产生式；（3分）(2)写出每个产生式对应的语义动
25、作。（7分）答：（1）分段产生式（3分）及语义动作(7分)(1)RànotEthen{Backpatch（$2.FC，nxq）;$$.chain=$2.Tc}(2)SàRS1{Backpatch（$2.chain，nxq）}一、填空题
26、（每题4分，共20分）1.乔母斯基定义的2型文法（上下文无关文法）产生式形式Aàβ,A∈Vn,β∈V+。2.词法分析程序的输入是字符串，其输出是单词符号。3算符有限分析方法每次都是对最左素短语进行规约。型为BàaB.的LR（0）项目被称为规约项目。4、写出x:=b*(d-e)/(c-d)+e的逆波兰式__xbde-*cd-/e+:=__。
27、5、常用的两种动态存贮分配办法是__栈式存储分配和堆式存储__分配。二．已知文法 G(S):(1)Sà^
28、a
29、(T)(2)TàT,S
30、S试：（1）写出句型（a,(a,a))的最左推到并画出语法树。（4分）（2）写出上述句子的短语，直接短语和句柄。（4分）答：（1）最左推到（2分）S==>（T）==>（T,S）==>(S,S)==>(a,S)==>(a,(T))==>(a,(T,S))==>(a,（S,S))==>(a,（a,S))==>(a,（a,a))(2)语法树（2分）（3）（4分）短语：（a,(a,a)），a,(a,a)，(a,a)
