清华大学1997年研究生入学考试编译原理试题（共50分）1．(8分)已知正规式（1）(（a|b）*|aa)*b和正规式（2）（a|b）*b,试用有限自动机的等价性证明正规式（1）和（2）是等价的,给出相应的正规文法。2．(8分)已知文法G[A]为：A→aABl|aB→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→aB→a①试判断G[S]是否为LALR（1）文法②当一个文法是LR（1）而不是LALR（1）时，那么LR（1）项目集的同心集合并后会出现哪几种冲突，请说明理由。5．(6分)试对下面基本块进行优化①应用DAG对该基本块进行优化，给出优化后的语句序列。②给出当只有L在基本块出口后为活跃时的优化结果。基本块为：X=B＊CY=B/CZ=X YW=9＊Z6．(6分)已知文法G[S]为：S→dABA→aA|aB→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).