华东交通大学编译原理试题库-试卷七.doc

《华东交通大学编译原理试题库-试卷七.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．已知正规式：(8分)（1）(（a

2、b）*

3、aa)*b和正规式（2）（a

4、b）*b,试用有限自动机的等价性证明正规式（1）和（2）是等价的,给出相应的正规文法。2．已知文法G[A]为：(8分)    A→aABl

5、a    B→Bb

6、d①试给出与G[A]等价的LL（1）文法G[A]②构造G'[A]的预测分析表给出输入串aade#的分析过程。3．有文法G[S]为：(8分)    S→a

7、b

8、（A）    A→SdA

9、S完成下列算符优先关系表，并判断G[S]是否为算符优先文法。G[S]的算符优先关系表ab()D#   >>>

10、   >>><<<=<    >>><<<>< <<<  =①给出句型（sdsds）的短语，简单短语句柄，素短语和最大素短语。②给出输入串（adb）＃的分析过程。4．已知文法G[S]为：(8分)    S→aAd

11、；Bd

12、aB↑

13、；A↑    A→a    B→a①试判断G[S]是否为LALR（1）文法②当一个文法是LR（1）而不是LALR（1）时，那么LR（1）项目集的同心集合并后会出现哪几种冲突，请说明理由。5．试对下面基本块进行优化(6分)①应用DAG对该基本块进行优化，给出优化后的语句序列。②给出当只有L在基本块出

14、口后为活跃时的优化结果。基本块为：    X=B＊C    Y=B/C    Z=X+Y    W=9＊Z6．已知文法G[S]为：(6分)    S→dAB    A→aA

15、a    B→Bb

16、ε①试向G[S]是否为正规文法，为什么？②G[S]新产生的语言是什么？G[S]能否改写为等价的正规文法？7．某语言允许过程嵌套定义和逆归调用（如PACAL语言），若在栈式动态存分配中采用嵌套层次显示表Display解决对非局部变量的引用问题，试给出下列程序执行到语句“b：=10；”时运行栈及Display表的示意图。(6分)    

17、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;

18、    end(main).