【人工智能_编译new】第一章引论

一 . 什么叫编译程序 二 . 编译过程概述 三 . 编译程序的结构 四 . 编译程序生成 五 . 课程学习指导 编译程序 是 系统软件 中 资格最老的成员之一 编译理论和技术近 30年来 发展十分迅速、成熟 1.编译程序历史 现已形成一套较为 系统化的 编译理论和技术 2.编译理论与其他课程关系 编译理论 自动机和形式语言 离散数学 数据结构操作系统 素材 基础 控制对象 编译理论 的许多想法和技术可用于 一般软件的设计 ： 3.编译理论的应用 有穷状态技术 模式识别 情报检索 文本编辑程序 上下文无关文法 语法制导翻译 建立多种文本处理程序 代码优化技术 由非结构化到结构化的程序转换 程序校验 翻译程序（ Translator） 是一种程序，其 输入 是 某种语言 的一系列语句，而其 输出 则是 另一种语言 的一系列语句。 4.翻译程序 源语言程序 目标语言程序Translator 输入 输出 编译程序（ Compiler） 是一种程序。它把用 高级语言写的 源程序 作为数据 接收 ，经过翻译转换，产生 面向机器的代 码 作为 输出 。 这当中代码还可能要由 汇编程序 或 装配程序 作进一步加工 ，得出 目标程序 ，交给计算机执行。 5.编译程序 高级语言源程序 面向机器代码Compiler 目标程序代码 汇编 装配 6.翻译与编译比较 源语言程序 目标语言程序转变为 高级语言源程序 面向机器代码编译为 这种变换程序称为 翻译程序 编译程序 有一些限制 （针对输入、输出） 这种变换程序称为 编译程序 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 生成四元式 将四元式重写为另一种形式的中间代码 (2) ( j,100, K, (9) (4) ( +, I, T1, M ) (9) ( ) 2 2 循环语句和 出口语句 彼此相连地 被定义 包括循环语 句开始到有 同一控制变 量的第一个 出口语句的 那些语句的 自然序列称 为一循环块 块嵌套不可交叉 ，嵌套块控制变 量不可同名 不正确 正确嵌套 缺省的 STEP = STEP 1 5.代码优化 任务 所做转换 依据 程序等价变换规则 主要理论基础 数据流方程 中间代码 中间代码（优化后） 对于代码（主要是中间代码）进行加工变换 ，以期能够产生更为高效（省时间和空间） 的目标代码 。 5.代码优化 示例 (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 (3) K := 1 (4) if 100K goto (9) (8) goto (4) (7) K := K + 1 (9) (3) T1 := 10 * K (4) M := I + T1 (1) M := I (5) M := M + 10 (5) T2 := 10 * K (2) N := J (6) N := N + 10 6.目标代码生成 任务 所做转换 依据 硬件体系结构、指令系统 中间代码 目标代码 将中间代码变换成特定机器上的低级语言代码 目标代码形式 绝对指令、可重定位指令、汇编指令 6.目标代码生成 LD R1, I L2: ST R1, M LD R2, J ST R2, N LD R0, 1 L1: CMP 100, R0 J L2 ADD R1, 10 ADD R2, 10 ADD R0, 1 J L1 示例 (8) goto (4) (7) K := K + 1 (1) M := I (9) (6) N := N + 10 (3) K := 1 (2) N := J (5) M := M + 10 (4) if 100K goto (9) (3) K := 1 (2) N := J (5) M := M + 10 1.编译程序总框 表 格 管 理 词法分析 语法分析 中间代码生成 代码优化 目标代码生成 源程序 单词符号 中间代码 语法单位 目标代码 中间代码 出 错 处 理 2.表格与表格管理 编译各阶段均须 维持表格 并进行 表格管理 建表的 技术支持 是 数据结构 表格的 分类、结构、处理方法 决定于 语言 及 机器 ， 还有 优化措施 2.表格与表格管理 编译程序涉及的表格有： 符号名表 常量名、变量名、数组 名、过程名、 性质、 引用、定义常数表 标号表 入口名表 过程引用表 各种类型常数的值 标号的定义和引用情况 过程的入口名和入口位置 外部过程的名字、引用位置 循环表 等价名表 公用链表 格式表 中间代码表 3.出错处理 一个好的编译程序应该： 全 最大限度发现错误 准 准确指出错误的性质和发生地点 局部化 将错误的影响限制在尽可能小的范围内 若能 自动校正错误 则更好，但其 代价非常高 3.出错处理 源程序中的错误通常分为 ： 语法错误 不符合语法（或词法）规则的错误 语义错误 不符合语义规则的错误 单词拼写错误、括号不匹配 . 说明错误、作用域错误、类型不匹配 . 4.遍 遍 是对源程序或源程序 的中间结果 从头到尾扫描 一次 ，并作有关的 加工处 理 ， 生成新的中间结果或 目标程序 。 词法分析 语法分析 中间代码生成 代码优化 目标代码生成 一遍 语法分析器 处于核心地位 一遍 局部优化 一遍 一遍 全局优化 5.编译前端与后端 词法分析 语法分析 中间代码生成 代码优化 目标代码生成 编译前端 主要由 与源语言有关 但 与目标机无关 的那些部分组 成 编译后端 包括编译程序中 与目标机有关 的那些部分 以往 编译程序的构造大多采用 机器语言 或 汇编语言 现在 编译程序的构造越来越多采用 高级语言 1.编译程序的构造工具 有时为了 充分发挥效率 或 满足不同需求 ，仍然采用 机 器语言 或 汇编语言 构造编译程序（或其核心部分） 2. T型图 S I T S表示源语言 T表示目标语言 I表示编译程序的实现语言 3. 用高级语言 L1构造编译程序 L1 A A L2 L1 A L2 A A 已有用 A机器代码实现的高级语言 L1的编译程序可用高级语言 L1编写另一个高级语言 L2的编译程序 将写好的语言 L2的编译程序用 L1的编译程序编译后 就可得到用 A机器代码实现的 L2编译程序 4. 编译程序的移植 L A A(1) L L B(2) L A B(3) 已有 A机器上的高级 语 言 L编译程序（ 1） L B B(4) 用 L编写能在 B机 器上运行的 L的 编译程序（ 2） 将 (2)用 (1)编译，得到 A机 器上运行的产生 B代码的 L 的编译程序（ 3） L L B(2) 再将 (2)用 (3)编译，即可 得到 B机器上运行的产生 B 代码的 L的编译程序（ 4） 至此，将 A机器上的 L的编 译程序 (1)移植为 B机器上 的 L的编译程序（ 4） 5. 自编译方式 先对语言的核心部分构造一个小小的编译程序 （ 可用低级语言实现） 再 以它为工具 构造能编译更多语言成分的较大编译程序 如此不断扩展，最后形成整个编译程序 （滚雪球） 6. 构造工具 构造编译程序的工具称为 编译程序 -编译程序 、 编译程 序产生器 或 翻译程序书写系统 自动产生扫描器 LEX FLEX 自动产生语法分析器 YACC BISON 原理课程：基础性、科学性、普适性 优点：揭示科学本质、长期受用的知识 缺点：抽象，连贯性差，学时矛盾大 1. 课程性质 2. 学习目的 加深理解计算概念，提高素质 为主流语言写编译器 写专业编译器机会很多 为应用提供思路、技术 3. 如何学好 学好 “四大原理 ”课程，是计算机专业学生必要条件 上课：准时到，认真听，注意记 课后：认真完成作业、实验 方法：编译是个大系统，要反复琢磨 进国家级精品课程网站，获取更多信息 程序设计语言 编译原理 （第二版） 陈火旺等 国防工业出版社 第 0章 编译原理和技术 （第二版） 陈意云