编译复习 精品.doc

1 编译程序：把用高级程序设计语言书写的源程序，翻译成等价的计算机汇编语言或机器语言书写的目标程序的翻译程序。2 编译的各个阶段1 词法分析词法分析目标代码生成代码优化语义分析及中间代码生成语法分析单词记号流字符流语法树中间表示中间表示目标机器代码任务：输入源程序，对构成原程序的字符串进行扫描和分解，识别出一个个单词。规则：词法规则2 语法分析任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位。规则：语法规则3 语义分析及中间代码生成任务：对语法分析所识别出的各类语法单位，分析其含义，并进行初步翻译，产生中间代码。规则：语义规则4 代码优化任务：对前端产生的中间代码进行加工变换，以期待在最后能产生更为高效的目标代码。规则：等价变换规则5 目标代码生成任务：把经过优化产生的中间代码变成特点机器上的低级语言代码。没有规则3 前端、后端、趟（遍）前端：分析部分揭示了程序的基本元素和它们所形成的层次结构，定义它们的含义，建立起源程序的中间表示，分析部分通常被称为前端。后端：综合部分从源程序的中间表示建立起和源程序等价的目标程序，他经常被称为后端。趟（遍）：对源程序或源程序的中间结果从头到尾扫描一次（读一个输入文件和写一个输出文件），并做加工处理，产生新的中间结果或最终结果的过程。4 词法分析词法记号1 定义：由记号名和属性值构成的二元组2 分类：常数、分界符、关键字、标识符、运算符词法单元：源程序中匹配一个记号模式的字符序列。串：字母表中的串是该字母表符号的有穷序列。 空串：是长度为0的特殊串。语言：字母表上的一个串集。*：闭包，+：正闭包，|：选择运算，：连接运算正规式：正规式是描述程序语言单词的表达式正规集：正规式表示的语言叫做正规集。不确定有限自动机：S：一个有限状态的集合；：一个输入符号的集合；move：一个转换函数，把状态和符号两元组映射到一个状态集合。S0：唯一的开始状态；F：接受（终止）状态的集合；确定有限自动机： P：单值部分函数5 语法分析及中间代码生成文法：乔姆斯基(Chomsky)把文法分成四种，即0型、1型、2型、3型。0型(短语文法)：文法，左部的长度1；P为产生式的有限集合1型(上下文有关文法)：G的任何产生式都满足；2型(上下文无关文法)：G的任何产生式的形式，3型(正规文法)：G的任何产生式或的形式，等价：如果两个文法产生同样的语言，则称这两个文法等价；句子：句子是只含终结符的句型；有文法GS，若，且，则称是文法G S的句子。句型：有文法G S， 若，且则称是文法G S的句型。规范推导（最右推导）：每步都代换最右边非终结符的推导。最左推导：每一步都代换句型中最左边非终结符的推导。二义性：一个文法，如果存在某个句子有不止一棵分析树与之对应，那么称这个文法是二义的。LL(1)文法：若文法的任何两个产生式都满足下面两个条件：12把满足这两个条件的文法叫做LL(1)文法。第一个L代表从左向右的扫描，第二个L表示产生最左推导，1表示向前搜索一个输入符号。规范归约（最左归约）：规范推导（最右推导）的逆过程；句柄：句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步。短语：若文法GS，是文法G的一个句型，如果有：则称是句型相对于非终结符的短语。直接短语：如果有则称是句型相对于规则的直接短语。活前缀：右句型的前缀，该前缀不超过最右句柄的右端。LR(1)文法：L表示从左到右扫描，R表示最右推导的逆过程。LR分析器的格局：是二元组，第一个成分时栈的内容，第二个成分时尚未扫描的输入。语法制导定义的形式：v 基础文法v 每个文法符号有一组属性v 每个文法产生式有一组形式为的语义规则，其中f 是函数，b和是该产生式文法符号的属性： 综合属性：如果b是A的属性， 是产生式右部文法符号的属性或A的其它属性，那么b称为A的综合属性。 继承属性：如果b是产生式右部某个文法符号X的属性，是A的属性或右部文法符号的属性，那么b称为X的继承属性。属性文法：指语义规则函数无副作用的语法制导定义。S属性定义：仅仅使用综合属性的语法制导定义。L属性定义：如果每个产生式的每条语义规则计算的属性是A的综合属性；或者是的继承属性，但它仅依赖： 该产生式中Xj左边符号的属性； A的继承属性S属性定义属于L属性定义语法制导翻译方案：首先根据基础文法构造输入的分析树；按上面讨论的方法构造属性依赖图；对依赖图的结点进行拓扑排序，得到语义规则的计算次序；按这个次序计算属性，得到输入串的翻译。语义规则的计算方法：分析树方法、基于规则的方法、忽略规则的方法安全语言：如果一个程序的运行不可能引起不会被捕获错误的出现，则称它是良行为的；所有合法程序都是良行为的语言叫做安全语言。返回值参数控制链访问链保存的机器状态局部数据临时数据活动记录：过程一次执行所需布局信息用一块连续的存储区来管理，这块存储区叫做活动记录或帧。 一般的活动记录包括：生存期：从过程体开始执行到执行结束的时间。存储分配策略：静态分配策略栈式分配策略堆式分配策略程序块：本身含有局部变量声明的语句。悬空引用：引用某个已被回收的存储单元叫做悬空引用。中间代码生成的表示方法：后缀表示、图形表示、三地址代码、静态单赋值形式表示布尔表达式的值的方法：完全计算、短路计算6 目