2011-2012 第一学年编译原理考查试卷(双号)

《2011-2012 第一学年编译原理考查试卷(双号)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、GYU2011-2012第一学年编译原理考查试卷(双号)2011-2012第一学年编译原理考查试卷班级___________学号__________________姓名___________一、给定如下方法G[E]:E→EiT

2、TT→T+F

3、iF

4、FF→E*

5、(试问，它是一个二义文法吗？为什么？解：∵句子(i(*存在如下两棵不同的语法树∴G[E]是二义性的二、给出下述语言的上下文无关的文法：nnmmL1={abab

6、n,m≥0}nmmnL2={IOIO

7、n,m≥0}解：L1：S→AAA→aAb

8、εL2：S→1S0

9、AA→0A1

10、ε1三、已知正规式和正规式((

11、a

12、b)aa)*b和(a

13、b)*b，试用有限自动机的等价性证明这两个正规式是等价的。解：By©Facky

14、E-Mail：haljong@qq.comGYU2011-2012第一学年编译原理考查试卷(双号)**(1)正规式((a

15、b)

16、aa)b对应的NFA如图（1）所示。3aabX12Ya4b图（1）正规式((a

17、b)*

18、aa)*b对应的NFA图用子集法将图（1）所示的NFA确定化为DFA，如图（2）所示：IIaIbSab{X,1,2,4}{1,2,3,4}{1,2,4,Y}123重新命名{1,2,3,4}{1,2,3,4}{1,2,4,Y}223{1

19、,2,4,Y}{1,2,3,4}{1,2,4,Y}323图（2）确定化后的状态转换矩阵由于对非终态的状态1、2来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，由此得到合并后的状态转换矩阵图（3）；由此得到最简DFA，如图下图（4）所示：aSabb11212b212a图（3）合并后的状态转换矩阵图（4）最简DFA*正规式(a

20、b)b对应的NFA如图下图所示：abX12Yb图（5正规式(a

21、b)*b对应的NFA）用子集法将图下图所示的NFA确定化为如图下图所示的状态转换矩阵：IIaIbSab{X,1,2}{1,2}

22、{1,2,Y}重新命名123{1,2}{1,2}{1,2,Y}2232{1,2,Y}{1,2}{1,2,Y}323图（6）确定化后的状态转换矩阵By©Facky

23、E-Mail：haljong@qq.comGYU2011-2012第一学年编译原理考查试卷(双号)*比较图（2）与图（6），重新命名后的转换矩阵是完全一样的，也即正规式(a

24、b)b可以同样得到化简后的DFA如图（4）所示。因此，两个自动机完全一样，即两个正规文法等价。四、设文法G[S]：S→(L)

25、aS

26、aL→L,S

27、S(1)消除左递归和回溯(2)计算每个非终结符的First集和Follow集(3)

28、构造预测分析表解：（1）S→(L)

29、aS’S’→S

30、εL→SL’L’→SL’

31、ε(2)FIRST(S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{)}FIRST(L’)＝{，，ε}FOLLOW(L’〕＝{)}（3）预测分析表a,()#S→aS’→(L)S’→S→ε→S→ε→εL→SL’→SL,L’→ε→ε五、选做题将文法G[S]改成等价的正规式文法：G[S]:S→dABA→aA

32、aB→Bb

33、ε解：正规式是daa*b*；自动机化简来得到相应的

34、正规文法为：G[S]:S→dAA→a

35、aBB→aB

36、a

37、b

38、bCC→bC

39、b也可由观察得:G[S]:S→dA3A→a

40、aA

41、aBB→bB

42、εBy©Facky

43、E-Mail：haljong@qq.com