编译原理与实现 河北科技大学 信息科学与工程学院计算机系 杨奎河 2008-09

编译原理的作用： 高级语言的源程序 编译 计算机的机器语言

教学目的： ① 掌握编译原理的基本知识。 ② 掌握一些典型问题的解决办法。 ③ 对程序有进一步的认识。 学习方法： ① 了解整体结构。 ② 掌握解决具体问题的具体办法。 ③ 掌握基本概念。

第一章 引论

§1.1 什么是编译程序 一、程序语言的分类 1、程序语言分为两类：高级语言 低级语言 2、低级语言可分为两类：机器语言 汇编语言

二、基本概念 把用汇编语言或高级语言写成的程序转换成机器语言的程序，被称为翻译程序。 汇编语言的翻译程序称为汇编程序 把高级语言的翻译程序称为编译程序。 编译程序的输入对象称为源程序，输出对象称为目标程序。

三、编译过程 1、执行一个高级程序一般分为两步： ① 通过编译程序把源程序翻译成机器语言程序。 ② 执行目标程序

编译过程：

编译方式： 编译程序 计算结果 源 程 序 目标程序 初始数据 运行系统子程序

源程序 计算结果 解释程序 初始数据 2、也可以采用边翻译边执行的解释执行方式，这种处理程序称为解释程序。解释程序的结果是源程序的执行结果。 解释方式： 解释程序 计算结果 源程序 初始数据

传统的语言（例如C、C++ ），源代码在经过编译连接后直接生成了二进制代码。而C#、java这些语言把源代码编译为了中间语言，C#把源代码编译为微软中间语言MSIL，Java把源代码编译为字节码。 采用这种方法的优势：可移植性。发布的程序理论上可以在任何硬件平台上运行。即C#通过安装在机子上的CLR(Common Language Runtime-公共语言运行时），Java通过安装在机子上的JVM(Java Virtual Machine-Java虚拟机)来执行中间代码和字节码。

C是直接编译成机器码，java是编译程序将java源程序编译成JVM可执行代码--java字节码，再由虚拟机解释执行。 简单的理解是，为了实现这种移植性，在机子上又加了一层平台（CLR、JVM),让中间代码在这个平台上进行运行，而JVM、CLR在不同的操作系统上以不同的方式实现。 C是直接编译成机器码，java是编译程序将java源程序编译成JVM可执行代码--java字节码，再由虚拟机解释执行。

§1.2 编译程序的组成 一、编译程序要完成的工作： 词法分析 语法分析 中间代码生成 中间代码优化 目标代码生成及和硬件有关的工作

表 格 管 理 错 误 处 理 词法分析 中间代码生成 语法分析 中间代码优化 目标代码生成 源程序 目标程序

例子：用Pascal将英语句子译成数字，用1～26替A～Z，空格用#，句号不变。例如：this is an example Program encode(input，output) Const blank=‘ ’,termin=‘.’,well=‘#’; Var letter:char;code:integer;

Begin Read(letter); While letter<>Termin do If letter=blank Then Write(well:2) Else Begin code:=Ord(letter)-Ord('A')+1;

Write(code:3) End Read(letter) Write(termin) 运行结果： 20 8 9 19 # 9 19 # 1 14 # 5 24 1 13 16 12 .

1、分析单词：保留字、标识符、常数、运算符、分界符 2、语法分析：分析语法结构和程序层次 二、编译的步骤 1、分析单词：保留字、标识符、常数、运算符、分界符 2、语法分析：分析语法结构和程序层次 程序 开始部分 说明部分 执行语句

(input, output) 开始部分 程序开始 程序名 参数 Program Encode 说明部分 常量 变量

Well=‘#‘ 常量定义 语句1 语句2 语句3 Blank=‘ ‘ Termin=‘.‘ ，

语句部分 Begin 语句组 End 语句1 ； 语句2 …… Read 参数 ( Letter ) 其他情况类似！

3、语义处理和产生目标程序 ① 程序处理 ② 说明语句处理 ③ 可执行语句处理

三、编译阶段的组合 词法分析 语法分析 中间代码生成 前端 中间代码优化 目标代码生成及和硬件有关的工作 后端

1、前后端结合 某编译程序前端 A机型后端 B机型后端 ＋ 不同机型上的编译程序

A编译程序前端 B编译程序前端 生成同一 中间语言 共同的 后端 ＋ ＋ 几种编译程序

2、结论： ① 分前后端可提高效率，减少重复劳动 ② 利于优化，便于组合

§1.3 编译程序的分遍 1、编译程序按其扫描遍数分为： 一遍扫描 多遍扫描 2、若通过对源程序的扫描直接生成目标代码，则称编译程序是单遍的。 3、多遍扫描的好处是：便于分工、便于优化，但前后扫描之间难免有些重复性工作。

多遍扫描的步骤： 源程序 →词法分析程序 →中间文件1 →语法分析程序 →中间文件2 →语义分析 →中间文件3 →优化 →中间文件4 →目标程序

目前大部分编译程序都是多遍扫描的。 一遍扫描:以语法分析为主。 参考文献： 吕映芝.编译原理.清华大学出版社,北京:1998.

§1.4 编译程序的开发 1、开发编译程序的步骤： ① 对语言的语法与语义有准确无误的理解。 ② 确定编译程序的要求。 ③ 根据编译程序的规模确定编译程序的具体分遍及每遍的具体任务。 ④分别调试各次的扫描程序，连调

2、编译程序的自动化 利用自展技术完成。 首先利用汇编语言的编写最简单的编译程序，例如加法的编译程序。 将乘法转换为加法，利用得到的加法编译程序得到乘法的编译程序，以此类推。 PL0……PLn均是PASCAL的子集。