编译原理总复习串讲

《编译原理总复习串讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、总复习串讲1、复习范围。2、习题讲解。3、模拟题讲解。教材《编译原理》陈意云，高教京。参考书籍：编译原理陈火旺国防工业出版社编译原理及实践Louden,K.C.机械工业出版社编译原理和技术陈意云中国科技大学出版社《编译原理》，吕映芝等，清华大学出版社，1998年1月第1版或第2版。章节第一章概述第三章文法和语言第四章词法分析第五章自顶向下语法分析LL（1）文法第六章自底向上优先语法分析第七章自底向上语法分析LR分析法第八章语法制导翻译和中间代码生成第十一章代码优化一、概论主要内容编译程序的实现策略T型图交叉编译自展编译程序总体结构8项功能、8个

2、模块书写语言目标语言源语言编译程序的结构二、文法分类主要内容文法的定义：Ｇ=(ＶT，ＶN，Ｐ，Ｓ)推导与归约：最左推导（左句型、最右归约）最右推导（右句型、规范句型、规范（最左）归约）语法树（CFG的分析树）二义性（定义）文法的分类PSG、CSG、CFG、RG（短语、上下文有关、上下文无关、正规文法）PSL、CSL、CFL、RL三、词法分析1、三型语言（RL）的等价描述1)RG、RE、FA(DFA、NFA、ε-NFA)2)RGRE例：S→0A

3、1BA→1S

4、1B→0S

5、03)RERG(正规定义式)例：1

6、01000*(100)*2(1

7、0)

8、+

9、0*4)RGFA(FARG、REFA、FARE)A→aB:aA→a：aT主要内容2、扫描器的设计与实现1)输入(Character字符流)2)输出(Token符号—二元组流)3)缓冲区4)状态图的实现3、Lex四、自顶向下语法分析1、左递归——按转换规范完成变换将A→Aα

10、β替换为A→βA’和A’→αA’

11、ε一般地：用产生式组A→β1B

12、β2B

13、…

14、βnBB→α1B

15、α2B

16、…

17、αnB

18、ε替换产生式组A→Aα1

19、Aα2

20、…

21、Aαn

22、β1

23、β2

24、…

25、βm其中：B为新变量，相当于A’四、自顶向下语法分析2、自顶向下：递归子程序、预测分析

26、(LL)核心寻找最左推导关键技术：根据当前输入符号确定候选式——FIRST(α)集与FOLLOW(A)集对于α∈(ＶT∪ＶN)*定义:α的首符号集FIRST(α)={a

27、α*a…，a∈ＶT*}P70对于A∈ＶN定义A的后续符号集：P71FOLLOW(A)={a

28、S*…Aa…，a∈ＶT}五、自底向上语法分析自底向上：算符优先、LR(0)、SLR(1)、[LR(1)、LALR]项目：A→x.byA→x.ByA→x.A→.项目集闭包与求法移进归约分析核心：在句型中寻找句柄进行归约算符优先关系表、LR分析表（动作表和状态转移表）六、语义分析和中

29、间代码生成属性文法定义、属性分类、属性文法分类简单算术表达式中间代码：三元式、四元式、逆波兰七、代码优化1、基本概念2、DAG图第三章练习参考答案第1题(1)允许0开头的偶正整数集合的文法解：E->NT

30、DT->NT

31、DN->D

32、1

33、3

34、5

35、7

36、9D->0

37、2

38、4

39、6

40、8(2)不允许0开头的偶正整数集合的文法解：E->NT

41、DT->FT

42、GN->D

43、1

44、3

45、5

46、7

47、9D->2

48、4

49、6

50、8F->N

51、0G->D

52、0第三章练习参考答案第2题可为句子a+a*a构造两个不同的最右推导:解：最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈

53、运算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a第三章练习参考答案第3题，G[E]为:E->E+T

54、E-TT->T*F

55、T/F

56、FF->(E)

57、I解：因为存在推导序列:EE+TE+T*F句型E+T*F的短语有:E+T*F,T*F

58、直接短语有:T*F句柄为:T*F第三章练习参考答案第4题（1）{anbnambm

59、n，m>=0}(2){1n0m1m0n

60、n，m>=0}S->AAS->1S0

61、AA->aAb

62、εA->0A1

63、ε第5题，(1){anbm

64、n,m>=1}的三型文法为：S->aAA->aA

65、BB->bB

66、b(2){anbmck

67、n,m,k>=0}的三型文法为:A->aA

68、BB->bB

69、CC->cC

70、ε第四章作业及答案1.构造正规式1(0

71、1)*101相应的DFA.(P66)确定化（子集法）01XAAAABABACABACAABYABYACAB重新命名，令AB为B、A

72、C为C、ABY为D01XAAABBCBCADDCBDFA：第五章练习及答案7、对于一个文法消除左递归，提取左公共因子。构造LL（1）分析表。练习7（2