《程序设计语言编译原理(版)》由会员分享，可在线阅读，更多相关《程序设计语言编译原理(版)（180页珍藏版）》请在金锄头文库上搜索。
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什么叫编译程序什么叫编译程序翻译程序翻译程序：一种语言程序：一种语言程序-另一种语言程序另一种语言程序源语言源语言目标语言目标语言编译程序编译程序：高级语言程序：高级语言程序-低级语言程序低级语言程序汇编
2、程序汇编程序：汇编语言程序：汇编语言程序-机器语言程序机器语言程序解释程序解释程序：源语言程序：源语言程序-边解释边执行边解释边执行（1）编译方式：先编译后执行。）编译方式：先编译后执行。（2）解释方式：）解释方式：以源程序作为输入，但以源程序作为输入，但不产生目标代码不产生目标代码，而，而 是是边解释边执行边解释边执行源程序本身。源程序本身。2.“2.“高级语言程序高级语言程序高级语言程序高级语言程序”的执行方式的执行方式的执行方式的执行方式1.1什么叫编译程序什么叫编译程序编译和解释的主要区别：编译和解释的主要区别：是否产生目标代码！是否产生目标代码！3.3.“编译程序编译程序”在计算在计
3、算机系统中的位置较机系统中的位置较接近于接近于“硬件硬件”1.1 什么叫编译程序什么叫编译程序4.4.发展发展发展发展20世纪世纪50年代年代 第一个编译程序第一个编译程序FORTRAN编译程编译程序序目前：目前：编译原理与技术得到迅速发展，现已形成一套比较编译原理与技术得到迅速发展，现已形成一套比较成熟的系统化的理论与方法，并开发出了一些好的编译程序成熟的系统化的理论与方法，并开发出了一些好的编译程序的实现语言、环境与工具。的实现语言、环境与工具。当时普遍认为设计和实当时普遍认为设计和实现编译程序是一件十分现编译程序是一件十分困难、令人生畏的事情困难、令人生畏的事情1.1什么叫编译程序什么叫
4、编译程序1.2编译过程概述编译过程概述Theelephantateanbanana.什么是语言？forK:=1to100dobeginM:=I+10*K;N:=J+10*Kend一一.类比自然语言翻译和编译过程类比自然语言翻译和编译过程英英汉汉 编译的工作过程编译的工作过程1)识识别别单单词词 词词法法分分析析2)分分析析句句子子语语法法结结构构 语语法法分分析析3)根根据据句句子子含含义义初初步步翻翻译译 语语义义分分析析与与中中间间代代码码产产生生4)修修饰饰译译文文 优优 化化5)写写出出最最后后译译文文 目目标标代代码码生生成成1.2编译过程概述编译过程概述1.词法分析for K:=1
5、 to 100 dobeginM:=I+10*K;N:=J+10*Kend 基本字基本字 forfor 标识符标识符 K K 赋值号赋值号 :=:=常数常数 1 1 基本字基本字 toto 常数常数 100100 基本字基本字 dodo 基本字基本字 beginbegin .1.2编译过程概述编译过程概述词法分析词法分析 规则：规则：规则描述工具：规则描述工具：任务：任务：依循词法规则依循词法规则.正规式和有限自动机（正规式和有限自动机（FA）.输入源程序输入源程序，对构成源程序的字符串进行扫描和，对构成源程序的字符串进行扫描和分解，分解，识别出一个个的单词符号识别出一个个的单词符号，如基本字
6、、标，如基本字、标识符、常数、算符、界符等。识符、常数、算符、界符等。1.2编译过程概述编译过程概述2.语法分析for K:=1 to 100 dobeginM:=I+10*K;N:=J+10*Kend规则：规则：规则描述工具：规则描述工具：任务：任务：依循语法规则依循语法规则.上下文无关文法上下文无关文法.在词法分析的基础上，根据语言的语法规则，对单词在词法分析的基础上，根据语言的语法规则，对单词符号串进行语法分析，识别出各类语法单位，最终判符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的断输入串是否构成语法上正确的“程序程序”。1.2编译过程概述编译过程概述3.语
7、义分析和中间代码产生规则：规则：规则描述工具：规则描述工具：任务：任务：语义规则语义规则属性文法属性文法两部分工作：两部分工作：1.对每种语法范畴进行对每种语法范畴进行静态语义检查静态语义检查;2.若语义正确，则进行若语义正确，则进行中间代码翻译中间代码翻译.对语法分析器识别出的各类语法单位，分析对语法分析器识别出的各类语法单位，分析其含义并进行初步翻译（产生其含义并进行初步翻译（产生中间代码中间代码）。）。中间代码：一种独立于中间代码：一种独立于具体硬件的记号系统，具体硬件的记号系统，更接近于机器代码更接近于机器代码 1.2编译过程概述编译过程概述forK:=1to100dobeginM:=
8、I+10*K;N:=J+10*Kend；K:=1L1:if100KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2K:=K+1gotoL1L2:语义分析后产生的中间代码：语义分析后产生的中间代码：三地址代码三地址代码具体实现：具体实现：三元式，四元式，间接三元式三元式，四元式，间接三元式1.2编译过程概述编译过程概述 K:=1L1:if100KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2K:=K+1gotoL1L2:序号OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j*+*+j110010I10JK
9、KKT1KT21K(9)T1MT2NK(2)四元式序列：四元式序列：1.2编译过程概述编译过程概述任务：任务：对中间代码进行加工变换，以期在最后阶段能产生出对中间代码进行加工变换，以期在最后阶段能产生出更为更为高效（省时间和空间）高效（省时间和空间）的目标代码。的目标代码。4.优化优化包括：公共子表达式的提取、包括：公共子表达式的提取、循环优化、删除无用代码等循环优化、删除无用代码等1.2编译过程概述编译过程概述序号序号 OPOPARG1ARG1 ARG2ARG2 RESULTRESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j*+*+j110010I10JKKKT1KT2
10、1K(9)T1MT2NK(2)序号序号 OPOPARG1ARG1 ARG2ARG2 RESULTRESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=:=:=j+jII1100MNK K10101MNK(9)MNK(2)优化前优化前优化后优化后1.2编译过程概述编译过程概述任务：任务：把中间代码变换成把中间代码变换成特定机器上特定机器上的低级语言代码，的低级语言代码，实现最后的翻译。实现最后的翻译。5.目标代码生成目标代码生成绝对指令代码绝对指令代码/可重定位的可重定位的指令代码指令代码/汇编指令代码汇编指令代码有赖于硬件系统结构和机器指令含义有赖于硬件系统结构和机器指令含义1
11、.2编译过程概述编译过程概述1.3编译程序的结构编译程序的结构一一.编译程序总框图编译程序总框图1.表格管理表格管理 编译编译各各阶阶段都要涉及到构造、段都要涉及到构造、查查找或找或 更新有关表格更新有关表格 。表格的作用：表格的作用：登记源程序的登记源程序的各类信息各类信息和编译和编译各阶段的进展状况各阶段的进展状况。符号表：符号表：用来登记源程序中出现的每个用来登记源程序中出现的每个名字名字以及以及名字的各种属性名字的各种属性。举例：举例：名字名字变量名变量名/常量名常量名/过程名过程名？变量名变量名类型？类型？/内存？内存？/地址？地址？1.3编译程序的结构编译程序的结构2.出错处理出错
12、处理 每一每一阶阶段都可能段都可能检测检测出出错误错误，绝绝大多大多 数数错误错误可在前三可在前三阶阶段段检测检测出来出来 .任务：任务：设法发现错误，并把有关错误信息报告给用户设法发现错误，并把有关错误信息报告给用户.语法错误语法错误：源程序中不符合语法：源程序中不符合语法/词法规则的错误。词法规则的错误。词法词法/语法分析时检测语法分析时检测语义错误语义错误：源程序中不符合语义规则的错误。：源程序中不符合语义规则的错误。语义分析语义分析/运行时检测出来运行时检测出来1.3编译程序的结构编译程序的结构二二.遍遍1.编译过程的划分：编译过程的划分：上述划分的五个阶段仅仅是上述划分的五个阶段仅仅
13、是逻辑功能逻辑功能上的一种划分上的一种划分2.遍（遍（Pass）对源程序或源程序的中间结果对源程序或源程序的中间结果从头到尾从头到尾扫描一次，并扫描一次，并作有关的加工处理，生成作有关的加工处理，生成新的新的中间结果或目标程序。中间结果或目标程序。具体实现时，受各方面具体实现时，受各方面（如源语言、设计要求（如源语言、设计要求等）限制，往往组织成等）限制，往往组织成若干遍若干遍1.3编译程序的结构编译程序的结构3.注意：注意：既可以将几个不同阶段合为一遍，也可以把一个阶段的既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍工作分为若干遍例如：例如：词法分析词法分析+语法分析语法分析
14、 一遍一遍语法分析语法分析+语义分析与中间代码产生语义分析与中间代码产生一遍一遍优化优化 若干遍若干遍单遍代码单遍代码不太有效。不太有效。根据系统资源的状况、运行目标根据系统资源的状况、运行目标的要求等，可以将一个编译程序的要求等，可以将一个编译程序设计形成多遍扫描的形式，在每设计形成多遍扫描的形式，在每一遍扫描中完成不同的任务。一遍扫描中完成不同的任务。1.3编译程序的结构编译程序的结构当一遍中包含若干阶段时，各阶段的工作是穿插进行的当一遍中包含若干阶段时，各阶段的工作是穿插进行的。例如：例如：识别出一个语识别出一个语法单位时法单位时语法分析器语法分析器词法分析器词法分析器语义分析和中间代码
15、产生器语义分析和中间代码产生器识别语法结构需识别语法结构需要下一个单词时要下一个单词时单单词词符符号号1.3编译程序的结构编译程序的结构三三.编译前端与后端编译前端与后端1.前端：前端：由与源语言由与源语言有关有关但与目标机但与目标机无关无关的那些部分组成的那些部分组成 包括包括词法分析、语法分析、语义分析与中间代码词法分析、语法分析、语义分析与中间代码 产生、部分代码优化工作产生、部分代码优化工作 2.后端：后端：包括编译程序中与目标机包括编译程序中与目标机有关有关的那些部分，如与的那些部分，如与 目标机有关的代码优化和目标代码生成等。目标机有关的代码优化和目标代码生成等。不依赖于源语言而仅
16、仅不依赖于源语言而仅仅依赖于中间语言依赖于中间语言1.3 1.3 编译程序的结构编译程序的结构1.5编译程序的生成编译程序的生成 一一.设计目标设计目标 目标程序小，执行速度快目标程序小，执行速度快编译程序小，执行速度快编译程序小，执行速度快诊断能力强，可靠性强诊断能力强，可靠性强可移植性，可扩充性可移植性，可扩充性 如何实现编译器？如何实现编译器？直接用可运行直接用可运行的代码编制的代码编制太费力！太费力！1.5编译程序的生成编译程序的生成 2.问题问题（1）历史上第一个高级语言的编译程序是怎样构造的？历史上第一个高级语言的编译程序是怎样构造的？-自编译技术（自展技术）自编译技术（自展技术）（2）已有已有A机器上的机器上的L1语言（如：语言（如：C语言）的编译程序，如何语言）的编译程序，如何构造构造A机器上的机器上的L2语言（如：语言（如：PASCAL语言）的编译程序？语言）的编译程序？（3）已有已有A机器上的机器上的L语言的编译程序，如何构造语言的编译程序，如何构造B机器上的机器上的L语言的编译程序？语言的编译程序？-交叉编译交叉编译 /移植移植STI源语言源语言编译程序编译程序实
