资源描述:
《编译原理习题及答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第27页共27页第一章编译程序概述1.1什么是编译程序 编译程序是现代计算机系统的基本组成部分之一,而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。1.2编译过程概述和编译程序的结构 编译程序完成从源程序到目标程序的翻译工作,是一个复杂的整体的过程。从概念上来讲,一个编译程序的整个工作过程是划分成阶段进行的,每个阶段将源程序的一种表示形式转换成另一种表示形式,各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成,代码优化和目
2、标代码生成六个阶段,这是一种典型的划分方法。事实上,某些阶段可能组合在一起,这些阶段间的源程序的中间表示形式就没必要构造出来了。我们将分别介绍各阶段的任务。另外两个重要的工作:表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里,编译各阶段的工作都涉及到构造、查找或更新有关的表格,因此需要有表格管理的工作;如果编译过程中发现源程序有错误,编译程序应报告错误的性质和错误发生的地点,并且将错误所造成的影响限制在尽可能小的范围内,使得源程序的其余部分能继续被编译下去,有些编译程序还能自动校正错误,这些工
3、作称之为出错处理。图1.1表示了编译的各个阶段。图1.1编译的各个阶段1.3高级语言解释系统答案参见我的新浪博客:http://blog.sina.com.cn/cty1009第27页共27页 为了实现在一个计算机上运行高级语言的程序,主要有两个途径:第一个途径是把该程序翻译为这个计算机的指令代码序列,这就是我们已经描述的编译过程。第二个途径是编写一个程序,它解释所遇到的高级语言程序中的语句并且完成这些语句的动作,这样的程序就叫解释程序。从功能上说,一个解释程序能让计算机执行高级语言。它与编译程序的主要不同是它不生成目标代码,它每遇到
4、一个语句,就要对这个语句进行分析以决定语句的含义,执行相应的动作。第二章:高级语言及其语法描述问答第1题 写一文法,使其语言是偶正整数的集合。要求: (1)允许0打头; (2)不允许0打头。答:(1)允许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[〈表达式〉]是二义的。 〈表达式〉∷
28、=a
29、(〈表达式〉)
30、〈表达式〉 〈运算符〉〈表达式〉〈运算符〉∷=+
31、-
32、*
33、/答:可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉a 〈表达式〉*a 〈表达式〉〈运算符〉〈表达式〉*a答案参见我的新浪博客:http://blog.sina.com.cn/cty1009第27页共27页 〈表达式〉〈运算符〉a*a 〈表达式〉+a*a a+a*a最右推导2〈表达式
34、〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉a 〈表达式〉〈运算符〉〈表达式〉*a 〈表达式〉〈运算符〉a*a 〈表达式〉+a*a a+a*a问答第3题 令文法G[E]为: E→T
35、E+T
36、E-T T→F
37、T*F
38、T/F F→(E)
39、i 证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。答 : 因为存在推导序列:EE+T
40、E+*F所以E+T*F是文法G[E]的一个句型 句型E+T*F的 短语有:E+T*F,T*F 直接短语有:T*F 句柄为:T*F问答第4题 给出生成下述语言的上下文无关文法: (1){anbnambm
41、n,m>=0} (2){1n0m1m0n
42、n,m>=0}答:(1) S→AA A→aAb
43、ε(2) S→1S0
44、A A→0A1
45、ε问答第5题 给出生成下述语言的三型文法: (1){anbm
46、n,m>=1}答案参见我的新浪博客:http://blog.sina.com.cn/cty1009第27页共27页 (2)
47、{anbmck
48、n,m,k>=0}答:(1) S→aA A→aA
49、B B→bB
50、b(2) A→aA
51、B B→bB
52、C C→cC
53、ε问答第6题 给出下述文法所对应的正规式: S→0A
54、1B