编译原理课件

1编译原理

第一讲引论课程信息编译程序概述高级语言的语法描述3§1.课程信息一、课程名称：编译原理基本内容是介绍编译程序构造的基本原理、方法和技术，包括词法分析、语法分析、语义分析与中间代码产生、代码优化及目标代码产生等。简言之，就是介绍如何将源程序翻译成目标代码程序。4二、课程性质：专业基础课，必修编译程序（器）出现于上世纪50年代后期（第一个高级语言1958年）60年代~70年代是研究高峰期60年代中期开始在高校中开设课程80年代开始作为计算机科学与技术专业的必修基础课程5三、课程特点：充分体现了计算学科中抽象、理论和设计三个学科形态该课程涉及多门课程的内容综合运用，涉及面广，内容庞杂，学习艰难程序设计语言、计算机体系结构、语言理论及算法等离散数学、数据结构该课程涉及的原理、方法和技术具有十分普遍的意义每一个计算机科学与技术工作者的职业生涯中反复用到，“享用一辈子”这儿接受的训练很难在其他地方获得：

如：抽象与形式化方法、局部与全局优化方法、构造技术、证明方法等6四、学习该课程的意义编译程序是计算机系统不可缺少的重要组成部分对程序设计语言的设计与实现能有更深刻的理解对程序设计语言有关理论有所了解从宏观上把握程序设计语言——掌握了编译原理后，就不能再说：“某语言未学过，所以不会”有助于快速理解、定位和解决程序调试与运行中出现的问题7编译方法与技术有着广泛应用安全技术、程序理解、软件逆向工程、应用软件与软件工具开发、软件测试与验证等编译课程蕴含着计算学科中解决问题的思路、抽象和方法，这些与高等数学一样，使你“享用一辈子”课程所涉及的内容至今非常活跃自然语言的翻译软件移植网络安全形式化方法形式语义学等8

鉴于以上所述，作为计算机科学与技术专业的学生必须学习和掌握编译原理这门课程，当然由于其综合性、处理问题的复杂性等，学习起来有一定难度，这就需要艰苦奋斗的精神和良好的学习方法9五、学习方法编译程序的构造是一个庞大而复杂的系统工程，无论是概念还是理论、方法，对初学者来说许多都是新的，学习起来会感到困难大一些，这一点必须有充分认识，为此建议学习方法上注意以下几点：10课前预习，课堂认真听讲，课后复习加深理解，特别要经常有意识地将前后内容联系起来融会贯通。因为编译程序是一个庞大的程序系统，讲解过程必须“分而治之”，这也是人们处理复杂问题的基本方法，这就要求大家在学习过程中，始终以处理过程为主线，把前后联系起来考虑。11理论联系实际——亲自动手，构造一个演示性编译程序，至少要完成扫描器和语法分析器，以及语法制导翻译产生中间代码认真完成作业，进一步巩固并加深理解所学知识特别要下功夫认真学习如何从实际问题进行抽象并形式化，最终建立实际问题的模型（上升为理性认识），并借助模型进一步设计实现，这将对你的能力提高大有益处12六、教材选择：

《程序设计语言编译原理》（第3版）

国防工业出版社陈火旺等内容详实丰富，理论与技术相结合新版充分考虑了新的研究成果——属性文法、LR分析法、全局优化等大多数院校一直采用，硕士入学考试参考书较为全面介绍了编译程序构造的基本原理、方法与技术13七、考试平时成绩：30%期终考试成绩：70%八、参考书目《编译原理》陈意云张昱高教出版社《编译原理》李建中姜守旭译A.V.Aho,RavSethi,J.D.Ullman著

机械工业出版社《编译原理及实践》冯博琴冯岚等译KennethC.Louden著）

机械工业出版社14§2.编译程序概述一、翻译程序（Translator）

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

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

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

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

①诊断编译程序(DiagnosticCompiler)

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

②优化编译程序(OptimizingCompiler)

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

③交叉编译程序(CrossCompiler)

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

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

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

这儿要强调的是：尽管本课程只介绍编译的基本理论、方法和技术，但这些基本理论、方法与技术对其他工具的构造同样起作用！22编辑器(Editor)

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

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

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

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

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

1.编译过程：

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

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

单词种类基本字：for，if，while等算符：＋，－，×，／等界符：，；（）等标识符：a123，pi等常数：9，36，4.8，6E6等无穷性有穷性！31

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

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

例：Position:=initial+rate*60词法分析（扫描器）基本字表(06,‘Position’)(11,─)(06,‘initial’)(12,─)(06,‘rate’)(13,─)(07,’60的二进制’)32第二阶段：语法分析——依据语言的语法规则，把扫描器提供的单词符号串分解成各种语法单位（范畴），如“短语”、“子句”、“句子”乃至“程序”。同时进行语法检查，以确定输入串是否正确，该工作是由语法分析器完成的。

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

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

对每种语法范畴进行静态语义检查，包括：变量是否定义过类型是否正确是否用了0作除数等34将语法范畴翻译成某种形式的中间代码，如四元式：OpARG1ARG2Result＊rate60T1＋initialT1T2:=T2Position35第四阶段：优化——对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出高效（节省时、空）的目标代码，这一任务是由优化器来完成的根据优化的范围不同，可分为：

局部优化，循环优化和全局优化一个循环优化的例子：36⑴＝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次加37第五阶段：目标代码生成——把中间代码翻译成目标代码显然这阶段要依赖于硬体系统结构和指令系统涉及存贮分配、寄存器调度这一阶段工作是由代码生成器完成的说明：以上各阶段（或称工序）并不是截然分开的，尤其编译程序结构十分复杂、体积相当庞大，所以有时人们把几个阶段的工作有机地组合在一起、穿插进行，构成遍。38遍（Pass）：对源程序或源程序的中间代码从头到尾扫描一次并做相应处理加工分遍的好处是结构清晰、节省内存（每遍都从外存获取前一遍的结果作为开始，工作结果仍记入外存，每遍几乎可使用全部内存）分不分遍、如何分遍要视具体情况——计算机内存容量、源语言的繁简、从事编译程序设计人员的情况等39如最早的基本BASIC语言采用一遍扫描的编译程序：返回符号源程序扫描器语法分析器整理目标程序停机语义分析器存储分配器代码生成器取字符取符号构造返回目标程序40又如PL/0编译程序的结构词法分析程序语法语义分析程序代码生成程序PL/0源程序目标程序表格管理程序出错处理程序41再如COBOL编译程序采用了四遍扫描的编译程序：源程序词法分析与名等内码内码生成器数据名长度计算与过程部分分析器数据结构特性解释程序数据特性记录器数据结构记录器目标生成器长度表数组信息表字表指源表树表目标程序形象字符表(Pic)基词表外名表文字信息表配对矩阵表424.前端与后端：概念上讲，编译程序的五个阶段可进一步划分为前端和后端：前端：主要由与源语言有关而与目标机无关的部分组成，包括词法分析、语法分析、语义分析和中间代码产生。代码优化一般也包含在前端。后端：主要由与目标机有关的部分组成，包括目标代码生成和与目标机有关的优化等。详见下图：43源程序词法分析语法分析语义分析和中间代码产生中间语言中间代码优化目标代码生成目标代码优化目标语言前端后端44

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

常数表(CT)

3.141592648…X哑元实型A数组整型

…………48DO编号(03)……L1入口地址……Swap二目子程序

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

标号表(LBT)

基本字表

(KWT)496.出错处理：这是编译程序的又一重要组成部分，因为编译的各个阶段都有可能发现源程序中的错误。一旦发现这样或那样的错误，就应把错误的性质及位置报告给用户，并且使编译能继续下去。50四、编译程序的构造过程1.需求分析，确定语言文本(1)确定语言的种类：

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

通过用户提供的应用范围，决定采用何种语言。例如：偏重于科学计算的则选用Fortran；偏重于符号处理的则选用Lisp或Snobol；偏重于事务处理的则选用Cobol或数据库管理语言；

……52(2)深刻理解语言的结构、语法及语义这就是说不仅仅是用程序设计语言编几个程序的问题，而是要在语法和语义方面下一些功夫。具体说来有以下几个方面：①程序语言的定义：任何程序语言都是某个确定的字符集上的符号按照一定规则组成的有穷序列。这里所谓的规则是从两个方面来谈的：

·语法规则：用于形成和产生一个正确的程序的一组规则。

·语义规则：用于定义程序意义的一组规则。53例如：从语法的角度看，标识符和名字是一个东西，都是以字母开头的字母数字串；但从语义的角度看，标识符是一个没有任何意义的字符序列，而名字却有确定的意义和属性，而且具有一定的作用域和定义域，即有局部和全部之分。又如：程序从语法角度看，是一些语法范畴构成的如下层次结构：54程序分程序或子程序（过程、函数等）语句表达式数据引用算符函数调用而从语义的角度来说，程序是描述一定的数据结构及其处理过程。55②程序结构：现代高级语言程序通常由若干子程序段（过程、函数等）构成，许多语言还引入了类、程序包等更高级的结构。例如，Fortran、C程序是块结构的；Pascal程序是过程嵌套的；Algol既有分程序嵌套，又有过程嵌套；Java与C++是面向对象的，它们很重要的方面是类和继承的概念，同时支持多态性和动态聚束等特性；而在Ada中引入了程序包，它可以把数据和操作代码封装在一起，支持数据抽象。（详见教材P15-18）56③语言的基本成分：包括数据类型、表达式、语句、过程或函数等，这些在学习语言课时都已经学过了，但从编译的角度出发，应如何了解这些基本成分呢？

·初等数据类型：牵扯到存储空间的问题；

·结构数据类型：牵扯到下标、维数、存放方式、分配时间----动态与静态等；

·表达式：牵扯到运算分量、运算符、形成规则、运算顺序等；

·语句：顺序、控制、循环等；

·过程与参数传递：传地址、传值、传名、得结果等；

·存储管理：静态存储分配、动态存储分配；572.由程序设计环境确定编译程序构造的方式和方法最早是直接使用机器语言或汇编语言现在一般使用高级语言Pascal或C语言

好处：编译方式还是解释方式便于阅读、理解和移植提高程序设计效率易于查错和修改58

任何一个编译程序至少要涉及三种语言：源语言（S）、目标语言（T）和编译程序实现语言（I），可用如下T型图来表示三者之间的关系：STI59Ada语言A

代码Ada语言A

代码CCA代码A代码A代码用C语言编写Ada编译程序

如若A机上已经有了一个用A机器语言（称A代码）实现的C语言编译程序，则可用C语言作为工具编写Ada语言的编译程序。这样Ada语言的编译程序经过C语言编译程序编译后就可得到A代码的Ada语言编译程序。可图示如下：60现在常用构造编译程序的方式除高级语言实现外，经常还用：自展（自编译）：类似于滚雪球。先确定一个非常简单的核心L0，用低级语言写出其编译程序C0。再把L0扩充为L1

，

，

并用L0来编写L1的编译程序。如此逐渐扩展下去，可得到一个系统编程语言族：

而Lk便是我们要编译的语言，其编译程序Ck可用Lk-1编写。这种滚雪球式的自展方法可大大减少开发工作量。61交叉编译：在机器A上产生机器B的目标代码，这种编译程序称为交叉编译。这儿A称宿主机，B称为目标机。这种情况一般是宿主机上有丰富的工具软件，而B机上没有任何高级语言可用。图示为：CB

代码CB

代码CCB代码B代码A代码62移植：如果一个程序能比较容易地从一台机器上搬到另一台机器上运行，则称其为可移植的，移植一个程序的工作量要远小于开发它的工作量才有意义。

显然一个编译程序要可移植，则其前端与后端的界面要清晰、简单，这样仅需改写后端即可。改写后亦可通过交叉编译的方法得到。63编译程序生成器：根据语言要求、设计实现的算法，能自动产生编译程序的工具软件。可图示为：643.确定编译方法：本课程要介绍若干方法，但不可能全采用，只能根据语言特点采用其中一种或二种4.总体设计：分不分遍、分几遍、前端与后端接口并画出总框5.详细设计：进一步细划总框6.实现及调试：采用何种方式实现、分调与连调等65本节目的：为语言的语法描述寻求形式化工具

工具就是对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式化工具就是将形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则是以什麽符号串能出现的方式来陈述。

§3.高级语言的语法描述66本节主要内容

预备知识

上下文无关文法及其语言的形式定义

文法的等价性

语法树及文法二义性

文法的类型

语法分析的一些思考67一、预备知识1.文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷多个句子的语言来讲，存在着如何给出它有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。例如：68“我是大学生”是汉语的一个句子

对该句子我们可以通过下列一组规则描述：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉有了这组规则以后，可按如下方式导出句子：先找∷=左端的带有〈句子〉的规则，并将它用∷=右端的符号串代替，于是表示成：

69

〈句子〉

〈主语〉〈谓语〉然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：

〈主语〉〈谓语〉

〈代词〉〈谓语〉依此类推，句子“我是大学生”的全部导出过程是：

〈句子〉

〈主语〉〈谓语〉

〈代词〉〈谓语〉

我〈谓语〉

我〈动词〉〈直接宾语〉

我是〈直接宾语〉

我是〈名词〉

我是大学生70“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据。换句话说，这些规则看成是一种元语言，用它描述汉语，仅仅涉及汉语句子的结构描述。这里“

”读作“导出”或“派生出”。而“::=”（通常又简记为“→”）读作“定义为”或“由…组成”，而每一条规则又称作是产生式或重写式。这样的一种描述形式就称作是BNF（BackusNormalForm）。71例如C语言中的赋值表达式可描述为：

<赋值表达式>→<左部>=<右部><左部>→<标识符><右部>→<表达式><表达式>→<表达式><算符><表达式><表达式>→<标识符>|<常数><标识符>→<字母>(<字母>|<数字>)n

<字母>→A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z<数字>→0|1|2|3|4|5|6|7|8|9<算符>→+|-|*|/722.语言概述语言是由句子组成的集合。汉语--所有符合汉语语法的句子的全体。英语--所有符合英语语法的句子的全体。程序设计语言--所有该语言的程序的全体。

每个句子构成的规则研究语言每个句子的含义每个句子和使用者的关系73研究程序设计语言每个程序构成的规则每个程序的含义每个程序和使用者的关系语言研究的三个方面:

语法(Syntax)--表示构成语言句子的各个记号之间的组合规则语义(Semantics)--表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用(Pragmatics)--表示在各个记号所出现的行为中，它们的来源、使用和影响。74

每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。75

如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。该数学系统称为文法。“形式”是指这样的事实：语言的所有规则描述什麽符号串以什么方式出现。形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。763.有关定义和记号—回顾符号：可以相互区别的记号（元素）。字母表

：符号（元素）的非空有穷集合。符号串(字)：由字母表

中的符号组成的任何有穷序列称为该字母表上的符号串。

①空字ε(没有符号的符号串)是

上的符号串；

②若x是

上的符号串,a是

的元素,则xa是

上的符号串；

③y是

上的符号串,当且仅当它可以由①和②

导出。

例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是

上的符号串77符号串s的前缀：符号串s的任何首部。如:ε、b、ba、…都是符号串banana的前缀.符号串s的后缀：符号串s的任何尾部。如:ε、a、na、…都是符号串banana的后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串.

如:ana是符号串banana的一个子串.符号串s的真前缀：x≠s且x≠ε的任何前缀x。s的真后缀，真子串可以类似地定义。78符号串的运算：

符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。ε的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy

如x=ab,y=cd则xy=abcd

又如εa=aε方幂：符号串自身连接n次得到的符号串

an定义为aa……aan个aa0=ε,a1=a,a2=aa…79符号串集合：若集合A中所有元素都是某字母表

上的符号串，则称A为字母表

上的符号串集合。符号串集合A和B的乘积：

AB=xy|xA且yB若集合A=ab,cdeB=0,1则AB=ab1,ab0,cde0,cde1Σ的闭包：

上的一切符号串（包括ε）组成的集合，记为*。Σ的正闭包：

上的除ε外的所有符号串组成的集合，记为

+。80例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

81语言：由句子构成的集合。换言之,字母表

上的一个语言是

上的一些符号串的集合

(字母表

上的每个语言是*的一个子集)。例如：字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}

集合{ab,aabb,aaabbb,…,anbn,…}或表示为{w|w∈Σ*且w=anbn,n≥1}为字母表

上的一个语言。

集合{a,aa,aaa,…}或表示为{w|w∈Σ*且w=an,n≥1}为字母表

上的一个语言。

ε

是一个语言，

即

也是一个语言。82二、上下文无关文法及其语言的形式定义1.如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示；如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途径：生成方式：语言中的每个句子可以用严格定义的规则来构造。识别方式：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，要麽永远继续下去。83

文法是从生成方式描述语言的，而自动机则是从识别的角度来描述语言的。本节仅介绍有关文法的概念。前面关于“我是大学生”及“赋值表达式”的例子中，涉及到如下的概念：

•<···>所表示的是一个类概念，通常称作语法范畴或语法变量，如果用一个符号来代替,也称为非终极符。所有规则中的非终极符就构成了一个非空有穷集，记为VN。上述两例中的“句子”及“赋值表达式”显然是最大的语法范畴，也是我们最感兴趣的非终极符，通常称作开始符号，记为S。

•“大学生”、“我”、“a”、“A”、“+”等表示的是一个具体概念，用一个符号来表示，则称为终极符号。所有这样的符号同样构成了一个非空有穷集，记为VT。

•<代词>→我、<数字>→8等称作产生式。所有产生式的集合显然是有穷的，记为P。这样我们可以将文法抽象为如下的一个数学系统：842.上下文无关文法的形式定义一个上下文无关文法G定义为一个四元式(VN,VT,S,

P)

其中：

VN为非终结符号的非空有穷集；

VT为终结符号的非空有穷集，VN∩

VT=φ；

P为产生式的集合；产生式也称重写规则或生成式，形如A→α，其中：

A∈VN,α∈(VN∪

VT)*

。

A称为产生式的左部，α称作产生式的右部。

S称作识别符号或开始符号，S∈VN

且至少要在一条产生式中作为左部出现。

VN∪

VT中的符号统称为文法符号。85例1文法G=（VN，VT，S，P）

VN={S},VT={0,1} P={S→0S1,S→01} S为开始符号例2文法G=（VN，VT，S，P）

VN={<标识符>，<字母>，<数字>} VT={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母>, <标识符>→<标识符><字母>, <标识符>→<标识符><数字>,<字母>→a,…,<字母>→z,<数字>→0,…,

<数字>→9} S=<标识符>86

文法的写法

①.G：S→aAb

A→abA→aAb

A→ε②.G[S]：S→aSbA→abA→aAbA→ε③.G[S]：S→aSbA→ab|aAb|ε

元符号：→∷=|<>

习惯表示：大写英文字母：终结符小写英文字母：非终结符

873.推导与规约

(1)直接推导“”A→γ是文法G的产生式，若有v,w满足：v=αAβ,w=αγβ,其中α∈V*,β∈V*

则称v直接推导出w,记作

v

w；也称w直接归约到v，就是说归约是推导的逆过程。例：G：S→0S1，S→01

0S100S1100S11000S111000S11100001111S0S188(2)推导

若存在vw0w1...wn=w,(n>0)，则记为

v+w，v推导出w，或w归约到v。若有v+w，或v=w，则记为v*w。例：G：S→0S1，S→01S0S10S100S1100S11000S111000S11100001111S0S100S11000S11100001111S

+00001111S

*S00S11

*00S1189(3)最左（最右）推导最左（最右）推导：在推导的任何一步α

β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换最右推导被称为规范推导。也就是说，规范推导具有最右性。规范推导的逆过程称为规范规约。也就是说，规范规约具有最左性。由规范推导所得的句型称为规范句型。904.句型、句子句型：有文法G，若S

*x，则称x是文法G的句型。句子：有文法G，若S

*x，且x∈VT*，则称x是文法G的句子。例1：G：S→0S1，S→01S0S100S11000S11100001111G的句型:S,0S1,00S11,000S111,00001111G的句子:00001111,0191例2：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

句子：用符号a，+，*，(和)构成的算术表达式925.语言的定义

由文法G生成的语言记为L(G),它是文法G的所有句子的集合。

L(G)={x|S

+x,S为开始符号,且x∈VT*}

例1G：S→0S1，S→01L(G)={0n1n|n≥1}

例2文法G[S]： （1）S→aSBE

（2）S→aBE

（3）EB→BE

（4）aB→ab

（5）bB→bb

（6）bE→be

（7）eE→ee

L（G）={anbnen|n≥1}为什么呢？93S

aSBE(S→aSBE)

aaBEBE(S→aBE)

aabEBE (aB→ab)

aabBEE (EB→BE)

aabbEE

（bB→bb)

aabbeE

（bE→be)

aabbee

（eE→ee)类似推导可以看出a,b,e在句子中出现的顺序及个数满足L(G)当然要进一步说明：G生成的每个句子都在L(G)中L(G)中的每个句子确实能被G生成94

使用产生式(1)n-1次，得到推导序列：

S

*an-1S(BE)n-1，然后使用产生式(2)一次，得到：S

*

an-1S(BE)n-1

an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBE

aaaBBEEBE

aaaBBEBEE

aaaBBBEEE。即有：S

*

anBnEn

再使用产生式(4)一次，得到S

*

anbBn-1En，然后使用产生式(5)n-1次得到：

S

*

anbnEn，进而使用产生式(6)一次，使用产生式(7)n-1次，最后得到：S

*

anbnen。也能证明，对于n≥1，串anbnen是唯一形式的终结符号串95

三、文法的等价性1.定义：若L(G1)=L(G2)，则称文法G1和G2是等价的。如文法G1[A]：A→0R与G2[S]：S→0S1等价

A→01S→01R→A1因为L（G1）=L（G2）={0n1n∣n≥1}。962.关于文法等价变换的几个定理(1)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2的开始符号不出现在任何产生式的右部。例1：G1:E→E+E∣E*E∣(E)∣iG2:S→EE→E+E∣E*E∣(E)∣i

具体做法：加一条单个非产生式S→E即可。(2)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2的每个非终结符都能导出一个终结符号串。可给出如下证明：97证明：①令β={A∣A→t∈G1&A∈VT+}；②递归扩充：β=β∪{W∣W→x&x∈(VT∪β)+}

由于G1的非终结符号是有穷的，上述过程一定是收敛的；③从G1的VN中删除不包含在β中的非终结符，并从其产生式集中删除其左部或右部中包含不属于β中的符号的产生式，这样得到的文法即为所要的G2。98例：G1[A]:A→Bed∣dDB→bD→Ea∣AD∣DBE→Da∣Eb①β={B}②β={B}∪{A}={A,B},到此为止；于是D,E及相关D,E的产生式均可删除，得到：G2[A]:A→BedB→b

可以证明L(G1)=L(G2)。类似还可以给出如下定理：(3)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2的每个非终结符都出现在某一句型中。99(4)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2中不含单个非产生式。如：G1[A]:A→B∣dDG2[A]:A→dD∣b∣c

B→A∣C∣bD→d∣Da

C→B∣c

D→d∣Da(5)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2中不含空产生式。形如E→ε的产生式称为空产生式。(6)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2中不含有左递归。形如E→E+T的产生式称为左递归的。100四、语法树和文法二义性

1.语法树：语法树是了解句子语法结构的一种辅助工具。树根即为开始符号所标记的结点。随着推导的展开，某个非终结符被它的产生式右部所替换时，则产生出下一代新结点。每个新结点和其父结点间都有一条连线。于是，可给出如下的定义：101设G=(VN,VT,S,P)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈VN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行谓之句型。102给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)。定理：G为上下文无关文法， 对于α≠ε，有S

*

α，当且仅当 文法G有以α为结果的一棵语法树(推导树)这里对该定理不作证明。103例如：文法G[E]:

E→E+E∣E*E∣(E)∣i

显然(i+i)*i是该文法产生的一个句子，它的推导过程可以用右边的语法树来描述。

子树与简单子树

只有单层分支的子树代次21345EE*E(E)E+Eiii104

在一棵语法树生长过程中的任何时刻，所有叶结点从左到右依次排列起来就是一个句型。这就是说，一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导。如果我们坚持使用最左（最右）推导，那么一棵语法树就完全等价于一个最左（最右）推导。105文法G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i

但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?不尽然。试看下例：1062.文法二义性

若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的；或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。显然，上例中的文法就是一个二义文法。

1073.二义性问题是不可判定的

不能设计一个算法，在有穷的步骤内确切地判定一个文法是否为二义性的。因此，我们所能做的工作只能是为二义性寻找一组充分（而非必要）条件来改造二义性文法。例如对前面提到的二义性文法G(E):E→E+E∣E*E∣(E)∣i

可将其改造为如下无二义文法G′：

G′(E):E→T∣E+TT→F∣T*FF→i∣(E)优先顺序和结合律108

注意：文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。上面的例子很好地说明了这一点。如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。109

语法树是了解句子语法结构的一种辅助工具，也是语法分析的辅助工具，因此又称为语法分析树。这样一来，就存在着自上而下和自下而上两种分析方法。

■在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？

■在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。110五、文法的分类----形式语言鸟瞰(1)通过对产生式施加不同的限制，Chomsky将文法分为四种类型：即0型、1型、2型、3型。

①0型文法：若文法G=(VN,VT,S,P)

的每个产生式α→β满足：

α∈(VN∪VT)+且至少含有一个非终结符，

β∈(VN∪VT)*，则该文法称为0型文法。

②若0型文法G的任何产生式α→β，都有|β|≥|α|，但S→ε除外，这时S不得出现在任何产生式的右部；则该文法称为1型文法。

③若文法G的任何产生式α→β，都有α∈VN，β∈(VN∪VT)*，则该文法称为2型文法。

④若文法G的任何产生式的形式都为A→αB或A→α，其中A∈VN

，B∈VN

，α∈VT*，则该文法称为3型文法。111例11型文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD例22型文法

文法G[S]： S→AB A→BS|0 B→SA|1112例33型文法G[S]：

S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT I→l T→lT

T→dT

T→l

T→d

试问：它们产生的语言是什么？113

(2)四种文法之间的逐级“包含”关系随着对产生式限制条件的增多，四种文法的能力逐级减弱。2型文法1型文法0型文法3型文法114(3)四种文法及其分别对应的语言和识别系统

0型文法（又称为短语文法）的能力相当于图灵机，可以表征任何递归可枚举集。0型文法产生的语言称为0型语言。而且任何0型语言都是递归可枚举的，或者说都可以被一个图灵机所接收；反之，递归可枚举集也必定是一个0型语言。

1型文法又称为上下文有关文法。这种文法意味着：对非终结符进行替换时必须考虑上下文，例如产生式的形式为α1Aα2→α1βα2，则只有当A出现在α1和α2这样的上下文环境时，才允许用β替换A。

1型文法产生的语言称为1型语言或上下文有关语言（CSL）。其识别系统是线性界限自动机(LBA)。115

带a0a1a2a3a4a5a6a7a8…an-1an

有限控制器磁头任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述116

2型文法：产生式的形式为A→β，β取代A时与A的上下文无关，因此又称为上下文无关文法（CFG

）

。它产生的语言称为2型语言或上下文无关语言（CFL），其识别系统是下推自动机(PDA)。

CFG有足够的能力描述现今大多数程序设计语言的语法结构，也就是说现今大多数程序设计语言都是CFL。

3型文法：产生式形式为A→αB或A→α的3型文法称为右线性文法，产生式形式为A→Bα或A→α的则称为左线性文法。由于3型文法等价于正规式（将在第三章介绍），所以也称为正规文法。相对应地，它所产生的语言称为3型语言或正规（则）语言，可以为有穷自动机（FA）所接收。117小结1.本节出现的概念较多,应重点理解文法,推导,句型,句子及语言的定义等概念.语法分析有关内容在后面章节会详细讨论.2.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的“形式”的含义—只涉及语言的语法不涉及语言的语义.3.本节内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。118§1.词法分析器的构造

编译程序首先在单词级别上来分析和翻译源程序。词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，即把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器(通常又称为扫描器,scanner）。119一、一般考虑：

1.词法分析程序的主要任务：读入字符串形式的源程序—输入剔除非单词符号—空格符、换行符，跳过注释拼单词符号—**、:=、FOR、BEGIN等捻接语句行并产生语句结束标志源程序的列表输出宏展开，……120

2.词法分析器的输入和输出形式输入—字符串形式的源程序输出—单词符号串。程序语言的单词符号一般分为五种：

关键字、运算符、界符、标识符、常数词法分析器输出的单词符号常常表示为二元式：

（单词种别，单词符号的属性值）121

★单词种别通常用整数编码

单词种别是对单词符号的一种分类。一个语言的单词符号如何分种，分成几种，怎样编码是一个技术性问题。它取决于处理上的方便。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。

122★单词符号属性信息记录单词符号的特征或特性

如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了，因此属性值就没有意义了。若同一个种别含有多个单词符号，那麽，对于它的每个单词符号，除了给出种别编码之外，还应给出各有关单词符号的属性信息。

属性值是反映特性或特征的值。例如，对于某个标识符，常将存放它有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放该常数二进制表项的指针作为其属性值。123

作为例子考虑下述C++语句：

while(i>=j)i--;

若while种别为01,(种别为11,标识符种别为20,>=种别为12,)种别为13,－－种别为14,;种别为30,则经词法分析器处理后，它将被转换为如下的单词符号序列：

(01,—)(11,—)(20,指向i的符号表项的指针)(12,—)(20,指向j的符号表项的指针)(13,—)(20,指向i的符号表项的指针)(14,—)(30,—)1243.词法分析器与语法分析器的衔接

通常把词法分析器安排成一个独立子程序，而不是单独的一遍。这样一来，就无须在外存中保留整个源程序的内码形式，而是每当语法分析器需要单词符号时就调用这个子程序。每一次调用，词法分析器就从源程序字符串中识别出一个单词符号，把它交给语法分析器。这样做的好处是：压缩编译时扫描字符的时间：编译时大量时间花费在字符的扫描上；词法规则描述简单，便于建立扫描器的自动方法，便于独立研究；使得语法分析获得更多信息；便于处理同一语言的几种不同表示形式；

125由以上考虑，可以初步设计为：源程序扫描器语法分析器取符号送符号126二、进一步考虑：

1.输入、预处理

词法分析器工作的第一步是输入源程序文本。输入串一般放在一个缓冲区中，这个缓冲区称源程序输入缓冲区。词法分析器的工作可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。于是可以设想构造一个预处理子程序，它完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样分析器就可以在此缓冲区中直接而方便地进行单词符号的识别工作。1272.对半互补缓冲区

分析器对扫描缓冲区进行扫描时一般使用两个指示器，一个指向当前正在识别单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。但是不论扫描缓冲区设得多大都不能保证单词符号不会被缓冲区的边界所打断。因此，扫描缓冲区最好使用一分为二的区域，并使两区首尾相接，形成一个对半互补缓冲区。例如：每半个区可容64个字符，而这两个半区又是互补的。如果搜索指示器从单词起点出发搜索到半区的边缘但尚未达到单词的终点，那么就调用预处理子程序，令其把后续的64个字符装入另半区。可以认定在另半区一定可以达到单词的终点。这意味着标示符和常数的长度实际上必须加以限制，否则即使缓冲区再大也无济于事。128于是对半互补缓冲区可图示如下：

。。。。。。While。。。。。。起点指针搜索指针

综上所述，预处理子程序、扫描器和语法分析器相互之间的关系及工作情况可图示如下：

129单词符号扫描器预处理子程序输入缓冲区源程序扫描缓冲区列表语法分析器取单词1303.单词符号识别－超前搜索技术问题发生在对基本字不加任何保护的语言中，基本字及用户自定义的标识符或标号之间无特殊分界符，这使得关键字的识别甚为麻烦。

请看下面的例子：

1DO99K=1,102IF(5.EQ.M)I=103DO99K=1.104IF(5)=55

这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以某基本字开头的。语句3和4是赋值语句，它们都是以用户自定义的标识符开头的。131

为了从1、2中识别出关键字DO和IF，我们必须要能够区别1、3和区别2、4。语句1、3的区别在于等号之后的第一个界符：一个为逗号，另一个为小数点，语句2、4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。这就是说，为了识别1、2句中的关键字，我们必须超前扫描许多个字符，超前到能够肯定词性的地方为止。对于1、3来说，尽管都以‘D’和‘O’两个字母开头，但不能一见‘DO’就认定是DO语句。而必须超前搜索，跳过所有的字母和数字，看看是否有等号。如果有，再向前搜索。若下一个界符是逗号，则可以肯定DO应为关键字。否则，DO不构成关键字，它只是用户标识符的头两个字母。132

所以为了区别1和3，必须超前扫描若干字符直到等号后的第一个界符处。对于2和4来说，同样需超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。若此字符是字母，则得逻辑IF。若此字符为数字，则得算术IF。否则，应认为是用户自定义标识符IF。这种向前扫描若干字符直到找到能区分单词的字符为止的技术就叫超前搜索。

133

标识符的识别：标识符是字母开头的一个字母数字串，一般有运算符和界符分开，与基本字的区别前已谈及，所以容易识别。常数的识别：算术常数大多相似，只是转换二进制的问题，但像3.E5、3.EQ.5显然也要用到超前搜索技术。另有3HABC一类的常数需要特殊处理。算符