编译原理知识点汇总.doc

编译原理知识点汇总第一章：一基础知识（10）1编译程序是现代计算机系统的基本组成部分之一2一个计算机系统中通常配置多个高级语言的编译程序3在一个计算机系统中可为某些高级语言配置多个不同性能的编译程序4编译程序是一种语言翻译程序，其功能是把一种语言编写的程序翻译成另一种语言的等价程序5被编译的程序称为源程序，编译后的等价程序称为目标程序6编译程序的任务就是将源语言程序翻译成等价的目标语言程序7通常将编译过程分为六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。8词法分析的主要任务是从左至右扫描字符序列，并按照此法规则识别出一个个的单词9单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。10计算机语言中，单词的种类通常有保留字、标识符、数、算符、界符等11语法分析的主要任务是：按照语言的语法规则，把词法分析所得的单词序列分解成各类语法成分。12词法分析和语法分析都是对源程序进行结构分析，但二者是有区别的。13语义分析的主要功能是审查源程序有无语义错误，伪代码生成阶段收集类型信息。14中间代码生成阶段的主要任务是，把源程序转换成一种中间代码15中间代码是一种结构简单、含义明确的记号系统16中间代码可以设计成多种形式，其设计原则有两点：一是容易生成，二是容易转换成目标代码17代码优化的主要任务是对中间代码进行改造，使生成的目标代码更为高效18目标代码生成阶段的任务是把中间代码转换成特定机器上的绝对指令代码或者可重定位的指令代码或者汇编指令代码19在编译过程的每个阶段中都含有出错处理和表格管理的工作20编译程序的结构可以按功能分为八个模块，即词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序，此外还有与上述每个阶段都有关系的出错处理程序和表格管理程序。21按照编译程序的工作主要是与源语言有关还是与目标机有关，编译过程也可前端和后端22前端的工作主要依赖于源语言而与目标机无关，包括词法分析、语法分析、语义分析、中间代码生成以及每个阶段中的出错处理和表格管理工作，还包括代码优化阶段的部分工作23后端的工作主要与目标机有关而与源语言无关，主要是代码生成及相关的出错处理和表格管理工作24编译过程中，对源程序或者中间语言程序从头至尾扫描一次并完成相应工作的过程称为“一遍”或者“一趟”25解释程序是另一种语言处理程序，其工作特点是边分析边执行，不生成目标代码。第二章：（2）1终结符：构成语言文法的单词，是语法成分的最小单位2非终结符：是由终结符和非终结符串或者终结符串构成的语法成分3终结符和非终结符都是语法成分第三章：一基础知识（10）1文法，是用有穷集合描述无穷集合的一个工具2字母表，是元素的非空有穷集合，表中的元素称为符号，因此也叫符号集3符号串，是由字母表中的符号组成的任何有穷序列4符号串的长度5符号串的头和尾，固有头和固有尾6符号串的连接7符号串的方幂8符号串集合的乘积9闭包与正闭包10文法的形式定义：G=（VN，VT，P，S），其中每个元素的含义是什么，VN和VT有何关系11推导，长度=1的推导，长度=0的推导12句型的定义13句子的定义14语言的定义15文法等价的定义16文法的四种类型：17语法树，也叫推导树，它需满足四个条件：18最左推导，最右推导，规范推导19文法的二义性20短语，直接短语，句柄21多余规则：有不可到达和不可中止两种二分析解答题：（20）习题1,2,3,4,5,6,8, 11,13第四章：一基础知识（10）1词法分析的工具有正规文法，正规式和有穷自动机三种，三者之间存在等价性2正规式的定义，参考例4.23正规式服从的代数规律：4正规式与正规文法的等价变换，表4.15有穷自动机分为两类：6DFA的定义7NFA的定义8每个NFA都可以确定化为一个等价的DFA9有穷自动机的无用状态有两种情况：10有穷自动机中两个状态等价的条件有两个：二分析解答题：（20）1正规文法与正规式的等价变换。参考例4.3、4.42画出有穷自动机的状态图。参考例4.6、4.73DFA化简。例4.94正规式与有穷自动机的等价变换。记住几个变换规则，参考例4.10、4.115正规文法与有穷自动机的等价变换。参考例4.12、4.136习题：1(1)、4(b)只需最小化、7（只需消除多余规则）、8第五章：一基础知识（5）1开始符号集的定义（定义5.1）2后跟符号集的定义（定义5.2）3SELECT集合的定义（定义5.3）4LL（1）文法的定义（即充要条件）5LL（1）文法的含义6非LL（1）文法到LL（1）文法等价变换的两种情况：7引起回溯的几种情况：二分析解答题：（10）1判断一个文法是否为LL（1）文法。参考例5.15.42非LL（1）文法到LL（1）文法等价变换。（1）提取左公因子，参考例5.6、5.7（2）消除左递归，参考P88-89页1）和2）3习题：1（1,3），2（1,2），7（1,5）第六-八章：（15）一基础知识（）1自底向上分析法也叫移进-归约分析法2规范归约是指自左向右的归约3自底向上优先分析法有简单优先分析法和算法优先分析法两种4简单优先分析法和算符优先分析法的特点5算符优先文法的基本概念（定义6.1,6.2,6.3）6LR分析法是自底向上分析法，其分析过程是