编译原理复习汇总

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

2、L脚本式语言： Shell 语言语言之间的转换(李静PPT41)高级语言之间的转换一般称为 预处理或转换。高级语言翻译成汇编语言或机器语言称之为 编译。把汇编语言翻译成机器语言称之为汇编。将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之为 交叉汇编。把机器语言翻译成汇编语言称之为反汇编。把汇编语言翻译成高级语言称之为反编译。编译器和解释器编译器源程序的翻译和翻译后的程序的运行是两个不同的阶段。编译阶段：用户输入源程序，经过编译器的处理，生成目 标程序。目标程序的运行阶段：根据要求输入数据，得出结果。解释器(凡是可以采用编译器的地方均可以采用解释器)解释器把翻译和运行结合到一起，编译一

3、段源程序，紧接着就 执行它。这种方式称为解释。解释器的优点(对比与编译器)具有较好的动态特性。具有较好的移植特性。解释器的缺点(对比于编译器)相比于编译器需花费大量的时间。占用更多的内存空间。编译器的工作阶段(结合第二章 6 小点红色部分理解) TOC o 1-5 h z 源程序 -词法分析器-语法分析器-语义分析器-中间代码生成器-代码优化器-目标代码生成器-目标代码工作过程中的每个阶段均采用了 符号表管理器， 出错处理器。编译器各阶段的工作过程(结合第二章 6 小点红色部分理解)源程序通过词法分析器翻译成 记号流 ，记号流通过语法分析产生语法树 ，然后根据语法树来进行适当的语义处理，语义分

4、析产生 符号 表和中间代码 。符号表的格式：标识符，类型，分配的地址。中间代码的格式：操作符，左操作数，右操作数，结果。中间代码的优化：传值的代码可以省略。目标代码生成：生成汇编指令， 格式为：操作数源码 目标 。二元运算： OP source target target := source OP target一元运算： MOVE source target tatget = source。各阶段工作归纳词法分析：根据词法规则识别出源程序的各个记号（ token ） ，每个 TOC o 1-5 h z 记号代表一类单词（lexeme） ，记号的分类如下： （第二章第4 小点）关键字：如var、

5、 begin、 end 等，不做他用，称为保留字。标识符：如x、 y、 z、 sort 等，在源程序中被用作变量名，过程名，类型名和标号等所有对象的名称。（用记号代替）字面量：如60、 Xidian、 University等，一般用于表示常数或字符串常量。 （保留原样）特殊符号 ： =、 * 、 +、 -、 ;等运算符，分隔符（保留原样）。例： var x,y,z:real ; x:= y+z*60; varid1,id2,id3:real;id1:=id2+id3*60;语法分析：得到语言结构并以树来表示。语义分析：考察结构正确的句子是否语义合法。中间代码生成。中间代码优化。目标代码生成。符

6、号表管理：合理组织符号，便于各阶段查找，填写等。出错处理：错误的种类 词法错，语法错，静态语义错，动态语义错。编译器的分析/ 综合模式。（ PPT53）前端（分析） ：语言结构的分析。 （语法和语义分析）后端（综合） ：语言意义的分析与处理。 （代码的生成、优化）中间代码：前段与后端的分解。第二章 词法分析词法分析 ：词法分析是编译过程中将字符流转换成为符号流的一个工作阶段，是编译的第一步操作，其后续工作是语法分析（配合第一章第 11 小点理解） 。词法分析输入源代码。词法分析输出记号流。词法分析需要识别此发错无，即非法的符号、单词。但不识别语法错误。词法分析器的作用源程序由单词组成， 单词是

7、最小的语义单位 。词法分析器的功能：扫描源程序字符流。按照源程序的语法规则识别出各类单词符号。产生用于语法分析的记号序列。填写符号表。辅助功能跳过源程序的注释和空白。把错误信息和源程序联系起来 （错误定位） 。宏预处理。模式（规则） （ patten ） ：将产生和识别单词的规则称为模式（规则） 。记号（ token ） ：按照某个模式识别出来的元素称为记号。 （第一章和本章第 11 小点一同理解）记号 = 记号的类别 + 记号的属性。 （用于识别）记号的类别：记号的类别可以用整形编码来表示。记号的属性：根据记号的类别不同，记号的属性可以用不同的表示方法，如 relation（81） 的属性值

8、为一个有限的可枚举的集合，可以用每个属性值在集合中的位置来表示它。 （课本P16） 。单词（ lexeme） ：被识别出元素自身的价值。 （结合本章第 9 点理解）词法分析器的作用和工作方式:特征：编译器中唯一与源程序打交道的部分。任务： （与第二章第2 点一同理解）滤掉源程序中的无用的部分，如注释，空格，回车等。处理与具体平台有关的输入。识别记号，并交给语法分析器，根据模式识别记号。调用符号表管理器或出错管理器，进行相关管理。工作方式单独一遍扫描。作为语法分析器的子程序。并行方式。输入输出结果的分析（结合第一章9、 10 小点理解）源程序-词法分析期-记号流源程序-词法分析器-记号流-语法分

9、析器-语法树。输入缓冲区设置缓冲区的必要性：超前搜索： 为了得到某一个单词符号的确切性质 ，需要超前扫描若干个字符。方便实现读字符和退字符操作，提高词法分析器的效率。字符串 ：从词法分析的角度看程序语言设计，他是由几号组成的集合（第二章第 4 小点）定义：语言L是有限字母表汇上有限长度字符串的集合。字母表是 组成字符串的所有字符的集合。即字符串中的所有字符取自字母表。两个有限： （ 有序集合 ） :因为计算机所能表示的字符个数和字符串长度是有限的。字母表是有限的，即字母表中的元素是有限多个。字符串长度是有限的，即字符串中字符的个数是有限多个的。字符串和集合的基本概念： （课本P19）语言概述：

10、 （第一章第3、 4 小点理解）语言 形式化的内容提取：是字和组合字的规则语言：满足一定条件的句子集合。句子：满足一定规则的单词序列单词：满足已定规则的字符。 （结合本章第 5 点理解）程序设计语言 形式化的内容提取：组成程序的所有语句的集合。程序：满足语法规则的语句序列。语句：满足语法规则的单词序列。单词：满足词法规则的字符串。 （结合本章第 5 点理解）描述形式 文法语法 语句语句的组成规则描述方法：BNF范式，语法图词法 单词 （结合本章第 5 点理解）单词的组成规则。描述方法：BNF范式，正规式。（结合下一小点理解）正规式和正规集1）正规式：令一个有限字母表，则 *的正规式及其表示的集

11、合递 归定义为：e是正规式，他表示集合 L （ e ） = e 若a是 J的字符，则a是正规式，他表示集合L （a） = a若正规式r和s分别表示集合L （r）和L （s）,则r|s是正规式，表示集合L （r）并L （s）。rs 是正规式，表示集合L（ r ） L（ s） 。r* 是正规式，表示集合L（ r ） * 。（ r ）是正规式，表示的集合仍是L（ r） 。 （加括号改变优先级，结合性）正规集：可用于正规式描述的语言称为 正规语言或正规集。正规式计算的优先级（具有左结合的性质）从高到低排列：闭包运算，连接运算，或运算。正规式中不必要的括号可以被省略。正规式和正规集之间的关系是多对一的关

12、系。正规式的等价 ：若正规式P 和 Q 表示了同一个正规集，则称P 和 Q是等价的，即为 P=Q正规式公理（课本P21）记号的说明 （用正规式来描述） （本章第 4小点） ：正规式可以严格规定记号的模式，用正规式说明记号的公式为：记号 = 正规式（记号是正规式）例如： id = a（a|b） 可以读作“ id 定 义为 a（a|b） ” （简称为正规式）通常在不引起混淆的情况下，也把说明记号的公式简称为正规式，或者规则。记号的识别 有限自动机模式的描述正规式记号的识别有限自动机（确定，不确定）不确定的有限自动机定义：NFA是一个五元组：M = （S, E, move, s0, F）A. S 是

13、有限个状态的集合。B.，是有限个输入字符（包括 ）的集合。Move 是一个状态转移函数， move（ si ， ch） = sj 表 示，当前状态si下若遇到输入字符ch,则转移到状态 sj。s0是唯一的初态（称为开始状态）F是终态集，他是S的子集，包含了所有的终态。NFA的表示方式A.状态转换图：用一个有向图直观表示NFA。终态用一个双圈来表示。B. 状态转换矩阵：用一个二维数组来直观表示NFA。NFA识别记号（课本 P24-25 , PPT29NFA识别记号存在的问题：只有尝试了全部可能的路径，才能确定一个输入序 列不被接受，而这些路径的条数随着路径长度的增长而成指数增长。识别过程中存在大

14、量回溯，时间复杂度和输入序列呈指数级增长。确定的有限自动状态机（DFA）定义：DFA是NFA的一个特例A.没有状态具有e状态转移，即状态转换图中没有标记e 的边。B.对每一个状态s和每一个字符a,最多有一个下一个状 态。DFA的特征：消除了 NFA的不确定性。A.定义move （si, a）函数是一对一的。转换图：从一个节点出发的边上标记均不相同。 （没有重复字符的状态转移）C.转换矩阵Msi, a是一个状态。（NFA可以为状态集）D.字母表不包括e。有限自动机的等价：若有限自动机M 和 M 识别同意正规集，则成 M 和 M 是等价的，即为M=M 。简化正规式描述正闭包：若r 是表示 L（ r

15、 ）的正规式，则 r 的正闭包是表示（ L（ r ） ）的正闭包的正规式；r+ = rr* = r*r, r* = r+| 0 +与*具有相同的运算结合性和优先 级2）可缺省：r? = r| 字符组：枚举： 【abc】 = a|b|c分段非字符组：若r是一个字符组形式的正规式，则Ar是表示汇-L （r）的正规式。5）用：若r是字符链运算的正规式，则用“ r”和r等价。从正规式到词法分析器构造词法分析器的一般方法和步骤：用正规式对模式进行描述。为每一个正规式构造一个NFA,他识别正规式所表示的正规集。将构造出的NFA转化为等价的DFA,这一过程也成为确定化。 优化DFA,使其状态数最少，这一过程

16、称为最小化。从优化的DFA构造词法分析器。从正规式到 NFA（ thompson 算法） 。对于字母表r,将其分解为最基本的正规式。对于8 , NFA为s0为初态，f为终态，该NFA接收 8 对于 J的任意一个字符a, NFA为s0为初态，f为终态, NFA接受 a。若正规式N （p）和N （q）是正规式p和q的NFA,则： （课本P27） 。3）从 NFA至U DFANFA标识记号的 并行”方法。避免回溯。由于并行的方法在每试探一步时，考虑了所有的下一步状态转移，因此走的每一步都是确定的。采用并行的方法，核心思想是将不确定的下一状态确定化。确定化的两个步骤：消除e状态转移；e的闭包。消除多余

17、一个的下一个状态转移。算法（课本P30）DFA最小化（课本35）第三章 语法分析词法分析：元素是字母表，组成字符串，线性结构，单词的集合。语法分析：元素是终结符，组成句子，树结构（分析树） ，句子的集合。1）语法规则：上下文无关文法（子集一一L做法或LR文法）2）语法分析：下推自动机（LL或LR分析器），自上而下（预测分析） 和自下而上（移进归约）分析语法错误的处理原则源程序中可能出现的错误：词法错误：非法字符或拼写错误的关键字，标识符等。语法错误：语法结构错误，缺少分号等。静态语义错误：类型不一致，参数不匹配等。动态语义错误：逻辑错误，无穷递归，变量为 0 做处暑等等。语法错误处理的目标清楚

18、而准确的报告错误的出现。迅速的从每个错误中恢复过来。不应使对语法正确源程序的分析速度降低太多。语法错误的基本恢复策略紧急方式恢复：抛弃若干输入，直至遇到同步记号。短语级回复出错产生式全局纠正上下文无关文法（CFG）1）定义：CFG是一个四元组G= （N, T, P, S）,其中：N 是非终结符的有限集合。T是终结符的有限集合，且 N交T为空集。P 是产生式的有限集合。A-a,其中A属于N （左部），a属于（N并T）的闭包（右部），若a= e ,则称A-e为空的产生式S是非终结符由产生式集表示CFG 前提：若文法正确，第一个产生式的左部是文法开始符号 S, 则N是出现在产生式左边符号的集合，T是

19、所有不出现在产生 式左边符号的集合。3）产生式的一般读法：读作 巡义为”，或者可导出”。4）终结符与非终结符在读写上的区别。大写英文字母A、B、C表示非终结符。小写字母表示终结符。小写希腊字母表示任意文法符号序列。5）产生式的缩写形式（产生式以非终结符命名）CFG产生语言的基本方法（PPT9 :通过推导的方法产生语言 =1）定义3.2 （PPT10：直接推导。2）强调的两点：推导具有自反性，推导具有传递性。3）定义3.3（PPT10：由CFG G所产生白语言L（G液定义为：L（G） = | SAco and 5,L（G称为上下文无关语言（ Context Free Language, CFL,

20、称 为句子。若S=a , aC （NUT）*,则称a为G的一个句型。4）定义3.4:在推导过程中，若每次直接推导均替换句型中最左边的 非终结符，则称为最左推导，由最左推导产生的句型被称为左句 型。推导，分析树，语法树。1）分析树的性质（具体语法树）：根由开始符号所标记。每个叶子都由一个终结符，非终结符，或e标记。每个内部结点由一个非终结符标记。若A是某内部节点的标记，且 X1, X2,，Xn是该节点从左到右所有孩子的标记，则 AX1X2.Xn是一个产生式。若 A一 则标记为A的结点可以仅有一个标记为e的孩子。2）分析树与语言和文法的关系：每一直接推导（每个产生式），对应一颗仅有父子关系的子树，即产生式左部非终结符 “长出 ”右部的孩子。分析树的叶子，从左到右构成G 的一个句型。若叶子仅由终结标记，则构成一个句子。最左最右推导的中间过程对应的分析树可能不同，因为句型不同，但最终的分析树相同，因为最终是同一个句子。分析树既反映了产生句型的推导过程，有反映了句型的结构。语法树（抽象语法树）定义3.6:对CFG G勺句型，表达式的语法树被定义为具有下述 性质的一棵树。根和内部节点由表达式中的操作符标记。叶子由表达式中的操作数标记。用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。7. 二义性和二义性的消除二义性：若G 对同一句子产生不止一颗分析树，则称G 为二义的