编译原理期末考试试卷及答案

期末考试试卷 （A）卷一、填空题（每小题2分，共20分）1、字母表，用* 表示上所有有穷长的串集合，*称为的 。2、设z=abc，则z的固有头是 。3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫 。4、设a,b， 上的正规式(a|b)(a|b) 相应的正规集为 5、NFA的映象f是从状态字映射到状态子集，f为 值函数。6、LR分析是按规范句型的 为可归约串。7、结点的 属性值由该结点的兄弟结点和父结点的属性值计算。8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算 。9、对于栈式符号表，引入一个显示嵌套层次关系表- 表，该表总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。10、任一有向边序列n1 n2,n2 n3,nk-1 nk为从结点n1到结点nk的一条通路。如果n1=nk，则称该通路为 。二、单项选择（每小题2分，共14分）1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。其中3型文法也称为（ ）。 A上下无关文法 B.正规文法 C上下文有关文法 D.无限制文法2、生成非0开头的正偶数集的文法是（ ）。 A Z:=ABC B. Z:=ABC C:=0|2|4|6|8 C:=0|2|4|6|8 B:=BA|B0| B:=BA|B0|0 A:=1|2|3|9 A:=1|2|3|9 C. Z:=ABC|2|4|6|8 D. Z:=ABC|2|4|6|8 C:=0|2|4|6|8 C:=0|2|4|6|8 B:=BA|B0|0 B:=BA|B0| A:=1|2|3|9 A:=1|2|3|93、简单优先分析法从左到右扫描输入串,当栈顶出现（ ）时进归约。A.素短语 B.直接短语 C.句柄 D.最左素短语4、同心集合并有可能产生新的（ ）冲突。 A.归约 B.移进移进 C.移进归约 D.归约归约5、在编译中，动态存储分配的含义是（ ）。A在运行阶段对源程序中的量进行存储分配B. 在编译阶段对源程序中的量进行存储分配C. 在说明阶段对源程序中的量进行存储分配D. 以上都不正确6、活动记录中的连接数据不包含（ ）。 A.老SP B.返回地址 C.全局DISPLAY地址 D形式单元7、有一语法制导翻译如下：SbAb printer(“1”)A(B printer(“2”)Aa printer(“3”)BAa) printer(“4”)若输入序列为b(aa)a)a)b，且采用自下而上的分析法，则输出序列为( )。A B C D三、写出条件语句 IF a0 THEN x:=x+1 ELSE x:=4*( x- 1) 的四元式序列（6分）四、设有基本块 （8分）B1： B:=3 D:=A+C E:=A*C F:=D+E G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L (1) 画出DAG图； (2) 假设只有L在基本块后被引用，请写出优化后的四元序列。 五、将下图DFA最小化，并写出最小化后DFA的正规式。（10分）cbba631dbadbca5bb742六、对下面的文法进行改写，并判断改写后是否是LL（1）文法。（15分）S Aa|bA SBB ab七、已知文法:SS；G|GGG（T）|HHa|(S)TT+S|S求句型#a;(T+S);H;(S)#短语、句柄、素短语、最左素短语（12分）八、【注意】计算机061/062班和计教061/062请做第1、2题，计算机063（海外班）请做第3题，做错题得0分。（15分）【计算机061/062班和计教061/062班做】1、给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。（5分）GS为： (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F a2、文法GM及其LR分析表如下，请给出对串dbba#的分析过程。（10分）GM: 1) M VbA 2) V d 3) V 4) A a 5) A Aba 6) A ACTIONGOTObda#MAV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5【计算机063海外班做】3、判断下列各题所示是否为LR类文法，若是请说明是LR(0)，SLR(1)，LALR(1)或LR(1)的哪一种，并构造相应分析表。（15分） SaAdeBdaBreAr Aa Ba答案：一、填空题（每空2分，共20分）1、 闭包 2、 ， a， ab 3、 语法 4、 aa，bb,ab,ba 5、 多 6、 句柄 7、 继承 8、 之后 9、 DISPLAY 10、 环路 二、单项选择（每小题2分，共14分）题号1234567答案BDCDADB三、写出条件语句 IF a0 THEN x:=x+1 ELSE x:=4*( x- 1) 的四元式序列（6分）解： (j,a ,0 , ) 评分标准：标号对给1分， (j, , , ) 四元式格式对给1分， (+,x ,1 ,T1) 每2条四元式序列对给1分。 (:= ,T1, , T2 ) (j , , , ) (- ,x, 1,T3) (*,4,T3, T4 ) (:= ,T4 , , x)四、 设有基本块 （8分）(1) 画出DAG图； (2) 假设只有L在基本块后被引用，请写出优化后的四元序列。评分标准：DAG图正确给4分，代码每条1分。解：（1）对于B1其DAG图：L,Mn1n9n3n4n2n7n6n5n8153KBAC+G*+F,JD,HE,I+*若只有L活跃，则代码为D:=A+C E:=A*C F:=D+E L:=F+15五、将下图DFA最小化，并写出最小化后DFA的正规式。（10分）解：P0=(6,7,1,2,3,4,5)P0=(6,7,1,2，3,4,5) 输入b进入不同状态。P0=(6,7,1,2，3,4,5) 3，4对d有定义，5没有定义最小化DFA如下： bcbba631da5正规式为：b*a(c|da)*bb* 评分标准：划分状态集过程给3分，图对得5分，图部分对根据对的多少给2-4分，正规上式对给2分。六、对下面的文法进行改写，并判断改写后是否是LL（1）文法。（15分）S Aa|bA SBB ab【解法1】 first(S)=b first(A)=b first(B)=a follow(S)=#,a follow(A)=a follow(B)=aselect(SAS)=first(AS)=b select(Sb)=first(b)=bselect(SAS)select(Sb)=b所以该文法不是LL（1）文法改写为： S Aa|b S SBa|bA SB A SBB ab B ab消除左递归： S bS 化简得： S b SS Ba S| S Ba S|A SB (多余) B abB abfirst(S)=b first(S)=a, first(B)=afollow(S)=# follow(S)=# follow(B)=aselect(SbS)=first(bS) =b select(SBaS)=first(BaS)=a select(S)=first()Ufollow(S)=#, select(SBaS)select(S)=所以改写后是LL(1)文法。评分标准：改写前判断LL（1）全对4分，改写正确4分，改写后判断LL（1）正确得6分，最后结论1分。【解法2】 first(S)=b first(A)=b first(B)=a follow(S)=#,a follow(A)=a follow(B)=aselect(SAS)=first(AS)=b select(Sb)=first(b)=bselect(SAS)select(Sb)=b所以该文法不是LL（1）文法用S的产生式右部代替A的产生式右部的S得： SAa|b AAaB|bBBab 消除左递归后文法变为： 0) SA a 1) Sb 2) Ab B N3) Na B N 4) N 5) Ba b非终结符 FIRST集 FOLLOW集 S b # A b a B a a N a, aSELECT(SA a)SELECT(Sb) = b b = b SELECT(Na B N)SELECT(N) = a a = a 所以文法不是LL(1)的。评分标准：改写前判断LL（1）全对4分，改写正确4分，改写后判断LL（1）正确得6分，最后结论1分。七、已知文法:SS；G|GGG（T）|HHa|(S)TT+S|S求句型#a;(T+S);H;(S)#短语、句柄、素短语、最左素短语（12分）解：语法图见下图短语有：a 相对非终结符 H、G 短语T+S 相对非终结符 T短语H 相对非终结符 G短语(S) 相对非终结符 H、G短语a(T+S) 相对非终结符 G短语a(T+S);H 相对非终结符 S短语a(T+S);H;(S) 相对非终结符 S短语句柄是 a素短语 a，T+S，（S）最左素短语 aSS；GS；GHGH（S）G（T）HT+Sa评分标准：语法图正确4分，短语正确5分，句柄正确1分，素短语正确1分，最左素短语正确1分。八、1、给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。（5分）GS为： (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F a解：I0：SE ， # E E+T ， #,+ E T ， #,+ T T*F ， #,+,* T F ， #,+,* F (E) ， #,+,* F a ， #,+,* 评分标准：前4条项目，每条0.5分，后面3条下面。每条1分2、文法GM及其LR分析表如下，请给出对串dbba#的分析过程。（10分）GM: 1) M VbA 2) V d 3) V 4) A a 5) A Aba 6) A 解：对串dbba#的分析过程如下表对输入串dbba#的分析过程步骤状态栈文法符号栈剩余输入符号动作12345678900302024024602467024601#d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a#移进用V d归约移进用A 归约移进移进用A Aba 归约用M VbA 归约接受评分标准：每条1分，格式1分。3、判断下列各题所示是否为LR类文法，若是请说明是LR(0)，SLR(1)，LALR(1)或LR(1)的哪一种，并构造相应分析表。（15分） SaAdeBdaBreAr Aa Ba解：LR(0)项目集规范族如图：I0：SSSaAdSeBdSaBrSeArI2：SaAdSaBrAaBaI1：SSI3：SeBdSeArAaBaI4：SaAdI5：SaBrI6：AaBaSaeABa在状态I6中有“规约-规约”冲突，且Follow(A)=follow(B)=d,r故不是LR(0)和SLR(1)。文法LR(1)项目集规范族如下：I0：SS ，#SaAd ，#SeBd ，#SaBr ，#SeAr ，#I2：SaAd ，#SaBr ，#Aa ，dBa ,rI1：SS ，#I3：SeBd ,#SeAr ,#Aa ,rBa ,dI4：SaAd ,#I5：SaBr ,#I6：Aa ,dBa ,rSaeABaI7：Aa ,rBa ,dI8：SeBd ,#I9：SeAr ,#I10：SaAd ,#I11：SaBr ,#I12：SeBd ,#I13：SeAr ,#