编译原理要点整理

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

1、编译原理要点整理//红色字体标注的是重点中的重点，大题的归宿第一章引论1.翻译器，编译器的定义2.编译器工作步骤和流程3.编译器前端后端的概念，理解为什么要有前端后端4.“遍”的概念第二章词法分析1.词法分析器的定义2.词法分析器所要完成的任务3.记号，模式，词法单元概念区分4.串的运算（和，连接，指数，闭包，正闭包）5.正规定义6.转换图（注意开始状态和结束状态以及需要将指针回退的状态）7.不确定的有限自动机（NFA）定义8.确定的有限自动机（DFA）定义9.从正规式到NFA（明确通过正规式如何构造连接运算，和运算，闭包运算的NFA）10.此方

2、法产生的NFA的性质11.从NFA到DFA（子集构造法）12.DFA的化简（合并不可区别状态）13.从语言描述直接到DFA14.了解Lex学完本章：能语言描述改写成正规定义，能将正规定义转化为语言描述，给出一个正规式，能转换成相应的NFA，DFA并化简。第三章语法分析1.上下文无关文法定义2.区分句子和句型3.最左推导&&最右推导4.分析树5.文法二义性6.消除左递归&&提左因子7.了解语言鸟瞰（0型文法：短语文法；1型文法：上下文有关文法；2型文法：上下文无关文法；3型文法：正规式）8.FIRST集合&&FOLLOW集合定义及计算方法9.LL（

3、1）文法定义10.了解自上而下的递归下降的预测分析11.自上而下非递归的预测分析（详细明确预测分析器接受某一输入串时的具体过程，明确栈如何变化，输入输出如何变化）12.预测分析表的构造13.句柄的概念14.自下而上的分析方法：用栈实现移近-归约分析（详细明确预测分析器接受某一输入串时的具体过程，明确栈如何变化，输入输出如何变化）1.LR文法和LR分析算法2.构造SLR分析表（从文法构造识别活前缀的DFA（LR（0）项目集规范族），从DFA构造SLR分析表）3.构造规范的LR分析表（从文法构造识别活前缀的DFA（LR（1）项目集规范族），从DFA构

4、造规范的LR分析表）4.构造LALR分析表（从文法构造识别活前缀的DFA（合并同心的LR（1）项目集），从DFA构造规范的LR分析表）（合并同心项目集可能会引起归约-归约冲突，不会引起新的移进-归约冲突）学完本章：能计算FIRST集合和FOLLOW集合；给定一个文法，能判断是否是LL(1)文法，并为其构造分析表；能构造LR(1)文法的三种预测分析表；明确移近归约分析中的每一个步骤，明确栈如何变化。第一章语法制导的翻译1.语法制导的定义2.综合属性（S属性定义）3.注释分析树（S属性定义可以自下而上的完成）4.继承属性5.语法树6.S属性的自下而上

5、计算（将LR分析器增加一个域来保存综合属性值）（一定要明确每一步移近-归约时属性栈如何变化）7.L属性定义（例：变量类型声明的语法制导定义）8.翻译方案（能根据文法以及需要计算的属性写出一个翻译方案）9.L属性定义的自上而下的计算10.L属性定义的自下而上的计算学完本章：要能根据要求设计简单问题的语法制导定义和翻译方案。例：为文法S—>(L)

6、aL—>L,S

7、S写一个语法制导定义，它输出括号的对数。第二章（不要求）第三章运行时存储空间的组织和管理1.过程定义、过程调用、形式参数、实在参数、活动的生存期2.名字的作用域和绑定3.活动记录（运行程序时

8、存储区布局，活动记录的一般布局）4.局部数据的安排（内存对齐问题）5.局部存储分配策略6.全局存储分配策略（静态，栈式，堆式）7.运行栈&&活动树8.访问链&&控制链9.非局部名字的访问（静态作用域，动态作用域的区别）1.四种参数传递方式的区别（值调用，引用调用，复写-恢复调用，换名调用）学完本章：能判断一个变量的作用域；熟悉静态分配与动态栈式分配的区别；明确非局部数据访问的实现方法；各种参数传递方式的区别；会处理内存对齐问题；会画活动树。例：指出下面程序中各个变量对应的分配策略？inta;voidp(intb){intc;int*d=mallo

9、c(sizeof(int)*b);}voidmain(){p(3);}第一章中间代码生成1.中间语言（能将表达式转化为后缀表示，图形表示，三地址代码形式）2.区分图形表示中的语法树和有向无环图学完本章：能将表达式转化为后缀表达式，语法树，有向无环图，三地址代码形式。例：将表达式a:=(b+c*d)+c*d转化为后缀表达式，有向无环图，三地址代码形式第二章代码生成1.指令的代价学完本章：会计算指令的代价例：指令代价MOVR0，R11MOVR5，M2ADD#1，R32SUB4(R0),*12(R1)3