[工学]ch1 编译程序概述.ppt

编译原理 数计学院 张晓红 * 课程介绍 l课程名称：编译原理 l课程性质：专业必修课 l先导课程：汇编语言、计算机组成原理、数据结构、 高级语言程序设计、离散数学 l上课时间：理论（17*3）课时 1-17周 实践（6*2）课时 5-10周 l上机时间：周三下午7.8节 l上机地点：四号楼机房 l学习方式：课堂讲解 + 课后作业 + 上机实践 l考试成绩：试卷成绩 + 作业成绩 + 上机成绩 l考试方式：闭卷考试 参考教材 l教材：编译原理，高等教育出版社 何炎祥编 著，2004年 l编译原理，清华大学出版社 张素琴、吕映芝 等编著，2005年 l编译原理（第2版） 高等教育出版社，陈意 云等编著，2008年 l陈火旺 刘春林等 程序设计语言编译原理 国 防工业出版社，2000年 教学要求 l掌握编译程序的一般构造原理 l掌握编译程序的基本实现技术 l熟悉一些自动构造工具 第一章 引论 * 本节内容 l什么是编译程序？ l为什么要学习编译程序？ l编译程序的工作过程 l编译程序的结构 l编译程序的组织方式 l编译程序的其他相关技术 1.1 什么是编译程序？ l计算机任务的交付方式：程序 l程序设计语言 l用来编写计算机程序的语言。 l是人与计算机交互联系的工具。 l不同语言书写不同程序。 l分为： 1 1）机器语言）机器语言 2 2）汇编语言）汇编语言 3 3）高级语言）高级语言 1 机器语言 l唯一能被计算机直接识别和执行的语言。 l用“0/1”组成的二进制代码指令编写。 l组成：操作码 + 地址码。 如：1 + 3 10000001 00000001 00000011 l特点： l难记、难认（直观性差）、难写（编程效率低）、难读（可 读性差）、难修改 l与机器有关：不同的计算机硬件，有不同的指令系统，也就 有不同的机器语言 l与机器有关，故不易移植 l执行速度快 2 汇编语言 l将机器语言符号化 l与机器语言一一对应 l汇编语言组成：指令助记符 + 地址符号 机器语言组成：操作码 + 地址码 如： 1 + 3 10000001 00000001 00000011 ADD 1 3 l不能被机器直接识别，必须把它翻译为机器语言程序才能执行 。 汇编语言源程序 （源程序） 机器语言程序 （目标程序） 汇编 （翻译 ） l特点： l比机器语言直观，容易理解和记忆，但编程仍不方便 l执行效率比机器语言低 l与机器有关 l与机器语言一起统称为低级语言。 3 高级语言 l目前比较流行的高级语言有：VC, VB, Java，Pascal,Lisp, Cobol等。 l表达方式接近于自然语言和数学语言。 l与具体的计算机硬件无关，面向问题、对象、方面。 l易于人们接受和掌握。 如：1 + 3 10000001 00000001 00000011 ADD 1 3 x = 1 + 3 l不能被机器直接识别。 l在执执行之前，必须须需要先翻译译成目标语标语 言程序（汇编汇编 程序或机器程序 ）。 高级语言源程序 （源程序） 低级语言程序 （目标程序） 翻译 l特点： l独立于机器。 l接近自然语言，容易学习和掌握，程效率高。 l程序易读、易懂、易修改、易移植。 l时间与空间效率比较低。 程序设计语言 定位 特点 是否可 直接执行 硬件识别 比较 高级语言 种类多，常用 低级语言 很少使用 低级语言 极少使用 l面向问题/对象 l占用内存大 l执行速度相对慢 l标准化程度高 l使用方便 l面向机器 l占用内存少 l执行速度快 l较为直观 l与机器语言一 一对应 l面向机器 l占用内存少 l执行速度快 l使用不方便 不可 需编译/解释、连接 不可 需汇编、连接 可直接执行 不可识别不可识别唯一可识别 高级语言汇编语言机器语言 问题: l计算机只能识别二进制数0、1表示的指令和 数构成的本计算机系统的机器语言。 l如何让计算机执行高级语言程序呢？ 翻译成机器语言程序 l谁来承担翻译工作？ 编译程序 Whats compiler? l A compiler is a program that reads a program written in a source language and translates it into an equivalent program in a target language. Compiler Source program Target Program Error messages Diverse 词法分析（自动分词+词性标注） 例:position = initial + 3rate * 60 单词值单词类型 position标识符(id1) = 运算符(赋值) initial 标识符(id2) +运算符(加) 3rate错误 *运算符(乘) 60 整数 词法分析（自动分词+词性标注） 2 语法分析 l第二阶段：保证句子结构的正确 l输入：单词流 l输出：语法树 l依据：语法规则 （如：Sif C S else S | if C S） l主要功能： 分析句子是否合乎语法规则； 输出语法树（保证句子的结构正确）； 发现并报告语法错误。 语法分析（自动句法分析） 语法规则（文法描述）: = + * () 例:position = initial + rate * 60 赋值语句 标识符= 表达式 表达式+ 表达式 表达式* 表达式 标识符 标识符整数 语法分析（自动句法分析） 例:position = initial + rate * 60 分析过程: （分析树） 语法分析（自动句法分析） 例:position = initial + rate * 60 分析结果: id1=id2+id3*N （结构正确的语法树） = +id1 (position) *id2 (initial) id3 (rate) N (60) 3 语义分析 l第三阶段：保证句子含义的正确 l输入：结构正确的语法树 l输出：语义正确的语法树 l依据：语义规则 （如实数和整数不能直接做+运算，需进行类型转 换） l主要任务：进行类型审查，保证标识符和常量的 正确使用，否则应报告错误。包括： 类型匹配 类型转换 例: int m() float rate, initial; int position; position = initial+rate * 60; /* error */ /* warning */ 语义分析（类型审查） 例:position = initial + rate * 60; 分析结果: id1=id2+id3*(inttoreal)N （语义正确的语法树） = +id1 (position) *id2 (initial) id3 (rate) N (60) inttoreal 语义分析（类型审查） 4 中间代码生成 l第四阶段：分解计算步骤 l输入：结构和语义正确的语法树 l输出：中间代码 l主要任务：分解计算步骤 中间代码生成（分解计算步骤） l中间代码：程序的一种内部表示形式。 l如：四元式的形式为： （算符，运算对象1，运算对象2，结果） 中间代码生成（分解计算步骤） 例:position = initial + rate * 60 生成四元式序列： = +id1 (position) *id2 (initial) id3 (rate) N (60) inttorealt1 t2 t3 （inttoreal 60 t1 ） （ id3 t1 t2） （ id2 t2 t3） （ t3 id1） 5 代码优化 l第五阶段：计算步骤的简化 l输入：中间代码 l输出：优化后的中间代码 l主要任务：对中间代码进行变换，使目标代码 更为高效。（节省时间和空间） 代码优化（等价变换，节省时空 ） 优化前的中间代码: 1:（inttoreal 60 t1 ） 2:（ id3 t1 t2 ） 3:（ id2 t2 t3 ） 4:（ t3 id1） 变换 1: （ id360.0 t1 ） 2: （ + id2 t1 id1） 例:position = initial + rate * 60; 6 目标代码生成 l第六阶段，最后一个阶段：目标生成 l输入：优化后的中间代码 l输出：目标代码 l主要任务：将中间代码变换成特定机器上的绝 对指令代码或可重定位的汇编指令代码。 l与硬件系统结构和指令含义有关。 目标代码生成（机器代码或汇编代码 ） 优化后的中间代码: 1: （ id360.0 t1 ） 2: （ + id2 t1 id1） 生成的目标代码： MOV id3, R2 MUL #60.0, R2 MOV id2, R1 ADD R2, R1 MOV R1, id1 例:position = initial + rate * 60; 符号表管理 l记录源程序中的所有标识符。 l收集每个标识符的各种属性信息： l如：种类（谁的名字）、类型、作用域、分配存储信息 名 字 种 类类 型层 次偏移量 m函 数 0 position变 量 float1d initial变 量 float1d+4 rate变 量 int1d+8 出错处理 l功能：在编译的各个阶段诊断和报告源程序中 的错误。 l可能的错误： 词法错误，语法错误，语义错误。 l错误报告：出错地点、类型。 l错误恢复：恢复到正确点，继续后续分析。 Reviewing the Entire Process E r r o r s position = initial + rate * 60 lexical analyzer syntax analyzer semantic analyzer intermediate code generator id1 = id2 + id3 * 60 = id1 id2 id3 + * 60 = id1 id2l id3 + * inttoreal 60 Symbol Table position initial . rate. Reviewing the Entire Process E r r o r s intermediate code generator code optimizer final code generator temp1 = inttoreal(60) temp2 = id3 * temp1 temp3 = id2 + temp2 id1 = temp3 temp1 = id3 * 60.0 id1 = id2 + temp1 MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 position initial . rate. Symbol Table 3 address code 1.4 编译程序的结构 编译程序一般分为6个阶段和2个辅助过程： 出 错 处 理 语法分析程序 语义分析程序 目标代码生成程序 词法分析程序 中间代码生成程序 代码优化程序 表 格 管 理 1.4 编译程序的结构 l1.分析和综合： l词法分析 l语法分析 l语义分析 l中间代码生成 l代码优化 l目标代码生成 分析阶段： 保证正确性 做分析记录 综合阶段 ：分解成 分生成代 码 1.4 编译程序的结构 l2.前端和后端 源程序 中间代码 目标代码 前 端 后 端 编译过程 前端：词法分析、语法分析、语义分析、 中间代码生成、优化工作。 后端：目标代码生成、出错处理、 符号表操作。 仅依赖源程序仅依赖目标机器 l3.遍（PASS)：对输入文件（源程序或其等价的中 间形式）从头到尾扫视，完成预定的处理。 一个编译程序可由一遍、两遍或多遍完成。每一遍可 完成不同的阶段或多个阶段的工作。 从时间和空 间角度看 多遍编译 :功能独立，单存； 少占内存，多耗时间 一遍编译 :各阶段以子程序完成 多占内存，少耗时间 输入文件 遍 输出文件 1.4 编译程序的结构 1.4 编译程序的结构 l编译程序分“遍”的决定因素： 宿主机的存储容量； 编译程序功能强弱； 目标程序优化的程度； 设计和实现编译程序时使用的工具的先进程度 ，参加人员的多少和素质等。 1.4 编译程序的结构 语法分析 start 词法分析 子程序 目标代码 整理 语义分析 子程序 中间代码 生成 代码 优化 目标代码 生成 源 程 序 目 标 程 序 1.5 编译程序的组织方式 lLi-1是第i遍扫描Compi的编译对象 lLi是第i遍扫描Compi的加工结果 Comp（Li）Li Li-1 lComp1（L0） Comp2（L1） Compn（Ln-1） = Ln l中间代码覆盖技术： 中间代码无须保留，后一中间代码课覆盖前一中加代码中 已经处理的部分。 Li Li-1 1.5 编译程序的组织方式 内 存 外 存 Comp1 编译总控程序 扫描对象 部分处理结果 Comp1 Comp2 Comp3 覆盖 输入 对象 加工 结果 Compi Li-1 Li 1.6 编译程序的其他相关技术 1 编译程序的自展技术 先用低级语言对语言的核心构造一个小编译程序 再以它为工具构造一个能够编译更多语言成分的 较大编译程序。 L0 L1 L2 Ln 1）L0由汇编或机 器语言编写 2）L1由L0编写 i）Li由Li-1编写 n）Ln由Ln-1编写 1.6 编译程序的其他相关技术 2 高级语言的自编译性 l构造编译程序可以用机器言语、汇编语言和高 级语言。 l高级语言的自编译性：一个语言可以用来编写 自己的编译程序。 1.6 编译程序的其他相关技术 3 编译程序的移植技术 l将一个机器（宿主机）上的一个具有自编译性 的高级语言编译程序移植到另一个机器（目标 机）上。 l利用A机器上的高级语言L编写能在B机器上 运行的高级语言L的编译程序。 1.6 编译程序的其他相关技术 4 编译程序自动化 lLEX：词法分析程序生成器； lYACC：语法分析程序生成器。 1.6 编译程序的其他相关技术 5 程序的可再入性 l可再入性：程序正在执行时： 可以随时中断执行进程； 也可随时从断点恢复到原来的执行进程； 中断时，可以从该程序头开始一个新的进程。 l可再入性必须满足的条件： 纯代码：执行过程，进程的指令不被修改； 不同进程有不同数据区，中断时保存； 中断时的寄存器的内容被保存。 1.6 编译程序的其他相关技术 6 并行编译 l把串行的源程序或尚未并行化的并行源程序自 动转换成并行计算机上运行的并行目标程