《编译原理》课程习题

《《编译原理》课程习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章编译程序概述1.1什么是编译程序　　编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。1.2编译过程概述和编译程序的结构　　编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。事

2、实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。图1.1表示了编译的各个阶段。图1.1编译的各个阶段1.3

3、高级语言解释系统　　为了实现在一个计算机上运行高级语言的程序,主要有两个途径：第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程序就叫解释程序。从功能上说，一个解释程序能让计算机执行高级语言。它与编译程序的主要不同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义，执行相应的动作。第二章：高级语言及其语法描述问答第1题　　写一文法，使其语言是偶正整数的集合。要求：　　(1)允许0打头；　　(2)不允许0打头。答：(1)

4、允许0开头的偶正整数集合的文法　　E→NT

5、D　　T→NT

6、D　　N→D

7、1

8、3

9、5

10、7

11、9　　D→0

12、2

13、4

14、6

15、8(2)不允许0开头的偶正整数集合的文法　　E→NT

16、D　　T→FT

17、G　　N→D

18、1

19、3

20、5

21、7

22、9　　D→2

23、4

24、6

25、8　　F→N

26、0　　G→D

27、0问答第2题　　证明下述文法G[〈表达式〉]是二义的。　　〈表达式〉∷=a

28、(〈表达式〉)

29、〈表达式〉　　〈运算符〉〈表达式〉〈运算符〉∷=+

30、-

31、*

32、/答：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉　　　　　　　　　　〈表达式〉〈运算符〉a　　　　　　　

33、　　　〈表达式〉*a　　　　　　　　　　〈表达式〉〈运算符〉〈表达式〉*a　　　　　　　　　　〈表达式〉〈运算符〉a*a　　　　　　　　　　〈表达式〉+a*a　　　　　　　　　　a+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉　　　　　　　　　　〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉　　　　　　　　　　〈表达式〉〈运算符〉〈表达式〉〈运算符〉a　　　　　　　　　　〈表达式〉〈运算符〉〈表达式〉*a　　　　　　　　　　〈表达式〉〈运算符〉a*a　　　　　　　　　　〈表达式〉+a*a　　　　　　　　　　a+a*a问答第3题　　令文法G[E]为：　

34、　E→T

35、E+T

36、E-T　　T→F

37、T*F

38、T/F　　F→(E)

39、i　　证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答　：　因为存在推导序列:EE+TE+*F所以E+T*F是文法G[E]的一个句型　　句型E+T*F的　　短语有:E+T*F,T*F　　直接短语有:T*F　　句柄为:T*F问答第4题　　给出生成下述语言的上下文无关文法：　　（1）{anbnambm

40、n，m>=0}　　（2）{1n0m1m0n

41、n，m>=0}答：(1)　　S→AA　　A→aAb

42、ε(2)　　S→1S0

43、A　　A→0A1

44、ε问答第5题　　给出生成下述语言的三型文法：

45、　　(1){anbm

46、n,m>=1}　　(2){anbmck

47、n,m,k>=0}答：(1)　　S→aA　　A→aA

48、B　　B→bB

49、b(2)　　A→aA

50、B　　B→bB

51、C　　C→cC

52、ε问答第6题　　给出下述文法所对应的正规式：　　S→0A

53、1B　　A→1S

54、1　　B→0S

55、0答：　R=(01

56、10)(01

57、10)*第三章：词法分析问答第1题　　构造正规式1(0

58、1)*101相应的DFA.答：先构造NFA：用子集法将NFA确定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y