第1章 编译概述

CompilersPrinciples主讲教师：陈大玲

课程要求熟练掌握C、Pascal语言的编程、语法结构；会一种程序设计语言的编程；会一种数据库开发语言，或熟悉文件的管理；按时完成作业；按课程的进程，按时完成课程实验；认真听讲，认真作笔记，上课不得迟到早退上课不得喧哗。2023/2/33第1章

编译概述

什么是编译程序

编译原理这门课程主要介绍设计和构造编译程序的基本原理和常用的技术和方法。本章重点介绍编译程序的基本概念。编译的过程编译程序的结构什么是编译程序

计算机只能识别机器语言，不能识别自然语言或高级语言，那么我们的高级语言程序是如何在计算机上执行的呢？在计算机上执行一个高级语言程序一般要分两步：第一步：用一个翻译程序把高级语言翻译成机器语言程序；第二步：运行所得的机器语言程序求得计算结果。第二步我们暂时不考虑，那么第一步“翻译程序”是我们这门课讨论的重点，什么样的程序叫翻译程序？翻译程序是如何翻译的？世界上第一个编译程序—FORTRAN编译程序是20世纪50年代中期研制成功的。2023/2/351.1翻译程序与编译程序

翻译程序是指这样一个程序,它把一种语言(称作源语言)所写的程序(源程序)翻译成等价的另一种语言(称作目标语言)的程序(目标程序)。

高级语言程序机器语言程序翻译程序#include<stdio.h>intmain(void){ printf("hello,world\n"); return0;}00001010…..2023/2/361.1翻译程序与编译程序

编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。

源程序高级语言程序编译程序目标程序汇编语言或者机器语言程序

定义：假设，SL指源语言程序，TL指目标语言程序，则：1.翻译程序－－把SL变换为TL的程序，SL与TL逻辑上等价。2.编译程序－－SL为高级语言、TL为低级语言的翻译程序。3.汇编程序－－SL为汇编语言程序，TL为机器语言程序。4.解释程序－－逐条翻译，且立即执行，不生成目标程序。2023/2/38程序运行阶段

采用编译方式在计算机上执行用高级语言编写的程序，需分阶段进行。第一种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段高级语言程序2023/2/39第二种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段汇编程序汇编语言目标程序汇编阶段高级语言程序程序运行阶段2023/2/3101.2编译过程与编译程序的基本结构

将英文句子“Iwishyousuccess”翻译成中文句子的大致过程是：

词法分析

语法分析

语义分析

修饰工作

翻译成文

2023/2/311

编译过程

编译程序是将一种语言形式翻译成另一种语言形式，因此，其工作过程一般可划分为如下五个阶段：

词法分析

语法分析

语义分析和中间代码生成

代码优化

目标代码生成2023/2/312floatr，h，s；

s=2*3.1416*r*(r＋h);例如计算圆柱体表面积的程序片断如下：

编译过程

2023/2/313

词法分析阶段的任务：对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词(也称单词符号,简称符号

)。

单词分类：基本字（if、else、for、while等）、标识符、常数、算符、界符（标点和括号）。1.

词法分析2023/2/314

词法规则是单词符号的形成规则,它规定了哪样的字符串构成一个单词符号。词法规则floatr，h，s；

s=2*3.1416*r*(h＋r)；例如2023/2/315

上述源程序通过词法分析识别出如下单词符号：基本字float 标识符r、h、s

常数3.1416、2 算符*、＋界符（、）、；、，、=词法规则2023/2/3162.语法分析

语法分析的任务是在词法分析的基础上,根据语言的语法规则从单词符号串中识别出各种语法单位,并进行语法检查,即检查各种语法单位在语法结构上的正确性。 语法单位：程序、程序段、语句、短语、表达式。2023/2/317语法规则

语言的语法规则规定了如何从单词符号形成语法单位，语法规则是语法单位的形成规则。floatr，h，s；

s=2*3.1416*r*(h＋r)；例如2023/2/318语法规则

单词符号串s=2*3.1416*r*(h＋r)中，“s”是<变量>，单词符号串

“2*3.1416*r*(h＋r)”组合成<表达式>这样的语法单位,由<变量>=<表达式>构成<赋值语句>这样的语法单位。2023/2/3193.语义分析和中间代码生成

语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式(比源语言更接近于目标语言的一种中间代码或直接用目标语言)来描述这种语义。中间代码的特点：结构简单、语义明确、易于转换、易于优化。中间代码的形式：

后缀式、三地址代码、四元式等。三地址代码：由指令序列组成，每条指令最多有三个操作数。四元式的形式是：

（算符，左操作数，右操作数，结果）2023/2/321

例如，前例中

将s

=2*3.1416*r*(h＋r)翻译成如下形式的四元式中间代码：(1)(*,2,3.1416,T1)(2)(*,T1, r,T2)(3)(+,h, r,T3)(4)(*,T2,T3,T4)(5)(=,T4,__,s)2023/2/3224.代码优化

代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效(即省时间和空间)的目标代码。优化主要包括局部优化和循环优化等，例如上述四元式经局部优化后得：(1)(*,6.28,

r,T2)(2)(+,h,r,T3)(3)(*,T2,T3,T4)(4)(=,T4,__,s)2023/2/3235.目标代码生成

目标代码生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。

2023/2/324表格管理和错误处理

编译程序在工作过程中需要建立一些表格，以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息，因此，在编译程序中必须有一组管理各种表格的程序。

在编译程序的各个阶段中，都要涉及表格管理和错误处理。2023/2/325表格管理和错误处理

一个好的编译程序在编译过程中，应具有广泛的程序查错能力，并能准确地报告错误的种类及出错位置，以便用户查找和纠正，因此，在编译程序中还必须有一个出错处理程序。

2023/2/326编译程序的结构

源程序语义分析和中间代码生成程序语法分析程序词法分析程序代码优化程序目标代码生成程序

目标程序表格管理程序出错处理程序(字符串)编译过程实例:Pascal语言的一条赋值语句：p:=i+r*60;

1.词法分析结果是识别出下列单词符号：标识符p

赋值号:＝标识符i标识符r

乘号*整常数60

分号；2.语法分析可得到如下所示的层次结构，称为语法分析树，简称语法树（或分析树）赋值语句表达式表达式标识符p+表达式标识符表达式标识符表达式数ir60*=：紧缩形式表示的语法分析树：:=p+i*r603.语义分析和中间代码生成类型检查是语义分析的一个重要部分，按照语言的类型规则检查和每个运算符相关的操作数。:=p+i*r60inttoreal语义分析插入整型到实型的转换由语义分析得到的分析树可得到表达式p:=i+r*60的三地址代码表示的中间代码：

t1:=inttoreal(60) t2:=r*t1 t3:=i+t2

p

:=t3:=p+i*r60inttoreal语义分析插入整型到实型的转换由语义分析得到的分析树可得到表达式p:=i+r*60的四元式表示的中间代码：(inttoreal()，60，，T1）(*，r，T1，T2)(+，i，T2，T3)(=，T3，_，p)课堂练习题：写出：Z:=Y*(X+0.418)/W的四元式和三地址代码表示的中间代码。4.代码优化p:=i+r*60的三地址代码可优化为用下面两条指令表示：

t1:=r*60.0

p

:=i+t15.目标代码生成例如：使用寄存器R1和R2，代码 t1:=r*60.0 p:=i+t1可以翻译成如下的代码：

MOVFr,R2MULF#60.0,R2MOVFi,R1ADDFR2,R1MOVFR1,p一个语句的翻译过程示意图Temp1:=id3*60.0id1:=id2+temp1中间代码生成器Temp1:=inttoreal(60)Temp2:=id3*temp1Temp3:=id2+temp2id1:=temp3代码优化器代码生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1从源程序到中间代码生成产品编译程序的结构源程序词法分析器语法分析器语义分析器中间代码生成器代码优化器目标代码生成器目标程序符号表管理器错误处理器分析部分综合部分

符号表管理符号表

是为每个标识符保存一个记录的数据结构，记录着每一个标识符的属性。符号表在各个阶段收集的信息一般不同。例如：在C，Pascal语言中的变量定义语句C语言:floatposition,initial,rate;Pascal语言:varposition,initial,rate:real;C语言中在读到变量名的时候，变量的属性已经知道，可以一起写入符号表，而Pascal语言中，词法分析器在程序扫描时，读到变量名的时候，并不知道标识符的属性，所以，符号表并不一定就记载有标识符的属性。出错处理一个好的编译程序不但能最大限度的发现错误，准确地指出错误的性质和发生错误的地点，而且能够把错误的范围缩小到尽可能小的范围，使程序的其他部分能继续编译下去；如果不仅能发现错误，而且能够知道校正错误就更好啦。源程序中的错误分为语法错误和语义错误

语法错误：源程序中不符合语法或词法规则的错误，可在语法或词法分析中检测出来。（非法字符、括号不配、缺少等）

语义错误：源程序中不符合语义规则的错误，一般在语义分析中检测出来，但有的要在运行时才能检测出来。（说明错误、作用域错误、类型不一致等）遍 编译程序具体实现时，受不同源语言、设计要求、使用对象和计算机条件的限制，往往将编译程序组织为若干遍。遍：就是对源程序或源程序的中间结果从头到位扫描一次，并作有关的加工，生成新的中间结果或目标程序。通常，一遍的工作，从外存上读取前一遍的中间结果开始，完成它的工作后，再将其产生的结果存到外存上去。例如：我们可以把词法分析、语法分析及语义分析与中间代码生成合为一遍。这时，语法分析处于核心位置，当他在识别语法结构时需要下一个单词，他就调用词法分析器，一旦识别出一个语法单位时，他就调用中间代码生成器。编译前端与后端编译前端主要由与源语言有关，但与目标机无关的部分组成。包括：词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可以包括在前端。编译后端主要由与目标机有关的部分组成。包括：与目标机有关的代码优化、目标代码生成等。可以取编译程序的前端，改写其后端生成不同目标机上的相同语言的编译程序。也可以为几种语言写出生成相同中间代码的前端，再配上相同的后端，形成同一台机器上不同语言的编译程序。编译器的伙伴语言扩充程序预处理器汇编器编译器装配器/连接编辑器源程序目标汇编程序绝对机器代码重定位机器代码库、重定位目标文件图1-5一个语言处理系统预处理器预处理器产生编译器的输入，负责收集源程序，他可以完成的任务：

（1）宏处理#define…

（2）文件包括例如：#include<math.h>

（3）语言扩充用内部宏定义增强老语言的功能（数据库语言、没有的语句结构）。宏处理的几个名词：宏定义、宏引用、形式参数、实在参数预处理器举例说明：

#definemin(a,b)

((a)>(b)?(b):(a))#include<stdio.h>main(){ intm,n,i;m=10;n=15;I=10*min(m,n);printf(“%d\n”,i);}汇编器源程序：b=a+2汇编语言程序：

mova,r1add#2,r1

movr1,b第一次扫描：结果：标识符地址

a0b4第二次扫描：

（可重定位的机器代码）

0001010000000000*0011011000000010

0010010000000100*装配器和连接编辑器装配器的两个功能:装入和连接编辑装入：指的是把可重定位的机器代码进行地址变换，装入内存储器指定的起始地址。连接编辑：指的是把几个可重定位的机器代码文件连接成一个可执行的程序。这些文件可以有分别编译或汇编产生的结果，也可以有从系统提供的库文件中取出的内容。2023/2/3461.3编译程序的生成方法

对源语言和目标语言认真分析

设计编译算法

选择语言编制程序

调试编译程序

提交相关文档资料

编译程序是一个复杂的系统程序，要生成一个编译程序一般要考虑以下几方面：2023/2/347编译程序的自动生成词法分析程序的自动生成系统LEX语法分析程序自动生成系统YACC编译程序产生器:可用来自动产生整个编译程序的软件工具,它的功能是将任一语言的词法规则、语法规则和语义解释的描述作为输入，自动生成该语言的编译程序。

随着编译技术和自动机理论的发展,近年来已研制出了一些编译程序的自动生成系统。如:2023/2/348编译程序的自动生成

生成编译程序的方