资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
编译原理试题3编译原理试题3课程测试试题(B卷)一、判断(15分)1 、编译程序是一种语言翻译程序,它将源语言程序翻译成功能等价的目标语言程序。2 、所谓规则或产生式是指形如a-或a:k3的(a,B)有序对,其中a是字母表V的正闭包元素,而3是字母表V的闭包元素。3 、设文法G=(VN,VT,P,S),若P中的每一个规则都是ZaB或Xa,其中A和B是非终结符,而a是终结符,则称此文法G为正规文法或3型文法。4 、实用文法中不得含有形如URU的有害规则,也不得含有由不可达或不可终止的非终结符所构成的多余规则。5 、对任意给定的一个正规式R,都可以将它转换为与之功能等价的正规文法,或与之功能等价的有穷自动机。6 、LEX是一个用于构造各种各样语言的词法分析程序;YACB一个用于构造各种各样语言的语法分析程序。7 、假设现有五元组表示的有穷自动机M=(K,V,F,S,Z),若M是NFA则S表示初态,且S具有唯一性,它是状态集K的一个元素。8 、算符优先分析方法和LR分析方法都是自下而上的分析方法,它们的分析过程实际上就是规范归约过程。9 、LR(0)项目集规范族中的项目由两部分构成,一部分是心,即原来的LR(1)项目,另一部分是向前搜索符号集。10 、所谓优化实质上是对代码进行等价变换,使得变换后的代码运行结果与变换前的代码运行结果相同,但运行速度或占用的存储空间加大。常用的优化技术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知变量与复写传播等。11 、对一个不包含空规则的算符文法,如果文法中的任意两个终结符构成的符号对之间最多只有大于、小于和等于三种优先关系中的一种成立,则称该算符文法为算符优先文法。12 、目标程序运行时的动态数据存储区分为堆区和栈区,它用于存放可变数据以及管理过程活动的控制信息。13 、在语法分析过程中,随着分析的步步进展,根据每个规则所对应的语义子程序或语义动作进行翻译的办法,称为语法制导翻译,它被现代很多编译程序所采用。14 、可归前缀本身就是活前缀,它是包含句柄在内的活前缀。15 、符号表用来存放语言程序中出现的有关标识符的属性信息,这些信息集中反映了标识符的语义特征属性。二、将表达式A:=B*(C-D)/D:(共9分)1、翻译成逆波兰式的中间代码形式。(2分)2、翻译成四元式的中间代码形式。(4分)3、将译成的四元式用DAGg示。(3分)三、现有文法GE:(共12分)1E+T|E-T|TTT*F|T/F|FFi|(E)4、证明:F+T*(E)是文法的一个句型。(3分)5、构造句型F+T*(E)的语法推导树。(3分)6、指出该句型所有短语、直接短语和句柄。(6分)四、给定正规式R=d(a|bc)*d,要求:(12分)1 、构造对应的NFAM犬态图,使得L(M尸L(R)。(4分)2、将所得NFAM确定化和最小化。(8分)五、现有文法GS:(共16分)S-S;D|DDD(T)|HHm|(S)TT*S|S2 、计算GS的FIRSTVT和LASTVT(4分)3 、构造GS的算符优先关系表,并说明GS是否为算符优先文法;分)4 、给出输入串(m*m)#的算符优先分析过程。(4分)4、根据分析过程总结算符优先分析方法的优缺点。(2分)六、已知GS:(18分)A(A)|a|bAA,S|S1 、给出(a,(b,b)的最左推导。(3分)2 、判断该文法是否为LL(1)文法。若是,直接给出它的预测分析表;若不是,先将其改写为LL(1)文法,再给出它的预测分析表;(10分)3 、给出输入串(b,b)#的分析过程,并说明该串是否为GS的句子。(5分)七、对给定文法GS:(共18分)0)S-S1)S-A2)S-B3)A-aAc4)A-a5)B-bBd6)Bb1、构造GS的LR(0)项目集规范族DFA并据此判断GS是否为LR(0)文法。(6分)2、进一步判断GS是否为SLR(1)文法,并给出对应的SLR分析表。(6分)3、给出输入串bbd#的SLR分析过程。(4分)4、判断GS是否为LR(1)文法和LALR(1)文法。(2分)编译原理课程测试试卷评分标准(数计学院03B卷)第一题:判断题(15分)1、共有15道小题,每小题1分,15X1=15分。第二题:(9分)1 、表达式A:=B*(C-D)/D的逆波兰式表示:ABCD-*D/:=。(2分)2、表达式A:=B*(C-D)/D的四元式表示:(4分)(1)(-,C,D,t1)(2)(*,B,t1,t2)(3)(/,t2,D,t3)(4)(k,t3一A)3、将译成的四元式用DAG表示:(3分)第三题:(12分)2 、证明(3分):因为存在推导序列E=E+T=T+T=F+T=F+T*F=F+T*(E),即有EF+T*(E)成立,所以,F+T*(E)是文法的一个句型。3 、语法树(3分)4 、句型分析(6分)句型F+T*(E)相对于E的短语有:F+T*(E),F。句型F+T*(E)相对于T的短语有:F,T*(E)。句型F+T*(E)相对于F的短语有:(E)。(3分)句型F+T*(E)相对于T-F的直接短语有:F。句型F+T*(E)相对于Ff(E)的直接短语有:(E)。(2分)句型F+T*(E)的句柄为:F。(1分)(2)短语每错两个扣1分。第四题:(12分)1、NFAM(4分)2、(1)确定化(4分)步骤如下表所示(可省):将集合T0至T3各用一个状态表示,确定化后所得DFAM如下:(2)最小化(4分)步骤如下表所示(可省):最后还有4个不可再分割的子集,每个子集中只包含一个状态,即原DFAM已经是最小化DFA。第五题:(16分)1 、对文法进行拓广,加入规则S-S后得GS,其非终结符的FIRSTVTLASTVT集计算如下:(4分)由FIRSTVTLASTVT集构造和A如下:2 、(1)优先关系表为:(4分)(2)该文法是算符优先文法(2分)。3 、(1)输入串(m*m)#的算符优先分析过程:(4分)(2由上述分析过程可知,用算符优先分析法分析在确定句柄时只考虑终结符之间的优先关系,而与非终结符无关,这使得算符优先分析法具有效率高的优点;但是,由于去掉了单非终结符之间的归约,有可能将错误的句子识别为正确的。上例中对输入串(m*m)#能分析成功,但(m*m)#并不是文法GS的句子。这就是算符优先分析法的缺点。第六题:(18分)1 、给出(a,(b,b)的最左推导:(3分)S=(A)=(A,S)=(S,S)=(a,S)=(a,(A)=(a,(A,S)=(a,(S,S)=(a,(b,S)=(a,(b,b)2 、(1)判断:(3分)计算各条规则的SELEC襟及左部相同规则的SELEC襟的交集如下:(2)将GS改写如下:(4分)GS:Aa|b|(A)Ar,SA|&ASA(2)预测分析表:(3分)第七题:(18分)1、(1)GS的LR(0)项目集规范族DFA(4分):(2)检查发现I4=Aa.,A.aAc,A.a和I5=Bb.,B.bBd,B.b中存在移进一归约冲突,所以,GS不是LR(0)文法。(2分)2、(1)在I4=A-a.,AfaAc,Afa中,由于根据归约项目A-a.所得的FOLLOW(A尸c,#中不含移进项目Af.aAc,或A7.a中的“a”。在构造LR分析表时,遇到移进项目AfaAc,或Af.a时,在“a”列置移进标记S4;遇到归约项目A-a.时,只在“c”,“#”两列置归约标记r4。所以,I4中的移进归约冲突通过引入FOLLOW集得到了解决。、同样,在I5=Bb.,B.bBd,B.b中,由于FOLLOW(B尸d,#中不含“b”。在构造LR分析表时,遇到移进项目BfbBd,B-.b时,在“b”列置移进标记S5;遇到归约项目B-b.时,只在“d”,“#两列置归约标记5。所以,I5中的移进-归约冲突通过引入FOLLOW!也得到了解决。故GS是SLR(1)文法。(3分)(2)SLR(1)分析表如下:(3分)3 LALR(1) SLR(1) LR(0)知:一个LR(0)文法肯定是SLR(1)文法;一个SLR(1)文法肯定是LALR(1)文法;而一个LALR(1)文法肯定是LR(1)文法。既然GS是SLR(1)文法,那么,它肯定也是LR(1)文法和LALR(1)文法。(2分)
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号