编译原理精课件

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

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

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

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

国防工业出版社陈火旺等内容详实丰富，理论与技术相结合较为全面介绍了编译程序构造的基本原理、方法与技术厚度适中大多数院校一直采用，硕士入学考试参考书所谓教材，实为第一参考书而已13可编辑课件PPT七、参考书目1.《编译原理》第2版赵建华等译，<Compilers:Principles,Techniques,&Tools>A.V.Aho,M.S.Lam,RaviSethi,J.D.Ullman著，机械工业出版社，2009；2.《编译原理课程设计》王雷等著，机械工业出版社，2005；八、期末总评

平时成绩：10% 课程设计：20% 期终考试：70%14可编辑课件PPT15可编辑课件PPT§2.编译程序概述一、翻译程序（Translator）

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

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

把源程序作为输入接收，边解释边执行的翻译程序源程序数据解释程序结果18可编辑课件PPT编译程序

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

①诊断编译程序(DiagnosticCompiler)

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

②优化编译程序(OptimizingCompiler)

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

③交叉编译程序(CrossCompiler)

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

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

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

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

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

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

装入程序使得可执行代码更加灵活27可编辑课件PPT调试程序(Debugger)

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

1.编译过程：

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

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

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

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

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

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

(11,─)

(06,‘initial’)

(12,─)

(06,‘rate’)

(13,─)

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

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

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

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

局部优化，循环优化和全局优化一个循环优化的例子：38可编辑课件PPT循环

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

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

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

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

常数表(CT)

48可编辑课件PPT入口表(ENT)

标号表(LBT)

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

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

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

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

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

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

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

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

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

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

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

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

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

好处：编译方式还是解释方式便于阅读、理解和移植提高程序设计效率易于查错和修改58可编辑课件PPT任何一个编译程序至少要涉及三种语言：源语言（S）、目标语言（T）和编译程序实现语言（I），可用如下T型图来表示三者之间的关系：59可编辑课件PPT如若A机上已经有了一个用A机器语言（称A代码）实现的C语言编译程序，则可用C语言作为工具编写Ada语言的编译程序。这样Ada语言的编译程序经过C语言编译程序编译后就可得到A代码的Ada语言编译程序。可图示如下：60可编辑课件PPT现在常用构造编译程序的方式除高级语言实现外，经常还用：自展（自编译）：类似于滚雪球。先确定一个非常简单的核心L0，用低级语言写出其编译程序C0。再把L0扩充为L1，

，

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

而Lk便是我们要编译的语言，其编译程序Ck可用Lk-1编写。这种滚雪球式的自展方法可大大减少开发工作量。61可编辑课件PPT交叉编译：在机器A上产生机器B的目标代码，这种编译程序称为交叉编译。这儿A称宿主机，B称为目标机。这种情况一般是宿主机上有丰富的工具软件，而B机上没有任何高级语言可用。图示为：62可编辑课件PPT移植：如果一个程序能比较容易地从一台机器上搬到另一台机器上运行，则称其为可移植的，移植一个程序的工作量要远小于开发它的工作量才有意义。

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

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

§3.高级语言的语法描述66可编辑课件PPT本节主要内容

预备知识

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

文法的等价性

语法树及文法二义性

文法的类型

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

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

〈句子〉

〈主语〉〈谓语〉

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

〈主语〉〈谓语〉

〈代词〉〈谓语〉

依此类推，句子“我是大学生”的全部导出过程是：

〈句子〉

〈主语〉〈谓语〉

〈代词〉〈谓语〉

我〈谓语〉

我〈动词〉〈直接宾语〉

我是〈直接宾语〉

我是〈名词〉

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

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

<赋值表达式>→<左部>=<右部><左部>→<标识符><右部>→<表达式><表达式>→<表达式><算符><表达式><表达式>→<标识符>|<常数><标识符>→a1|b123|salary|stu_age

<常数>→18|123|4.5|<算符>→+|-|*|/72可编辑课件PPT2.语言概述语言是由句子组成的集合。汉语--所有符合汉语语法的句子的全体。英语--所有符合英语语法的句子的全体。程序设计语言--所有符合该语言语法的程序的全体。

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

语法(Syntax)--表示构成语言句子的各个记号之间的组合规则语义(Semantics)--表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用(Pragmatics)--表示在各个记号所出现的行为中，它们的来源、使用和影响。74可编辑课件PPT每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。75可编辑课件PPT如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。该数学系统称为文法。“形式”是指这样的事实：语言的所有规则描述什麽符号串以什么方式出现。形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。76可编辑课件PPT3.有关定义和记号—回顾符号：可以相互区别的记号（元素）。字母表

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

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

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

上的符号串；

②若x是

上的符号串,a是

的元素,则xa是

上的符号串；

③y是

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

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

上的符号串77可编辑课件PPT符号串s的前缀：符号串s的任何首部。如:ε、b、ba、…都是符号串banana的前缀.符号串s的后缀：符号串s的任何尾部。如:ε、a、na、…都是符号串banana的后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串.如:ana是符号串banana的一个子串.符号串s的真前缀：x≠s且x≠ε的任何前缀x。s的真后缀，真子串可以类似地定义。78可编辑课件PPT符号串的运算：

符号串的长度：符号串中符号的个数.符号串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可编辑课件PPT符号串集合：若集合A中所有元素都是某字母表

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

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

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

上的一切符号串（包括ε）组成的集合，记为

*

。Σ的正闭包：

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

+

。80可编辑课件PPT例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

81可编辑课件PPT语言：由句子构成的集合。换言之,字母表上的一个语言是

上的一些符号串的集合(字母表上的每个语言是*的一个子集)。例如：字母表Σ={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可编辑课件PPT二、上下文无关文法及其语言的形式定义1.如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示；如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途径：生成方式：语言中的每个句子可以用严格定义的规则来构造。识别方式：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，要麽永远继续下去。83可编辑课件PPT

文法是从生成方式描述语言的，而自动机则是从识别的角度来描述语言的。本节仅介绍有关文法的概念。前面关于“我是大学生”及“赋值表达式”的例子中，涉及到如下的概念：<...>所表示的是一个类概念，通常称作语法范畴或语法变量，如果用一个符号来代替,也称为非终结符(nonterminal)。所有规则中的非终结符构成了一个非空有穷集，记为VN。上述两例中的“句子”及“赋值表达式”显然是最大的语法范畴，也是我们最感兴趣的非终结符，通常称作开始符号，记为S。“大学生”、“我”、“是”、“a”、“+”等表示的是一个具体概念，用一个符号来表示，则称为终结符(terminal)。所有这样的符号同样构成了一个非空有穷集，记为VT。<代词>→我、<数字>→8等称作产生式(production)。所有产生式的集合显然是有穷的，记为P。这样我们可以将文法抽象为如下的一个数学系统：84可编辑课件PPT2.文法的形式定义一个文法G定义为一个四元式(VN,VT,S,

P)其中：VN为非终结符号的非空有穷集；VT为终结符号的非空有穷集，VN∩

VT=φ；P为产生式的集合；产生式也称重写规则或生成式，形如A→α，其中：A∈VN,α∈(VN∪

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

S称作识别符号或开始符号，S∈VN且至少要在一条产生式中作为左部出现。

VN∪

VT中的符号统称为文法符号。85可编辑课件PPT例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可编辑课件PPT

文法的写法

①.G：S→aAb

A→abA→aAb

A→ε

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

元符号：→∷=|<>

习惯表示：大写英文字母：非终结符/集合字母表中靠前的小写英文字母：终结符字母表中靠后的小写英文字母：字符串87可编辑课件PPT上下文无关文法：它所定义的语法范畴是完全独立于这种范畴所能出现的环境。程序设计语言的词：a+b/3a1<a2…自然语言的词：丢了钱，他很难过。我家门前的沟很难过去。有谁不愿意跟我走，我就让他跟你走！上下文无关文法不能完整地表述自然语言，但对程序设计语言来说，大多数情况下都可以准确表述。因此，我们只关注上下文无关文法(Context-FreeGrammar,CFG)。其实，前面给出的定义，就是CFG的形式定义。文法的范畴更广一些。88可编辑课件PPT3.推导与规约(1)直接推导“”A→γ是文法G的产生式，若有v,w满足：v=αAβ,w=αγβ,其中α,β∈(VN∪VT)*则称v直接推导出w,记作v

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

0S100S1100S11000S111000S11100001111S0S189可编辑课件PPT(2)推导若存在v=w0w1...wn=w,(n>0)，则记为

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

+00001111S

*S00S11

*00S1190可编辑课件PPT(3)最左（最右）推导最左（最右）推导：在推导的任何一步α

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

*x，x∈(VN∪VT)*,则称x是文法G的句型。句子：有文法G，若S

*x，且x∈VT*，则称x是文法G的句子。例1：G：S→0S1，S→01S0S100S11000S11100001111G的句型:S,0S1,00S11,000S111,00001111G的句子:00001111,0192可编辑课件PPT例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，+，*，(和)构成的算术表达式思考：写出一个不同的文法，同样能够产生这些句子93可编辑课件PPT5.语言的定义

由文法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}这个文法生成什么语言？这个文法与前面见过的文法有什么不同？94可编辑课件PPTS

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生成95可编辑课件PPT使用产生式(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是唯一形式的终结符号串。96可编辑课件PPT三、文法的等价性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}。97可编辑课件PPT2.关于文法等价变换的几个定理(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的每个非终结符都能导出一个终结符号串。可给出如下证明：98可编辑课件PPT证明：①令β={A∣A→t∈G1&t∈VT+}；②递归扩充：β=β∪{W∣W→x&x∈(VT∪β)+}由于G1的非终结符号是有穷的，上述过程一定是收敛的；③从G1的VN中删除不包含在β中的非终结符，并从其产生式集中删除其左部或右部中包含不属于β中的符号的产生式，这样得到的文法即为所要的G2。99可编辑课件PPT例：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的每个非终结符都出现在某一句型中。证明？100可编辑课件PPT(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的产生式称为左递归的。递归哪里去了101可编辑课件PPT四、语法树和文法二义性

1.语法树：语法树是了解句子语法结构的一种辅助工具。树根即为开始符号所标记的结点。随着推导的展开，某个非终结符被它的产生式右部所替换时，则产生出下一代新结点。每个新结点和其父结点间都有一条连线。于是，可给出如下的定义：102可编辑课件PPT设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中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的串谓之句型。103可编辑课件PPT给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)。定理：G为上下文无关文法， 对于α≠ε，有S

*

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

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

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

子树与简单子树

只有单层分支的子树代次21345EE*E(E)E+Eiii105可编辑课件PPT

在一棵语法树生长过程中的任何时刻，所有叶结点从左到右依次排列起来就是一个句型。这就是说，一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导。如果我们坚持使用最左（最右）推导，那么一棵语法树就完全等价于一个最左（最右）推导。106可编辑课件PPT文法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

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

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

108可编辑课件PPT3.二义性问题是不可判定的

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

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

G′(E):E→T∣E+TT→F∣T*FF→i∣(E)如此改造，所依何据？优先级&结合规则109可编辑课件PPT以代数运算为例，说明操作符的：结合规则左结合：当一个操作数的左右两侧都有+时，它将被左侧的+使用。4+5+9=(4+5)+9右结合：523=58优先级优先级表左结合：+-左结合：*/右结合：幂110可编辑课件PPT

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

语法树是了解句子语法结构的一种辅助工具，也是语法分析的辅助工具，因此又称为语法分析树。这样一来，就存在着自上而下和自下而上两种分析方法。■在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？■在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。

结合前面的例子