编译原理基础精选文档.ppt

《编译原理基础精选文档.ppt》由会员分享，可在线阅读，更多相关《编译原理基础精选文档.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理基础本讲稿第一页，共五十页第第6章章 编译原理基础编译原理基础Principles of Compilation中原工学院软件学院中原工学院软件学院韩玉民韩玉民本讲稿第二页，共五十页编译程序是高级语言的支撑基础，是计算机系统中重要的系统软件之一。第第6章章 编译原理编译原理本讲稿第三页，共五十页6.1 6.1 程序设计语言的编译与解释程序设计语言的编译与解释程序设计语言的编译与解释程序设计语言的编译与解释6.2 6.2 形式语言形式语言形式语言形式语言6.3 6.3 第一阶段第一阶段第一阶段第一阶段 词法分析词法分析词法分析词法分析6.4 6.4 第二阶段第二阶段第二阶段第二阶段 语法

2、分析语法分析语法分析语法分析6.5 6.5 第三阶段第三阶段第三阶段第三阶段 语义分析与中间代码生成语义分析与中间代码生成语义分析与中间代码生成语义分析与中间代码生成6.6 6.6 第四阶段第四阶段第四阶段第四阶段 代码优化代码优化代码优化代码优化6.7 6.7 符号表管理和错误处理符号表管理和错误处理符号表管理和错误处理符号表管理和错误处理6.8 6.8 第五阶段第五阶段第五阶段第五阶段 目标代码生成目标代码生成目标代码生成目标代码生成 第第6章章 编译原理编译原理本讲稿第四页，共五十页程序设计语言分成两大类:n低级语言低级语言:包括机器语言和汇编语言，主要是面向机器的。n高级语言高级语言:

3、高级语言则是面向应用的，分成很多种，如FORTRAN、Pascal、C、C#、VB、Java等。6.1 程序设计语言的编译与解释程序设计语言的编译与解释6.1.1 6.1.1 程序设计语言程序设计语言程序设计语言程序设计语言本讲稿第五页，共五十页n机器语言本身是有由0和1组成的，符合计算机的硬件特性，因此能够直接执行。但用机器语言编写程序很不方便且容易出错，因此就用助记符代替机器语言，产生了汇编语言。n汇编语言比机器语言在可读性方面有了进步，但是其依赖具体机器的特性无法改变，给程序设计语言增添了难度。6.1.2 6.1.2 程序的编译与解释程序的编译与解释程序的编译与解释程序的编译与解释6.1

4、 程序设计语言的编译与解释程序设计语言的编译与解释本讲稿第六页，共五十页n高级语言不能直接在机器上运行，它不是面向机器，而是面向应用的，因此，要想让高级语言运行必须有编译程序。n n编译程序编译程序就是这样的一种程序，它能将高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。1.1.编译方式编译方式编译方式编译方式 6.1 程序设计语言的编译与解释程序设计语言的编译与解释本讲稿第七页，共五十页n高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段，源程序的运行过程如图1-1所示。#includeMain()For(;)Printf(“Hello World!n”);源程序编

5、译程序01101001100101011001001110101010101011000011111001011111110010101010001010001111101101目标程序编译初始数据目标程序、运行系统计算结果输入处理输出程序的编译 程序的执行 6.1 程序设计语言的编译与解释程序设计语言的编译与解释本讲稿第八页，共五十页n编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等）接受程序的初始数据作为输入，运行后输出计算结果。n如果目标程序是汇编语言的形式，则需要在编译阶段和运行阶段之间加一个汇编阶段。#includeMain

6、()For(;)Printf(“Hello World!n”);源程序汇编程序011010011001010010101011000011111011机器语言程序ADD A,BMOV B,C编译程序汇编语言程序 编译汇编6.1 程序设计语言的编译与解释程序设计语言的编译与解释本讲稿第九页，共五十页高级语言编写的程序除了可以通过编译方式外，还可以通过解释程序执行。所谓解释程序是一种语言翻译程序，按动态顺序，读入一条语句，解释一条语句，执行一条语句，即边翻译边执行。源程序解释程序计算结果源程序、输入解释执行输出数 据 2.2.解释方式解释方式解释方式解释方式 6.1 程序设计语言的编译与解释程序设

7、计语言的编译与解释本讲稿第十页，共五十页n高级语言源程序经编译程序编译的经过目标代码还可以是待装配高级语言源程序经编译程序编译的经过目标代码还可以是待装配的目标代码（相对目标代码），这种形式的目标程序通常由多个的目标代码（相对目标代码），这种形式的目标程序通常由多个目标模块组成，各目标模块由相应的源程序模块经编译生成，必目标模块组成，各目标模块由相应的源程序模块经编译生成，必须将相关的多个目标模块组装成到一个可执行目标程序中，才能须将相关的多个目标模块组装成到一个可执行目标程序中，才能运行。完成集成工作的程序称为连接程序。运行。完成集成工作的程序称为连接程序。n连接程序还连接目标程序和用于标准

8、库函数的代码，以及连接连接程序还连接目标程序和用于标准库函数的代码，以及连接目标程序和由计算机的操作系统提供的资源（例如，存储分配目标程序和由计算机的操作系统提供的资源（例如，存储分配程序及输入与输出设备）。程序及输入与输出设备）。3.3.连接程序（连接程序（连接程序（连接程序（linkerlinker）6.1 程序设计语言的编译与解释程序设计语言的编译与解释本讲稿第十一页，共五十页n解释程序与编译程序的主要区别是：解释程序与编译程序的主要区别是：l编译程序将源程序翻译成目标程序后再执行目标程序.l解释程序是逐条读出源程序中的语句并执行，即在解释程序的执行过程中并不产生目标程序。6.1 程序设

9、计语言的编译与解释程序设计语言的编译与解释本讲稿第十二页，共五十页6.1.3 6.1.3 编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构 编译程序的功能是将用高级语言编写的源程序翻译成等价的低级语言（汇编语言或机器语言）目标程序。编译的过程就是一个不同语言翻译的过程，所以其过程类似于自然语言的翻译。本讲稿第十三页，共五十页6.1.3 6.1.3 编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构 步骤完 成 的 工 作自

10、然语言翻译（英语翻译成汉语）编译程序（源程序翻译成机器目标代码）1根据英文单词拼写规则，识别出各个单词和标点符号等，并检查单词是否有拼写错误。这就是词法分析对源程序进行词法分析，检查有无拼写错误，识别出其中的单词（关键字、标识符等）2根据英文语法规则，对词法分析中得到的各个单词和标点符号等进行分析、检查，看是否能组成一个符合语法规则的句子。因此，该步骤称为语法分析进行语法分析，检查单词串是否组成符合语法的正确的程序语句，如表达式是否正确等3对语法分析后得到的符合英文语法规则的句子进行分析，理解句子的含义，初步翻译成中文。该步骤称为语义分析分析翻译语句要完成的操作，是将源程序初步翻译成目标程序（

11、一种中间代码）。这是为了方便编译过程的实现，同时也便于进行代码优化4对初步翻译的中文进行修饰、润色等代码优化5将英文翻译成最终的中文将优化后的中间代码转换成特定机器上的机器语言程序或汇编语言程序自然语言的翻译自然语言的翻译本讲稿第十四页，共五十页6.1.3 6.1.3 编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构 源程序词法分析语法分析语义分析和中间代码生成代码优化生成目标代码出错处理表格管理目标程序编译过程编译过程编译程序结构编译程序结构编译程序结构编译程序结构词法分析程序语法分析程序语义分析和中间代

12、码生成程序代码优化程序生成目标代码编译过程可以划分成五个阶段编译过程可以划分成五个阶段1.1.编译过程编译过程编译过程编译过程本讲稿第十五页，共五十页n编译程序的功能是把高级语言源程序翻译成等价的低级语言目标程序。n源程序是由一些基本符号构成的，我们在运行这个程序时，先编译，若某处有错误，就报错，无错误就运行。编译程序在编译时，先将程序中的单词一个个分离出来，登记在一个表中，这叫词法分析，然后检查语句格式，叫做语法分析。然后检查类型是否一致，计算表达式的值叫语义分析。这些功能都是由编译程序相应的程序完成的。6.1.3 6.1.3 编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的

13、结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构 本讲稿第十六页，共五十页n一般来说，整个编译过程可以划分成五个阶段：l词法分析阶段l语法分析阶段l语义分析和中间代码生成阶段l中间代码的优化l目标代码的生成。6.1.3 6.1.3 编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构 1.1.编译过程编译过程编译过程编译过程本讲稿第十七页，共五十页6.1.3 6.1.3 编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过

14、程和编译程序的结构 2.2.一遍与多遍编译一遍与多遍编译一遍与多遍编译一遍与多遍编译 编译程序还采用“分遍”的形式，即编译过程可通过一遍或多遍编译来完成。所谓编译的“一遍”（pass）是指下述过程：对于源程序或中间代码，从头到尾扫描一遍，并完成规定的处理任务，生成新的源程序的中间代码代码或目标代码。在单遍编译中，编译程序包括了编译程序的各个阶段的任务，所有的阶段由一遍完成，其结果是编译得很好，但通常代码效率差。本讲稿第十八页，共五十页6.1.3 6.1.3 编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构编译程序的编译过程和编译程序的结构

15、2.2.一遍与多遍编译一遍与多遍编译一遍与多遍编译一遍与多遍编译 在多遍扫描的编译程序中，每一遍完成一个或几个相关逻辑的工作，一个阶段的工作也可以分多遍来完成。例如，将词法分析作为第一编，语法分析和语义分析作为第二遍等。本讲稿第十九页，共五十页6.2 6.2 形式语言形式语言形式语言形式语言 程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述n 程序和自然语言一样，也有其语法规则，要对程序进行语法分析，就要先了解程序的语法规则。程序的语法规则称为文法，即文法是描述语言的形式规则（语法规则）。n n用一组数学符号和规则来描述的语言称为形式语言。用一组数学符号

16、和规则来描述的语言称为形式语言。用一组数学符号和规则来描述的语言称为形式语言。用一组数学符号和规则来描述的语言称为形式语言。n 目前程序设计语言都是用形式语言来描述，形式语言是编译原理的理论基础。1.1.什么是形式语言什么是形式语言什么是形式语言什么是形式语言?本讲稿第二十页，共五十页6.2 6.2 形式语言形式语言形式语言形式语言 程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序和自然语言一样，也有其语法规则，要对程序进行语法分析，就要先了解程序的语法规则。程序的语法规则称为文法，即文法是描述语言的形式规则（语法规则）。这种规则要能够描述程序语言各

17、种不同的结构，同时还要使程序能够易于分析和翻译，最好能够根据其语法规则自动生成有效的语法分析程序。目前程序设计语言都是用形式语言来描述目前程序设计语言都是用形式语言来描述，形式语言是编译原理的理论基础。本讲稿第二十一页，共五十页6.2 6.2 形式语言形式语言形式语言形式语言 程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述 2.2.字母表和符号串字母表和符号串字母表和符号串字母表和符号串 任何一种语言，都是由该语言的基本符号所组成的符号串的集合。例如，英语文章是由句子和标点符号构成的，句子是由单词构成的，而单词则是由字母构成的。本讲稿第二十二页，共五十

18、页6.2 6.2 形式语言形式语言形式语言形式语言 程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述 2.2.字母表和符号串字母表和符号串字母表和符号串字母表和符号串（1 1）字母表）字母表）字母表）字母表 字母表是符号的非空有穷集合，字母表中的元素称为符号。因此字母表也称为符号表。不同的语言有不同的字母表，例如英语的字母表是26个英文字母、数字和一些特殊符号。汉语的字母表是汉字、数字和专用符号等。而C语言的字母表包括关键字、字母、数字和一些专用符号。（2 2）符号串）符号串）符号串）符号串 字母表中的符号所组成的任何有穷序列称为该字母表上的符号串。例如

19、语句“if(x=8)then a=5 else a=9”可以看作是定义在C语言字母表上的一个符号串。本讲稿第二十三页，共五十页6.2 6.2 形式语言形式语言形式语言形式语言 程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述3.3.什么是文法什么是文法什么是文法什么是文法?文法是描述语言语法结构的形式规则。文法是描述语言语法结构的形式规则。文法是描述语言语法结构的形式规则。文法是描述语言语法结构的形式规则。我们以自然语言为例来说明。在描述一种语言时，就是要说明这种语言包含哪些句子。例如汉语，但汉语的句子有无穷多个，无法全部写出来。这就要制定有限条语法规则

20、，用这些语法规则来产生汉语的全部句子。这些规则就是所谓的文法。本讲稿第二十四页，共五十页6.2 6.2 形式语言形式语言形式语言形式语言 程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述3.3.什么是文法什么是文法什么是文法什么是文法?语法规则语法规则 例如，定义如下语法规则：例如，定义如下语法规则：语法规则语法规则 例如，定义如下语法规则：例如，定义如下语法规则：=|=我我|你你|他他|她她 =李翔李翔|韩方韩方|计算机计算机|大学生大学生|教师教师|C语言语言 =是是|学习学习 =由语法规则推导句子由语法规则推导句子本讲稿第二十五页，共五十页6.2

21、6.2 形式语言形式语言形式语言形式语言 程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述如用EBNF来描述文法的定义：=+|-=0|1|2|3|4|5|5|6|7|8|9本讲稿第二十六页，共五十页6.2 6.2 形式语言形式语言形式语言形式语言 程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述程序设计语言的语法描述 =|=|=_|=a|b|c|d|e|f|g|h|i|j|z =A|B|C|D|E|F|G|H|I|J|Z =|8|9 =0|1|2|3|4|5|6|7C语言的语言的“标识符标识符”用用BNF描述为：描述为：本讲稿第二十七页

22、，共五十页n词法分析是编译过程的基础，其任务是扫描源程序，根据语言的词法规则，分解和识别出每个单词，并把单词翻译成相应的机内表示。当然，词法分析在识别单词的过程中，同时也做了词法检查。6.3 第一阶段第一阶段-词法分析词法分析本讲稿第二十八页，共五十页n在高级语言中，所谓单词，就是指逻辑上紧密相连的一组字符，这些字符具有集体含义。n单词是语言中最小的语义单位，如语言中的关键字、标识符、运算符和界限符。n词法分析的依据是词的构造。单词的构造规则在高级语言中有明确的规定，比如哪些为保留字、变量如何定义、常量如何构造、分界符有哪些等。6.3 第一阶段第一阶段-词法分析词法分析本讲稿第二十九页，共五十

23、页词法分析的主要内容包括：（1）分析并识别单词及其属性；（2）跳过空格、回车、制表符等分隔符；（3）滤掉注释；（4）进行词法检查，报告发现的错误；（5）还要根据需要创建符号表、常量表等。6.3 第一阶段第一阶段-词法分析词法分析本讲稿第三十页，共五十页main()float x=2,y=3,s;s=x+y*5;n例如，用C 语言编写的程序段如下：n识别出的单词序列为表所示6.3 第一阶段第一阶段-词法分析词法分析本讲稿第三十一页，共五十页表表1 词法分析程序词法分析程序类型名单词类型名单词保留字main左括号(右括号)花括号保留字float标识符x等号=常量2逗号,标识符y等号=常量3逗号,标

24、识符s分号;标识符s等号=标识符x运算符+标识符y运算符*常量5分号;花括号6.3 第一阶段第一阶段-词法分析词法分析作为第二阶段的输入作为第二阶段的输入本讲稿第三十二页，共五十页n语法分析是在词法分析的 基础上进行的，是编译过程的第二个阶段。n语法分析的任务是根据语言的语法规则，把单词符号串分解成各类语法单位，如表达式、语句等。并在分析过程中，对单词串组成的源程序进行语法正确性检查。n通过语法分析，可以确定整个输入符号串是否构成一个正确的程序。6.4 第二阶段第二阶段-语法分析语法分析本讲稿第三十三页，共五十页6.4 第二阶段第二阶段-语法分析语法分析语法分析的结果是无语法错误的语法成分，有

25、多种输出形式。语法分析的结果是无语法错误的语法成分，有多种输出形式。本讲稿第三十四页，共五十页6.5 6.5 第三阶段第三阶段第三阶段第三阶段-语义分析和中间代码的生成语义分析和中间代码的生成语义分析和中间代码的生成语义分析和中间代码的生成n一个源程序通过词法分析和语法分析后，可以确定该源程序在单词拼写和语法上是正确的，但并没有分析其语句的逻辑含义，即要执行什么操作要执行什么操作要执行什么操作要执行什么操作？n词法和语法的正确并不能保证语义的正确n正如一篇单词拼写正确、语法正确的文章，人们在阅读时首先是要能读通，然后是要理解每句话及整篇文章的含义或思想。这就是对文章的语义分析。本讲稿第三十五页

26、，共五十页语义分析的任务是对各种不同语句进行翻译，包括两方面的工作：n一是对每种语法范畴进行语义检查，如变量是否定义、一是对每种语法范畴进行语义检查，如变量是否定义、类型是否正确等；类型是否正确等；n二是在语义检查正确的情况下，进行中间代码的翻译。二是在语义检查正确的情况下，进行中间代码的翻译。程序的语义分析就是对程序的逻辑含义进行分析，是编译过程中最实质性的工作。Why?6.5 6.5 第三阶段第三阶段第三阶段第三阶段-语义分析和中间代码的生成语义分析和中间代码的生成语义分析和中间代码的生成语义分析和中间代码的生成1.1.语义分析语义分析语义分析语义分析本讲稿第三十六页，共五十页中间代码是介

27、于高级语言语句和低级语言语句之间的一种独立于具体硬件的记号系统，它即有一定程度的抽象，又和低级语言十分接近，因此，转换成目标代码很容易。Why?6.5 6.5 第三阶段第三阶段第三阶段第三阶段-语义分析和中间代码的生成语义分析和中间代码的生成语义分析和中间代码的生成语义分析和中间代码的生成2.2.中间代码的生成中间代码的生成中间代码的生成中间代码的生成本讲稿第三十七页，共五十页中间代码的表示形式有很多种，常见的有:n四元式n三元式n间接三元式n逆波兰式等。其中四元式的形式为:（运算符，运算对象1，运算对象2，结果）6.5 6.5 第三阶段第三阶段第三阶段第三阶段-语义分析和中间代码的生成语义分

28、析和中间代码的生成语义分析和中间代码的生成语义分析和中间代码的生成本讲稿第三十八页，共五十页6.6 第四阶段第四阶段中间代码优化中间代码优化代码优化就是为提高目标代码质量而进行的加工和处理工作，使得目标代码在执行时效率更高，即执行时间更短，同时占用内存空间更小。一般优化工作阶段是在中间代码生成之后或目标代码生成之后，实际上，编译程序通常包括许多代码改进或优化步骤。本讲稿第三十九页，共五十页中间代码优化通过调整和改变中间代码中某些操作次序，以最终产生更加高效的目标代码。优化的主要手段有:l删除冗余运算l删除无用赋值l合并已知量l循环优化等。6.6 第四阶段第四阶段中间代码优化中间代码优化本讲稿第

29、四十页，共五十页6.6 第四阶段第四阶段中间代码优化中间代码优化本讲稿第四十一页，共五十页n这一阶段的任务是对前一阶段的中间代码变换成特定机器上的机器语言或汇编语言程序，实现机器的最终翻译。n最后阶段的工作因为目标语言的关系而十分依赖机器的硬件系统，即如何充分利用机器现存的寄存器，合理的选择指令，生成尽可能短的目标代码，这与机器的硬件有关。6.7 第五阶段第五阶段目标代码的生成目标代码的生成本讲稿第四十二页，共五十页目标代码生成程序生成的目标代码有不同的形式，一般有以下三种形式。（1）能够立即执行的机器语言代码）能够立即执行的机器语言代码 这种代码所有地址已定位，编译后可以立即执行。（2）待装

30、配的机器语言代码模块）待装配的机器语言代码模块 需要执行时，必须经由连接装配程序将它们与另外一些运行子程序（如语言的系统函数库）连接装配起来，构成可以执行的机器代码。（3）汇编语言代码）汇编语言代码 必须经过汇编程序将其汇编成可执行的机器语言代码。6.7 第五阶段第五阶段目标代码的生成目标代码的生成本讲稿第四十三页，共五十页6.7 第五阶段第五阶段目标代码的生成目标代码的生成本讲稿第四十四页，共五十页词法分析器语法分析器语义分析器中间代码生成器中间代码的优化目标代码生成器源程序表格管理出错处理目标程序编译程序结构示意图6.8 符号表管理和错误处理符号表管理和错误处理本讲稿第四十五页，共五十页6

31、.8 符号表管理和错误处理符号表管理和错误处理 在编译的各个阶段常常要收集和使用源程序的各种信息，为了方便，通常把这些信息保存在一些表中，如关键字表、常量表、数组信息表、标识符表等等，这关键字表、常量表、数组信息表、标识符表等等，这些表称为符号表些表称为符号表。这样，对源程序各种信息的记录、使用和管理，实际上就是对这些符号表的存储、访问和管理。1.符号表符号表 本讲稿第四十六页，共五十页6.8 符号表管理和错误处理符号表管理和错误处理 1.符号表符号表 本讲稿第四十七页，共五十页6.8 符号表管理和错误处理符号表管理和错误处理 2.错误处理错误处理 尽管现在许多集成开发环境都提供了多种方法来保

32、证源程序的正确性，如Visual Studio的关键字及其属性和方法的逐步提示等，但源程序往往含有各种各样的错误，包括不符合词法规则、语法规则、语义规则等规定产生的错误，以及数组维数太大等违反语言环境限制的错误等。例如编程时经常出现的关键字拼写错误、变量未声明、语句缺少成分不符合语法规则、运算的操作数类型不匹配等等。本讲稿第四十八页，共五十页6.8 符号表管理和错误处理符号表管理和错误处理 2.错误处理错误处理 对于有错误的源程序，编译程序要具有查错和改错的功能。n n查错查错查错查错是指在编译过程中应该能够准确、及时地检查出错误，并以简明的形式报告错误的性质和出错位置，使程序员能够方便地修改源程序。n n改错改错改错改错是指在编译时不能一发现有错误就终止编译工作，发现错误时要对错误做适当的处理，从而使编译工作能够继续下去。本讲稿第四十九页，共五十页小小 结结本讲稿第五十页，共五十页