资源描述：
《编译原理复习教学ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、复习内容基本概念基本方法期末考试题型分布基本概念第一章计算机程序设计语言高级语言的执行过程解释程序、编译程序及其区别编译过程的五个阶段编译程序的七个组成部分及其关系“遍”的概念编译程序的开发技术构造编译程序所应掌握的内容基本概念第二章单词符号的分类和输出形式状态转换图正规表达式和正规集符号、字母表、符号串、空符号串、符号串集合自反闭包、正则闭包有限自动机、确定有限自动机、非确定有限自动机有限自动机的表示词法分析器自动生成系统LEX、语法分析器自动生成工具YACC基本概念第三章文法和语言文法的开始符号、终结符、非终结符和产生式直接推导和推导、最左推导、最右推导文法产生
2、的语言形式语言分类、四类文法的关系与区别规范推导、短语、句柄、素短语语法树、子树和短语文法的二义性基本概念第三章（续）自上而下分析法：递归下降分析、LL(1)分析递归下降分析法要点:自上而下分析存在的不确定性如何实现确定的(即无回溯的)自上而下分析?消除左递归、消除回溯LL(1)分析法要点:LL(1)分析法的基本思想LL(1)分析器组成LL(1)文法的性质基本概念第三章（续）自下而上分析法：算符优先分析法、LR分析法归约、规范归约、可归约串、最左素短语算符文法和算符优先文法算符优先关系表LR分析法对文法的限制LR分析器的工作原理活前缀、LR(0)项目、LR(0)项目
3、集规范族拓广文法、LR(0)文法SLR(1)分析法、SLR(1)文法基本概念第四章语义分析的概念语法制导翻译方法文法的属性、继承属性与综合属性属性文法几种常见的中间语言数组元素的地址计算变址存数、变址取数基本概念第五章优化、优化三个不同的级别局部优化、循环优化和全局优化基本块、局部优化常用的优化技术利用DAG进行基本块优化的基本思想程序流图、必经结点、必经结点集、回边、循环可归约流图循环优化常用的优化技术基本方法正规表达式和正规集正规表达式到有限自动机的构造文法和语言推导和归约文法二义性的消除消除左递归、消除回溯LL(1)文法的判别FIRST集合、FOLLOW集合的
4、构造LL(1)分析表的构造基本方法算符优先文法的判别FIRSTVT集合、LASTVT集合的构造算符优先关系表的构造LR(0)分析表的构造SLR(1)分析表的构造表达式翻译成逆波兰式典型语句的翻译（生成四元式序列）基本块的划分、基本块的优化程序流图、必经结点集、回边、循环正规式到正规文法的转换与正规式R=a(a
5、d)*等价的正规文法G的产生过程为正规式a(a
6、d)*的字母表∑={a,d},故G的VT={a,d}设定开始符号S,生成产生式S→a(a
7、d)*按分解规则:S→aA,A→(a
8、d)*S→aA,A→(a
9、d)A,A→εS→aA,A→aA
10、dA,A→ε故得到等价的
11、正规文法G:S→aAA→aA
12、dA
13、ε正规文法到正规式的转换与含有下列产生式的正规文法G:S→aAA→aA
14、aBB→bCC→cB
15、c等价的正规式的产生过程为将C→cB
16、c代入B→bC得B→b(cB
17、c),即B→bcB
18、bc也就是B→(bc)*(bc)或者写成B→(bc)+将B→(bc)+代入A→aA
19、aB得A→aA
20、a(bc)+,即A→a+(bc)+将A→a+(bc)+代入S→aA得S→aa+(bc)+因此,与文法G等价的正规式为aa+(bc)+正规文法到FA的转换方法设有正规文法G[S]:S→aA
21、bB
22、aA→aB
23、bAB→aS
24、bA
25、b则与G[S]等价的FA构造
26、过程如下:FA的∑={a,d}.G[S]有三个非终结符S、A、B,对应FA的三个状态.S为开始状态.另设一个状态Z作为FA的终态.对G[S]的每个产生式构造转换函数,画出FA的状态转换图.SBZAabbbaaabFA到正规文法的转换方法有FA如右图所示。构造其对应的正规文法G=(VN,VT,S,P)VT={0,1}VN={A,B,C,D}开始符为A产生式为：A→1D
27、0B
28、0B→0D
29、1CC→0B
30、1D
31、0D→0D
32、1B
33、1ADBC01111000FA到正规式的转换方法02413a,baba,ba,bbaFA到正规式的转换方法（续）02413a,baba,ba,bb
34、aXεYεεFA到正规式的转换方法（续）024a
35、bbba
36、ba
37、baaXεYεεFA到正规式的转换方法（续）0a
38、bbb(a
39、b)*aa(a
40、b)*XεYFA到正规式的转换方法（续）0a
41、b(aa
42、bb)(a
43、b)*XεYXY(a
44、b)*(aa
45、bb)(a
46、b)*正规式到FA的转换方法将正规式r=10
47、(0
48、11)0*1转换成等价的FA:XY10
49、(0
50、11)0*1XY(0
51、11)0*110正规式到FA的转换方法（续）XY(0
52、11)0*1110正规式到FA的转换方法（续）XY0*110230
53、111正规式到FA的转换方法（续）XY0*110231110正规式
