第1讲-基础知识

编译原理课件兰州大学信息学院1CompilerPrinciples第一讲引论课程介绍编译程序概述2CompilerPrinciples§1.课程介绍一、课程名称：编译原理基本内容是介绍编译程序构造的基本原理、方法和技术，包括词法分析、语法分析、语义分析与中间代码产生、代码优化及目标代码产生等。简言之，就是介绍如何将源程序翻译成目标代码程序。3CompilerPrinciples二、课程性质：专业基础课，必修编译程序（器）出现于上世纪50年代后期（第一个高级语言1958年）60年代~70年代是研究高峰期60年代中期开始在高校中开设课程80年代开始作为计算机科学与技术专业的必修基础课程4CompilerPrinciples5CompilerPrinciples三、课程特点：充分体现了计算学科中抽象、理论和设计三个学科形态该课程涉及多门课程的内容综合运用，涉及面广，内容庞杂，学习艰难程序设计语言、计算机体系结构、语言理论及算法等数据结构、离散数学该课程涉及的原理、方法和技术具有十分普遍的意义每一个计算机科学与技术工作者的职业生涯中反复用到，“享用一辈子”这儿接受的训练很难在其他地方获得，如：抽象与形式化方法、局部与全局优化方法、构造技术、证明方法等6CompilerPrinciples四、学习该课程的意义编译程序是计算机系统不可缺少的重要组成部分对程序设计语言的设计与实现能有更深刻的理解对程序设计语言有关理论有所了解从宏观上把握程序设计语言—掌握了编译原理后，就不能再说：“某语言未学过，所以不会”有助于快速理解、定位和解决程序调试与运行中出现的问题7CompilerPrinciples编译方法与技术有着广泛应用安全技术、程序理解、软件逆向工程、应用软件与软件工具开发、软件测试与验证等编译课程蕴含着计算学科中解决问题的思路、抽象和方法，这些与高等数学一样，使你“享用一辈子”课程所涉及的内容至今非常活跃自然语言的翻译软件移植网络安全形式化方法形式语义学等8CompilerPrinciples

鉴于以上所述，作为计算机科学与技术专业的学生必须学习和掌握编译原理这门课程，当然由于其综合性、处理问题的复杂性等，学习起来有一定难度，这就需要艰苦奋斗的精神和良好的学习方法9CompilerPrinciples五、学习方法编译程序的构造是一个庞大而复杂的系统工程，无论是概念还是理论、方法，对初学者来说许多都是新的，学习起来会感到困难大一些，这一点必须有充分认识，为此建议学习方法上注意以下几点：10CompilerPrinciples课前预习，课堂认真听讲，课后复习加深理解，特别要经常有意识地将前后内容联系起来融会贯通。

因为编译程序是一个庞大的程序系统，讲解过程必须“分而治之”（这也是人们处理复杂问题的基本方法），这就要求大家在学习过程中，始终以处理过程为主线，把前后联系起来考虑。11CompilerPrinciples理论联系实际——亲自动手，构造一个演示性编译程序，至少要完成扫描器和语法分析器，以及语法制导翻译产生中间代码（课程设计）认真完成作业，进一步巩固并加深理解所学知识特别要下功夫认真学习如何从实际问题进行抽象并形式化，最终建立实际问题的模型（上升为理性认识），并借助模型进一步设计实现，这将对你能力的提高大有益处12CompilerPrinciples六、参考书13CompilerPrinciples§2.编译程序概述一、翻译程序（Translator）

能够把一种语言程序（称为源语言程序）转换成逻辑上等价的另一种语言程序（称为目标语言程序）的程序14CompilerPrinciples任何非机器语言程序都需要翻译程序翻译程序的工作就是进行等价变换（映射）两个程序逻辑上等价是指对相同输入得到相同的输出翻译程序解释程序汇编程序编译程序15CompilerPrinciples汇编程序(Assembler)

把汇编语言程序转变为机器语言程序的翻译程序解释程序(Interpreter)

把源程序作为输入接收，边解释边执行的翻译程序源程序数据解释程序结果16CompilerPrinciples编译程序

将高级语言程序转变为低级语言程序的翻译程序源程序编译程序目标程序17CompilerPrinciples这是GCC的例子18CompilerPrinciples19CompilerPrinciples编译程序又可根据用途和侧重点的不同，进一步分类为：

①诊断编译程序(DiagnosticCompiler)

专门用于帮助程序开发和调试的编译程序

②优化编译程序(OptimizingCompiler)

着重于提高目标代码效率的编译程序

③交叉编译程序(CrossCompiler)

能够产生不同于其宿主机机器代码的编译程序

④可变目标编译程序(Retargetablecomplier)

无须重写与机器无关部分就能改变目标机的编译程序20CompilerPrinciples二、与编译程序相关的程序本讲义只介绍编译程序（器）构造的基本原理、方法与技术，但在一个完整的语言开发（或称程序设计）环境中，除了编译器这一主要工具外，还需要其他一些工具，如编辑器、连接器、装入程序等。现代计算机系统常将这些相互独立的程序设计工具集成起来，构成一个集成化的程序开发环境，以提高程序设计效率和程序的质量。如TurboC、VisualC++等语言环境都是集成化的程序设计环境。而Ada语言的集成环境是这方面的典型代表。21CompilerPrinciples如Ada语言的集成环境是一个分层的程序开发环境编译程序MAPSE编辑程序连接程序宿主机OSAPSE工具界面用户界面KAPSE调试程序配置管理程序命令解释程序其他工具22CompilerPrinciples这儿要强调的是：尽管本课程只介绍编译的基本理论、方法和技术，但这些基本理论、方法与技术对其他工具的构造同样起作用！23CompilerPrinciples编辑器(Editor)

完成源程序输入、编辑并产生标准文件（如ASCII文件）的程序。近来已与编译器和其他程序捆绑进一个交互开发环境——IDE中尽管这样的编辑器仍生成标准文件，但会转向正被讨论的程序设计语言的格式或结构（称为基于结构的），且已包含了编译器的某些操作；因此在程序编写时而不是编译时就可得知错误，甚至也可调用编译器24CompilerPrinciples预处理程序(Preprocessor)

在真正翻译开始之前产生编译程序的输入的程序处理宏及注释：宏是被经常使用的较长结构的缩写处理文件包含：把头文件包含到程序正文中（如C的文件包含include<….h>）“理解”预处理器：把现代控制流和数据结构机制添加到比较老式的语言中语言扩充：通过大量的内部宏定义来增强语言的能力，如Equel语言是一种嵌套在C语言中的数据库查询语言25CompilerPrinciples连接程序(Linker)——又称为连接编辑器。将分别在不同的目标文件中编译（或汇编）的代码、所用标准库函数的代码以及操作系统提供的资源（如存储分配程序及输入/输出设备）收集到一个可直接执行的文件中的程序装配程序(Loader)

完成程序的装入和连接编辑两项功能。装入过程包括读入可重定位机器代码、修改可重定位地址、并将修改后的指令和数据放到内存的适当位置。

装入程序使得可执行代码更加灵活26CompilerPrinciples调试程序(Debugger)

可在被编译了的程序中判定执行错误的程序它经常与编译程序一起放在IDE中运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数源代码信息，它可以在预先指定的位置（断点BreakPoint）暂停执行，并提供有关信息（已调用的函数、变量名的当前值等）27CompilerPrinciples其他有关的还有描述器(Profiler)——执行中搜集目标程序行为统计的程序项目管理程序(ProjectManager)——如Unix系统中的SCCS（源代码控制系统）和RCS（修正控制系统）和汇编程序等综上所述可给出一个“语言处理系统”的图示：28CompilerPrinciples我们这个课只介绍编译程序这一部分29CompilerPrinciples三、编译过程与编译程序结构

1.编译过程：

输入输出（高级语言源程序）（低级语言目标程序）

编译程序工作过程如下：识别出一个个的单词分析句子的语法结构分析句子的语义并进行初步翻译对初步翻译进行优化整理出目标程序对以上过程进一步整理可得如下编译程序结构总框：编译程序30CompilerPrinciples2.编译程序总框：词法分析器语法分析器语义分析与中间代码产生器优化器目标代码生成器单词符号语法单位中间代码中间代码出错处理表格管理源程序目标代码31CompilerPrinciples3.五个阶段简介第一阶段：词法分析——依据语言构词规则，识别出一个个单词（符号）

单词种类保留字：forifwhile算符：＋－×／界符：，；（）{}标识符：a1a2pi常数：910244.86E6无穷性有穷性思考：识别有穷集合VS识别无穷集合32CompilerPrinciples

词法分析工作由词法分析器（或称扫描器）完成。

扫描器输出为等长度的单词符号（二元式）流。

例：Position=initial+rate*60词法分析（扫描器）保留字表(06,‘Position’)

(11,─)

(06,‘initial’)

(12,─)

(06,‘rate’)

(13,─)

(07,’60的二进制’)33CompilerPrinciples第二阶段：语法分析——依据语言的语法规则，把扫描器提供的单词符号串分解成各种语法单位（范畴），如“短语”、“子句”、“句子”乃至“程序”。同时进行语法检查，以确定输入串是否正确，该工作是由语法分析器完成的。

如：Position=initial+rate*60是一个“赋值表达式”（C语言中）Position=表达式表达式表达式+表达式标识符表达式*表达式initial标识符常数rate60标识符34CompilerPrinciples第三阶段：语义分析与中间代码产生——针对各类不同的语法范畴，按语言的语义规则进行语义分析和初步翻译工作，产生某种中间语言形式的中间代码（即一种结构简单，含义明确的记号系统）。

该阶段工作通常包括两个方面的工作：

对每种语法范畴进行静态语义检查，包括：变量是否定义过类型是否正确是否用了0作除数……35CompilerPrinciples将语法范畴翻译成某种形式的中间代码，如四元式：OpARG1ARG2Result＊rate60T1＋initialT1T2

=T2Position36CompilerPrinciples第四阶段：优化——对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出高效（节省时、空）的目标代码，这一任务是由优化器来完成的根据优化的范围不同，可分为：

局部优化，循环优化和全局优化一个循环优化的例子：37CompilerPrinciples⑴＝1K⑴＝IM⑵J<100K⑼⑵＝JN⑶＊10KT1⑶＝1K⑷＋IT1M⑷J<100K⑼⑸＊10KT2⑸＋M10M⑹＋JT2N⑹＋N10N⑺＋K1K⑺＋K1K⑻Ｊ⑵⑻Ｊ⑷⑼…⑼…循环

For(k=1;k<=100;k++){M=I+10*k;N=J+10*k;}优化前用了两个临时工作单元(T1,T2),

优化后没有用临时单元优化前循环体中要做300次加、200次乘，

优化后循环体内只做300次加38CompilerPrinciples第五阶段：目标代码生成——把中间代码翻译成目标代码显然这阶段要依赖于硬体系统结构和指令系统涉及存贮分配、寄存器调度这一阶段工作是由代码生成器完成的说明：以上各阶段（或称工序）并不是截然分开的，尤其编译程序结构十分复杂、体积相当庞大，所以有时人们把几个阶段的工作有机地组合在一起、穿插进行，构成遍。39CompilerPrinciples遍（Pass）：对源程序或源程序的中间代码从头到尾扫描一次并做相应处理加工分遍的好处是结构清晰、节省内存（每遍都从外存获取前一遍的结果作为开始，工作结果仍记入外存，每遍几乎可使用全部内存）分不分遍、如何分遍要视具体情况——计算机内存容量、源语言的繁简、从事编译程序设计人员的情况等40CompilerPrinciples如某PL/0编译程序的结构词法分析程序语法语义分析程序代码生成程序PL/0源程序目标程序表格管理程序出错处理程序41CompilerPrinciples

4.前端与后端：概念上讲，编译程序的五个阶段可进一步划分为前端和后端：前端：主要由与源语言有关而与目标机无关的部分组成，包括词法分析、语法分析、语义分析和中间代码产生。代码优化一般也包含在前端。后端：主要由与目标机有关的部分组成，包括目标代码生成和与目标机有关的优化等。42CompilerPrinciples源程序词法分析语法分析语义分析和中间代码产生中间语言中间代码优化目标代码生成目标代码优化目标语言前端后端43CompilerPrinciples划分前端和后端，就可以仅改写后端而生成不同目标机上的目标程序，当然也可考虑对不同语言仅稍加改变前端而产生相同的中间代码，经同一后端生成相同目标机的目标代码。就目前来说，针对相同中间代码适应不同目标机的工作较多，如Ada语言的APSE(Ada程序设计环境)中使用的Diana中间代码，Java语言定义的虚拟机代码——Bytecode中间语言，都是定义良好的中间语言。44CompilerPrinciplesJava的传统环境Java源程序(.java)编译环境Java编译器Java字节码(.class)Java字节码（本地或网络传输）运行环境类加载程序字节码验证Java类库Java解释器即时编译器Java虚拟机硬件45CompilerPrinciples5.表格与表格管理表格记录源程序中的各类有用信息——名字、函数、标号、过程、数值等每个阶段的工作都要与表格打交道：查、填、改等表格的结构与处理方法：统一的大表与分类的小表统一大表名字栏为主栏（关键字栏），信息栏又分成若干子栏——种属、类型等NAMEINFORMATION46CompilerPrinciples分类小表：每类一张表，如：符号名表(SNT)

常数表(CT)

3.141592648…X哑元实型A数组整型…………47CompilerPrinciplesDO编号(03)……L1入口地址……Swap二目子程序

入口地址……入口表(ENT)

标号表(LBT)

基本字表(KWT)48CompilerPrinciples6.出错处理：这是编译程序的又一重要组成部分，因为编译的各个阶段都有可能发现源程序中的错误。一旦发现这样或那样的错误，就应把错误的性质及位置报告给用户，并且使编译能继续下去。

思考：如何准确地报告错误如何从错误中恢复过来49CompilerPrinciples四、编译程序的构造过程1.需求分析，确定语言文本(1)确定语言的种类：

按语言范型分类，当今大多数程序语言可分为四类：过程式(强制式语言)：命令驱动，面向语句，如FORTRAN、PASCAL、Ada及C等函数式(应用式)语言：功能驱动，面向函数，如LISP、SNOBOL及ML等逻辑式(基于规则的)语言：依据条件进行逻辑推演，如Prolog等OO语言：支持封装性、继承性、多态性及动态聚束等，以对象为运行单位，如Smalltalk、Java、C++等50CompilerPrinciples

通过用户提供的应用范围，决定采用何种语言。例如：偏重于科学计算的则选用Fortran；偏重于符号处理的则选用Lisp或Snobol；偏重于事务处理的则选用Cobol或数据库管理语言；……51CompilerPrinciples(2)深刻理解语言的结构、语法及语义这就是说不仅仅是用程序设计语言编几个程序的问题，而是要在语法和语义方面下一些功夫。具体说来有以下几个方面：①程序语言的定义：任何程序语言都是某个确定的字符集上的符号按照一定规则组成的有穷序列。这里所谓的规则是从两个方面来谈的：·语法规则：用于形成和产生一个正确的程序的一组规则。·语义规则：用于定义程序意义的一组规则。52CompilerPrinciples例如：从语法的角度看，标识符和名字是一个东西，都是以字母开头的字母数字串；但从语义的角度看，标识符是一个没有任何意义的字符序列，而名字却有确定的意义和属性，而且具有一定的作用域和定义域，即有局部和全部之分。又如：程序从语法角度看，是一些语法范畴构成的如下层次结构：53CompilerPrinciples程序分程序或子程序（过程、函数等）语句表达式数据引用算符函数调用而从语义的角度来说，程序是描述一定的数据结构及其处理过程。54CompilerPrinciples②程序结构：现代高级语言程序通常由若干子程序段（过程、函数等）构成，许多语言还引入了类、程序包等更高级的结构。例如，Fortran、C程序是块结构的；Pascal程序是过程嵌套的；Algol既有分程序嵌套，又有过程嵌套；Java与C++是面向对象的，它们很重要的方面是类和继承的概念，同时支持多态性和动态聚束等特性；而在Ada中引入了程序包，它可以把数据和操作代码封装在一起，支持数据抽象。（详见教材P15-18）55CompilerPrinciples③语言的基本成分：包括数据类型、表达式、语句、过程或函数等，这些在学习语言课时都已经学过了，但从编译的角度出发，应如何了解这些基本成分呢？·初等数据类型：牵扯到存储空间的问题；·结构数据类型：牵扯到下标、维数、存放方式、分配时间----动态与静态等；·表达式：牵扯到运算分量、运算符、形成规则、运算顺序等；·语句：顺序、控制、循环等；·过程与参数传递：传地址、传值、传名、得结果等；·存储管理：静态存储分配、动态存储分配；56CompilerPrinciples2.由程序设计环境确定编译程序构造的方式和方法最早是直接使用机器语言或汇编语言现在一般使用高级语言Pascal或C语言

好处：编译方式还是解释方式便于阅读、理解和移植提高程序设计效率易于查错和修改57CompilerPrinciples任何一个编译程序至少要涉及三种语言：源语言（S）、目标语言（T）和编译程序实现语言（I），可用如下T型图来表示三者之间的关系：STI58CompilerPrinciplesAda语言A

代码Ada语言A

代码CCA代码A代码A代码用C语言编写Ada编