编译原理 复习 要点.ppt

《编译原理 复习 要点.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理课程复习一、课程基本框架1、基础知识：文法2、词法分析理论模型——正规文法与有限自动机实现——词法分析程序3、语法分析理论模型：自上而下分析——下推自动机自下而上分析——优先分析和LR分析实现——递归下降分析法、YACC4、中间代码生成语法制导翻译6、中间代码优化：局部优化、循环优化、全局优化7、目标代码生成5、运行时数据区的管理：静态存储管理、栈式存储管理、堆式存储管理二、复习范围第一章到第七章三、复习方法1、认真理解书中的基本概念、基本原理与基本算法2、弄懂书中的例题与习题4、在理解的基础上记忆

2、四、考试题型同书上例题或习题形式，及判断题、选择题。3、在看书时或理解例题时，一定要划出相应的细节变化过程，通过画图来加深理解1、第三章a)Chomsky文法b)由语言构造文法包括上下文无关文法和正规文法c)根据算法构造无产生式的上下文无关文法五、各章主要知识点主要掌握上下文无关文法和正规文法及所对应的自动机类型题型根据语言写文法；构造无空串产生式的上下文无关文法；文法化简；例如：给出奇数集的上下文无关文法，且每个奇数不以0开头N→AB

3、BA→AC

4、DB→1

5、3

6、5

7、7

8、9D→B

9、2

10、4

11、6

12、8C→0

13、D

14、给出语言L={amban

15、m,n>=0}的正规文法。S→aS

16、bBB→aB

17、ε2、第二章a)NFA确定化子集法b)DFA最小化划分法c)带边的NFA确定化使用-闭包d)正规式、正规文法、自动机之间的转换五、各章主要知识点题型：1、不确定自动机的确定化（注意是否带空串）2、确定自动机的最小化3、正规式、正规文法、自动机之间的转换。例如已知NFAM如下，将M确定化，最小化得DFAM`，使得L(M)=L(M`)aSAZBbaεεaSAZBbaεε3、第四章a)消除左递归b)构造LL(1)分析表First、Fo

18、llowc)LL(1)分析过程五、各章主要知识点题型1、消除左递归；2、提取最左公因子；3、构造LL(1)分析表；4、判断文法是否是LL(1)文法；6、利用LL(1)分析方法分析某句子是否正确。例如设文法G(S)：S→(L)

19、aS

20、aL→L，S

21、S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW。五、各章主要知识点5、第五章a)LR(0)、SLR分析表构造除了历史，还考虑当前输入符号。通过First和Follow，解决冲突。b)二义文法的应用根据附加信息解决冲突。附加信息：结合规则和

22、优先级除了历史、当前符号，还考虑展望信息——确实是规范句型中跟在句柄之后的终结符例如：设有文法G:S－>S(S)S－>ε求：构造识别文法规范句型可归前缀的DFA；这个文法是LR[0]的吗？说明理由这个文法是SLR[1]的吗？是就构造其SLR分析表，否就说明理由五、各章主要知识点6、第六章a)算术表达式及赋值语句翻译b)控制语句中布尔表达式翻译留有真、假出口回填过程与并链函数c)标号和转移语句翻译d)IF语句的翻译e)WHILE语句的翻译题型为简单的复合语句进行翻译。语法制导生成后缀式例如：根据下面语句由语法

23、制导生成逆波兰式。Ifb∨c>dthenc:=c+eelsec:=e;