编译原理 第1章+概述

1编译原理CompilerPrinciples南京邮电大学软件学院管有庆[e-mail]2教材及参考资料教材王汝传.编译技术原理及其实现方法.成都：成都科技大学出版社,1998.参考书[1]吕映芝，张素琴，蒋维杜．编译原理．北京：清华大学出版社，1998.[2]陈火旺等．程序设计语言编译原理．北京：国防工业出版社，2000.3课程性质目的和任务是一门计算机专业课程通过本课程的学习能对高级程序设计语言如何翻译成计算机硬件能够识别的机器语言的整个编译过程有较好的理解能够从理论上掌握编译(例如词法分析和语法分析等)的几种经典算法，能够应用于实践中。4教学内容第一章引论第二章语言的基本知识第三章词法分析第四章语法分析第五章语法制导翻译技术5第一章引论§1.1程序设计语言和翻译程序§1.2编译过程概述§1.3编译程序的生成6第一章引论§1.1程序设计语言和翻译程序程序设计语言一、语言的概念和分类二、程序设计语言简述翻译程序一、汇编程序二、解释程序三、编译程序7一、语言的概念和分类1.概念2.语言的分类(1)自然语言(2)数理语言(3)程序设计语言8二、程序设计语言简述1.机器语言（第一代语言）2.汇编语言(第二代语言:50年代中期出现)3.高级程序设计语言(第三代语言:50年代中期提出)4.超高级程序设计语言（第四代语言）9电子计算机之父JohnvonNeumann冯诺依曼1949EDSAC计算机工作原理计算机的两个基本能力：一是能够存储程序，二是能够自动地执行程序。计算机是利用“存储器”（内存）来存放所要执行的程序的，而称之为CPU的部件可以依次从存储器中取出程序中的每一条指令，并加以分析和执行，直至完成全部指令任务为止。冯·诺依曼计算机101.机器语言（第一代语言）(1)定义：由机器指令构成的语言称机器语言，即用二进制编码组成。如01110101机器指令：是二进制编码，基本上是由操作码和地址码两部分组成，所以要用机器语言编程序一定要知道多种不同的操作码。11（2）特点：费时费事难懂容易错只能在一种型号计算机上运行可以直接在计算机上运行1.机器语言（第一代语言）122.汇编语言(第二代语言:50年代中期出现)(1)定义用容易记忆的符号来代替机器指令中操作码和地址码的一种语言.如:ADD代表“+”SUB代表“-”MOV代表“传递”(2)特点程序直观容易阅读优点编程工作量小只能在一种型号机器上运行缺点不能直接在计算机上运行133.高级程序设计语言(第三代语言）——50年代中期提出1956年，第一个高级程序设计语言FORTRAN(FORmulaTRANslator)正式开始使用。（1）定义高级程序设计语言是一种面向过程语言（不是面向机器），它用一些符号和数字对实际问题进行描述的语言，也称过程化语言。14（2）分类（按发展时间）1)高级语言初始时期①FORTRAN语言(FORmulaTRANslator公式翻译)②ALGOL语言(ALGOrithmicLanguage算法语言)③COBOL语言（COmmonBusinessOrientedLanguage面向商业通用语言)15IBM公司程序师约翰·巴科斯（J.Backus）16艾伦·佩利(艾伦J.Perlis)17商业通用语言语言开发小组182)高级语言发展时期①LISP语言（LIStProcessor表处理）②APL语言（AProgrammingLanguage)③SNOBOL语言(StringOrientedSymbolLanguage面向字符串符号的语言)④PL/1语言（PogrammingLanguage)⑤SIMULA语言(仿真语言)⑥BASIC语言（BeginnerAll-purposeSybolicInstructorCode初学者通用符指令码）191964年由美国达特茅斯大学研制，BASIC语言不仅用于科学计算，还用于事务处理，且具有简单易学的特点。是许多大中专院校的启蒙教学语言。美国达特茅斯学院约翰·凯梅尼（J.Kemeny）和托马斯·卡茨（T.Kurtz）203)结构程序设计时期①PASCAL语言②MODULA-2语言③Ada语言④C语言CAT&T贝尔实验室的邓尼斯·里奇（D.Ritchie）和肯·汤姆森（K.Thompson）214)多范型程序设计语言时期①函数式语言典型函数式语言，如LISP、APL、ML等。②逻辑式语言其代表语言是PROLOG③面向对象式语言smalltalk、C++、java、C#等都是面向对象式语言。C++贝尔实验室另一研究人员比加尼·斯楚士舒普（B.Stroustrup）把C语言扩展成一种面向对象的程序设计语言C++④网络语言如：JAVA，PERL,C#等22(3)高级语言的特点1）直观、易写易读工作量小2）不依赖于具体的机器3）便于程序交流4）不可直接在计算机上运行，经编译程序编译成机器语言后方可运行。234.超高级程序设计语言（第四代语言）（1）定义只需指出所求问题、输入数据及输出形式，就能得出输出结果，无需对算法和计算过程描述的语言。第四代语言主要包括：1）数据库及其查询语言，如；SQL;2）应用生成程序；3）可执行规格说明语言。目前问世的第四代语言有ADF、MAPPER（2）特点1）语言功能强，效率高，使用方便2）开发应用系统修改方便、维护容易3）系统复杂，不但要编译还要生成程序。24下面我们对程序设计语言做一下总结机器语言(第一代)低级语言汇编语言(第二代)初期：FORTRAN、ALGOL、COBOL发展期：LISP、APL、SNOBOL、PL/1、(第三代)SIMULA、BASIC程序设计语言高级语言结构化时期：PASCAL、MODULA-2、Ada、C函数式：ML、LISP、APL多范型时期逻辑式：PROLOG面向对象：Smalltalk、C++、Java(第四代)SQL网络：Java、Perl、C#超高级语言报表语言MAPPER25翻译程序翻译程序将一种语言程序（称为源程序）改造成另一种等价的语言程序（称为目标程序）的程序。源语言书写源程序的语言称为源语言.目标语言书写目标程序的语言称为目标语言.26翻译程序一、汇编程序二、解释程序三、编译程序27汇编程序：把汇编语言写的源程序翻译成机器语言的目标程序，这个翻译过程称为汇编。如下图：初始数据汇编源程序汇编程序目标程序结果数据汇编程序执行过程汇编程序一般对源程序进行两遍扫描来完成。第一遍：进行存贮分配，造出第二遍扫描时用的各种表格；第二遍：用机器语言操作码来代替汇编符号操作码。一、汇编程序28解释程序：将高级语言写的源程序作为输入数据，但并不产生目标程序，而是边解释边执行源程序本身的一种程序。如下图源程序解结释果程数初始数据序据解释程序执行过程解释程序适合于会话型语言，如BASIC语言。解释程序主要优点是易于为用户提供调试功能，对源程序的语法分析及出错处理都很及时，修改调试也很方便，但是解释程序执行速度较慢，运行效率低。二、解释程序29编译程序是将高级语言写的源程序翻译成目标语言（汇编语言、机器语言）的程序。这种翻译过程称为编译。编译系统目标程序，再加上运行系统（如服务子程序、动态分配程序、装配程序等）就可获得计算结果，整个系统称为编译系统。三、编译程序30编译程序执行过程源程序编译程序目标程序（机器语言）源程序编译程序目标程序（汇编语言）汇编程序目标程序（机器语言）编译阶段编译阶段汇编阶段目标程序（机器语言）运行系统可执行程序结果数据运行阶段31上述三种翻译程序，汇编程序最容易实现，其次是解释程序，编译程序最难。所以只要掌握了编译程序实现方法，汇编程序和解释程序就迎刃而解了。下面我们就具体介绍一下编译程序……32§1.2编译过程概述一、编译步骤二、编译过程简述三、趟程（遍）33类似于外文资料的翻译过程：读一个个字母（字符）构成独立单词分析语法关系初步译成中文加工修改写出译文一、编译步骤34翻译外文资料阅读原文识别单词分析句子修辞加工写出译文编译过程输入源程序（读符号）词法分析语法语义分析修饰优化目标代码生成它们之间的对应关系如下：35编译过程基本包括以下几个步骤：1.词法分析2.语法分析3.语义分析4.中间代码生成5.修饰优化6.生成目标程序36二、编译过程简述下面通过一个简单PASCAL源程序实例，说明编译基本过程。例1.1计算圆柱体全面积S=2πR(H+R)其中R为半径，H为高，用PASCAL可写出下列源程序：PROGRAMexample;VARr,h,s:real;BEGINs∶=2*3.1416*r*(r+h)END对上例PASCAL源程序编译过程一般需要经过以下几个步骤：371.词法分析（1）功能1)扫描源程序进行读取符号，删除无用字符（如空格、注释等）2)将一个个有独立意义的单词识别出来，并且转换成统一长度的内部编码。3)建立有关表格（如名字特征表、常数表），进行词法检查以供语法和语义分析用。。381.词法分析（2）分析过程1）识别单词：将有独立意义的单词分辨出来。源程序中有些符号具有独立意义，如:+、-、*等程序中共有下面27个独立意义单词：PROGRAMexample;VARR,H,S:real;BEGINS:=2*3.1416*R*(H+R)END39这些单词大致上可分为以下几种类型：保留字。如：PROGRAMVARBEGINENDreal专用符号。运算符，如：+*赋值符，如:=分界符，如：,:();标识符。如：exampleRHS整型常数。如：2实型常数，如：3.1416402）将单词转换成内部编码①.要求：a.长度统一：即在机器里有相等的二进制位数b.反映单词属性：即通过内部编码可以知道该单词的性质或类型。c.便于编译程序进行内部加工处理例子中：program,begin,var,real,end是保留字+，*是运算符（，）是分隔符H，R，S，example是标识符41②.单词内部编码：由类别和单词值两部分组成。格式如下：类别单词的值a.单词类别用整数表示，通常可将单词分为以下5个类型1：保留字如PROGRAMBEGINVARrealEND2：专用符号如+、*、：=、；、，、（、）等3：标识符如R、H、S、example4：无符号整数如25：无符号实数如3.141642b.保留字及专用符号的单词值可以用一个三位八进制数表示，如本例中为保留字和专用字符指定了如下的单词值：PROGRAM000，007BEGIN001（010END002）011REAL003；012VAR004：=013*005：014+006.01543根据内部编码的格式，例子中的PROGRAM，BEGIN和*依次可以表示如下：PROGRAM1000BEGIN1001*2005标识符和常数的单词值为对应的内存地址。3）建立各种表以供语法和语义分析，如名字特性表，常数表等。对应上例名字特性表及常数表如下：名字特性表000R实型存储系统002H实型存储系统004S实型存储系统006example实型存储系统每个名字占两个存储单元000，002，004表示相对地址44常数表00020013.1416对于标识符和常数，可以用其在特征表或常数表中的相对地址来表示单词值。如例中：R3000H30023.1416500124000一个常数占一个存储单元45所以经词法分析后，其内部编码形式于机器内为如下形式10003006201210043000200730022007PROGRAMexample;VARR,H,30042014100320121001300420134000S:real;BEGINS:=220055001200530002005201030022006*3.1416*R*(H+300020111002R)END由上述分析可知，经词法分析，源程序转换成内部编码形式，不同类型的单词其长度是统一的，这有助于以后的语法分析。462.语法分析(1)功能语法分析阶段就是将词法分析后所有单词组