清华大学1997年研究生入学考试编译原理试题（共50分） 



1．(8分) 

已知正规式（1）(（a|b）*|aa)*b和正规式（2）（a|b）*b,试用有限自动机的等价性证明正规式（1）和（2）是等价的,给出相应的正规文法。 

2．(8分) 

已知文法G[A]为： 

A→aABl|a 

B→Bb|d 

①试给出与G[A]等价的LL（1）文法G[A] 

②构造G’[A]的预测分析表给出输入串aade#的分析过程。 

3．(8分) 

有文法G[S]为： 

S→a|b|（A） 

A→SdA|S 

完成下列算符优先关系表，并判断G[S]是否为算符优先文法。 
G[S]的算符优先关系表 

表1算符优先关系表 

a 
b 
( 
) 
D 
# 

a 
·> 
·> 
·> 

b 
·> 
·> 
·> 

( 
<· 
<· 
<· 
=· 
<· 

) 
·> 
·> 
·> 

d 
<· 
<· 
<· 
·> 
<· 

# 
<· 
<· 
<· 
=· 


①给出句型（sdsds）的短语，简单短语句柄，素短语和最大素短语。 

②给出输入串（adb）＃的分析过程。 

4．(8分) 

已知文法G[S]为： 

S→aAd|；Bd|aB↑|；A↑ 

A→a 

B→a 

①试判断G[S]是否为LALR（1）文法 

②当一个文法是LR（1）而不是LALR（1）时，那么LR（1）项目集的同心集合并后会出现哪几种冲突，请说明理由。 

5．(6分) 

试对下面基本块进行优化 

①应用DAG对该基本块进行优化，给出优化后的语句序列。 

②给出当只有L在基本块出口后为活跃时的优化结果。 

基本块为： 

X=B＊C 

Y=B/C 

Z=X Y 

W=9＊Z 

6．(6分) 

已知文法G[S]为： 

S→dAB 

A→aA|a 

B→Bb|ε 

①试向G[S]是否为正规文法，为什么？ 

②G[S]新产生的语言是什么？ 

G[S]能否改写为等价的正规文法？ 

7．(6分) 

某语言允许过程嵌套定义和逆归调用（如PACAL语言），若在栈式动态存分配中采用嵌套层次显示表Display解决对非局部变量的引用问题，试给出下列程序执行到语句“b：=10；”时运行栈及Display表的示意图。 

varx,y; 

procedurcp; 

vara; 

procedureq; 

varb; 

begin(q) 

b:=10; 

end(q); 

procedures; 

varc,d; 

procedurer; 

vare,f; 

begin(r) 

callq; 

edn(r); 

begin(s) 

callr; 

end(s); 

begin(p) 

calls; 

end(p); 

begin(main) 

callp; 

end(main).