编译原理课件：第1章 绪论

编译原理课程内容和教材

教材：《编译原理》（第二版）张素琴、芝吕映等，清华大学出版社内容：除以下说明外，按教材目录顺序(1)重点讲授1至12章的内容。(2)第6、7章放在最后讲授。(3)课堂和实验教学与第2章和附录A的PL/0编译程序紧密结合，要求读懂源程序，完成若干扩充编译器的实验，为期末课程设计打好基础。《编译原理》教材主要讲授内容第1章引论第2章PL/0编译程序的实现第3章文法和语言第4章词法分析第5章自顶向下语法分析第6章自底向上优先分析第7章LR分析第8章语法制导翻译和中间代码生成第9章符号表第10章目标程序运行时的存储组织第11章代码优化第12章代码生成第1章引论什么是编译程序编译过程概述编译程序的结构编译阶段的组合高级语言解释系统编译技术的应用什么是编译程序(compiler)语言和翻译低级语言（LowlevelLanguage)字位码、机器语言、汇编语言特点：与特定的机器有关，功效高，但使用复杂、繁 琐、费时、易出错高级语言

--Fortran、Pascal、C语言等特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。编译程序:编译程序就是一个语言的翻译程序,是把一种语言(称源语言)书写的程序翻译成另一种等价功能语言(称目标语言)的程序。换句话说，编译是指把一种用源语言表示的算法转换成另一种等价的用目标语言表示的算法所以，我们说编译程序是用某种语言编写的翻译程序源程序：用汇编语言或高级语言编写的程序称为源程序目标程序：用目标语言所表示的程序翻译程序：将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。源程序、翻译程序、目标程序三者关系：源程序翻译程序目标程序SOURCEPROGRAMTRANSLATEROBJECTPROGRAM即源程序是翻译程序的输入，目标程序是翻译程序的输出汇编程序

若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过程称为“汇编”编译程序若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称“编译”（Compile)汇编程序与编译程序都是翻译程序，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系。汇编程序所要做的翻译工作比编译程序简单的多。源程序的编译和运行编译或汇编阶段运行阶段源程序目标程序编译程序或汇编程序输出数据目标程序+运行子程序输入数据编译程序的必要性：随着计算机的普及，必须建立人与计算机之间的信息交流，但计算机只认识由“0”和“1”构成的机器语言。并不认识Pascal,C,C++,Java等高级程序设计语言。用机器语言书写的程序，不仅不易学，且可调试性，可读性，可维护性和结构性都很差，开发时间也很长。一条C语言语句if(i==0)i=3；

elsei=5;

由高级语言编写的程序虽然便于人类理解，但计算机无法识别。因此，编译程序必不可少。功能术语源语言S(源程序)目标语言O(目标程序)实现语言ISOI

高级语言书写的程序

编译程序低级语言程序源程序、翻译程序、目标程序三者关系：

预处理器编译器汇编器装配连接编辑需预处理的源程序

源程序

目标汇编程序

可重定位机器代码

绝对机器码可重定位目标文件库语言处理过程一个源程序可分为几个模块存放在不同的文件中,将这些源程序汇集在一起的任务由预处理程序来完成。有些预处理还包括宏展开。源语言实现语言目标语言汇编语言汇编程序机器语言高级语言编译程序低级语言翻译对象翻译程序翻译结果第1章引论什么是编译程序编译过程概述编译程序的结构编译阶段的组合高级语言解释系统编译技术的应用1.2编译过程概述编译逻辑过程词法分析语法分析语义分析中间代码生成代码优化目标代码生成词法分析（扫描器Scanner）

position:=initial+rate*60;

从左至右读字符流的源程序、识别(拼)单词例字符序列───>单词序列

词法分析

position:=initial+rate*60;

单词类型 单词值标识符1(id1) position

算符(赋值) :=

标识符2(id2) initial

算符(加) +

标识符3(id3) rate

算符(乘) *

整数 60

界符 ；又如一个C源程序片断：inta;a=a+2;词法分析后可能返回:

单词类型 单词值保留字int

标识符(变量名)

a

界符;

标识符(变量名)

a

算符(赋值) =

标识符(变量名)a

算符(加) +

整数 2

界符 ;语法分析（分析器Analyzer）任务：在词法分析的基础上，将单词序列组成各类语法短语如：语句、表达式、程序段等。功能:层次分析。依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树)。position:=initial+rate*60;规则<赋值语句>::=<标识符>“:=”<表达式><表达式>::=<表达式>“+”<表达式><表达式>::=<表达式>“*”<表达式><表达式>::=“(”<表达式>“)”<表达式>::=<标识符><表达式>::=<整数><表达式>::=<实数>语句分隔符

赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*positioninitialrate

60

id1:=id2+id3*N :=+N60*id1Positionid2initialid3rate

例A／B＊C语法树

表达式

项

项

＊

因子

项／

因子标识符

因子标识符

标识符<表达式>::=<项>|<表达式>+<项><项>::=<因子>|<项>*<因子>|<项>/<因子><因子>::=标识符|(<表达式>)ABC语义分析语义审查(静态语义)上下文相关性类型匹配类型转换例: programp(); varrate:real; procedureinitial; … position:=initial+rate*60; …又比如某些语言规定运算对象可被强制转换，那么当二目运算施于一个整型量和一个实型量时，编译程序应将整型量自动转换成实型量而不能认为是源程序的错误。如：在赋值语句:

position:=initial+rate*60算符*的两个运算对象分别是rate和60,而rate是实型变量，60是整型量。语义分析阶段进行类型审查之后，将整型量提升为实型量。在语法分析所得到的分析树上增加一个一目算符结点，这个结点的名称为inttoreal，表示将整型量变成实型量的语义处理。语义分析60:=+*Id1positionId2initialId3rateinttoreal中间代码生成在进行了上述的词法分析，语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。源程序的内部(中间)表示三元式、四元式、P-Code、C-Code等等。很多编译程序采用“四元式”中间代码。(运算符，运算对象1，运算对象2，结果)

中间代码生成 id1:=id2+id3*60(1) (inttoreal, 60, -, t1 )(2) (*, id3, t1, t2 )(3) (+, id2, t2, t3 )(4) (:=, t3, -, id1 )四元式：(运算符，运算对象1，运算对象2，结果)

30“四元式”的常用表示形式四元式(运算符，运算对象1，运算对象2，结果)常写成赋值语句的形式(结果=运算对象1运算符运算对象2)。比如c语言的源程序a=b*c+b*d的四元式序列为

(1)t1=b*c

(2)t2=b*d

(3)t3=t1+t2

(4)a=t3if(a<=b)

a=a–c;c=b*c;翻译成的四元式:(1)t1=a>b(2)ift1gotol(3)t2=a–c(4)a=t2(5)l:t3=b*c(6)c=t3翻译分支，循环和函数调用等语句时，四元式的生成就复杂一些。代码优化──可进行多次代码优化阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。例

id1:=id2+id3*60(1) (inttoreal, 60, -, t1 )(2) (*, id3, t1, t2 )(3) (+, id2, t2, t3 )(4) (:=, t3, -, id1 )变换(1) (*, id3, 60.0, t1 )(2) (+, id2, t1, id1 )代码优化t1=b*ct1=b*ct2=t1+0t2=t1+t1t3=b*ca=t2t4=t2+t3a=t4目标代码生成(* id3 60.0 t1 )(+ id2 t1 id1 )movf id3,R2mulf #60.0,R2movf id2,R1addfR2,R1movf R1,id1目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。

第一条指令将id3的内容送至寄存器R2，第二条指令将其与实常数60.0相乘，这里用#表明60.0处理为常数，第三条指令将id2移至寄存器R1，第四条指令计算出R1加R2的值，第五条指令将寄存器R1的值移到id1的地址中。一个语句的编译过程例：源程序为X1=5*X1+X2词法分析X1，=，5，*,X1，+，X2语法分析x25=x1+*x1语义分析T1=inttoreal（5）T2=X1*T1T3=X2+T2X1=T3代码优化T1=X1*5.0X1=X2+T1代码生成MOVx1，R1MUL5.0R1MOVX2R2ADDR1R2MOVR2,X1目标代码生成程序代码优化程序语义分析生成中间代码语法分析程序词法分析程序编译过程小结S.PO.P

按逻辑功能不同，可将编译过程划分为五个基本阶段，与此相对应，我们将实现整个编译过程的编译程序划分为五个逻辑阶段（即五个逻辑子过程）。每个阶段中都要有：符号表管理和错误处理符号表管理填表：把源程序中的信息和编译过程中所产生的信息登记在表格中。如：Const1常量 值：35Var1 变量 类型：实 层次：2查表：在随后的编译过程中同时又要不断的查找这些表格中的信息出错处理 检查错误报告出错信息排错恢复编译工作第1章引论

什么是编译程序编译过程概述编译程序的结构编译阶段的组合高级语言解释系统编译技术的应用1.3编译程序结构

(components)词法分析程序语法分析程序语义分析程序及中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序出错处理语法分析程序语义分析程序及中间代码生成程序目标代码生成程序词法分析程序代码优化程序表格管理第1章引论

什么是编译程序编译过程概述编译程序的结构编译阶段的组合高级语言解释系统编译技术的应用编译阶段也常常划分为两大步骤：分析步骤和综合步骤

分析步骤是指对源程序的分析

－线性分析(词法分析或扫描)

－层次分析(语法分析)

－语义分析

综合步骤是指后端的工作，为目标程序的生成而进行的综合

编译阶段的组合根据编译程序各部分功能，将编译程序分成前端和后端

前端：通常将与源程序有关的编译部分称为前端。 词法分析、语法分析、语义分析、中间代码生成

---分析部分

特点：与源语言有关

后端：与目标机有关的部分称为后端。代码优化、代码生成

---综合部分

特点：与目标机有关编译程序的前端和后端若按照这种组合方式实现编译程序，可以设想：某一编译程序的前端加上相应不同的后端则可以为不同的机器构成同一个源语言的编译程序。也可以设想：不同语言编译的前端生成同一种中间语言，再使用一个共同的后端，则可为同一机器生成几个语言的编译程序。一个编译过程可由一遍、两遍或多遍完成。遍（趟）从头到尾扫描源程序（各种形式）一遍(pass)。

例如一遍可以只完成词法分析工作；一遍完成词法分析和语法分析工作；甚至一遍完成整个编译工作。在实际的编译系统的设计中，编译的几个阶段的工作究竟应该怎样组合，即编译程序究竟分成几遍，参考的因素主要是源语言和机器(目标机)的特征。比如源语言的结构直接影响编译的遍的划分；像PL/1那样的语言，允许名字的说明出现在名字的使用之后，那么在看到名字之前是不便为包含该名字的表达式生成代码的，这种语言的编译程序至少分成两遍才容易生成代码。另外机器的情况，即编译程序工作的环境也影响编译程序的遍数的划分。遍数多一点，整个编译程序的逻辑结构可能清晰些，但遍数多即意味着增加读写中间文件的次数，势必消耗较多时间，一般会比一遍的编译要慢。第1章引论什么是编译程序编译过程概述编译程序的结构编译阶段的组合高级语言解释系统编译技术的应用

高级语言解释系统(interpreter)功能让计算机执行高级语言

它与编译程序的不同1）不生成目标代码

2）能支持交互环境

源程序

初始数据