期末考试试卷（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::=ABCC::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|ε B::=BA|B0|0A::=1|2|3|…|9 A::=1|2|3|…|9C. Z::=ABC|2|4|6|8D. Z::=ABC|2|4|6|8C::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|0 B::=BA|B0|ε1 / 11A::=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.老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．32224441 B．34242421 C．12424243 D．34442212三、写出条件语句 IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1) 的四元式序列（6分）四、设有基本块（8分）(1) 画出DAG图；(2) 假设只有L在基本块后被引用，请写出优化后的四元序列。
五、将下图DFA最小化，并写出最小化后DFA的正规式。
（10分）b六、对下面的文法进行改写，并判断改写后是否是LL（1）文法。
（15分）S →Aa|bA →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 →VbA 2) V →d 3) V →ε4) A →a 5) A →Aba 6) A →ε3 / 11【计算机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、 DISPLAY 10、环路二、单项选择（每小题2分，共14分）三、写出条件语句IF a>0 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图：5 / 11若只有L 活跃，则代码为D:=A+CE:=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没有定义正规式为：b*a(c |da)*bb*评分标准：划分状态集过程给3分，图对得5分，图部分对根据对的多少给2-4分，正规上式对给2分。
六、对下面的文法进行改写，并判断改写后是否是LL （1）文法。
（15分）S →Aa|b A →SB B →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）文法b改写为： S →Aa|b S →SBa|bA →SB A →SBB →ab B →ab消除左递归： S →bS’化简得： S →b S’S →Ba S’|εS’ →Ba S’|ε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|bB B→ab消除左递归后文法变为：0) S→A a 1) S→b 2) A→b B N3) N→a B N 4) N→ε 5) B→a b非终结符 FIRST集 FOLLOW集S {b} {#}A {b} {a}B {a} {a}N {a,ε} {a}SELECT(S→A a)∩SELECT(S→b) ={ b }∩{ b }={ b }≠φSELECT(N→a B N)∩SELECT(N→ε) ={ a }∩{ a }={ a }≠φ所以文法不是LL(1)的。
评分标准：改写前判断LL（1）全对4分，改写正确4分，改写后判断LL（1）正确得6分，最后结论1分。
七、已知文法:S→S；G|GG→G（T）|HH→a|(S)7 / 11T→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）最左素短语 a评分标准：语法图正确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解：评分标准：前4条项目，每条0.5分，后面3条下面。
每条1分2、文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。
（10分）G[M]: 1) M →VbA 2) V →d3) V →ε4) A →a 5) A →Aba 6) A →ε解：对串dbba#的分析过程如下表对输入串dbba#的分析过程3、判断下列各题所示是否为LR类文法，若是请说明是LR(0)，SLR(1)，LALR(1)或LR(1)的哪一种，并构造相应分析表。
（15分）S→aAd∣eBd∣aBr∣eArA→aB→a解：LR(0)项目集规范族如图：9 / 11在状态I6中有“规约-规约”冲突，且Follow(A)=follow(B)={d,r}故不是LR(0)和SLR(1)。
文法LR(1)项目集规范族如下：在状态I6、I7中有“规约-规约”冲突，但归依项目的向前搜索符集不相交，故文法是LR(1)。
