程序设计语言编译原理(第三版)第1章.ppt

《程序设计语言编译原理(第三版)第1章.ppt》由会员分享，可在线阅读，更多相关《程序设计语言编译原理(第三版)第1章.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理编译原理于静洋于静洋程序设计语言程序设计语言第一章第一章 引论引论1.1 1.1 什么叫编译程序什么叫编译程序1.2 1.2 编译过程概述编译过程概述1.3 1.3 编译程序的结构编译程序的结构1.4 1.4 编译程序与程序设计环境（略）编译程序与程序设计环境（略）1.5 1.5 编译程序的生成编译程序的生成1.1.1.1.什么是编译程序？什么是编译程序？什么是编译程序？什么是编译程序？1.1 什么叫编译程序什么叫编译程序翻译程序翻译程序：一种语言程序：一种语言程序-另一种语言程序另一种语言程序源语言源语言目标语言目标语言编译程序编译程序：高级语言程序：高级语言程序-低级语言程序低级语

2、言程序汇编程序汇编程序：汇编语言程序：汇编语言程序-机器语言程序机器语言程序解释程序解释程序：源语言程序：源语言程序-边解释边执行边解释边执行（1 1）编译方式：先编译后执行。）编译方式：先编译后执行。（2 2）解释方式：）解释方式：以源程序作为输入，但以源程序作为输入，但不产生目标代码不产生目标代码，而，而 是是边解释边执行边解释边执行源程序本身。源程序本身。2.2.2.2.“高级语言程序高级语言程序高级语言程序高级语言程序”的执行方式的执行方式的执行方式的执行方式1.1 什么叫编译程序什么叫编译程序编译和解释的主要区别：编译和解释的主要区别：是否产生目标代码！是否产生目标代码！3.3.“编

3、译程序编译程序”在计在计算机系统中的位置算机系统中的位置较接近于较接近于“硬件硬件”1.1 什么叫编译程序什么叫编译程序4.4.4.4.发展发展发展发展2020世纪世纪5050年代年代 第一个编译程序第一个编译程序 FORTRAN FORTRAN编译程序编译程序目前：目前：编译原理与技术得到迅速发展，现已形成一套比较编译原理与技术得到迅速发展，现已形成一套比较成熟的系统化的理论与方法，并开发出了一些好的编译程序成熟的系统化的理论与方法，并开发出了一些好的编译程序的实现语言、环境与工具。的实现语言、环境与工具。当时普遍认为设计和实当时普遍认为设计和实现编译程序是一件十分现编译程序是一件十分困难、

4、令人生畏的事情困难、令人生畏的事情1.1 什么叫编译程序什么叫编译程序1.2 编译过程概述编译过程概述Theelephantateanbanana.什么是语言？forK:=1to100dobeginM:=I+10*K;N:=J+10*Kend一一.类比自然语言翻译和编译过程类比自然语言翻译和编译过程英英汉汉 编译的工作过程编译的工作过程1)1)识别单词识别单词词法分析词法分析2)2)分析句子语法结构分析句子语法结构语法分析语法分析3)3)根据句子含义初步翻译根据句子含义初步翻译语义分析与中间代码产生语义分析与中间代码产生4)4)修饰译文修饰译文优化优化5)5)写出最后译文写出最后译文目标代码生

5、成目标代码生成1.2编译过程概述编译过程概述1.词法分析词法分析for K:=1 to 100 dobeginM:=I+10*K;N:=J+10*Kend 基本字基本字 for for 标识符标识符 K K 赋值号赋值号:=:=常数常数 1 1 基本字基本字 to to 常数常数 100 100 基本字基本字 do do 基本字基本字 begin begin .1.2 编译过程概述编译过程概述词法分析词法分析 规则：规则：规则描述工具：规则描述工具：任务：任务：依循词法规则依循词法规则.正规式和有限自动机（正规式和有限自动机（FAFA）.输入源程序输入源程序，对构成源程序的字符串进行扫描和，对

6、构成源程序的字符串进行扫描和分解，分解，识别出一个个的单词符号识别出一个个的单词符号，如基本字、标，如基本字、标识符、常数、算符、界符等。识符、常数、算符、界符等。1.2 编译过程概述编译过程概述2.语法分析语法分析for K:=1 to 100 dobeginM:=I+10*K;N:=J+10*Kend规则：规则：规则描述工具：规则描述工具：任务：任务：依循语法规则依循语法规则.上下文无关文法上下文无关文法.在词法分析的基础上，根据语言的语法规则，对单词在词法分析的基础上，根据语言的语法规则，对单词符号串进行语法分析，识别出各类语法单位，最终判符号串进行语法分析，识别出各类语法单位，最终判断

7、输入串是否构成语法上正确的断输入串是否构成语法上正确的“程序程序”。1.2 编译过程概述编译过程概述3.语义分析和中间代码产生语义分析和中间代码产生规则：规则：规则描述工具：规则描述工具：任务：任务：语义规则语义规则属性文法属性文法两部分工作：两部分工作：1.1.对每种语法范畴进行对每种语法范畴进行静态语义检查静态语义检查;2.2.若语义正确，则进行若语义正确，则进行中间代码翻译中间代码翻译.对语法分析器识别出的各类语法单位，分析对语法分析器识别出的各类语法单位，分析其含义并进行初步翻译（产生其含义并进行初步翻译（产生中间代码中间代码）。）。中间代码：一种独立于中间代码：一种独立于具体硬件的记

8、号系统，具体硬件的记号系统，更接近于机器代码更接近于机器代码 1.2 编译过程概述编译过程概述forK:=1to100dobeginM:=I+10*K;N:=J+10*Kend；K:=1L1:if100KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2K:=K+1gotoL1L2:语义分析后产生的中间代码：语义分析后产生的中间代码：三地址代码三地址代码具体实现：具体实现：三元式，四元式，间接三元式三元式，四元式，间接三元式1.2 编译过程概述编译过程概述 K:=1K:=1L L1 1:if 100K goto L:if 100K goto L2 2 T T1 1:=10

9、*K:=10*K M:=I+T M:=I+T1 1 T T2 2:=10*K:=10*K N:=J+T N:=J+T2 2 K:=K+1K:=K+1 goto L goto L1 1L L2 2:序号OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j*+*+j110010I10JKKKT1KT21K(9)T1MT2NK(2)四元式序列：四元式序列：1.2 1.2 编译过程概述编译过程概述任务：任务：对中间代码进行加工变换，以期在最后阶段能产生出对中间代码进行加工变换，以期在最后阶段能产生出 更为更为高效（省时间和空间）高效（省时间和空间）的目标代码。的

10、目标代码。4.4.优化优化包括：公共子表达式的提取、包括：公共子表达式的提取、循环优化、删除无用代码等循环优化、删除无用代码等1.2 1.2 编译过程概述编译过程概述序号序号 OPOPARG1ARG1 ARG2ARG2 RESULTRESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j*+*+j110010I10JKKKT1KT21K(9)T1MT2NK(2)序号序号 OPOPARG1ARG1 ARG2ARG2 RESULTRESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=:=:=j+jII1100MNK K10101MNK(9)MNK(2)优化前优化前优

11、化后优化后1.2 1.2 编译过程概述编译过程概述任务：任务：把中间代码变换成把中间代码变换成特定机器上特定机器上的低级语言代码，的低级语言代码，实现最后的翻译。实现最后的翻译。5.5.目标代码生成目标代码生成绝对指令代码绝对指令代码/可重定位的可重定位的指令代码指令代码/汇编指令代码汇编指令代码有赖于硬件系统结构和机器指令含义有赖于硬件系统结构和机器指令含义1.2 1.2 编译过程概述编译过程概述1.3 1.3 编译程序的结构编译程序的结构一一.编译程序总框图编译程序总框图1.1.表格管理表格管理 编译各各阶段都要涉及到构造、段都要涉及到构造、查找或找或 更新有关表格更新有关表格 。表格的作

12、用：表格的作用：登记源程序的登记源程序的各类信息各类信息和编译和编译各阶段的进展状况各阶段的进展状况。符号表：符号表：用来登记源程序中出现的每个用来登记源程序中出现的每个名字名字以及以及名字的各种属性名字的各种属性。举例：举例：名字名字变量名变量名/常量名常量名/过程名过程名？变量名变量名类型？类型？/内存？内存？/地址？地址？1.3 1.3 编译程序的结构编译程序的结构2.2.出错处理出错处理 每一每一阶段都可能段都可能检测出出错误，绝大多大多 数数错误可在前三可在前三阶段段检测出来出来.任务：任务：设法发现错误，并把有关错误信息报告给用户设法发现错误，并把有关错误信息报告给用户.语法错误语

13、法错误：源程序中不符合语法：源程序中不符合语法/词法规则的错误。词法规则的错误。词法词法/语法分析时检测语法分析时检测语义错误语义错误：源程序中不符合语义规则的错误。：源程序中不符合语义规则的错误。语义分析语义分析/运行时检测出来运行时检测出来1.3 1.3 编译程序的结构编译程序的结构二二.遍遍1.1.编译过程的划分：编译过程的划分：上述划分的五个阶段仅仅是上述划分的五个阶段仅仅是逻辑功能逻辑功能上的一种划分上的一种划分2.2.遍（遍（PassPass）对源程序或源程序的中间结果对源程序或源程序的中间结果从头到尾从头到尾扫描一次，并扫描一次，并作有关的加工处理，生成作有关的加工处理，生成新的

14、新的中间结果或目标程序。中间结果或目标程序。具体实现时，受各方面具体实现时，受各方面（如源语言、设计要求（如源语言、设计要求等）限制，往往组织成等）限制，往往组织成若干遍若干遍1.3 1.3 编译程序的结构编译程序的结构3.3.注意：注意：既可以将几个不同阶段合为一遍，也可以把一个阶段的既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍工作分为若干遍例如：例如：词法分析词法分析+语法分析语法分析 一遍一遍语法分析语法分析+语义分析与中间代码产生语义分析与中间代码产生一遍一遍优化优化 若干遍若干遍单遍代码单遍代码不太有效。不太有效。根据系统资源的状况、运行目标根据系统资源的状况、运行

15、目标的要求等，可以将一个编译程序的要求等，可以将一个编译程序设计形成多遍扫描的形式，在每设计形成多遍扫描的形式，在每一遍扫描中完成不同的任务。一遍扫描中完成不同的任务。1.3 1.3 编译程序的结构编译程序的结构当一遍中包含若干阶段时，各阶段的工作是穿插进行的当一遍中包含若干阶段时，各阶段的工作是穿插进行的。例如：例如：识别出一个语识别出一个语法单位时法单位时语法分析器语法分析器词法分析器词法分析器语义分析和中间代码产生器语义分析和中间代码产生器识别语法结构需识别语法结构需要下一个单词时要下一个单词时单单词词符符号号1.3 1.3 编译程序的结构编译程序的结构三三.编译前端与后端编译前端与后端

16、1.1.前端：前端：由与源语言由与源语言有关有关但与目标机但与目标机无关无关的那些部分组成的那些部分组成 包括包括词法分析、语法分析、语义分析与中间代码词法分析、语法分析、语义分析与中间代码 产生、部分代码优化工作产生、部分代码优化工作 2.2.后端：后端：包括编译程序中与目标机包括编译程序中与目标机有关有关的那些部分，如与的那些部分，如与 目标机有关的代码优化和目标代码生成等。目标机有关的代码优化和目标代码生成等。不依赖于源语言而仅仅不依赖于源语言而仅仅依赖于中间语言依赖于中间语言1.3 1.3 编译程序的结构编译程序的结构1.5 1.5 编译程序的生成编译程序的生成 一一.设计目标设计目标

17、 目标程序小，执行速度快目标程序小，执行速度快编译程序小，执行速度快编译程序小，执行速度快诊断能力强，可靠性强诊断能力强，可靠性强可移植性，可扩充性可移植性，可扩充性 如何实现编译器？如何实现编译器？直接用可运行直接用可运行的代码编制的代码编制太费力！太费力！1.5 1.5 编译程序的生成编译程序的生成 2.2.问题问题（1 1）历史上第一个高级语言的编译程序是怎样构造的？历史上第一个高级语言的编译程序是怎样构造的？-自编译技术（自展技术）自编译技术（自展技术）（2 2）已有已有A A机器上的机器上的L1L1语言（如：语言（如：C C语言）的编译程序，如何语言）的编译程序，如何构造构造A A机

18、器上的机器上的L2L2语言（如：语言（如：PASCALPASCAL语言）的编译程序？语言）的编译程序？（3 3）已有已有A A机器上的机器上的L L语言的编译程序，如何构造语言的编译程序，如何构造B B机器上的机器上的L L语言的编译程序？语言的编译程序？-交叉编译交叉编译/移植移植STI源语言源语言编译程序编译程序实现语言实现语言目标语言目标语言一般采用基于一般采用基于T T形图的方式：形图的方式：表现语言翻译的表现语言翻译的T T形图形图1.5 1.5 编译程序的生成编译程序的生成 问题：问题：已知已知A A机上有一个用机上有一个用A A代码实现的高级语言代码实现的高级语言L1L1的编的编

19、译程序，可以用译程序，可以用L1L1实现在实现在A A机上能运行一个新语言机上能运行一个新语言L2L2编编写的程序。写的程序。L1AA已知条件目标L2L1A二二.多级编译程序多级编译程序 1.1.本机编译器利用本机编译器利用 分析：分析：1.5 1.5 编译程序的生成编译程序的生成 条件目标L2L1AL1AAL2AAL L1 1语言写成的语言写成的L L2 2语言语言的编译程序的编译程序A A代码写成的代码写成的L L1 1语语言的编译程序言的编译程序得到得到A A代码写成的代码写成的L L2 2语言的编译程序语言的编译程序P P0 0P P1 1P P2 2说明：说明：P P0 0L L2

20、2语言的编译程序，用语言的编译程序，用L L1 1语言实现语言实现 P P1 1L L1 1语言的编译程序，用语言的编译程序，用A A代码实现代码实现 P P2 2L L2 2语言的编译程序，用语言的编译程序，用A A代码实现代码实现 1.5 1.5 编译程序的生成编译程序的生成 问题：问题：已知已知A A机上有一个用机上有一个用A A代码实现的高级语言代码实现的高级语言L L的的编译程序（即编译程序（即A A机上可直接运行机上可直接运行L L语言程序），是否可语言程序），是否可利用该编译程序实现在利用该编译程序实现在B B机上运行机上运行L L语言程序？语言程序？LAA条件目标LLB2.2.

21、交叉交叉编译/移植移植（思考思考）1.5 1.5 编译程序的生成编译程序的生成 LAA条件LLB目标LLBLAALABLLBLBB说明：说明：过程过程在在A A机上运行的产生机上运行的产生B B代码的代码的L L编译程序源程序（编译程序源程序（L L语言编写）语言编写）1.5 1.5 编译程序的生成编译程序的生成 1.5 1.5 编译程序的生成编译程序的生成 3.3.自编译过程自编译过程 通过一系列自展途径而形成编译程序的过程通过一系列自展途径而形成编译程序的过程叫做自编译过程。叫做自编译过程。1.5 1.5 编译程序的生成编译程序的生成 三三.如何学习构造编译程序如何学习构造编译程序 要在某

22、一台机器上为某种语言构造一个编译程序，必须掌要在某一台机器上为某种语言构造一个编译程序，必须掌握以下内容：握以下内容：源语言源语言：对被编译的源语言，要深刻理解其结构（语法）和对被编译的源语言，要深刻理解其结构（语法）和 含义（语义）。含义（语义）。目标语言目标语言：假定目标语言是机器语言，那么，假定目标语言是机器语言，那么，就必须搞清硬就必须搞清硬 件的系统结构和件的系统结构和OSOS的功能。的功能。编译方法编译方法：把一种语言程序翻译为另一种语言程序的方法很把一种语言程序翻译为另一种语言程序的方法很 多，但必须准确的掌握一、二。多，但必须准确的掌握一、二。第第1 1章章 总结总结1.1.编译程序的概念编译程序的概念2.2.编译过程（掌握）编译过程（掌握）3.3.基本概念：遍，编译前端基本概念：遍，编译前端/后端（掌握）后端（掌握）4.T4.T型图（了解）型图（了解）