编译原理试题与解析北京工业大学.doc

《编译原理试题与解析北京工业大学.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、北京工业大学2004∽2005年度第2学期计算机学院02级【编译原理】考试题考试形式：开卷考试时间：2005年6月24日9:55-11:30学号姓名1234567附加题总分分数1.（6分）回答下列问题1）在存储管理中，为什么在活动记录内为临时变量分配空间？答：在栈式存储管理方式中，以活动记录的形式为一次过程调用（函数调用）中的局部数据提供存储空间，该活动记录随过程调用被分配，随过程调用的结束而释放；临时变量通常用于保存表达式计算中的中间结果，在活动记录中为临时变量分配空间，可以保证该空间随过程调用被分配，随活动记录的释放被自动释放。

2、2）在符号表管理中，为什么将变量名保存在符号表中？答：符号表中将保存变量名及其各种属性，变量名将用于变量的识别、涉及变变量名与存储空间的绑定、以及类型、作用域、存储地址等各种变量属性的设置、获取等各种维护功能。2.(8分)试消除下列文法中的左递归。 S→SaA

3、Se

4、BA→BbA

5、BB→cSd

6、e解：消除左递归提取左因子改写后的文法S→SaA

7、Se

8、BA→BbA

9、BS→BS’→S（aA

10、e）

11、B→B(bA

12、e)S’→aAS’

13、eS’

14、e引进非终结符S’引进非终结符A’A→BA’S→BS’A→BA’A’→bA

15、eS’→（aA

16、e）S’

17、

18、eA’→bA

19、eB→cSd

20、e第7页共7页3.(15分)写出下列文法中各候选式的FIRST集和各非终结符的FOLLOW集,构造该文法的LL（1）分析表，并说明它是否为LL（1）文法。 S→aA

21、BAA→cB

22、eB→bB

23、e各候选式的FIRST集(4分)FIRST（aA）={a}FIRST（BA）={b，c，e}FIRST（cB）={c}FIRST（e）={e}FIRST（bB）={b}FIRST（e）={e}各非终结符的FOLLOW集(4分)FOLLOW(S)={#}FOLLOW(A)={#}FOLLOW(B)={c，#}LL（1

24、）分析表(5分)abc#SS→aAS→BAS→BAS→BAAA→cBA→eBB→bBB→eB→e说明它是否为LL（1）文法(2分)判断1分，理由1分因为LL（1）分析表无冲突，所以该文法是LL（1）文法。第7页共7页4.（18分）给定文法G[S]S→L+L｜LL→LB

25、BB→0

26、1 (1)构造拓广文法，按LR(0)分析的需要画出识别这个拓广文法的所有规范句型活前缀的DFA。解1：相应的DFA如下图所示。0SI0:Sˊ→.SS→.L+LS→.LL→.LBL→.BB→.0B→.1I8:S→L+L.L→L.BB→.0B→.1I2:S→L.

27、+LS→L.L→L.BB→.0B→.1I3:L→B.I1:Sˊ→S.LL01B0BB01+BI7:L→LB.I6:S→L+.LL→.LBL→.BB→.0B→.1I5:B→1.I4:B→0.11解2：0Sˊ→0S11S→0L2+6L82S→0L23L→0，6L2，8B74L→0，6B35B→0，2，6，8046B→0，2，6，815I0：{（0，0），（1，0），（2，0），（3，0），（4，0），（5，0），（6，0）}I1：{（0，1）}I2：{（1，1），（2，1），（3，1），（5，0），（6，0）}I3：{（4，1）}I4：

28、{（5，1）}I5：{（6，1）}I6：{（1，2），（3，0），（4，0），（5，0），（6，0）}I7：{（3，2）}I8：{（1，3），（3，1），（5，0），（6，0）}第7页共7页0SI0:（0，0），（1，0），（2，0），（3，0），（4，0），（5，0），（6，0）I8:（1，3），（3，1），（5，0），（6，0）I2:（1，1），（2，1），（3，1），（5，0），（6，0）I3:（4，1）I1:（0，1）LL01B0BB01+BI7:（3，2）I6:（1，2），（3，0），（4，0），（5，0），（6，0）I5

29、:（6，1）I4:（5，1）11(2)求出这个文法的SLR（1）分析表。解：给产生式编号：①S→L+L②S→L③L→LB④L→B⑤B→0⑥B→1FOLLOW(S)={#}FOLLOW(L)={0,1,+,#}FOLLOW(B)={0,1,+,#}状态ACTIONGOTO01+#SLB0S4S51231acc2S4S5S6r273r4r4r4r44r5r5r5r55r6r6r6r66S4S5837r3r3r3r38S4S5r17第7页共7页5.（7分）写出能产生字母表{x,y}上的不含两个相邻的x,且不含两个相邻的ｙ的全体符号串的有限

30、状态自动机。解：6.（16分）设文法G[E]:E→RP

31、PP→(E)

32、iR→RP+

33、RP*

34、P+

35、P*画出句子i+i*(i+i)的语法分析树，给出其最右推导和最左归约，并指出它的句柄。解：(1)语法分析树：（2）最右推导：EÞRPÞR