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

《编译原理期末考试试卷及答案2.pdf》由会员分享，可在线阅读，更多相关《编译原理期末考试试卷及答案2.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、期末考试试卷（A）卷一、填空题（每小题2 分，共 2 0 分）1、字母表,用X*表示X 上所有有穷长的串集合，*称为的 。2、设 z=a b c，则 z的固有头是 o3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫 O4、设 2=缶,同，Z上的正规式（a|b）（a|b）相应的正规集为 5、N F A 的映象f 是从 状态X 字 映射至 状态子集，f为 值函数。6、LR 分析是按规范句型的 为可归约串。7、结点的 属性值由该结点的兄弟结点和父结点的属性值计算。8、如果分析树中一结点的属性b 依赖于属性c,那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算 。

2、9、对于栈式符号表，引入一个显示嵌套层次关系表-表，该表总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。1 0、任一有向边序列n l-n 2,n 2 -n 3,，n kT f n k为从结点n l到结点n k的一条通路。如果n l=n k,则称该通路为 。二、单项选择（每小题2 分，共 1 4分）1、乔姆斯基把文法分成4 种类型，即。型、1 型、2型和3 型。其中3 型文法也称为（）oA.上下无关文法B.正规文法C.上下文有关文法D.无限制文法2、生成非0 开头的正偶数集的文法是（)oA.Z:=A B C B.Z:=A B CC:=0|2|4|6|8C:=0|2|4|6|8

3、B:=B A|B O|eB:=B A|B O|OA:=1|2|3|-|9A:=1|2|3|-|9C.Z:=A B C|2|4|6|8 D.Z:=A B C|2|4|6|8C:=0|2|4|6|8C:=0|2|4|6|8B:=B A|B 0|0B:=B A|B O|eA:=1|2|3|-|9 A:=1|2|3|-|93、简单优先分析法从左到右扫描输入串，当栈顶出现()时进归约。A.素短语 B.直接短语 C.句柄 D.最左素短语4、同心集合并有可能产生新的()冲突。A.归约 B.移进/移进 C.移进/归约 D.归约/归约5、在编译中，动态存储分配的含义是()。A.在运行阶段对源程序中的量进行存储分

4、配B.在编译阶段对源程序中的量进行存储分配C.在说明阶段对源程序中的量进行存储分配D.以上都不正确6、活动记录中的连接数据不包含()。A.老 S P B.返回地址 C.全局DI S P L AY地址 D 形式单元7、有一语法制导翻译如下：S-bAb prin ter(1 )A-(B prin ter(a2f,)A-a prin ter(3 )B-*Aa)prin ter(4 )若输入序列为b(aa)a)a)b,且采用自下而上的分析法，则输出序列为()。A.3 2 2 2 4 4 4 1 B.3 4 2 4 2 4 2 1 C.1 2 4 2 4 2 4 3 D.3 4 4 4 2 2 1 2三

5、、写出条件语句I F a0 T H EN x:=x+l EL S E x:=4*(x-1)的四元式序列(6分)四、设有基本块(8分)Bl：B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5(1)画出DAG 图；(2)假设只有L 在基本块后被引用，请写出优化后的四元序列。试卷第2页 共1 1页五、将下图DFA最小化，并写出最小化后DFA的正规式。(1 0 分)六、对下面的文法进行改写，并判断改写后是否是L L (1)文法。(1 5 分)S Aa|bA fS BB-ab七、已知文法：S fS；G|GG fG (T)|HH fa|(S)T T+S

6、|S求句型#a;(T+S);H;(S)#短语、句柄、素短语、最左素短语(1 2 分)八、【注意】计算机0 61/0 62 班和计教0 61/0 62 请做第1、2 题,计算机0 63 (海外班)请做第3 题，做错题得0分。(1 5 分)【计算机0 61/0 62 班和计教0 61/0 62 班做】1、给出文法G S 的L R(1)项目集规范族中1 0 项目集的全体项目。(5 分)G S 为：(1)E.E+T (2)E f T (3)T fT*F(4)T -F(5)F-(E)(6)F f a2、文法G M 及其L R 分析表如下，请给出对串dbba#的分析过程。(1 0 分)G M:1)M-V

7、bA 2)V -d 3)V 4)Aa5)A fAba 6)AACT I O NG O T Obda#MAV0r3S 3121acc2S 43r24r6S 5r665r4r46S 7rl7S 88r5r5【计算机0 63 海外班做】3、判断下列各题所示是否为L R 类文法，若是请说明是L R(0),S L R(l),L AL R(l)或L R(1)的哪一种，并构造相应分析表。(1 5 分)S faAd|eBd|aBr|eArA-aBfa试卷第4页 共1 1页答案：一、填空题(每空2 分，共 2 0 分)1 闭包 2、8，a,ab 3 语法 4、aa,bb,ab,ba5、多 6、句柄 7、继承 8

8、、之后9、DI S P L AY 10,环路二、单项选择(每小题2 分，共 1 4 分)题号1234567答案BDCDADB三、写出条件语句IF a0 THEN x:=x+l ELSE x:=4*(x-1)的四元式序列(6分)解：)评分标准：标号对给1分，0，,，)四元式格式对给1分，(+,x,1,T1)每2条四元式序列对给1分。(:=,T1,T2)0，,)(7,1,T3)(*,4,T3,T4)(:=,T 4,x)四、设 有 基 本 块(8分)(1)画出DAG 图；(2)假设只有L 在基本块后被引用，请写出优化后的四元序列。评分标准：DAG 图正确给4 分，代码每条1 分。解：(1)对于B1其

9、DAG图：E:=A*CF:=D+EL:=F+1 5五、将下图DFA最小化，并写出最小化后DFA的正规式。(1 0 分)解:P O=(6,7,1,2,3,4,5 )P O=(6,7,1,2 ,3,4,5 )输入 b 进入不同状态。P O=(6,7,1,2 ,3,4 ,5 )3,4 对 d 有定义，5 没有定义正规式为:b*a(c|da)*bb*评分标准：划分状态集过程给3分，图对得5分，图部分对根据对的多少给2-4分，正规上式对给2分。六、对下面的文法进行改写，并判断改写后是否是L L (1)文法。(15分)S -A a|bA f S BB-a b【解法 1】f ir st(S)=b f ir

10、st(A)=b f ir st(B)=a f o l l o w(S)=#,a f o l l o w (A)=a f o l l o w(B)=a se l e c t(S.A S)=f ir st(A S)=b se l e c t(S b)=f ir st(b)=b 试卷第6页 共11页se l e c t(S-A S)A se l e c t(S b)=b W 6所以该文法不是L L (1)文法改写为：S -A a|b S -S Ba|bA f S BA f S BB-a bB消除左递归:S-b S 化简得：S fb S S f B a S)1 S f B a S A一S B(多余)B

11、 a bB a bf ir st(S)=b f ir st尸a,f o l l o w(S)=#f o l k)w(S 尸#se l e c t(S-b S,)=f ir st(b S,)=b f ir st(B)=a f o l l o w(B)=a se l e c t(S,-Ba S,)=f ir st(Ba S,)=a se l e c t(S5-)=f ir st()U f o l l o w(S,)=#,se l e c t(S Ba S)C se l e c t(S.)=6所以改写后是L L 文法。评分标准：改写前判断L L (1)全对4分，改写正确4分，改写后判断L L (1)

12、正确得6分，最后结论1分。【解法 2】f ir st(S)=b f ir st(A)=b f ir st(B)=a f o l l o w(S)=#,a f o l l o w(A)=a f o l l o w(B)=a se l e c t(S A S)=f ir st(A S)=b se l e c t(S-b)=f ir st(b)=b se l e c t(S A S)A se l e c t(S b)=b W 6所以该文法不是L L (1)文法用S的产生式右部代替A的产生式右部的S得：S-*A a|b A-A a B|b B Ba b消除左递归后文法变为：0)S-*A a 1)S-b

13、 2)A-b B N3)N-a B N 4)N-e 5)B-a b非终结符 F I R S T集 F O L L O W集sABN#aanrjlrjbba/I/lxa,a S E L E CT(S-A a)n S E L E CT(S-b)=b A b =b WS E L E CT (N-a B N)A S E L E CT (N-*e )=a A a =a W6所以文法不是L L(1)的。评分标准：改写前判断L L (1)全对4分，改写正确4分，改写后判断L L (1)正确得6分，最后结论1分。七、已知文法：S f S；GIGG fG (T)|HHfaKS)TfT+S|S求句型#a;(T+S

14、);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)最左素短语a评分标准：语法图正确4分，短语正确5分，句柄正确1分，素短语正确1分，最左素短语正确1分。八、1、给出文法G S 的L R(1)项目集规范族中I。项目集的全体项目。(5分)G S 为：(1)E .E+T (2)E (3)T f T*F试卷第8页 共1 1页(4)

15、T-F(5)F f (E)(6)F f a解:10：S,f E ,#E 一 E+T,#,+E 一 T,#,+T T*F,#,+,*T-F ,#,+,*F 一 (E),#,+,*F-a ,#,+,*对输入串dbba#的分析过程评分标准：前 4 条项目，每条0.5分，后面3 条下面。每 条 1 分2、文法GM及 其 LR分析表如下，请给出对串dbba#的分析过程。(10分)G|M|:l)M VbA 2)V-d 3)V 一4)A-a 5)A-Aba 6)A-E解：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作10dbba#移进203#dbba#用 V d 归约302#Vbba#移

16、进4024#Vbba#用 A 归约50246#VbAba#移进602467#VbAba#移进7024678#VbAba#用 A A ba归约80246#VbA#用 M V bA 归约901#M#接受评分标准：每条1分，格式1 分。3、判断下列各题所示是否为LR类文法，若是请说明是LR(0),SLR(l),LALR或LR(1)的哪一种，并构造相应分析表。(15分)S aAd|eBd|aBr|eArA faB解：LR(0)项目集规范族如图：在状态16中有“规约-规约”冲突，且Follow(A尸follow(B尸 d,r故不是LR(O)和SLR(l)o文法LR(1)项目集规范族如下：10：S-s#S-aAd#S f eBdS f aBr#S f eAr#在状态16、17中有“规约-规约”冲突，但归依项目的向前搜索符集不相交，故文法是LR(l)o试 卷 第1 0页 共1 1页16,F7是同心集，若合并，则合并后的状态16,17有项目：A fa ,r/dB f a ,d/r向前搜索符集相交，故文法不是LALR(l)。因此，本文法是LR(1)文法。评分标准：LR(0)和SLR(1)的判断正确给4分，LR(0)和SLR(1)的结论1分，LR项目集规范族正确的给6分，判断LALR(1)同心集正确给2分，LALR(1)结论1分，LR(1)结论1分。