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

期末考试试卷〔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.正规文法2、生成非0开头的正偶数集的文法是〔〕。A．Z::=ABCB.Z::=ABCC::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|…|9A::=1|2|3|…|9C.Z::=ABC|2|4|6|8D.Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|…|9A::=1|2|3|…|93、简单优先分析法从左到右扫描输入串,当栈顶出现〔〕时进归约。4、同心集合并有可能产生新的〔〕冲突。A.归约B.移进／移进C.移进／归约D.归约／归约5、在编译中，动态存储分配的含义是〔〕。A．在运行阶段对源程序中的量进展存储分配B.在编译阶段对源程序中的量进展存储分配C.在说明阶段对源程序中的量进展存储分配D.以上都不正确6、活动记录中的连接数据不包含〔〕。A.老SPB.返回地址C.全局DISPLAY地址D形式单元7、有一语法制导翻译如下：S→bAb{printer(“1”A→(B{printer(“2”A→a{printer(“3”B→Aa){printer(“4”假设输入序列为b(((aa)a)a)b，且采用自下而上的分析法，那么输出序列为()。A．32224441B．34242421C三、写出条件语句IFa>0THENx:=x+1ELSEx:=4*(x-1)的四元式序列〔6分〕四、设有根本块〔8分〕B1：B:=3D:=A+CB1：B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L(1)画出DAG图；(2)(1)画出DAG图；(2)假设只有L在根本块后被引用，请写出优化后的四元序列。五、将以下图DFA最小化，并写出最小化后DFA的正规式。〔10分〕cbba631cbba631dbdbadbca5adbca5bb742bb742六、对下面的文法进展改写，并判断改写后是否是LL〔1〕文法。〔15分〕SA®SBB®ab七、文法:S®S；G|GG®G〔T〕|HH®a|(S)T®T+S|S求句型#a;(T+S);H;(S)#短语、句柄、素短语、最左素短语〔12分〕八、【注意】计算机061/062班和计教061/062请做第1、2题，计算机063〔海外班〕请做第3题，做错题得0分。〔15分〕【计算机061/062班和计教061/062班做】1、给出文法G[S]的LR(1)工程集标准族中I0工程集的全体工程。〔5分〕G[S]为：(1)E®E+T(2)E®T(3)T®T*F(4)T®F(5)F®(E)(6)F®a2、文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。〔10分〕G[M]:1)M→VbA2)V→d3)V→ε4)A→a5)A→Aba6)A→εACTIONGOTObda#MAV0r3S3

1

21

acc

2S4

3r2

4r6

S5r6

6

5r4

r4

6S7

r1

7

S8

8r5

r5

【计算机063海外班做】3、判断以下各题所示是否为LR类文法，假设是请说明是LR(0)，SLR(1)，LALR(1)或LR(1)的哪一种，并构造相应分析表。〔15分〕S®aAd½eBd½aBr½eArA®aB®a答案：一、填空题〔每空2分，共20分〕1、闭包2、ε，a，ab3、语法4、｛aa，bb,ab,ba}5、多6、句柄7、继承8、之后9、DISPLAY10、环路二、单项选择〔每题2分，共14分〕题号1234567答案BDCDADB三、写出条件语句IFa>0THENx:=x+1ELSEx:=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,ML,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如下：bcbba631bcbba631dda5a5正规式为：b*a(c|da)*bb*评分标准：划分状态集过程给3分，图对得5分，图局部对根据对的多少给2-4分，正规上式对给2分。六、对下面的文法进展改写，并判断改写后是否是LL〔1〕文法。〔15分〕SA®SBB®ab【解法1】first(S)={b}first(A)={b}first(B)={a}follow(S)={#,a}follow(A)={a}follow(B)={a}select(S®AS)=first(AS)={b}select(S®b)=first(b)={b}select(S®AS)∩select(S®b)={b}≠φ所以该文法不是LL〔1〕文法改写为：S®Aa|bS®SBa|bA®SBA®SBB®abB®ab消除左递归：S®bS’化简得：S®bS’S®BaS’|εS’®BaS’|εA®SB(多余)B®abB®abfirst(S)={b}first(S’)={a,ε}first(B)={a}follow(S)={#}follow(S’)={#}follow(B)={a}select(S®bS’)=first(bS’)={b}select(S’®BaS’)=first(BaS’)={a}select(S’®ε)=first(ε)Ufollow(S’)={#,ε}select(S’®BaS’)∩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)={a}select(S®AS)=first(AS)={b}select(S®b)=first(b)={b}select(S®AS)∩select(S®b)={b}≠φ所以该文法不是LL〔1〕文法用S的产生式右部代替A的产生式右部的S得：S→Aa|b

A→AaB|bBB→ab消除左递归后文法变为：0)S→Aa

1)S→b2)A→bBN3)N→aBN4)N→ε5)B→ab非终结符

FIRST集

FOLLOW集S

{b}

{#}A

{b}

{a}B

{a}

{a}N

{a,ε}

{a}SELECT(S→Aa)∩SELECT(S→b)={b}∩{b}={b}≠φSELECT(N→aBN)∩SELECT(N→ε)={a}∩{a}={a}≠φ所以文法不是LL(1)的。评分标准：改写前判断LL〔1〕全对4分，改写正确4分，改写后判断LL〔1〕正确得6分，最后结论1分。七、文法:S®S；G|GG®G〔T〕|HH®a|(S)T®T+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〕最左素短语aSSS；GS；GHGH〔S〕G〔T〕HT+Sa评分标准：语法图正确4分，短语正确5分，句柄正确1分，素短语正确1分，最左素短语正确1分。八、1、给出文法G[S]的LR(1)工程集标准族中I0工程集的全体工程。〔5分〕G[S]为：(1)E®E+T(2)E®T(3)T®T*F(4)T®F(5)F®(E)(6)F®a解：I0I0：S’·®E，#E·®E+T，#,+E·®T，#,+T·®T*F，#,+,*T·®F，#,+,*F·®(E)，#,+,*F·®a，#,+,*评分标准：前4条工程，每条0.5分，后面3条下面。每条1分2、文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。〔10分〕G[M]:1)M→VbA2)V→d3)V→ε4)A→a5)A→Aba6)A→ε解：对串dbba#的分析过程如下表对输入串dbba#的分析过程步骤状态栈文法符号栈剩余输入符号动作1

2

3

4

5

6

7

8

90

03

02

024

0246

02467

024678

0246

01#

#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分〕S®aAd½eBd½aBr½eArA®aB®a解：LR(0)工程集标准族如图：I0：I0：S’®·SS®·aAdS®·eBdS®·aBrS®·eArI2：S®a·AdS®a·BrA®·a