编译原理试卷一

一、 选择

1.一个正规语言只能对应(　　)？
A 一个正规文法；
B 一个最小有限状态自动机；

2.文法G[A]：A→ε A→aB B→Ab B→a是(　　)：
A 正规文法
B 二型文法

3.下面说法正确的是(　　)：
A 一个SLR（1）文法一定也是LALR（1）文法
B 一个LR（1）文法一定也是LALR（1）文法

4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(　　)：
A 必要条件
B 充分必要条件

二、多项选择

1.PL/0语言的目标程序解释执行时用到的数据对象有(　　)：
A 目标代码CODE
B 符号表TABLE
C 数据栈S
D 关键字表WORD

2.PL/0语言编译时产生或使用的数据对象有(　　)：
A 目标代码CODE
B 符号表TABLE
C 数据栈S
D 关键字表WORD

三、问答题

问答第1题
(5分)将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。
　　G[S]： S→bSAe | bA
　　　　　 A→Ab | d


问答第2题
(10分) 判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。
　　S→aH
　　H→aMd | d
　　M→Ab | ε
　　A→aM | e


问答第3题
　　给出与正规式R＝（ab）*（a|b*）ba等价的NFA。


问答第4题
将下图的NFA确定化为DFA。


问答第5题
(7分)
　　（1）给出下列PL/0示意程序中当程序执行到X过程调用Z过程后（即执行Z过程 体时）的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容。
　　（2）说明Display表和DL（老SP）,RA,TOP及全局Display的作用。 PL/0示意程序为：
　　const a=80;
　　var b,c;
　　procedure X;
　　　var d;
　　　procedure Z;
　　　　var e,g;
　　　　begin (* Z *)
　　　　　c:=b*a；
　　　　end ；(* Z *)
　　　begin (* X *)
　　　　call Z;
　　　end ；(* X *)
　　　procedure Y;
　　　　var f;
　　　　begin (* Y *)
　　　　　call X;
　　　　end ；(* y *)
　　　begin (* main *)
　　　　call Y;
　　　end. (* main *)


问答第6题
(5分)给出问答第5题PL/0示意程序编译到Y过程体时TABLE表的内容。


问答第7题
(10分)某语言的拓广文法G′为：(0) S′→T
　　　　　　　　　　　　　　 (1) T →aBd|ε
　　　　　　　　　　　　　　 (2) B →Tb|ε
证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。


问答第8题
(5分)给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。
G[S]为： S →BD|D
　　　　 B →aD|b
　　　　 D →B
I0:


问答第9题
(5分)文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。
G[M]: 1) M →VbA 　　　2) V →d
　　　3) V →ε 　　 　4) A →a
　　　5) A →Aba 　　　6) A →ε
name ACTION GOTO

b

 d a # M A V
0 r3 S3     1   2
1       acc      
2 S4            
3 r2            
4 r6   S5 r6   6  
5 r4     r4      
6 S7     r1      
7     S8        
8 r5     r5      


问答第10题
（5分）文法G[E]为： E→E+T|T
　　　　　　　　　　T→T*F|F
　　　　　　　　　　F→(E)|i
试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。


问答第11题
（6分）按指定类型给出下列语言的文法。
(1)L1={ anbm c| n≥0,m>0 } 用正规文法。
(2) L2={ a0n1n bdm | n>0，m >0} 用二型文法。


问答第12题
（6分）试对 if (ad) then s:=e else s:=f 的四元式序列给出第四区段应回填的指令地址，并指出真假出口链和链头及回填的次序。
    应回填的值 回填的次序  
(1) if a<b goto ( 　 ) ( 　 ) 真链头 E.true=
(2) goto ( 　 ) ( 　 ) 真出口链( 　 )
(3) if a>d goto ( 　 ) ( 　 )  
(4) goto ( 　 ) ( 　 ) 假链头 E.false=
(5) s:=e     假出口链( 　 )
(6) goto ( 　 ) ( 　 )  
(7) s:=f      
(8) ...