编译原理课件：Chapter-1 概论

《编译原理课件：Chapter-1 概论》由会员分享，可在线阅读，更多相关《编译原理课件：Chapter-1 概论（28页珍藏版）》请在金锄头文库上搜索。

1、1编译原理编译原理2课程要求课程要求 分为两部分上分为两部分上:(:(分别计分分别计分) )编译原理编译原理理论基础理论基础(48(48学时学时) ) 课堂教学，按时交作业课堂教学，按时交作业(30%)(30%)，闭卷考试，闭卷考试(70%)(70%)。编译实践编译实践实践部分实践部分(32(32机时机时) ) 上机实践，自己独立编写一个编译系统。上机实践，自己独立编写一个编译系统。编译原理编译原理和和编译实践编译实践需同时选修！需同时选修！ 目的目的: 掌掌握握编编译译的的基基本本理理论论、常常用用的的编编译译技技术术，了了解解编编译译过过程程及及编编译译系系统统的的构构造造（结结构构和和机

2、机理理）。能能运运用用所所学学技技术解决实际问题，能独立编写一个小型编译系统术解决实际问题，能独立编写一个小型编译系统。3教材教材张莉等，张莉等，编译原理及编译程序构造编译原理及编译程序构造，清华出版社，清华出版社，2011年年6月。月。参考书参考书Alfred V. Aho等，等，编译原理编译原理（龙书），机械工业出（龙书），机械工业出版社。版社。刘春林等，刘春林等，编译原理编译原理学习指导与典型题解析学习指导与典型题解析，国防工业出版社。国防工业出版社。2004年年8月。月。要求：要求：提前预习，上课认真听讲；提前预习，上课认真听讲；课后即时复习，认真完成作业。课后即时复习，认真完成作业。

3、辅导老师（辅导老师（TA）：）：4第一章第一章概论概论（介绍名词术语、了解编译系统的结构和编译过程）（介绍名词术语、了解编译系统的结构和编译过程）5内内 容容1.1. .编译的起源：程序设计语言的发展编译的起源：程序设计语言的发展1.2. 基本概念基本概念1.3. 编译过程和编译程序构造编译过程和编译程序构造 1.4. 编译技术的其它应用编译技术的其它应用61.1 基本概念基本概念低级语言低级语言（Low level Language)字位码、机器语言、汇编语言字位码、机器语言、汇编语言特特点点：与与特特定定的的机机器器有有关关，功功效效高高，但但使使用用复复杂杂、繁繁 琐、费时、易出错。琐、

4、费时、易出错。高级语言高级语言 Fortran、Pascal、C语言等语言等特点：不依赖具体机器，移植性好，对用户要求低，特点：不依赖具体机器，移植性好，对用户要求低，易使用，易维护等。易使用，易维护等。7 源程序源程序 用汇编语言或高级语言编写的程序称为源程序。用汇编语言或高级语言编写的程序称为源程序。 目标程序目标程序 用用目标语言目标语言所表示的程序。所表示的程序。 目标语言：可以是介于源语言和机器语言之间的目标语言：可以是介于源语言和机器语言之间的“中中间语言间语言”，可以是某种机器的机器语言，可以是某种机器的机器语言, ,也可以是某也可以是某种种机机器的汇编语言。器的汇编语言。 翻译

5、程序翻译程序 将将源程序源程序转换为转换为目标程序目标程序的程序称为翻译程序。它是的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。程序、编译程序以及各种变换程序的总称。8源程序、翻译程序、目标程序源程序、翻译程序、目标程序 三者关系：三者关系：源程序源程序翻译程序翻译程序目标程序目标程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM即源程序是翻译程序的输入，目标程序是翻译程序的输出。即源程序是翻译程序的输入，目标程序是翻译程序的输出。9 汇编程序与编

6、译程序都是汇编程序与编译程序都是翻译程序翻译程序，主要区别是加工对象，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一的不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系，所以汇编程序所要做的翻译工作比编译程序简对应的关系，所以汇编程序所要做的翻译工作比编译程序简单得多单得多。 汇编程序汇编程序 若源程序用汇编语言书写，经过翻译程序得到用机器语言若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序。这种翻译过表示的程序，这时的翻译程序就称之为汇编程序。这种翻译过程称为程称为“汇编汇编”(Assemble)。 编译程序编译程

7、序 若源程序是用高级语言书写，经加工后得到目标程序，上若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称述翻译过程称“编译编译” (Compile)。10源程序的编译和运行源程序的编译和运行编译或汇编阶段编译或汇编阶段运行阶段运行阶段源程序源程序目标程序目标程序编译程序编译程序或汇编程序或汇编程序输出数据输出数据目标程序目标程序+运行子程序运行子程序输入数据输入数据11工作过程工作过程解释程序（解释程序（Interpreter） 对源程序进行解释执行的程序。对源程序进行解释执行的程序。输出数据输出数据输入数据输入数据源程序源程序 特点、与编译程序比较特点、与编译程序比较解释程序解释

8、程序12“编译编译-解释执行解释执行”系统系统源程序源程序编译程序编译程序源程序的中间形式输出数据输出数据解释程序解释程序输入数据输入数据13 所谓编译过程是指将所谓编译过程是指将高级语言程序高级语言程序翻译为等价的翻译为等价的目标程目标程序序的过程。的过程。1.2 编译过程编译过程词法分析词法分析语法分析语法分析语义分析、生成中间代码语义分析、生成中间代码代码优化代码优化生成目标程序生成目标程序习惯上是将编译过程划分为习惯上是将编译过程划分为5 5个基本阶段：个基本阶段：14单词：单词：是语言的基本语法单位，一般语言有四大类单词是语言的基本语法单位，一般语言有四大类单词 语言定义的关键字或保

9、留字语言定义的关键字或保留字（如（如BEGIN、END、IF） 标识符标识符 常数常数 分界符分界符（运算符）（运算符） （如（如+ +、- -、* *、/ /、; ;、（、）、（、） ）对于如下的字符串对于如下的字符串,词法分析程序将分析和识别出词法分析程序将分析和识别出9个单词个单词： X1 := ( 2.0 + 0.8 ) * C1 1 2 3 4 5 6 7 8 9 源程序是由字符序列构成的，词法分析扫描源程序源程序是由字符序列构成的，词法分析扫描源程序( (字符串字符串),),根据语言的词法规则分析并识别单词，并以某根据语言的词法规则分析并识别单词，并以某种编码形式输出种编码形式输出

10、。一、词法分析一、词法分析 任务：分析和识别任务：分析和识别单词单词。15 例如，对于前面提到的例子例如，对于前面提到的例子X1 := (2.0 + 0.8 ) * C1 我们可以根我们可以根据语言赋值语句的文法来分析和识别该语句（单词串）。首先给据语言赋值语句的文法来分析和识别该语句（单词串）。首先给定文法定文法： :=:= 语法分析根据文法，将语法分析根据文法，将 、 、 识识别出来，进而将赋值语句识别出来。在识别过程中进行语法检查；别出来，进而将赋值语句识别出来。在识别过程中进行语法检查；若有错误，则应输出出错信息。若有错误，则应输出出错信息。任务：根据任务：根据语法规则语法规则（即语言

11、的文法），分析并识别出（即语言的文法），分析并识别出各种语法成分，如表达式、各种说明、各种语句、各种语法成分，如表达式、各种说明、各种语句、 过程、函数、程序等，并进行语法正确性检查过程、函数、程序等，并进行语法正确性检查。二二、语法分析语法分析16中间代码：一种介于源语言和目标语言之间的中间语言形式。中间代码：一种介于源语言和目标语言之间的中间语言形式。生成中间代码的目的：生成中间代码的目的： 便于做优化处理；便于做优化处理； 便于编译程序的移植（中间代码不依赖于目标计便于编译程序的移植（中间代码不依赖于目标计 算机）。算机）。中间代码的形式：编译程序设计者可以自己设计，常用的有中间代码的形

12、式：编译程序设计者可以自己设计，常用的有 四元式四元式、三元式三元式、逆波兰表示逆波兰表示等等。 任务：对识别出的各种语法成分进行语义分析，并产生相应任务：对识别出的各种语法成分进行语义分析，并产生相应的的中间代码。中间代码。三三、语义分析、生成中间代码语义分析、生成中间代码17例：例： X1 := ( 2.0 + 0.8 ) * C1 由语法分析识别出为赋值语句，由语法分析识别出为赋值语句，语义分析语义分析首先首先要分析语义上的正确性，例如要检查表达式中和赋要分析语义上的正确性，例如要检查表达式中和赋值号两边的类型是否一致。值号两边的类型是否一致。 根据赋值语句的语义，根据赋值语句的语义，生

13、成中间代码生成中间代码。即用一。即用一种语言形式来代替另一种语言形式，这是翻译的关种语言形式来代替另一种语言形式，这是翻译的关键步骤。（翻译的实质：键步骤。（翻译的实质：语义的等价性语义的等价性） 下面介绍一种常用的中间代码来替换上述的赋下面介绍一种常用的中间代码来替换上述的赋值语句。值语句。18四元式四元式（三地址指令三地址指令）四元式的语义为： 2.0 + 0.8 T1 T1 * C1 T2 T2 X1 这样所生成的四元式与原来的赋值语句在语言的形式上不同，但语义上等价。 运算符 左运算对象 右运算对象 结果(1) + 2.0 0.8 T1(2) * T1 C1 T2(3) := X1 T

14、2 其中T1和T2为编译程序引入的工作单元。对于前面提到的例子 X1 := ( 2.0 + 0.8 ) * C119 例如：上面的四元式中第一个四元式是计算常例如：上面的四元式中第一个四元式是计算常量表达式值，该值在量表达式值，该值在编译时编译时就可以算出并存放在工就可以算出并存放在工作单元中，不必生成目标指令来计算，这样四元式作单元中，不必生成目标指令来计算，这样四元式可优化为：可优化为： 编译时编译时：2.0 + 0.8 T1运算符运算符 左运算对象左运算对象 右运算对象右运算对象 结果结果 * T1 C1 T2 := X1 T2 任务：任务：目的是为了得到高质量的目标程序。目的是为了得到

15、高质量的目标程序。 四四、代码优化代码优化20五、生成目标程序五、生成目标程序 由中间代码很容易生成目标程序（地址指令序列）。这由中间代码很容易生成目标程序（地址指令序列）。这部分工作与机器关系密切，所以要根据具体机器进行。在部分工作与机器关系密切，所以要根据具体机器进行。在做这部分工作时（要注意充分利用累加器），也可以进行做这部分工作时（要注意充分利用累加器），也可以进行优化处理。优化处理。 注意：在翻译成目标程序的过程中，要切记保持语义注意：在翻译成目标程序的过程中，要切记保持语义的等价性。的等价性。211.3 编译程序构造编译程序构造 1.3.1 编译程序的逻辑结构编译程序的逻辑结构按逻

16、辑功能不同，可将编译过程划分为五个基本阶按逻辑功能不同，可将编译过程划分为五个基本阶 段。与此相对应，我们将实现整个编译过程的编译程序划段。与此相对应，我们将实现整个编译过程的编译程序划 分为五个逻辑阶段（即五个逻辑子过程）。分为五个逻辑阶段（即五个逻辑子过程）。O.P生成目标程序代码优化程序语义分析生成中间代码语法分析程序S.P词法分析程序22在上列五个阶段中都要做两件事：在上列五个阶段中都要做两件事：（1）建表和查表建表和查表 （2）出错处理出错处理所以编译程序中都要包括表格管理和出错处理两部分。所以编译程序中都要包括表格管理和出错处理两部分。 出错处理出错处理 规模较大的源程序难免有多种

17、错误。编译程序必须要有出规模较大的源程序难免有多种错误。编译程序必须要有出错处理的功能，即能诊察出错误，并向用户报告错误性质和位错处理的功能，即能诊察出错误，并向用户报告错误性质和位置，以便用户修改源程序。出错处理能力的优劣是衡量编译程置，以便用户修改源程序。出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。序质量好坏的一个重要指标。 表格管理（符号表组织）表格管理（符号表组织） 在整个编译过程中始终都要贯穿着建表（填表）和查表的工在整个编译过程中始终都要贯穿着建表（填表）和查表的工作。即要及时地把源程序中的信息和编译过程中所产生的信息登作。即要及时地把源程序中的信息和编译过程中所产生的

18、信息登记在表格中，而在随后的编译过程中同时又要不断地查找这些表记在表格中，而在随后的编译过程中同时又要不断地查找这些表格中的信息。格中的信息。23典型的编译程序具有典型的编译程序具有7个逻辑部分个逻辑部分S.PO.P语义分析、生成中间代码语义分析、生成中间代码生成目标程序生成目标程序代码优化代码优化语法分析程序语法分析程序词法分析程序词法分析程序出出错错处处理理符符号号表表管管理理241.3.2 遍（遍（PASS） 遍遍：对源程序（包括源程序中间形式）从头到尾扫描一次，：对源程序（包括源程序中间形式）从头到尾扫描一次，并做有关的加工处理，生成新的源程序中间形式或目标程序，并做有关的加工处理，生

19、成新的源程序中间形式或目标程序，通常称之为一遍。通常称之为一遍。 第一遍 第二遍 S.P中间形式中间形式1S.P中间形式中间形式2C2C1S.PO.P 上一遍的结果是下一遍的输入，最后一遍生成目标程序。五个基本阶段五个基本阶段：是将源程序翻译为目标程序在逻辑上要完成的：是将源程序翻译为目标程序在逻辑上要完成的 工作。工作。 遍遍：是指完成上述：是指完成上述5个基本阶段的工作，要经过几次扫描处理。个基本阶段的工作，要经过几次扫描处理。要注意遍与基本阶段的区别要注意遍与基本阶段的区别25一遍扫描即可完成整个编译工作的称为一遍扫描即可完成整个编译工作的称为一遍扫描编译程序。一遍扫描编译程序。 取单词

20、取单词 返回单词返回单词其结构为其结构为：S.P.词法分析语法分析整理目标程序 停机语义分析生成目标程序O.P.语法成分语法成分返回分析结果返回分析结果261.3.3 前端和后端前端和后端 根据编译程序各部分功能，将编译程序分成根据编译程序各部分功能，将编译程序分成前端前端和和后端后端。 前端前端：通常将与：通常将与源程序源程序有关的编译部分称为前端。有关的编译部分称为前端。 词法分析、语法分析、语义分析、中间代码生成、词法分析、语法分析、语义分析、中间代码生成、 代码优化代码优化 -分析部分分析部分 特点：与特点：与源语言源语言有关有关 后端后端：与：与目标机目标机有关的部分称为后端。有关的

21、部分称为后端。 目标程序生成（与目标机有关的优化）目标程序生成（与目标机有关的优化）-综合部分综合部分 特点：与特点：与目标机目标机有关有关271.4 1.4 编译程序的前后处理器编译程序的前后处理器编译程序的前后处理器编译程序的前后处理器 源程序源程序：多文件、宏定义和宏调用，包含文件：多文件、宏定义和宏调用，包含文件 目标程序目标程序：一般为汇编程序或可重定位的机器代码：一般为汇编程序或可重定位的机器代码框架源程序框架源程序预处理器预处理器源程序源程序编译程序编译程序目标程序（汇编）目标程序（汇编）汇编程序汇编程序可重定位机器码可重定位机器码（Obj文件）文件）可重定位机器码可重定位机器码（文件组）（文件组）连接编译连接编译库目标、可重库目标、可重定位目标文件定位目标文件可重定位机器码可重定位机器码加载器加载器可运行的机器代码可运行的机器代码281.5 1.5 编译技术的应用编译技术的应用编译技术的应用编译技术的应用语法制导的结构化编译器语法制导的结构化编译器程序格式化工具程序格式化工具软件测试工具软件测试工具程序理解工具程序理解工具高级语言的翻译工具高级语言的翻译工具等等。等等。作业：第作业：第15页页1、2、3题题