编译原理第一章编译引论剖析.ppt

* * 一. 什么叫编译程序 二. 编译过程概述 三. 编译程序的结构 四. 编译程序生成 五. 课程学习指导 编译程序是系统软件中资格最老的成员之一 编译理论和技术近30年来发展十分迅速、成熟 1.编译程序历史 现已形成一套较为系统化的编译理论和技术 2.编译理论与其他课程关系 编译理论 自动机和形式语言 离散数学 数据结构 操作系统 素材 基础 控制对象 编译理论 的许多想法和技术可用于一般软件的设计： 3.编译理论的应用 有穷状态技术 模式识别 情报检索 文本编辑程序 上下文无关文法 语法制导翻译 建立多种文本处理程序 代码优化技术 由非结构化到结构化的程序转换 程序校验 翻译程序（Translator）是一种程序，其输入是某种语言的一系列语句，而其输出则是另一种语言的一系列语句。 4.翻译程序（Translator） 源语言程序 目标语言程序 Translator 输入 输出 编译程序（Compiler）是一种程序。它把用高级语言写的源程序作为数据接收，经过翻译转换，产生面向机器的代码作为输出。 这当中代码还可能要由汇编程序或装配程序作进一步加工，得出目标程序，交给计算机执行。 5.编译程序（Compiler） 高级语言源程序 面向机器代码 Compiler 目标程序代码 汇编 装配 6.解释程序（Interpreter） 这是另外一种类型的翻译程序，在翻译过程它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。 源程序 （高级语言） 解释程序 计算结果 输入 输出 初始数据 1.编译过程的组成 编译过程 词法分析 语法分析 中间代码生成 代码优化 目标代码生成 源程序 单词符号 中间代码 语法单位 目标代码 中间代码（优化后） 源程序 目标代码 2.词法分析 任务 所做转换 依据 构词规则 主要理论基础 自动机理论 源程序字符串 单词符号 输入源程序；扫描、分解字符串，识别出一个个单词（关键字、标识符、运算符、界符、常数） 2.词法分析 示例 FOR K := 1 TO 100 M := I + 10 * K N := J + 10 * K NEXT K TO NEXT FOR K N M I J K K K := 100 := := 1 10 10 + * * + 关键字 标识符 分界符 运算符 常数 3.语法分析 任务 所做转换 依据 语法规则 主要理论基础 上下文无关文法 单词符号 语法单位（语法范畴） 在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。 3.语法分析 示例 TO NEXT FOR K N M I J K K K := 100 := := 1 10 10 + * * + 变量、常数及其运算结果均是表达式 表达式 表达式 表达式 表达式 表达式 表达式 赋值句的形式为“变量　：＝　表达式” 赋值句 赋值句 多个赋值句可构成语句块 语句块 表达式可作为循环的初值和终值 初值 终值 简单数值变量可作为循环的控制变量 控制变量 控制变量 此时可以看出上述结果符合ＦＯＲ循环语句 的语法定义，故语法分析成功完成 4.中间代码生成 任务 所做转换 依据 语义规则 主要理论基础 属性文法 语法范畴 中间代码 对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 4.中间代码生成 示例 TO NEXT FOR K N M I J K K K := 100 := := 1 10 10 + * * + (1) ( :=, 1, , K ) (2) ( j,100, K, ) (3) ( *, 10, K, T1 ) (8) ( j, , , (2)) (7) ( +, K, 1, K ) (4) ( +, I, T1, M ) (9) ( ) (9) (5) ( *, 10, K, T2 ) (6) ( +, J, T2, N ) T1 T2 (1) K := 1 (2) if 100K goto (9) (3) T1 := 10 * K (8) goto (2) (7) K := K + 1 (4) M := I + T1 (9) (5) T2 := 10 * K (6) N := J + T2 循环语句 出口语句 循环块 STEP 1 生成四元式 将四元式重写为另一种形式的中间代码 (1) ( :=, 1, , K ) (2) ( j,1