编译原理复习提纲

1、2021-7-121 n编译器编译器 n一个编译程序就是一个语言翻译程序，它把 一种语言（称作源语言）书写的程序翻译成 另一种语言（称作目标语言）书写的等价的 程序。 第第1章章 编译概述编译概述 2021-7-122 n编译的分析编译的分析-综合模型综合模型 n分析：分析源程序，计算其基本属性，生成 源程序的中间表示 n综合：将源程序的中间表示转换为目标代码 第第1章章 编译概述编译概述 2021-7-123 n编译的逻辑编译的逻辑阶段阶段 n词法分析词法分析 n语法分析语法分析 n语义分析语义分析 n中间代码生成中间代码生成 n代码优化代码优化 n目标代码生成目标代码生成 第第1章章 编译

2、概述编译概述 2021-7-124 n* 符号表管理 n* 出错处理 第第1章章 编译概述编译概述 2021-7-125 n遍遍 n对源程序或源程序中间表示的一次扫描，每一 遍读入一个文件，执行一个或几个阶段的编译 操作，并输出源程序的一个中间表示 n遍数多：编译器结构清晰，但时间效率不高 n遍数少：编译速度快，但对机器的内存要求高 第第1章章 编译概述编译概述 2021-7-126 n语言语言 n某个字母表上的符号串的集合 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-127 n文法文法 G 四元组（四元组（VT，VN，S，P）：）： n上下文无关文法上下文无关文法 nA

3、nA 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-128 n推导与归约推导与归约 n推导推导是用产生式的右部代替左部，归约归约是用产 生式的左部代替右部，归约是推导的逆过程 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-129 n最左推导与最右推导最左推导与最右推导 n最右归约与最左归约最右归约与最左归约 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-1210 n句型句型 与与 句子句子 n句型：从文法的开始符号出发进行零步或多于 零步的推导得到的文法符号串 n句型可以既包含终结符号又包含非终结符号， 只包含终结符号的句型称为句子 第第2

4、章章 程序语言的基本知识程序语言的基本知识 2021-7-1211 n语言语言的形式定义的形式定义 n文法 G 推导出的所有句子组成的集合，称为 语言语言，记为 L（G） 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-1212 n句型的短语、直接短语和句型的短语、直接短语和句柄句柄 n如果S A和A ，则称是关于A的，句 型的一个短语短语（子树的叶子） * S A 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-1213 n如果S A和 A =，则称是关于 A的， 句型的一个直接短语直接短语（只有父子两代的 子树的叶子） * S A 第第2章章 程序语言的基本

5、知识程序语言的基本知识 2021-7-1214 n最左直接短语称为句柄句柄 n最左性体现在分析树和句型中 S A 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-1215 n句型的素短语、最左素短语 1、是关于A的，句型的一个短语 2、至少含有一个终结符 3、除自身外不含更小的带终结符的短语 称是关于A的，句型的一个素短语素短语 n句型最左边的素短语称为最左素短语最左素短语 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-1216 n句子、文法和语言的二义性句子、文法和语言的二义性 n如果一个文法的句子有两棵或两棵以上的分 析树，称此句子是二义句子是二义的 n最

6、左（右）推导与分析树一一对应，句子二义说 明它有两个或以上最左（右）推导 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-1217 n如果一个文法有一个句子是二义的，此文法 称为二义文法二义文法 n如果一个语言的所有文法都是二义的，称此 语言是二义的语言是二义的 第第2章章 程序语言的基本知识程序语言的基本知识 2021-7-1218 n正规表达式正规表达式 n正规表达式是一个表示字符串格式的模式 n用来描述单词符号的结构 n递归定义递归定义 第第3章章 词法分析词法分析 2021-7-1219 n有限自动机有限自动机 n是具有离散输入与离散输出的一种数学模型 n输入：字符串

7、n输出：是、否 n它能对输入字符串是否属于某个模式（正规集、 正规语言）作出判断 第第3章章 词法分析词法分析 2021-7-1220 n非确定的有限自动机非确定的有限自动机 NFA nS 状态集合状态集合 n 输入符号集合输入符号集合 nmove 转换函数（转换函数（S 2S） nS0 开始状态开始状态 nF 接受状态集合接受状态集合 第第3章章 词法分析词法分析 2021-7-1221 n确定的有限自动机确定的有限自动机 DFA n没有边转移 n一个状态面临一个输入符号时最多只转 移到一个状态 第第3章章 词法分析词法分析 2021-7-1222 nNFA-DFA 的转换的转换 子集构造法

8、子集构造法 n从正规表达式构造从正规表达式构造 NFA nDFA 的化简（最小化）的化简（最小化） 第第3章章 词法分析词法分析 2021-7-1223 n自顶向下分析：自顶向下分析： n从根到叶子来建立句子的分析树 n或，给出句子的一个从开始符号出发的推导 序列 第第4章章 语法分析语法分析 2021-7-1224 n自底向上分析：自底向上分析： n从叶子到根来建立句子的分析树 n或，给出一个从句子出发到开始符号的归约 序列 第第4章章 语法分析语法分析 2021-7-1225 n不确定的自顶向下分析：不确定的自顶向下分析： n带回溯的分析方法 n本质上是一种基于穷举原理的试探方法一种基于穷

9、举原理的试探方法，是 个反复使用不同的产生式谋求匹配输入串的 过程 n不确定性体现在每次选择的产生式不一定是每次选择的产生式不一定是 正确的正确的 第第4章章 语法分析语法分析 2021-7-1226 n确定的自顶向下分析：确定的自顶向下分析： n基本思想：从文法的开始符号出发，根据当 前的输入符号输入符号和其它信息其它信息，唯一地确定选用 哪条产生式往下推导，构造分析树。 n无论对错，都没有回溯 第第4章章 语法分析语法分析 2021-7-1227 nFIRST集：集： nFOLLOW集：集： nSELECT集集 n构造构造LL（1）分析表）分析表 nLL（1）文法）文法 第第4章章 语法分

10、析语法分析 2021-7-1228 n提取左因子提取左因子 n含有上面产生式的文法不是 LL（1）的，因为: SELECT（ A ） SELECT（ A ） n文法中可能含有形如：A | 的产生式 第第4章章 语法分析语法分析 2021-7-1229 A 1 | 2 | 3 | | n A （1 | 2 | 3 | | n） A A A 1 | 2 | 3 | | n 第第4章章 语法分析语法分析 2021-7-1230 n消除左递归消除左递归 n文法可能含有形如 A A | 的产生式或 A A的推导，称为左递归文法左递归文法 n左递归文法不是 LL（1）文法， 第第4章章 语法分析语法分析

11、2021-7-1231 n自底向上分析法自底向上分析法，又称为，又称为移进移进-归约法归约法， 它的实现思想：它的实现思想： n对输入符号串自左向右进行扫描，并将输入 符逐个移入一个先进后出栈中，边移进移进边分 析，一旦栈顶符号串形成某个句型的可归约可归约 串串时，就用相应产生式的左部非终结符代替 此可归约串。重复这一过程，直到归约到栈 中只剩下文法的开始符号时分析成功。 第第4章章 语法分析语法分析 2021-7-1232 n算符优先分析的基本思想：算符优先分析的基本思想： n利用算符优先关系来寻找可归约串 n算符优先分析算符优先分析 第第4章章 语法分析语法分析 2021-7-1233 n

12、LR（k）分析技术：）分析技术： nL 指从左至右扫描输入符号串 nR 指构造一个最右推导的逆过程（最左归约） nk 指在作出分析决定前要向前看的输入符号个 数，通常为 0 或 1 nLR 分析技术是功能最强的（自底向上）语法分 析技术，适用文法广，效率高，分析能力强 第第4章章 语法分析语法分析 2021-7-1234 nLR分析过程中的性质与特点：分析过程中的性质与特点： n栈中的文法符号串并上剩余的输入串构成一 个右句型（规范句型） n当该右句型的句柄出现在栈顶时，归约，否则， 移进 n栈中的文法符号串是当前句型的前缀，该前缀 不包含句型句柄后面的符号，称之为活前缀活前缀 第第4章章 语

13、法分析语法分析 2021-7-1235 n语义分析阶段分析源程序的含义，并作相语义分析阶段分析源程序的含义，并作相 应的处理，语义分析的基本功能：应的处理，语义分析的基本功能： n确定类型确定类型 n类型检查类型检查 n产生中间代码产生中间代码 n语义分析的主流技术语义分析的主流技术 语法制导翻译语法制导翻译 技术技术 第第5章章 语法制导翻译语法制导翻译 2021-7-1236 n文法符号的属性：文法符号的属性： 1、综合属性综合属性：属性值是分析树中该结点的子 结点的属性值的函数 2、继承属性继承属性：属性值是分析树中该结点的父 结点和和/或或兄弟结点的属性值的函数 第第5章章 语法制导翻

14、译语法制导翻译 2021-7-1237 n语法制导定义：语法制导定义： n为每一条产生式（A ）引入一套语义规则 n规则形式：b := f (c1,c2,ck) 第第5章章 语法制导翻译语法制导翻译 2021-7-1238 n语法制导翻译语法制导翻译: n根据语法分析中产生式对应的语义规则语义规则进行翻 译的方法称为语法制导翻译语法制导翻译。 第第5章章 语法制导翻译语法制导翻译 2021-7-1239 nS -属性定义属性定义 n只含有综合属性的语法制导定义 第第5章章 语法制导翻译语法制导翻译 2021-7-1240 nL -属性定义属性定义 n是一种语法制导定义 n对于产生式 AX1X2

15、Xn 右部 Xj 的继承属性， 它依赖于： 1、 X1，X2，Xj-1 （ Xj左边的文法符号）的 属性 2、A 的继承属性 n* L-属性定义包含 S-属性定义 第第5章章 语法制导翻译语法制导翻译 2021-7-1241 n翻译模式：翻译模式： n将语义规则放到 中，并插入到产生式右部 的适当位置，以反映语义规则的计算顺序，这 种书写形式称之为翻译模式翻译模式 第第5章章 语法制导翻译语法制导翻译 2021-7-1242 n从 L-属性定义出发，构造一个满足要求的翻译 模式 n 将计算产生式右边某文法符号的继承属性的 语义规则插入到此符号之前 n将计算产生式左边非终结符号综合属性的语 义规

16、则放在产生式右端的末尾 第第5章章 语法制导翻译语法制导翻译 2021-7-1243 nL-属性定义 深度优先翻译 两遍扫描 nS-属性定义 自底向上翻译 一遍扫描 第第5章章 语法制导翻译语法制导翻译 2021-7-1244 n三地址代码三地址代码 n一般形式：x := y op z n一般含三个地址（名字、常数、临时变量）， 两个操作数，一个运算结果 n中间代码中间代码 第第7章章 中间代码生成中间代码生成 2021-7-1245 n根据给定语法制导定义，翻译赋值语句、根据给定语法制导定义，翻译赋值语句、 布尔表达式、控制流语句等，得到中间代布尔表达式、控制流语句等，得到中间代 码码 n参

17、考例子，掌握方法 第第7章章 中间代码生成中间代码生成 2021-7-1246 n代码优化代码优化 n编译时刻为改进目标程序的编译时刻为改进目标程序的质量质量而进行的各而进行的各 项工作项工作 n与机器相关的优化与机器相关的优化 n与机器无关的优化与机器无关的优化 第第9章章 代码优化代码优化 2021-7-1247 n根据优化范围根据优化范围 n局部优化 针对程序基本块基本块 n循环优化 针对循环体 n全局优化 针对整个程序 第第9章章 代码优化代码优化 2021-7-1248 n名字的联编 n名字的左值左值 内存地址，存储名字的瞬时值 n名字的右值右值 名字的瞬时值 n名字的联编联编 将一

18、个内存地址与一个名字 联系起来 n在程序的一次运行中，一个名字右值（瞬时 值）可能会经常改变，一个名字也可能被联 编到多个地址（如递归调用中） 第第6章章 运行时刻环境的组织运行时刻环境的组织 2021-7-1249 n运行时刻内存的典型划分运行时刻内存的典型划分 n操作系统收到运行目标 程序的指令，分配一块 连续的内存空间使目标 程序在其上运行 n栈栈：支持过程的递归调用 n堆堆：支持动态内存申请 第第6章章 运行时刻环境的组织运行时刻环境的组织 代码代码 静态数据静态数据 栈栈 堆堆 2021-7-1250 n活动记录活动记录 n是一段连续的存储区，用以存放过程的一次 执行所需要的信息，如局部数据 第第6章章 运行时刻环境的组织运行时刻