清华大学1997年研究生入学考试 编译原理试.docxVIP

清华大学1997年研究生入学考试 编译原理试 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 # ? =? ? ? D ? ? # ? ? 清华大学1997年研究生入学考试 编译原理试题（共50分） ① 给出句型（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). 感谢您的阅读，祝您生活愉快。