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表的示意图。
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）