《编译原理资料.docx》由会员分享，可在线阅读，更多相关《编译原理资料.docx（51页珍藏版）》请在金锄头文库上搜索。
1、 编译原理资料第一章n 1.编译器概念：从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言-source language）书写的程序翻译成另一种语言（称作目标语言-target language）书写的等价的程序。n 2.编译的逻辑过程：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、机器代码优化。n 3.词法分析（又称线性分析或扫描）功能：从左至右读源程序（字符流），识别单词符号（又称记号token）源程序字符序列 单词符号序。例：position := initial + rate * 60 单词类型 单词值 单词类型 单词值 标识符1(id1
2、) position 标识符3(id3) rate 算符(赋值) := 算符(乘) * 标识符2(id2) initial 整数 60 算符(加) +n 4.语法分析（又称解析）功能：层次分析依据：源程序的语法规则 （例：P 6-73）单词符号序列 分析树（或语法树-） 分析树 语法树（分析树的压缩示）n 5.语义分析功能：语义检查，即验证语法结构合法的程序是否在语义上正确（程序的各个组成部分组合在一起是否有意义）。收集代码生成阶段需要的语义信息类型检查与类型转换分析树带语义（注释）的树n 6.中间代码生成功能：生成源程序的中间表示。三地址代码（three address-code）带语义（注
3、释）的树 中间代码 7.代码优化功能：对中间代码进行优化（提高时间与空间效率）8.代码生成功能：生成目标代码机器代码、可重定位的机器代码、汇编语言代码n 9.符号表管理(占编译的大部分时间)功能：管理分析过程中得到的源程序中的标识符的各种信息记录源程序中使用的标识符收集每个标识符的各种属性信息，包括类型、作用域、存储分配信息n 10.出错处理功能：检查错误的位置、检查错误的性质（词法、语法、语义）、错误恢复n 11.一个例子语句的完整编译过程 书本P4页n 12.前端与后端(把编译程序分成前端和后端两部分)前端：只依赖于源程序，独立于目标机器. 生成中间代码后端：依赖于目标机器，与源程序无关，
4、只与中间语言有关.从中间代码生成目标代码好处：提高开发编译器的效率:(1)取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器;(2)不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）.n 13.遍（Pass）对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示。每一遍的输入是上一遍的输出，第一遍的输入是源程序正文，最后一遍的输出是目标代码。遍数多：编译器结构清晰，但时间效率不高；遍数少：编译速度快，但对机器的内存要求高。n 14. 其他（1世界上第一个编译器是用机器语言开发的 。（2词法分析
5、器自动生成程序 LEX （3预处理器：删除注释、宏展开、处理包含文件、语言扩充。 （4一个语言处理系统 书本P2页（5汇编器：处理汇编语言代码，产生可重定位的机器代码（6装配器和连接编辑器：将多个可重定位机器代码文件连接装配成一个可执行机器代码文件。第二章：n 1.主要章节内容：串和语言、文法和语言的定义、文法和语言的分类、分析树与句型n 2.字母表：字母表是符号的非空有穷集合，用表示；符号：可以相互区别的记号（元素）；不同的语言有不同的字母表：汉语汉字;英语26个英文字母.n 3.符号串：符号串是由字母表中的符号所组成的有穷序列.例如： =a,b a, b, aa, ab, aabba都是上
6、的符号串;是任何上的符号串在语言理论中，符号串又称为:句子、字。（1符号串的长度：符号串中包含符号的个数；符号串 s 的长度记为 |s|。例：对于字母表a,b,c，aab 是其上的一个符号串，| aab |=3注意：空符号串，|=0（2符号串的前缀、后缀、子串：前缀：移走符号串 s 尾部的零个或多于零个符号得到的符号串例如： b是符号串banana的一个前缀后缀：删去符号串 s 头部的零个或多于零个符号得到的符号串例如： nana是符号串banana的一个后缀子串：从 s 中删去一个前缀和一个后缀得到的符号串例如：ana是符号串banana的一个子串* 对于每个符号串s，s和两者都是符号串 s
7、的前缀，后缀和子串符号串的真前缀、真后缀和真子串非空。n 4.语言：某个字母表上的符号串的集合。例:汉语所有符合汉语语法的句子构成的集合；PASCAL语言所有合法的PASCAL程序构成的集合；注意：空集 、 F 和的不同（1串的运算：1.连接：符号串x、y的连接，是把 y 的符号写在 x 的符号之后得到的符号串 xy。如 x = ab, y = cd 则 xy = abcd 注：=2.方幂：符号串自身连接n次得到的符号串n 定义为 n个 1 =, 2 =，注：0 =（2语言的运算：语言是符号串的集合，集合的运算有并、交、差等1.并运算 等同于集合的并运算2.连接（乘积）：两个符号串集合 A 和
8、 B 的乘积定义为：AB = xy | x A 且 y B 例如：集合A=ab,cde B=0,1 则 AB= ab1,ab0,cde0,cde1 L = L = L LLL = Ln L0 = 3.* 闭包：L* = L0L1L2L3 4. +闭包：L+ = L1L2L3 L* = L+ 注: 后面通常是考虑字母表的*闭包和+闭包 例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,综合性的例子：书本P73例3.3 L = A,B,C,Z,a,b,c,z D = 0,1,9把 L 和 D 两个字母表看作长度为1的符号串集合
9、，即语言答案：1. L D 2. LD 3. L4 4. L* 5. L(L D)* 6. D+n 5.如何来描述一种语言？(1.如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示(2.如果语言是无穷的，找出语言的有穷表示。(3.语言的有穷表示有两个途经：1.生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。2.识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）注：文法即是以生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造n 6.文法 G 定义
10、为四元组（VT，VN，S，P）：（1.VT ：终结符集，其中的元素一般用小写字母或数字表示（a,b,c0,1.），代表语言中不可再分的基本符号，如汉语中的汉字、PASCAL语言中的基本字。（2.VN ：非终结符集，其中的元素一般用大写字母表示（A,B,C），或者用尖括号括起，代表语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等(3.S是一个特殊的非终结符号，称为开始符号.至少要在一条产生式中作为左部出现(4.P是一个产生式的集合. 产生式（重写规则、生成式），是形如或=的（，）有序对，且V+，V* 其中 V = （VTVN）称为产生式的左部，不能为空;称为产生式的右部
11、，可以为空（如：A ）（5.可以只写出产生式，通过产生式可以得到文法的其它部分（6. 左部相同的产生式可以写在一起，如:S 0S1 | 01n 7. 推导与归约（1.直接推导与直接归约：如果 A 是 G 的一条产生式，则称用代替A为一步直接推导，记为A =；称用A代替为一步直接归约，记为+，长度大于等于1的推导 = *，长度大于等于0的推导推导的例子：S = 0S1 = 00S11 = 000111，长度为3 记为：S = +000111 S= *S（3最左推导与最右推导 =是一步推导， ， （VTVN）*1.最左推导(=lm) 对 中的最左非终结符进行展开2.最右推导(=rm) 对 中的最右
12、非终结符进行展开（最右推导又称为规范推导（4最右归约与最左归约1.最左推导的逆过程是最右归约，即对最右边的可归约串进行归约最右归约：a*a = a*F = F*F = T*F = T= E （最左归约称为规范归约）2.最右推导的逆过程是最左归约，即对最左边的可归约串进行归约 最左归约：*a = F*a = T*a = T*F =T *例：在推导：E =T =T*F =F*F =a*F =a*a中，句型有： E 、T、T*F 、F*F 、a*F 、a*a 句子是： a*an 9.语言的形式定义：文法G推导出的所有句子组成的集合，称为语言，记为 L（G）L（G）=| S= *， VT* 是由一个或多个 0 开头，后跟同样数目的 1 的符号串构成的集合（语言），可记为：L(G)=0n1n|n1G2产生的是表达式的集合. G3产生的也是表达式的集合(1.一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为等价文法。 例G2与G3n 10. 四类形式语言: 乔姆斯基（Chomsky）在 1956 年提出形式语言理论，他将形式文法分为四类 ( 0 , 1 , 2 , 3 )，对应四类形式语言 ( 0 , 1 , 2 , 3 )。分类的方法是对文法的产生式进行不同的限制。（1）.0型文法 |0，即 （）（2）.1型（上下文有关）文法
