编译原理复习陆筱霞.pptVIP

编译原理复习课 陆筱霞 公共邮箱：zzti_soft@126.com 密码：soft_zzti 第一章 引 论 一. 什么是编译程序 一. 什么是编译程序 一. 什么是编译程序 二. 编译过程 编译程序的工作一般分为五个阶段: 词法分析 语法分析 中间代码产生 优化 目标代码产生 1. 词法分析 任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。 依循的原则：构词规则 描述工具：有限自动机 FOR I := 1 TO 100 DO 保留字 标识符 等符 整常数 保留字 整常数 保留字 2. 语法分析 任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。 依循的原则：语法规则 描述工具：上下文无关文法 Z := X + 0.618 * Y 算术表达式，赋值语句 3. 中间代码产生 任务:对各类不同语法范畴按语言的语义进行初步翻译。 依循的原则：语义规则 中间代码:三元式，四元式，树形结构等 Z:=X + 0.618 * Y 翻译成四元式为 (1) * 0.618 Y T1 (2) + X T1 T2 (3) := T2 _ Z 4. 优化 任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。 依循的原则：程序的等价变换规则 5. 目标代码产生 任务: 把中间代码变换成特定机器上的目标代码。 依赖于硬件系统结构和机器指令的含义 目标代码三种形式: 绝对指令代码: 可直接运行 可重新定位指令代码: 需要连接装配 汇编指令代码: 需要进行汇编 三. 编译程序结构 编译程序总框 2. 表格和表格管理 常见的表格:符号名表，常数表，标号表，入口名表，过程引用表。 格式: 3. 出错处理 出错处理程序：发现源程序中的错误，把有关错误信息报告给用户 语法错误 语义错误 4. 遍(pass) 所谓遍， 就是对源程序或源程序的中间表示从头到尾扫描一次。 阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。 5. 编译前端与后端 编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化 编译后端：与目标机有关，与目标机有关的优化，目标代码产生 优点：减少对内存容量的要求，程序逻辑结构清晰; 优化更充分，有利于移植。 不足: 编译程序运行的效率低 第二章 高级语言及其语法描述 一. 语法 程序本质上是一定字符集（称为字母表）上的字符串（有限序列）。 语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。 规则的一部分称为词法规则，另一部分称为语法规则（或产生式规则）。 语 法 词法规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。 描述工具：有限自动机 语法规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、分程序、过程、函数、程序等; 描述工具：上下文无关文法 语义 语义：一组规则，用它可以定义一个程序的意义。 描述方法： 自然语言描述：隐藏错误、二义性和不完整性 形式描述： 操作语义(PL/1) 指称语义(ADA) 代数语义(PASCAL) 2.3 程序语言的语法描述 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 ∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε 例如: 设 ∑={a， b}，则 ∑*={ε,a,b,aa,ab,ba,bb,aaa,...} ?即? ?是空集，表示一个不含任何元素的集合。 ∑*的子集U和V的连接（积）定义为 UV＝{ ?? | ??U ??V } 设： U＝{ a, aa } V＝ { b, bb } 那么： UV= { ab, abb, aab, aabb} V自身的 n次积记为 Vn=VV…V 规定V0={?}，令 V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; 记 V＋＝VV* ，称V+是V的正规闭包。 闭包V*中每个符号串都是由V中的符号串经有限次连接而成的。 2.3.1 上下文无关文法 文法： 描述语言的语法结构的形式规则 上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT ? VN=? S：文法的开始符号，S?VN P：产生