编译原理——大学计算机专业课程要点.

1、编译原理复习资料 ATSA89 2010-6-24第一章 编译系统概述1. 编译程序的工作过程词法分析 执行词法分析任务的程序称为词法分析器。任务：字符串形式的单词 编码形式的单词内部码（二元式） 依据：语言的构词规则语法分析 执行语法分析任务的程序称为语法分析器。任务：检查源程序的语法结构是否正确 依据：语言的语法规则语义分析 执行语义分析任务的程序称为语义分析器或中间代码产生器。任务：建立符号表和常数表，记录源程序中标识符属性和常数值，根据语言的语义规定生成中间代码。 依据：语言的语义内涵目标代码生成 执行目标代码生成的程序称为目标代码生成器。任务：中间代码 目标代码（机器指令或汇编语言）

2、 依据：目标机器的系统结构2. 编译程序与解释程序源程序：用程序设计语言书写的程序 源语言：源程序设计语言翻译程序：将源程序译成逻辑上等价的目标程序的程序目标语言：机器语言(二进制数)，也可以是汇编语言目标程序：经翻译程序加工后用目标语言表示的程序编译程序：也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。 解释程序：对源程序的加工过程是边解释边执行3. 符号表 符号表用于记录源程序中出现的标识符(Identifier)，一个标识符往往具有 一系列的语义值，它包括标识符的名称、标识符的种属、标识符的类型、标识符值的存 放地址等等。每个标识符在符号表中有一项记录，用

3、于记录标识符的各种语义值，而在四元式中填写的是标识符在符号表中的记录地址，通常称为符号表入口4. 编译程序可以发现源程序的错误类型错误类型 词法错误（可在词法分析阶段发现）语法错误（可在语法分析阶段发现）语义错误（可在语义分析阶段发现）出错处理 一旦发现错误，暂停编译程序工作，指出错误的地点和类型。在发现错误后，不中断编译程序工作。采取某些措施，使得源程序的编译工作可继续下去，尽可能发现源程序中比较多的错误编译程序前端组成：词法分析器、语法分析器和中间代码产生器特点：依赖于被编译的源语言，输出结果用中间代码描述，和目标机器无关。编译程序后端组成：目标代码生成器特点：和源语言无关，以中间代码形式

4、的源程序为输入进行处理，输出结果依赖于目标机器。第二章 词法分析1. 词法分析器：执行词法分析任务的程序2. 单词类型及二元式编码：单词类型基本字、标识符、常数、运算符、界符单词的性质l 个数确定和不确定l 单字符或多字符构成单词二元式编码经词法分析后，单词用二元式 (code,val) 表示。l code表示单词的种别，用整数码表示，在语法分析时使用；单词的语法特性。l val表示单词的值，在本书中用字符串表示，在语义分析时使用；单词语义特性。编码原则通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符一种。 3. 预处理工作的主要内容：删除注释删除续行符，以及后续换行符(0A

5、H)。换行符、TAB和空格具有界符作用，预处理时通常予以保留大多数语言（除C语言）不区分大小写，可在预处理时，将大写字母变换成小写字母，或相反，以方便后续处理。对于受书写格式限制的语言，还应识别标号区，正确给出语句标号4. 遍：由外存获得前一遍的工作结果(对于第一遍而言，从外存获得源程序)，完成它所含 的有关阶段工作之后，再把结果存于外存。5. 正规集：是程序设计语言单词集的抽象6. 正规式：是程序设计语言构词规则的抽象；二个正规式是相等的，当且仅当二个正规式所表示的正规集是相等的；7. 构造正规式的非确定有限自动机一个非确定的有限自动机M是一个五元式M=（S，f，S0，Z）l S是一个有限集

6、，它的每一个元素称为状态。l 是一个有穷字母表，它的每个元素称为一个输入字符。l f是一个从S*到S的子集映照，即，f：S*2S（多值函数）2S表示幂集，若S=0，1，则2S =，0，1，0，1。l S0S，是一个非空初态集，即NFA的初态不一定唯一。l ZS，是一个终态集。8. 非确定有限自动机的确定化一个非确定的有限自动机M是一个五元式M=（S，f，S0，Z）l S是一个有限集，它的每一个元素称为状态。l 是一个有穷字母表，它的每个元素称为一个输入字符。l f是一个从S*到S的子集映照，即，f：S*2S（多值函数）2S表示幂集，若S=0，1，则2S =，0，1，0，1。l S0S，是一个非

7、空初态集，即NFA的初态不一定唯一。l ZS，是一个终态集。9. 正规式与确定有限自动机的等价性对于上的每个正规式V，存在一个上的确定有限自动机M，便得L(V)=L(M)。VNFA将V表示成拓广NFA根据三条规则对V进行分裂，直至每条弧上的标记为上的一个字符或。NFADFAI的闭包IaNFA确定化算法10.自动生成过程构造描述每个单词的正规式Pi(1iN)。根据正规式Pi构造NFA Mi(1iN)，假定初态均为0。在构造NFA Mi的同时，逐步并且最终形成识别全部单词的NFA M。NFA M确定化重新标记，构造DFA M。11.构造下列正规式相应的DFA（状态转换矩阵形式）1(0|1)*101

8、第三章 程序设计语言的语法描述1. 文法：对语言结构的定义和描述。2. 语法树：句子结构的图形表示法。非叶结点称为语法单位，在形式语言中称为非终结符。处于根结点位置的结点又称为开始符号。叶结点称为单词符号，在形式语言中称为终结符。语法规则的符号：“”读作“定义为”,有些书表示“：=”；3. 产生式：规则在形式语言中的名称；“”左边的符号串称：产生式左部；右部称产生一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。 产生式是定义语法单位的一种书写规则。4. 递归文法l 递归的定义：定义某事物，又用到该事物本身。l 递归规则（直接递归）：在规则的左部和右部

9、有相同的非终结符。l 递归文法：含有递归规则和间接递归的文法，称为递归文法。l 引入递归文法的意义利用递归文法，可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。5. 判断句型（句子）是否符合文法的方法l 利用产生式推导形式语言的奠基人乔姆斯基将文法分为4种类型，它们是：l 短语文法（0型文法）；上下文有关文法（1型文法）；上下文无关文法（2型文法）正规文法（3型文法）一个文法G是一个四元式(VT,VN,S,VP)，其中VT是一个终结符的非空有限集，终结符通常用小写字母表示。VN是一个非终结符的非空有限集，非终结符通常用大写字母表示。S是一个特殊的

10、非终结符（SVN），称为开始符号。 VP是一个产生式（规则）的有限集合，每个产生式的形式是A ，其中AVN，(VTVN)*。6. 句型、句子、语言假定G是一个文法，S是它的开始符号。如果S=*,则称是G的一个句型。仅含终结符的句型是一个句子。文法G所产生的句子的全体称为文法的语言。记作L(G)。7. 习题2、3第四章 自上而下的语法分析1. 自上而下的语法分析方法的基本思想从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。自上而下语法分析方法的基本思想是:从文法的开始符号 出发.不断建立最左直接推导 试图构造一个推导序列, 最左直接推导,

11、出发.不断建立最左直接推导,试图构造一个推导序列,最终由 它推导出与输入符号串相同的符号串. 它推导出与输入符号串相同的符号串. 符号串2. 带回溯的自上而下的语法分析存在的问题对于左递归文法定义的语言，不能采用自上而下的语法分析法。存在虚假匹配，回溯不可避免编译程序的语法分析和语义分析通常是同时进行的。当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。3. first集 是文法G的任一符号串（包括候选式），(VTVN)* first()=aa，aVT若，则规定fir

12、st()。 4. follow集设S是文法开始符号，对于文法的任何非终结符A follow(A)=aSAa，aVT 特别是，若SA，规定#follow(A)。5分析法：是由一张分析表和一个控制程序构成。6.分析表构造规则构造所有候选式的first集，构造所有非终结符的follow集。对于文法的每个产生式A执行和。对于每个终结符afirst()，把A加至MAa。若first()，则对于每个终结符bfollow(A)，把A加至MAb。把所有未定义的MAc标上“出错标志”（cVT）。7.LL（1）文法的含义预测分析法是由分析表和控制程序构成的，控制程序与文法无关，分析表随文法而异。在预测分析表中，若

13、某一单元持有一个以上产生式，则称该预测分析表含多重定义，多重定义使得控制程序无法工作。一个文法，若它的预测分析表不含多重定义，则称该文法是LL(1)文法、分析表为LL(1)分析表。LL是指从左到右的左分析器。“1”表示向前看一个符号；一个文法是LL(1)的，对于文法的每一个非终结符的任何两个不同候选式(A|)，下述条件成立：l first()first()=l 若，则first()follow(A)=二义文法不是LL(1)文法二义文法在预测分析法中的应用第五章 自下而上的语法分析什么是自下而上的语法分析：从叶结点出发，步步向上归约,直到根结点。1. 句型的短语、直接短语、句柄短语设是文法G的一

14、个句型。如果有S=A 且 A=，则称是句型中相对于非终结符A的短语，其中、(VTVN)*。直接短语（简单短语）设是文法G的一个句型。若有S=A且A=，则称是句型中相对于非终结符A（或称相对于规则A）的直接短语，其中、(VTVN)*。句柄 一个句型的最左面的直接短语称为该句型的句柄。 2. 规范规约:在规约过程中始终对句柄进行规约而形成的序列；也称最左归纳。3. 规范句型:由最左规约所得到的句型。4. LR分析法的基本原理LR分析法严格执行最左归约，每次按句柄归约。LR分析法把句柄的识别过程划分为若干状态，每个状态只识别句柄的一个符号，若干个状态就可识别句柄的一部分左端符号。5.前缀：字的任意首

15、部；6.后前缀：指规范句型的一个前缀，这种前缀不包含句柄之后的任何符号。因为在它的右边增添一些终结符号之后，就可以构成一个规范句型。产生式A只对应一个项目A7.LR(0)分析表之前的预备工作引入产生式SS，将文法拓广成G。对G的产生式进行编号。构造文法G的状态转换函数GO(I,X)和项目集规范族C。第六章 语法制导翻译和中间代码生成语法制导翻译的含义语法分析和语义分析的区别语义分析主要工作建立符号表和常数表。诊察和报告源程序中的语义错误。根据语言的语义产生中间代码（或机器指令），或直接解释执行。6.1 语法制导翻译概述语法制导翻译方法简介为每一个产生式配一个语义子程序。在语法分析过程中，当一个产生式获得匹配或用于归约时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。实现方法（以SLR分析器为例）分析表不变改造工作栈l 状态栈l 符号栈 l 单词值栈：用于保存单词的值（字符串形式）。l 语义栈：用于记录分析过程中需保留的语义值。例，值（val）、地址（addr）、种属（cat）、类型（type）等。修改总控程序l 在移进时，除移进状态和单词的种别外，还需