编译原理复习汇总

《编译原理复习汇总》由会员分享，可在线阅读，更多相关《编译原理复习汇总（14页珍藏版）》请在金锄头文库上搜索。

1、复习汇总一、 第一章概述1. 文法与自动机的等价1) 0 型文法图灵机2) 1 型文法线性有界非确定图灵机3) 2 型文法非确定下推自动机4) 3 型文法有限状态自动机2. 编译技术的应用1) 语法制导的结构化编辑器2) 程序格式化工具3) 软件测试工具4) 程序理解工具5) 高级语言的翻译工具6) 等等3. 从面向机器的语言到面向人类的语言(结合第二章第 9 小点理解)1) 面向机器的语言：机器指令，汇编语言2) 面向人类的语言：通用程序设计语言，数据查询语言，形式化描述 语言(正规式,产生式)等等。4. 各语言的分类(结合第二章第 9小点理解)1) 过程式语言，面向对象语言：通用程序设计语

2、言。2) 函数语言：面向特点领域的，递归特性。例如 LISP 语言3) 说明性，非算法式语言：LEX/YACC,SQL。4) 脚本式语言： Shell 语言5. 语言之间的转换(李静 PPT41)1) 高级语言之间的转换一般称为预处理或转换。2) 高级语言翻译成汇编语言或机器语言称之为编译。3) 把汇编语言翻译成机器语言称之为汇编。4) 将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之为交叉汇编。5) 把机器语言翻译成汇编语言称之为反汇编。6) 把汇编语言翻译成高级语言称之为反编译。6. 编译器和解释器1) 编译器源程序的翻译和翻译后的程序的运行是两个不同的阶段。编译阶段：用户输入源

3、程序，经过编译器的处理，生成目标 程序。 目标程序的运行阶段：根据要求输入数据，得出结果。2) 解释器(凡是可以采用编译器的地方均可以采用解释器) 解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执 行它。这种方式称为解释。7. 解释器的优点(对比与编译器)1) 具有较好的动态特性。2) 具有较好的移植特性。8. 解释器的缺点(对比于编译器)1) 相比于编译器需花费大量的时间。2) 占用更多的内存空间。9. 编译器的工作阶段(结合第二章 6小点红色部分理解)1) 源程序-词法分析器-语法分析器-语义分析器-中间代码生成器- 代码优化器-目标代码生成器-目标代码2) 工作过程中的每个阶段均

4、采用了符号表管理器，出错处理器。10. 编译器各阶段的工作过程(结合第二章 6小点红色部分理解)1) 源程序通过词法分析器翻译成记号流，记号流通过语法分析产生语 法树，然后根据语法树来进行适当的语义处理，语义分析产生符号 表和中间代码。2) 符号表的格式：标识符，类型，分配的地址。3) 中间代码的格式：操作符，左操作数，右操作数，结果。4) 中间代码的优化：传值的代码可以省略。5）目标代码生成：生成汇编指令，格式为：操作数源码目标。 二元运算： OP source target target := source OP target 一元运算：MOVE source target tatget

5、= source。11. 各阶段工作归纳1）词法分析：根据词法规则识别出源程序的各个记号（token）,每个 记号代表一类单词（lexeme）,记号的分类如下（第二章第4小点） 关键字：如 var、begin、end 等，不做他用，称为保留字。 标识符：如 x、y、z、sort 等，在源程序中被用作变量名，过程 名，类型名和标号等所有对象的名称。 （用记号代替） 字面量：如 60、Xidian、University 等，一般用于表示常数或字 符串常量。（保留原样） 特殊符号： =、*、+、-、;等运算符，分隔符（保留原样）。 例： var x,y,z:real ; x:= y+z*60; va

6、rid1,id2,id3:real;id1:=id2+id3*60;2）语法分析：得到语言结构并以树来表示。3）语义分析：考察结构正确的句子是否语义合法。4）中间代码生成。5）中间代码优化。6）目标代码生成。7）符号表管理：合理组织符号，便于各阶段查找，填写等。8）出错处理：错误的种类词法错，语法错，静态语义错，动态语义 错。12.编译器的分析/综合模式。（PPT53）1）前端（分析）：语言结构的分析。（语法和语义分析）2）后端（综合）：语言意义的分析与处理。（代码的生成、优化）3）中间代码：前段与后端的分解。二、 第二章词法分析1. 词法分析：词法分析是编译过程中将字符流转换成为符号流的一个

7、工作阶段，是编译的第一步操作，其后续工作是语法分析（配合第一章第11小点理解）。1） 词法分析输入源代码。2） 词法分析输出记号流。3）词法分析需要识别此发错无，即非法的符号、单词。但不识别语法 错误。2. 词法分析器的作用1） 源程序由单词组成，单词是最小的语义单位。2） 词法分析器的功能：扫描源程序字符流。按照源程序的语法规则识别出各类单词符号。 产生用于语法分析的记号序列。 填写符号表。3） 辅助功能 跳过源程序的注释和空白。 把错误信息和源程序联系起来（错误定位）。 宏预处理。3. 模式（规则）（patten ：将产生和识别单词的规则称为模式（规则）。4. 记号（token ：按照某个

8、模式识别出来的元素称为记号。（第一章和本章 第 11 小点一同理解）1）记号 = 记号的类别 +记号的属性。（用于识别）2）记号的类别：记号的类别可以用整形编码来表示。3）记号的属性：根据记号的类别不同，记号的属性可以用不同的表示 方法，如relational）的属性值为一个有限的可枚举的集合，可以用 每个属性值在集合中的位置来表示它。（课本P16）。5. 单词（lexeme ：被识别出元素自身的价值。（结合本章第9点理解）6. 词法分析器的作用和工作方式:1）特征：编译器中唯一与源程序打交道的部分。2）任务：（与第二章第 2 点一同理解） 滤掉源程序中的无用的部分，如注释，空格，回车等。处理

9、与具体平台有关的输入。识别记号，并交给语法分析器，根据模式识别记号。 调用符号表管理器或出错管理器，进行相关管理。3）工作方式 单独一遍扫描。 作为语法分析器的子程序。 并行方式。4）输入输出结果的分析（结合第一章 9、10小点理解） 源程序-词法分析期-记号流 源程序-词法分析器-记号流-语法分析器-语法树。7. 输入缓冲区1） 设置缓冲区的必要性： 超前搜索：为了得到某一个单词符号的确切性质，需要超前扫描 若干个字符。 方便实现读字符和退字符操作，提高词法分析器的效率。8. 字符串：从词法分析的角度看程序语言设计，他是由几号组成的集合（第 二章第 4小点）1）定义：语言L是有限字母表E上有

10、限长度字符串的集合。字母表是 组成字符串的所有字符的集合。即字符串中的所有字符取自字母表。2）两个有限：（有序集合）:因为计算机所能表示的字符个数和字符串 长度是有限的。 字母表是有限的，即字母表中的元素是有限多个。 字符串长度是有限的，即字符串中字符的个数是有限多个的。3）字符串和集合的基本概念 （课本 P19）9. 语言概述：（第一章第 3、4小点理解）1）语言形式化的内容提取：是字和组合字的规则 语言：满足一定条件的句子集合。 句子：满足一定规则的单词序列 单词：满足已定规则的字符。（结合本章第5点理解）2) 程序设计语言形式化的内容提取：组成程序的所有语句的集合。程序：满足语法规则的语

11、句序列。语句：满足语法规则的单词序列。 单词：满足词法规则的字符串。(结合本章第5点理解)3) 描述形式文法 语法语句语句的组成规则描述方法：BNF范式，语法图 词法单词(结合本章第 5点理解) 单词的组成规则。描述方法：BNF范式，正规式。(结合下一小点理解)10. 正规式和正规集1) 正规式：令是一个有限字母表，则三上的正规式及其表示的集合递归定义为： 是正规式，他表示集合L( ) = 若a是三上的字符，则a是正规式，他表示集合L (a) = a若正规式r和s分别表示集合L (r)和L (s)，则 r|s是正规式，表示集合L (r)并L (s)。 rs 是正规式，表示集合 L( r) L(

12、 s)。 r*是正规式，表示集合L (r) *。 (r)是正规式，表示的集合仍是L (r)。(加括号改变优先 级，结合性)2) 正规集：可用于正规式描述的语言称为正规语言或正规集。 正规式计算的优先级(具有左结合的性质) 从高到低排列：闭包运算，连接运算，或运算。 正规式中不必要的括号可以被省略。3) 正规式和正规集之间的关系是多对一的关系。4) 正规式的等价：若正规式P和Q表示了同一个正规集，则称P和Q 是等价的，即为 P=Q5） 正规式公理（课本 P21）11. 记号的说明（用正规式来描述）（本章第 4小点）：正规式可以严格规定 记号的模式，用正规式说明记号的公式为：1）记号=正规式（记号

13、是正规式）例如：id = a（a|b）可以读作“id定义 为a（a|b）”（简称为正规式）2）通常在不引起混淆的情况下，也把说明记号的公式简称为正规式， 或者规则。12. 记号的识别有限自动机1）模式的描述正规式2）记号的识别有限自动机（确定，不确定）不确定的有限自动机定义：NFA是一个五元组：M = （S,E, move, s0, F）A. S是有限个状态的集合。B. 三是有限个输入字符（包括8 ）的集合。C. Move 是一个状态转移函数, move（si , ch） = sj 表示,当前状态或下若遇到输入字符ch,则转移到状态sj。D. s0是唯一的初态（称为开始状态）E. F是终态集，

14、他是S的子集，包含了所有的终态。 NFA的表示方式A. 状态转换图：用一个有向图直观表示NFA。终态用一个 双圈来表示。B. 状态转换矩阵：用一个二维数组来直观表示 NFA。 NFA识别记号（课本P24-25 , PPT29）A. NFA识别记号存在的问题：1. 只有尝试了全部可能的路径，才能确定一个输入序 列不被接受，而这些路径的条数随着路径长度的增 长而成指数增长。2. 识别过程中存在大量回溯，时间复杂度和输入序列 呈指数级增长。确定的有限自动状态机(DFA)定义：DFA是NFA的一个特例A. 没有状态具有g状态转移，即状态转换图中没有标记E 的边。B. 对每一个状态s和每一个字符a,最多有一个下一个状 态。 DFA的特征：消除了 NFA的不确定性。A. 定义move (si, a)函数是一对一的。B. 转换图：从一个节点出发的边上标记均不相同。(没有重 复字符的状态转移)C. 转换矩阵Msi, a是一个状态。(NFA可以为状态集)D. 字母表不包括&。有限自动机的等价：若有限自动机M和M识别同意正规集， 则成M和M是等价的，即为M=M。13. 简化正规式描述1) 正闭包：若r是表示L (r)的正规式，则r的正闭包是表示(L (r) 的正闭包的正规式； r+ = rr* = r*r, r* = r+|g 。 +与*具有相同的运算结合性和优先级2)