北航计算机学院编译习题讲解.docx

《北航计算机学院编译习题讲解.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习习题题课课(1(1--33章章））1、复习2、习题讲解北京航空航天大学计算机科学与工程系2008年6月27日1第第一一章章概论(介绍名词术语、了解编译系统的结构和编译过程）北京航空航天大学计算机科学与工程系2008年6月27日211..22编编译译过过程程所谓编译过程是指将高级语言程序翻译为等价的目标程序的过程。习惯上是将编译过程划分为5个基本阶段：词法分析语法分析语义分析、生成中间代码代码优化生成目标程序北京航空航天大学计算机科学与工程系2008年6月27日3典型的编译程序具有7个逻辑部分S.P词法分

2、析程序符语法分析程序出号错语义分析、生成中间代码表处管理代码优化理生成目标程序O.P北京航空航天大学计算机科学与工程系2008年6月27日4第第二二章章•掌握符号串和符号串集合的运算、文法和语言的定义•几个重要概念：递归、短语、简单短语和句柄、语法树、文法的二义性、文法的实用限制等。•掌握文法的表示：BNF、扩充的BNF范式、语法图。•了解文法和语言的分类北京航空航天大学计算机科学与工程系2008年6月27日5第第三三章章::词词法法分分析析3.1词法分析的功能3.2词法分析程序的设计与实现–状态图3.3

3、词法分析程序的自动生成–有穷自动机、LEX北京航空航天大学计算机科学与工程系2008年6月27日6补补充充正则文法正则文法15264NFA正则表达式NFA正则表达式3DFADFA最小化北京航空航天大学计算机科学与工程系2008年6月27日7习习题题11－－33章章北京航空航天大学计算机科学与工程系2008年6月27日8第第一一章章•2．典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？北京航空航天大学计算机科学与工程系2008年6月27日91.2编译过程所谓编译过程是指将高级语言程序翻译

4、为等价的目标程序的过程。习惯上是将编译过程划分为5个基本阶段：词法分析语法分析语义分析、生成中间代码代码优化生成目标程序北京航空航天大学计算机科学与工程系2008年6月27日10典型的编译程序具有7个逻辑部分S.P词法分析程序符语法分析程序出号错语义分析、生成中间代码表处管理代码优化理生成目标程序O.P北京航空航天大学计算机科学与工程系2008年6月27日11P19：4.试证明：A+=AA*=A*A证：∵A*=A0∪A+，A+=A1∪A2∪…∪An∪…得：A*=A0∪A1∪A2∪…∪An∪…∴AA*=A（

5、A0∪A1∪A2∪…∪An∪…）=AA0∪AA1∪AA2∪…∪AAn∪…=A∪A2∪A3∪An+1∪…=A+同理可得：A*A=(A0∪A1∪A2∪…∪An∪…)A=A0A∪A1A∪A2A∪…∪AnA∪…=A∪A2∪A3∪An+1∪…=A+因此：A+=AA*=A*A北京航空航天大学计算机科学与工程系2008年6月27日12P26:1.设G[〈标识符〉]的规则是：〈标识符〉::=a

6、b

7、c

8、〈标识符〉a

9、〈标识符〉c

10、〈标识符〉0

11、〈标识符〉1试写出VT和VN，并对下列符号串a,ab0,a0c01,0a,11

12、,aaa给出可能的一些推导。解：VT={a,b,c,0,1}，VN={〈标识符〉}(1)不能推导出ab0,11,0a(2)〈标识符〉=>a(3)〈标识符〉=>〈标识符〉1=>〈标识符〉01=>〈标识符〉c01=>〈标识符〉0c01=>a0c01(4)〈标识符〉=>〈标识符〉a=>〈标识符〉aa=>aaa2008年6月27日13北京航空航天大学计算机科学与工程系P26P26：：22．．写写一一文文法法，，其其语语言言是是偶偶整整数数的的集集合合常见错误：1.终结符集中没有奇数。2.如下定义：<偶整数>=><

13、数字串><偶数字>，<数字串>=><数字>

14、<数字串><数字><数字串>不能=>ε。3.忽略负偶数。北京航空航天大学计算机科学与工程系2008年6月27日14作法一：<偶整数>::=2×<整数><整数>::=<数字串><数字><数字串>::=<数字><数字>::=0

15、1

16、2

17、3

18、4

19、5

20、6

21、7

22、8

23、9作法二：z=偶整数G(z)=0

24、2

25、2Z

26、2(Z+1)

27、2(Z-1)或：G(Z)=0

28、2

29、Z+2

30、Z-2北京航空航天大学计算机科学与工程系2008年6月27日15解：G[<偶整数>]：<偶整数>::=<符号>

31、<偶数字>

32、<符号><数字串><偶数字><符号>::=+

33、—

34、ε<数字串>::=<数字串><数字>

35、<数字><数字>::=<偶数字>

36、1

37、3

38、5

39、7

40、9<偶数字>::=0

41、2

42、4

43、6

44、83.写一文法，使其语言是偶整数的集合，但不允许有以0开头的偶整数。北京航空航天大学计算机科学与工程系2008年6月27日16•4.设文法G的规则是：〈A〉::=b

45、cc试证明：cc,bcc,bbcc,bbbcc∈L[G]证：（1）〈A〉=