编译原理复习总结.ppt

第一章 引论,编译程序是现代计算机系统的基本组成部分之一，许多计算机系统中，都会含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。 一、什么是编译程序 掌握编译程序的概念。它是一种把由高级程序设计语言写出的源程序翻译成由机器语言组成的目标文件的程序或软件。可以将编译程序看作一个“黑盒子”，负责将由高级语言编写的源程序翻译成低级语言表示的目标程序。 理解高级语言程序的处理过程。一个典型的程序时间程序的典型处理过程如下图所示。,二、编译过程概述 一个编译程序的整个过程是划分成阶段进行的，可划分为：源程序词法分析语法分析语义分析中间代码生成代码优化目标代码生成目标程序。其中表格处理和出错处理贯穿整个过程。如图所示。,词法分析阶段：编译过程的第一阶段。任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。单词间的空格被滤掉。 语法分析：第二阶段。在词法分析的基础上将单词序列分解成语法短语，如“程序”，“语句”，“表达式”等。语法短语也叫语法单位，可表示成语法树。语法分析所依据的是语言的语法规则，通过语法分析确定整个输入串是否构成一个语法上正确的程序。 语义分析阶段：审查源程序有无语意错误，为代码生成阶段收集类型信息。比如它的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序就报错。例如，不能用实数作数组下标而用了就报错。 中间代码生成：在语法分析和语意分析阶段的工作以后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫中间语言或中间代码。 “中间代码”是一种结构简单，含义明确的记号系统，可设计为多种多样的形式，重要的色痕迹原则有两点：一是容易生成，二是容易将它翻译成目标代码。多数编译程序使用了一种近似“三地址四指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运算对象1，运算对象2，结果）。 代码优化：对前阶段生成的中间代码进行变换或改造。目的：使生成的目标代码高效，即省时间、省空间。 目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，涉及到硬件系统功能部件的运用、机器指令的选择，各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。,三、编译阶段的组合,编译过程中的阶段划分是编译程序的逻辑组织。有是把编译过程分为前端（front end）和后端（back end）。 前端：这些阶段的工作依赖于源语言而与目标机无关，通常这些阶段包括词法分析，语法分析，语意分析和中间代码生成，某些优化工作也可以放在前端，还包括与前端每个阶段相关的出错处理工作和对符号表管理工作。 后端：指那些依赖于目标机而一般不依赖于源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关的出错处理工作和对符号表管理工作。,第二章 高级语言,一、文法和语言的形式定义 掌握文法的形式定义。 文法G定义为四元组(Vn，VT，P，S)。其中Vn为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；Vn，VT和 P是非空有穷集。称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 Vn和VT不含公共的元素，即VnVT= 通常用V表示VnVT，V称为文法G的字母表或字汇表。 其中规则，也称重写规则、产生式或生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称为规则的右部。,二、文法的类型,文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。 设G=(VN，VT，P，S)，如果它的每个产生式是这样一种结构：( VNVT )*且至少含有一个非终结符，而( VNVT )*，则G是一个0型文法。 设G=(VN，VT，P，S)为一文法，若P中的每一个产生式均满足| ，仅仅S除外，则文法G是1型或上下文有关的。 设G=(VN，VT，P，S)，若P中的每一个产生式满足：是一非终结符，( VNVT )*则此文法称为2型的或上下文无关的。有时将2型文法的产生式表示为形如：A其中AVN，也就是说用取代非终结符A时，与A所在的上下文无关，因此取名为上下文无关文法。 设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是AaB或Aa，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法。,三、上下文无关文法及其语法树,掌握上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式，描述各种语句等等。 给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树满足下列4个条件： 每个结点都有一个标记，此标记是V的一个符号。 根的标记是S。 若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在Vn中。 如果结点n的直接子孙，从左到右的次序是结点n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式。,四、句型的分析,句型分析是识别一个输入符号串是否为语法上正确的程序的过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。 掌握自上而下的识别算法和自下而上的识别算法。,第三章 词法分析,词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。,一、掌握词法分析程序的设计的主要思想,了解词法分析程序与语法分析程序的接口方式：可以将词法分析作为独立的一遍进行处理，但更常用的方法是将词法分析程序设计为一个子程序，当语法分析需要单词时，就调用该子程序。 了解词法分析程序的输出：词法分析程序的功能是读入源程序，输出单词符号。单词符号一般可分成5种：保留字，标识符，常数，运算符和界符。 将词法分析工作从语法分析中分离出来的原因：使整个编译程序的结构更简洁、清晰和条理化；编译程序的效率会改进；增强编译程序的可移植性。,二、单词的描述工具 掌握正规式的定义以及正规式服从的代数规律。 熟练掌握正规文法和正规式的等价性以及转换规则。 三、单词的识别工具 掌握有穷自动机的定义和分类。掌握确定有穷自动机（DFA）的定义，并熟悉其状态图的表示和矩阵表示；掌握不确定有穷自动机（NFA）的定义，并熟悉NFA的状态图表示和矩阵表示。 掌握将NFA转化为DFA的算法子集法。 确定有穷自动机的化简与有穷自动机的等价转换。,第四章 自顶向下语法分析方法,语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。需要掌握确定的自顶向下分析思想，以及该分析方法对文法的要求。,一、 理解确定的自顶向下分析思想,确定的自顶向下分析方法，是从某文法的开始符号出发，考虑如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或如何构造一棵相应的语法树，其末端结点以从左向右的顺序连接正好为给定的输入符号串，则所给的输入符号串为该文法的句子。,二、 掌握LL（1）文法的判别步骤,一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法。 某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。 掌握LL(1)文法的定义。熟练掌握FIRST集、FOLLOW集和SELECT集的计算方法。,三、某些非LL（1）文法到LL（1）文法的等价交换,理解两种非LL（1）文法的等价变换方法，特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL（1）文法的条件。,四、确定的自顶向下分析方法,掌握递归下降子程序的特点以及用PL/0程序分析PL/0编译程序的语法分析过程。 掌握如何构造预测分析表； 能用预测分析方法判断给定的输入符号串是否是该文法的句子。,第五章 自底向上语法分析方法,自底向上分析法，也称移进-归约分析法。它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，(该句柄对应某产生式的右部)，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。,算符优先分析法,对给定的文法能够判断该文法是否是算符文法 对给定的算符文法能够判断该文法是否是算符优先文法 对给定的算符文法能构造算符优先关系表，并能利用算符优先关系表判断该文法是否是算符优先文法。 能应用算符优先分析算法对给定的输入串进行移进-归约分析，在分析的每一步能确定当前应移进还是归约，并能判断所给的输入串是否是该文法的句子。 了解算符优先分析法的优缺点和实际应用中的局限性。,第六章 属性文法和语法制导翻译,一、掌握属性文法、综合属性、继承属性、S-属性文法、L-属性文法和语法制导翻译的概念 （1）属性文法 形式上讲，一个属性文法是一个三元组，A（G，V，F），其中G是一个上下文无关文法；V是有穷的属性集，每个属性与文法的一个终结符或非终结符关联，这些属性代表与文法符号相关信息，比如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。F是关于属性的属性断言或一组属性的计算规则（称为语义规则）。断言或语义规则与一个规则式关联，只引用该规则式左端或右端的终结符或非终结符关联的属性。 （2）综合属性和继承属性 在一个属性文法中，对于所有产生式12n，的属性计算仅依赖1,n的属性，则该属性称之为综合属性；或者对于所有产生式12n，Xi的属性计算仅依赖A,1,i-1的属性，则该属性称之为继承属性。 （3）S-属性文法和L-属性文法 S-属性文法是仅包括综合属性的属性文法；L -属性文法是包括综合属性和继承属性的属性文法。,二、掌握语法制导翻译的基本思想,（1）语法制导翻译 在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的过程称作语法制导翻译。 一般的语法制导翻译过程如下： 分析输入符号，建立语法分析树； 从语法分析树得到描述结点属性之间的依赖关系和计算次序； 按照语义规则计算属性值。 （2）S-属性文法和自底向上的翻译 对于S-属性的定义，其属性的计算通常采用自底向上的分析方法，即用哪个产生式进行归约，便执行那个产生式所对应的语义规则，以计算属性的值。 （3）L-属性文法和自顶向下的翻译 对于L_属性定义，其属性的值可以按照深度优先的次序计算。也就是说，可以直接地使用翻译方案实现。 L_dfvisit(n) for m=从左到右的n的每个子节点 do 计算m的继承属性； L_dfvisit(m); 计算n的综合属性。 ,第七章 语义分析和中间代码生成,掌握几种典型的中间代码形式 编译程序所使用的中间代码有多种形式。常见的有逆波兰式、三元式、四元式和树形表示。 （1）逆波兰式 逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。 这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。,（2）三元式和树形表示 另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式。每个三元式由三个部分组成，分别是：算符op，第一运算对象ARG1和第二运算对象ARG2。运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。 例如a:=b*c+b*d的表示为： （1）（*， b，c） （2）（*， b，d）（3）（+ （1）， （2） （4）（ （2）， a） 树形表示是三元式表示的翻版。例如上述的三元式也可表示成下面的树形表示：,（3）四元式 四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG