清华大学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 算符优先关系表
ab()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表的示意图。
var x, y;
procedurc p;
var a;
procedure q;
var b;
begin(q)
b : =10;
end (q);
procedure s;
var c,d;
procedure r;
var e, f;
begin (r)
call q;
edn (r);
begin (s)
call r;
end (s);
begin (p)
call s;
end (p);
begin (main)
call p;
end (main).