[2018年必威体育精装版整理](编译原理)讲义.docVIP

概述 计算机由硬件和软件组成，软件又包括程序设计语言、系统软件和应用软件，而编译系统属系统软件。 最早人们只能使用计算机可直接接受的机器语言，到1956年，在IBM704计算机上构造了第一个FORTRAN编译程序，使人们从繁重的机器语言程序设计中解放出来。 计算机是一种逻辑电子装置，它只能接受二进制数，要使得计算机接受高级语言程序，就要借助于编译程序将高级语言程序翻译成机器可接受的机器语言。 §1编译程序和解释程序： 要在计算机上实现除机器语言之外的任一程序设计语言，就首先应使此语言为计算机所“理解”。解决这一问题的方法有两种：一种是对程序进行翻译；另一种是对程序进行解释。 翻译程序：①汇编程序 ②编译程序 翻译程序：是把一种语言编写的程序翻译成等价的另一种语言的程序；前一种语言称为源语言，后一种语言称为目标语言； 根据源语言和目标语言的不同，有各种不同的翻译程序： 汇编程序：若源语言是汇编语言，目标语言是机器语言，这种翻译程序称为汇编程序。 编译程序：若源语言是高级语言，而目标语言是某计算机的汇编语言或机器语言，这种翻译程序称为编译程序。 解释程序：它以用该语言编写的源程序作为输入，但不产生目标程序，而是按照源语言的定义边解释边执行源程序本身。 通常的编译程序是先将源程序比较简单地翻译成某种中间形式的程序，然后再对这种中间形式进行解释；这种中间形式的语言有多种：波兰表示、三元组、四元组、树、伪代码等。 编译程序和解释程序相比，解释程序的执行效率比较低，但占用时间较少。 §2编译程序的组成部分： 编译程序将首先根据源语言的定义来对源程序进行分析，之后进行综合，并从而得到与源程序等价的目标程序； 分析：对源程序进行结构分析和语义分析； 综合：创建出与源程序等价的目标程序； 结构分析：①词法分析 ②语法分析 综合：①中间代码生成 ②代码生成 每一个编译程序一般都要做以下几个方面的工作： 词法分析 语法分析 语义分析 中间代码生成 代码生成 代码优化 源程序 目标程序 图1。1编译程序的基本组成 在编译过程中，要从头到尾扫视源程序或其内部表示（等价的中间语言程序）。每扫视一遍称为一趟扫描。如果经过一趟扫描就能生成目标代码，这样的编译程序称为一趟扫描的编译程序，否则称为多趟扫描的编译程序。 下图是一个不带代码优化的五趟扫描的编译程序的实现方案： 编译程序总控 源程序 中间语言1，表 中间语言2，表 中间语言3，表 理想机代码，表 图1。2不带代码优化的五趟扫描 的编译程序的实现方案 目标代码 这个五趟扫描的编译程序工作过程如下：首先，编译程序的主程序调用词法分析程序，词法分析程序把源程序作为输入，将它转换为一种内部表示，称为中间语言1，并得到有关的一些表；然后，主程序调用语法分析程序，语法分析程序把中间语言1作为输入，进行语法分析，并转换为中间语言2；。。。。。。；最后，主程序调用目标代码生成程序，把中间代码（可看作为一种理想机代码）作为输入，并转换为目标代码。 对于一趟扫描的编译程序，程序本身紧凑，编译程序快； 对于多趟扫描的编译程序，它的功能块清晰，占用内存器少（重叠使用内存）。 词法分析：词法分析程序又称扫描程序；主要任务是从构成源程序的符号串中识别出一个个具有独立意义的最小单位——单词，并把需要存放的单词放到符号表中；词法分析是一种线性分析； 例1：对赋值语句a:=b+c*d进行词法分析，得到以下的结果： 单词类别值 单词自身值 （1）标识符（IDENT） a （2）赋值号（BECOMES） ：= （3）标识符（IDENT） b （4）加号（PLUS） + （5）标识符（IDENT） c （6）乘号（TIMES） * （7）标识符（IDENT） d （8）分号（SEMICOLON） ； 识别标识符要根据词法规则。例如：标识符的词法规则是以字母开