编译原理第1章

编译原理

袁彩虹

yuanch@程序设计语言什么是编译？机器语言(MachineLanguage)0、1代码汇编语言(AssembleLanguage)：助记符高级语言(HighLevelLanguage)：定义数据、描述算法（程序） 如：C、Pascal、C++、Java、SQL高级语言低级语言学习的意义(1)一门基础专业课,对于”计算机专业”的同学而言,类似于”高等数学”对于”理工科”学生工作和学习的影响,使其”享用一辈子”.(2)作用

＊有利于大家对”程序设计语言”的理解

→较迅速掌握新的语言工具.

＊包含许多软件技术,对于以后从事软件设计很有价值.→从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。

＊蕴涵着计算机学科中解决问题的思路﹑抽象问题和解决问题的方法.课程要求1、认真听课，认真理解书中基本概念、基本原理与基本算法；2、弄懂书中的例题与习题；3、在看书或理解例题时，一定要动手画出相应的细节变化过程，通过画图来加深理解；4、在理解的基础上记忆；5、理论结合实践。考核方式考核方式：

--平时成绩占30%--期末考试成绩占70%平时成绩：

--考勤

--作业

--实验第1章引论第2章高级语言及其语法描述第3章词法分析第4章语法分析——自上而下分析第5章语法分析——自下而上分析第6章属性文法和语法制导翻译第7章语义分析和中间代码产生第8章符号表第9章运行时存储空间组织第10章优化

第11章目标代码生成目录第一章引论1.1什么叫编译程序1.2编译过程概述1.3编译程序的结构1.4编译程序与程序设计环境（略）1.5编译程序的生成1.什么是编译程序？1.1什么叫编译程序翻译程序：一种语言程序---------->另一种语言程序源语言目标语言编译程序：高级语言程序---------->低级语言程序汇编程序：汇编语言程序---------->机器语言程序解释程序：源语言程序---------->边解释边执行（1）编译方式：先编译后执行。（2）解释方式：以源程序作为输入，但不产生目标代码，而是边解释边执行源程序本身。2.“高级语言程序”的执行方式1.1什么叫编译程序编译和解释的主要区别：是否产生目标代码！3.“编译程序”在计算机系统中的位置较接近于“硬件”1.1什么叫编译程序4.发展20世纪50年代第一个编译程序——FORTRAN编译程序目前：编译原理与技术得到迅速发展，现已形成一套比较成熟的系统化的理论与方法，并开发出了一些好的编译程序的实现语言、环境与工具。当时普遍认为设计和实现编译程序是一件十分困难、令人生畏的事情1.1什么叫编译程序1.2编译过程概述Theelephantateanbanana.什么是语言？forK:=1to100do begin M:=I+10*K; N:=J+10*K end一.类比自然语言翻译和编译过程英→汉编译的工作过程1)识别单词……………词法分析2)分析句子语法结构…………………语法分析3)根据句子含义初步翻译…………语义分析与中间代码产生4)修饰译文…………………优化5)写出最后译文…………………目标代码生成1.2编译过程概述1.词法分析forK:=1to100do begin M:=I+10*K; N:=J+10*K end

基本字for

标识符K

赋值号:=

常数1

基本字to

常数100

基本字do

基本字begin......1.2编译过程概述词法分析

——

规则：规则描述工具：任务：依循词法规则正规式和有限自动机（FA）输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词符号，如基本字、标识符、常数、算符、界符等。1.2编译过程概述2.语法分析forK:=1to100do begin M:=I+10*K; N:=J+10*K end规则：规则描述工具：任务：依循语法规则上下文无关文法在词法分析的基础上，根据语言的语法规则，对单词符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。1.2编译过程概述3.语义分析和中间代码产生规则：规则描述工具：任务：语义规则属性文法两部分工作：1、对每种语法范畴进行静态语义检查2、若语义正确，则进行中间代码翻译对语法分析器识别出的各类语法单位，分析其含义并进行初步翻译（产生中间代码）。

中间代码：一种独立于具体硬件的记号系统，更接近于机器代码

1.2编译过程概述forK:=1to100dobeginM:=I+10*K;N:=J+10*Kend；

K:=1L1:if100<KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2

K:=K+1gotoL1L2:语义分析后产生的中间代码：三地址代码具体实现：三元式，四元式，间接三元式1.2编译过程概述

K:=1L1:if100<KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2

K:=K+1gotoL1L2:序号OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j<*+*++j110010I10JKKKT1KT21K(9)T1MT2NK(2)四元式序列：1.2编译过程概述任务：对中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。规则:等价变换规则包括：公共子表达式的提取、循环优化、删除无用代码等1.2编译过程概述4.优化序号OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j<*+*++j110010I10JKKKT1KT21K(9)T1MT2NK(2)序号OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=:=:=j<+++jII1100MNK

K10101MNK(9)MNK(2)优化前优化后1.2编译过程概述任务：把中间代码变换成特定机器上的低级语言代码，实现最后的翻译。5.目标代码生成

绝对指令代码/可重定位的指令代码/汇编指令代码有赖于硬件系统结构和机器指令含义1.2编译过程概述1.3编译程序的结构一.编译程序总框图1.表格管理编译各阶段都要涉及到构造、查找或 更新有关表格。表格的作用：

登记源程序的各类信息和编译各阶段的进展状况。符号表：

用来登记源程序中出现的每个名字以及名字的各种属性。

举例：名字——变量名/常量名/过程名…？ 变量名——类型？/内存？/地址？1.3编译程序的结构2.出错处理每一阶段都可能检测出错误，绝大多 数错误可在前三阶段检测出来任务：设法发现错误，并把有关错误信息报告给用户

语法错误：源程序中不符合语法/词法规则的错误。 词法/语法分析时检测语义错误：源程序中不符合语义规则的错误。

语义分析/运行时检测出来1.3编译程序的结构二.遍1.编译过程的划分：上述划分的五个阶段仅仅是逻辑功能上的一种划分2.遍（Pass）对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。具体实现时，受各方面（如源语言、设计要求等）限制，往往组织成若干遍1.3编译程序的结构3.注意：既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍例如：词法分析+语法分析 一遍语法分析+语义分析与中间代码产生一遍优化

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

由与源语言有关但与目标机无关的那些部分组成包括——词法分析、语法分析、语义分析与中间代码产生、部分代码优化工作

2、后端： 包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。不依赖于源语言而仅仅依赖于中间语言1.3编译程序的结构1.5编译程序的生成一.设计目标

目标程序小，执行速度快编译程序小，执行速度快诊断能力强，可靠性强可移植性，可扩充性

如何实现编译器？直接用可运行的代码编制太费力！STI源语言编译程序实现语言目标语言一般采用高级语言实现，可用T形图表示如下：表现语言翻译的T形图1.5编译程序的生成问题：已知A机上有一个用A代码实现的高级语言L1的编译程序，可以用L1实现在A机上能运行一个新语言L2编写的程序。

L1AA已知条件目标L2L1A二.多级编译程序

1、本机编译器利用

分析：1.5编译程序的生成条件目标L2L1AL1AAL2AAL1语言写成的L2语言的编译程序A代码写成的L1语言的编译程序得到A代码写成的L2语言的编译程序P0P1P2说明：P0——L2语言的编译程序，用L1语言实现

P1——L1语言的编译程序，用A代码实现

P2——L2语言的编译程序，用A代码实现

1.5编译程序的生成问题：能否用A机上有的高级语言L实现在B机上运行L语言程序？LAA条件目标LLB2、交叉编译/移植（思考）1.5编译程序的生成LAA条件LLB目标LLBLAALABLLBLBB说明：过程在A机上运行的产生B代码的L编译程序源程序（L语言编写）1.5编译程序的生成1.5编译程序的生成3、自编译过程

通过一系列自展途径而形成编译程序的过程叫做自编译过程。

1.5编译程序的生成三.