编译原理期末考试习题及答案

1一、填空题|（每题4分，共20分）1.乔母斯基定义的3型文法（线性文法）产生式形式ABa|a,或AaB|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|E+T(2)TF|F*F(3)F（E）|i（1）写出句型（T*F+i）的最右推到并画出语法树。（4分）（2）写出上述句型的短语，直接短语和句柄。（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|ε是二义的。（6分）答：句子aaa对应的两颗语法树为：因此，文法是二义文法2四.给定正规文法G（S）：(1)SSa|Ab|b(2)ASa请构造与之等价的DFA。（6分）答：对应的NFA为：（6分）状态转换表：ab{F}Φ{S}{S}{S,A}Φ{S,A}{S,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^|a|(T)(2)TT,S|S试：（1）消除文法的左递归；（4分）（2）构造相应的first和follow集合。（6分）答：（1）消除文法的左递归后文法G’（S）为：(1)S^|a|(T)(2)TST’|S3(3)T’,ST’|ε（4分）（2）（6分）firstfollowSa^(#,)Ta^()T’,ε)七.已知文法G(S):(1)SSiA|A(2)AA+B|B(3)BA*|（试构造非终止符的firstVT和lastVT集合。（10分）答：（10分）firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(八.已知文法G(S):(1)SBB(2)BaB(3)Bb的follow集合如表：试：（1）给出该文法的LR（0）项目集规范族划分；（2）填写相应的SLR（1）的分析表。（15分）答：（1）LR（0）项目集规范族划分(8分)(2)SLR(1)分析表（7分）状态ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2I0S’.SS.BBB.aBB.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.FollowS#Ba,b,#4九．设某语言的not-then-else语句的语法形式为：SnotEthenS1其语义解释为：针对自上而下的语法分析器，(1)分段产生式；（3分）(2)写出每个产生式对应的语义动作。（7分）答：（1）分段产生式（3分）及语义动作(7分)(1)RnotEthen{Backpatch（$2.FC，nxq）;$$.chain=$2.Tc}(2)SRS1{Backpatch（$2.chain，nxq）}一、填空题|（每题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+:=__。5、常用的两种动态存贮分配办法是__栈式存储分配和堆式存储__分配。二．已知文法G(S):(1)S^|a|(T)(2)TT,S|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分）5（3）（4分）短语：（a,(a,a)），a,(a,a)，(a,a)，a,a,a直接短语：a句柄：a三．证明文法G(S)：SaSb|Sb|b是二义的。（6分）答：句子aabbbb对应的两颗语法树为：因此，文法是二义文法四.给定正规文法G（S）：(1)SaA(2)AaB|bA（3）BaA|b请构造与之等价的DFA。（6分）答：对应的DFA为：（6分）五.构造识别正规语言(ab*|a)*最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分）6（2）将（1）所得的NFA确定化：（5分）ab{1}{1,2}Φ{1,2}{1,2}{1,2}（5分）六.已知文法G(S):(1)S^|a|(T)(2)TST’|S(3)T’,ST’|ε试：求first和follow集合，构造改文法的LL（1）分析表。（10分）答：文法相应的first和follow集合（5分）firstfollowSa^(#,)Ta^()T’,ε)其LL（1）分析表如下：七.已知文法G(S):7(1)SSiA|A(2)AA+B|B(3)BA*|（非终止符的firstVT和lastVT集合如下:firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(试构造算符的优先关系表。（10分）答：i+()*I+()*八已知文法G(S):(1)Sa|aAb|b|bBa(2)A1A0|ε(3)B1B0|ε求：该文法的LR（0）项目集规范族。（15分）答：九．设某语言的DO-while语句的语法形式为：SdoS1whileE其语义解释为：8针对自上而下的语法分析器，(1)分段产生式；（3分）(2)写出每个产生式对应的语义动作。（7分）答：（1）分段产生式（3分）G(S):(1)Rdo(2)URS1while(3)SUE(2)产生式对应的语义动作(7分)(1)Rdo{$$.loop=nxq}(2)URS1while{$$.loop=$1.loop}(3)SUE{backpatch（$2.FC，$1.loop）；Backpatch（$2.TC，nxq）}