您好,欢迎访问三七文档
当前位置:首页 > 高等教育 > 习题/试题 > 编译原理期末考试习题及答案
1一、填空题|(每题4分,共20分)1.乔母斯基定义的3型文法(线性文法)产生式形式ABa|a,或AaB|a,A,B∈Vn,a,b∈Vt。2.语法分析程序的输入是单词符号,其输出是语法单位。3型为B.aB的LR(0)项目被称为移进项目,型为Ba.B的LR(0)项目被称为待约项目,4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。二.已知文法G(S)(1)ET|E+T(2)TF|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):SSaS|ε是二义的。(6分)答:句子aaa对应的两颗语法树为:因此,文法是二义文法2四.给定正规文法G(S):(1)SSa|Ab|b(2)ASa请构造与之等价的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)TT,S|S试:(1)消除文法的左递归;(4分)(2)构造相应的first和follow集合。(6分)答:(1)消除文法的左递归后文法G’(S)为:(1)S^|a|(T)(2)TST’|S3(3)T’,ST’|ε(4分)(2)(6分)firstfollowSa^(#,)Ta^()T’,ε)七.已知文法G(S):(1)SSiA|A(2)AA+B|B(3)BA*|(试构造非终止符的firstVT和lastVT集合。(10分)答:(10分)firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(八.已知文法G(S):(1)SBB(2)BaB(3)Bb的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.I2SB.BB.aBB.b---I5--I3--I4BabI3Ba.BB.aBB.b---I6--I3--I4BabI4Bb.I5SBB.I6BaB.FollowS#Ba,b,#4九.设某语言的not-then-else语句的语法形式为:SnotEthenS1其语义解释为:针对自上而下的语法分析器,(1)分段产生式;(3分)(2)写出每个产生式对应的语义动作。(7分)答:(1)分段产生式(3分)及语义动作(7分)(1)RnotEthen{Backpatch($2.FC,nxq);$$.chain=$2.Tc}(2)SRS1{Backpatch($2.chain,nxq)}一、填空题|(每题4分,共20分)1.乔母斯基定义的2型文法(上下文无关文法)产生式形式Aβ,A∈Vn,β∈V+。2.词法分析程序的输入是字符串,其输出是单词符号。3算符有限分析方法每次都是对最左素短语进行规约。型为BaB.的LR(0)项目被称为规约项目。4、写出x:=b*(d-e)/(c-d)+e的逆波兰式__xbde-*cd-/e+:=__。5、常用的两种动态存贮分配办法是__栈式存储分配和堆式存储__分配。二.已知文法G(S):(1)S^|a|(T)(2)TT,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):SaSb|Sb|b是二义的。(6分)答:句子aabbbb对应的两颗语法树为:因此,文法是二义文法四.给定正规文法G(S):(1)SaA(2)AaB|bA(3)BaA|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)TST’|S(3)T’,ST’|ε试:求first和follow集合,构造改文法的LL(1)分析表。(10分)答:文法相应的first和follow集合(5分)firstfollowSa^(#,)Ta^()T’,ε)其LL(1)分析表如下:七.已知文法G(S):7(1)SSiA|A(2)AA+B|B(3)BA*|(非终止符的firstVT和lastVT集合如下:firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(试构造算符的优先关系表。(10分)答:i+()*I+()*八已知文法G(S):(1)Sa|aAb|b|bBa(2)A1A0|ε(3)B1B0|ε求:该文法的LR(0)项目集规范族。(15分)答:九.设某语言的DO-while语句的语法形式为:SdoS1whileE其语义解释为:8针对自上而下的语法分析器,(1)分段产生式;(3分)(2)写出每个产生式对应的语义动作。(7分)答:(1)分段产生式(3分)G(S):(1)Rdo(2)URS1while(3)SUE(2)产生式对应的语义动作(7分)(1)Rdo{$$.loop=nxq}(2)URS1while{$$.loop=$1.loop}(3)SUE{backpatch($2.FC,$1.loop);Backpatch($2.TC,nxq)}
本文标题:编译原理期末考试习题及答案
链接地址:https://www.777doc.com/doc-5368827 .html