编译原理精.ppt

1.第一讲 引论u课程信息u编译程序概述u高级语言的语法描述2.1.课程信息一、课程名称：编译原理v基本内容是介绍编译程序构造的基本原理、方法和技术，包括词法分析、语法分析、语义分析与中间代码产生、代码优化及目标代码产生等。简言之，就是介绍如何将源程序翻译成目标代码程序。3.二、课程性质：专业基础课，必修v编译程序（器）出现于上世纪50年代后期（第一个高级语言1958年）v60年代70年代是研究高峰期v60年代中期开始在高校中开设课程v80年代开始作为计算机科学与技术专业的必修基础课程4.5.三、课程特点三、课程特点：v充分体现了计算学科中抽象、理论和设计三个学科形态v该课程涉及多门课程的内容综合运用，涉及面广，涉及面广，涉及面广，涉及面广，内容庞杂，学习艰难内容庞杂，学习艰难内容庞杂，学习艰难内容庞杂，学习艰难程序设计语言、计算机体系结构、语言理论及算法等数据结构、离散数学v该课程涉及的原理、方法和技术具有十分普遍的意义每一个计算机科学与技术工作者的职业生涯中反复用到，“享用一辈子”这儿接受的训练很难在其他地方获得，如：抽象与形式化方法、局部与全局优化方法、构造技术、证明方法等6.四、学习该课程的意义v编译程序是计算机系统不可缺少的重要组成部分对程序设计语言的设计与实现能有更深刻的理解对程序设计语言有关理论有所了解从宏观上把握程序设计语言掌握了编译原理后，就不能再说：“某语言未学过，所以不会”有助于快速理解、定位和解决程序调试与运行中出现的问题7.v编译方法与技术有着广泛应用安全技术、程序理解、软件逆向工程、应用软件与软件工具开发、软件测试与验证等v编译课程蕴含着计算学科中解决问题的思路、抽象和方法，这些与高等数学一样，使你“享用一辈子”v课程所涉及的内容至今非常活跃自然语言的翻译软件移植网络安全形式化方法形式语义学等8.鉴于以上所述，作为计算机科学与技术专业的学生必须学习和掌握编译原理这门课程，当然由于其综合性、处理问题的复杂性等，学习起来有一定难度，这就需要艰苦奋斗的精神和良好的学习方法9.五、学习方法v编译程序的构造是一个庞大而复杂的系统工程，无论是概念还是理论、方法，对初学者来说许多都是新的，学习起来会感到困难大一些，这一点必须有充分认识，为此建议学习方法上注意以下几点：10.1.课前预习，课堂认真听讲，课后复习加深理解，特别要经常有意识地将前后内容联系起来融会贯通。因为编译程序是一个庞大的程序系统，讲解过程必须“分而治之”（这也是人们处理复杂问题的基本方法），这就要求大家在学习过程中，始终以处理过程为主线，把前后联系起来考虑。11.2.理论联系实际亲自动手，构造一个演示性编译程序，至少要完成扫描器和语法分析器，以及语法制导翻译产生中间代码（课程设计）3.认真完成作业，进一步巩固并加深理解所学知识4.特别要下功夫认真学习如何从实际问题进行抽象并形式化，最终建立实际问题的模型（上升为理性认识），并借助模型进一步设计实现，这将对你能力的提高大有益处12.六、教材程序设计语言编译原理（第3版）国防工业出版社 陈火旺等1.内容详实丰富，理论与技术相结合2.较为全面介绍了编译程序构造的基本原理、方法与技术3.厚度适中4.大多数院校一直采用，硕士入学考试参考书5.所谓教材，实为第一参考书而已13.七、参考书目1.编译原理第2版 赵建华等译，A.V.Aho,M.S.Lam,Ravi Sethi,J.D.Ullman著，机械工业出版社，2009；2.编译原理课程设计 王雷等著，机械工业出版社，2005；八、期末总评平时成绩：10%课程设计：20%期终考试：70%14.15.2.编译程序概述一、翻译程序（Translator）能够把一种语言程序（称为源语言程序）转换成逻辑上等价的逻辑上等价的另一种语言程序（称为目标语言程序）的程序16.v任何非机器语言程序都需要翻译程序v翻译程序的工作就是进行等价变换（映射）v两个程序逻辑上等价是指对相同输入得到相同的输出翻译程序解释程序汇编程序编译程序17.1.汇编程序(Assembler)把汇编语言程序转变为机器语言程序的翻译程序2.解释程序(Interpreter)把源程序作为输入接收，边解释边执行的翻译程序源程序数据解释程序结果18.3.编译程序将高级语言程序转变为低级语言程序的翻译程序源 程 序编译程 序目 标程 序19.20.v编译程序又可根据用途和侧重点的不同，进一步分类为：诊断编译程序(Diagnostic Compiler)专门用于帮助程序开发和调试的编译程序 优化编译程序(Optimizing Compiler)着重于提高目标代码效率的编译程序 交叉编译程序(Cross Compiler)能够产生不同于其宿主机机器代码的编译程序 可变目标编译程序(Retargetable complier)无须重写与机器无关部分就能改变目标机的 编译程序21.二、与编译程序相关的程序 本讲义只介绍编译程序（器）构造的基本原理、方法与技术，但在一个完整的语言开发（或称程序设计）环境中，除了编译器这一主要工具外，还需要其他一些工具，如编辑器、连接器、装入程序等。现代计算机系统常将这些相互独立的程序设计工具集成起来，构成一个集成化的程序开发环境，以提高程序设计效率和程序的质量。如Turbo C、Visual C+等语言环境都是集成化的程序设计环境。而Ada语言的集成环境是这方面的典型代表。22.如Ada语言的集成环境是一个分层的程序开发环境编译程序MAPSE编辑程序连接程序宿主机OSAPSE工具界面用户界面KAPSE调试程序配置管理程序命令解释程序其他工具23.这儿要强调的是：尽管本课程只介绍编译的基本理论、方法和技术，但这些基本理论、方法与技术对其他工具的构造同样起作用！24.1.编辑器(Editor)完成源程序输入、编辑并产生标准文件（如ASCII文件）的程序。v近来已与编译器和其他程序捆绑进一个交互开发环境IDE中v尽管这样的编辑器仍生成标准文件，但会转向正被讨论的程序设计语言的格式或结构（称为基于结构的），且已包含了编译器的某些操作；因此在程序编写时而不是编译时就可得知错误，甚至也可调用编译器25.2.预处理程序(Preprocessor)在真正翻译开始之前产生编译程序的输入的程序v处理宏及注释：宏是被经常使用的较长结构的缩写v处理文件包含：把头文件包含到程序正文中（如C的文件包含include）v“理解”预处理器：把现代控制流和数据结构机制添加到比较老式的语言中v语言扩充：通过大量的内部宏定义来增强语言的能力，如Equel语言是一种嵌套在C语言中的数据库查询语言26.3.连接程序(Linker)又称为连接编辑器。将分别在不同的目标文件中编译（或汇编）的代码、所用标准库函数的代码以及操作系统提供的资源（如存储分配程序及输入/输出设备）收集到一个可直接执行的文件中的程序4.装配程序(Loader)完成程序的装入和连接编辑两项功能。装入过程包括读入可重定位机器代码、修改可重定位地址、并将修改后的指令和数据放到内存的适当位置。装入程序使得可执行代码更加灵活27.5.调试程序(Debugger)可在被编译了的程序中判定执行错误的程序v它经常与编译程序一起放在IDE中v运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数源代码信息，它可以在预先指定的位置（断点BreakPoint）暂停执行，并提供有关信息（已调用的函数、变量名的当前值等）28.6.其他有关的还有v描述器(Profiler)执行中搜集目标程序行为统计的程序v项 目 管 理 程 序(Project Manager)如Unix系统中的SCCS（源代码控制系统）和RCS（修正控制系统）和汇编程序等综上所述可给出一个“语言处理系统”的图示：29.我们这个课只介绍编译程序这一部分30.三、编译过程与编译程序结构三、编译过程与编译程序结构 1.编译过程：输入 输出（高级语言源程序）（低级语言目标程序）编译程序工作过程如下：l识别出一个个的单词l分析句子的语法结构l分析句子的语义并进行初步翻译l对初步翻译进行优化l整理出目标程序对以上过程进一步整理可得如下编译程序结构总框：编译程序31.2.编译程序总框：词法分析器语法分析器语义分析与中间代码产生器优化器目标代码生成器单词符号语法单位中间代码中间代码出错处理表格管理源程序源程序目标代码目标代码32.3.五个阶段简介l第一阶段：词法分析依据语言构词规则，识别出一个个单词（符号）单词种类l保留字：for if whilel算符：l界符：，；（）l标识符：a1 a2 pil常数：9 1024 4.8 6E6无穷性有穷性思考：识别有穷集合 VS 识别无穷集合 33.词法分析工作由词法分析器（或称扫描器）完成。扫描器输出为等长度的单词符号（二元式）流。例：Position=initial+rate*60词法分析（扫描器）保留字表(06,Position)(11,)(06,initial)(12,)(06,rate)(13,)(07,60的二进制)34.l第二阶段：语法分析依据语言的语法规则，把扫描器提供的单词符号串分解成各种语法单位（范畴），如“短语”、“子句”、“句子”乃至“程序”。同时进行语法检查，以确定输入串是否正确，该工作是由语法分析器完成的。如：Position=initial+rate*60 是一个“赋值表达式”（C语言中）Position =表达式表达式表达式+表达式标识符表达式*表达式initial标识符常数rate60标识符35.l第三阶段：语义分析与中间代码产生针对各类不同的语法范畴，按语言的语义规则进行语义分析和初步翻译工作，产生某种中间语言形式的中间代码（即一种结构简单，含义明确的记号系统）。该阶段工作通常包括两个方面的工作：对每种语法范畴进行静态语义检查，包括：l变量是否定义过l类型是否正确l是否用了0作除数 36.l将语法范畴翻译成某种形式的中间代码，如四元式：37.l第四阶段：优化对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出高效（节省时、空）的目标代码，这一任务是由优化器来完成的l根 据 优 化 的 范 围 不 同，可 分 为：局部优化，循环优化和全局优化l一个循环优化的例子：38.循环循环 For(k=1;k=100;k+)M=I+10*k;N=J+10*k;For(k=1;k=100;k+)M=I+10*k;N=J+10*k;优化前用了两个临时工作单元(T1,T2),优化后没有用临时单元优化前循环体中要做300次加、200次乘，优化后循环体内只做300次加39.l第五阶段：目标代码生成把中间代码翻译成目标代码l显然这阶段要依赖于硬体系统结构和指令系统l涉及存贮分配、寄存器调度这一阶段工作是由代码生成器完成的说明：以上各阶段（或称工序）并不是截然分开 的，尤其编译程序结构十分复杂、体积相当庞大，所以有时人们把几个阶段的工作有机地组合在一起、穿插进行，构成遍。40.v遍（Pass）：对源程序或源程序的中间代码从头到尾扫描一次并做相应处理加工分遍的好处是结构清晰、节省内存（每遍都从外存获取前一遍的结果作为开始，工作结果仍记入外存，每遍几乎可使用全部内存）分不分遍、如何分遍要视具体情况计算机内存容量、源语言的繁简、从事编译程序设计人员的情况等41.如某PL/0编译程序的结构词法分析程词法分析程序序语法语义分析程序语法语义分析程序代码生成程序代码生成程序PL/0PL/0源程序源程序目标程序目标程序表格管理程序出错处理程序42.4.前端与后端：概念上讲，编译程序的五个阶段可进一步划分为前端和后端：前端：主要由与源语言有关而与目标机无关的部分组成，包括词法分析、语法分析、语义分析和中间代码产生。代码优化一般也包含在前端。后端：主要由与目标机有关的部分组成，包括目标代码生成和与目标机有关的优化等。43.源程序词法分析语法分析语义分析和中间代码产生中间语言中间代码优化目标代码生成目标代码优化目标语言前端前端后端后端44.l 划分前端和后端，就可以仅改写后端而生成不同目标机上的目标程序，当然也可考虑对不同语言仅稍加改变前端而产生相同的中间代码，经同一后端生成相同目标机的目标代码。就目前来说，针对相同中间代码适应不同目标机的工作较多，如Ada语言的APSE(Ada程序设计环境)中使用的Diana中间代码，Java语言定义的虚拟机代码Bytecode中间语言，都是定义良好的中间语言。45.Java的传统环境Java源程序(.java)编译环境编译环境Java编译器Java字节码(.class)Java 字节码（本地或网络传输）运行环境运行环境类加载程序字节码验证Java类库Java解释器即时编译器Java虚拟机硬件46.5.表格与表格管理表格记录源程序中的各类有用信息名字、函数、标号、过程、数值等每个阶段的工作都要与表格打交道：查、填、改等表格的结构与处理方法：统一的大表与分类的小表统一大表名字栏为主栏（关键字栏），信息栏又分成若干子栏种属、类型等47.分类小表：每类一张表，如：符号名表(SNT)常数表(CT)48.入口表(ENT)标号表(LBT)基本字表 (KWT)49.6.出错处理：这是编译程序的又一重要组成部分，因为编译的各个阶段都有可能发现源程序中的错误。一旦发现这样或那样的错误，就应把错误的性质及位置报告给用户，并且使编译能继续下去。思考：l如何准确地报告错误l如何从错误中恢复过来50.四、编译程序的构造过程1.需求分析，确定语言文本(1)确定语言的种类：按语言范型分类，当今大多数程序语言可分为四类：v过程式(强制式语言)：命令驱动，面向语句，如FORTRAN、PASCAL、Ada及C等v函数式(应用式)语言：功能驱动，面向函数，如LISP、SNOBOL及ML等v逻辑式(基于规则的)语言：依据条件进行逻辑推演，如Prolog等vOO语言：支持封装性、继承性、多态性及动态聚束等，以对象为运行单位，如Smalltalk、Java、C+等51.通过用户提供的应用范围，决定采用何种语言。例如：偏重于科学计算的则选用Fortran；偏重于符号处理的则选用Lisp或Snobol；偏重于事务处理的则选用Cobol或数据库管理语言；52.(2)深刻理解语言的结构、语法及语义 这就是说不仅仅是用程序设计语言编几个程序的问题，而是要在语法和语义方面下一些功夫。具体说来有以下几个方面：程序语言的定义：任何程序语言都是某个确定的字符集上的符号按照一定规则组成的有穷序列。这里所谓的规则是从两个方面来谈的：语法规则：用于形成和产生一个正确的程序的 一组规则。语义规则：用于定义程序意义的一组规则。53.例如：从语法的角度看，标识符和名字是一个东西，都是以字母开头的字母数字串；但从语义的角度看，标识符是一个没有任何意义的字符序列，而名字却有确定的意义和属性，而且具有一定的作用域和定义域，即有局部和全部之分。又如：程序从语法角度看，是一些语法范畴构成的如下层次结构：54.程序分程序或子程序（过程、函数等）语句表达式数据引用算符函数调用而从语义的角度来说，程序是描述一定的数据结构及其处理过程。55.程序结构：现代高级语言程序通常由若干子程序段（过程、函数等）构成，许多语言还引入了类、程序包等更高级的结构。例如，Fortran、C程序是块结构的；Pascal程序是过程嵌套的；Algol既有分程序嵌套，又有过程嵌套；Java与C+是面向对象的，它们很重要的方面是类和继承的概念，同时支持多态性和动态聚束等特性；而在Ada中引入了程序包，它可以把数据和操作代码封装在一起，支持数据抽象。（详见教材 P15-18）56.语言的基本成分：包括数据类型、表达式、语句、过程或函数等，这些在学习语言课时都已经学过了，但从编译的角度出发，应如何了解这些基本成分呢？初等数据类型：牵扯到存储空间的问题；结构数据类型：牵扯到下标、维数、存放方式、分配时间-动态与静态等；表达式：牵扯到运算分量、运算符、形成规则、运算顺序等；语句：顺序、控制、循环等；过程与参数传递：传地址、传值、传名、得结果 等；存储管理：静态存储分配、动态存储分配；57.2.由程序设计环境确定编译程序构造的方式和方法最早是直接使用机器语言或汇编语言现在一般使用高级语言Pascal或C语言好处：编译方式还是解释方式便于阅读、理解和移植提高程序设计效率易于查错和修改58.任何一个编译程序至少要涉及三种语言：源语言（S）、目标语言（T）和编译程序实现语言（I），可用如下T型图来表示三者之间的关系：59.如若A机上已经有了一个用A机器语言（称A代码）实现的C语言编译程序，则可用C语言作为工具编写Ada语言的编译程序。这样Ada语言的编译程序经过C语言编译程序编译后就可得到A代码的Ada语言编译程序。可图示如下：60.l现在常用构造编译程序的方式除高级语言实现外，经常还用：v自展（自编译）：类似于滚雪球。先确定一个非常简单的核心L0，用低级语言写出其编译程序C0。再把L0扩充为L1，并用L0来编写L1的编译程序。如此逐渐扩展下去，可得到一个系统编程语言族：而Lk便是我们要编译的语言，其编译程序Ck可用Lk-1编写。这种滚雪球式的自展方法可大大减少开发工作量。61.交叉编译：在机器A上产生机器B的目标代码，这种编译程序称为交叉编译。这儿A称宿主机，B称为目标机。这种情况一般是宿主机上有丰富的工具软件，而B机上没有任何高级语言可用。图示为：62.移植：如果一个程序能比较容易地从一台机器上搬到另一台机器上运行，则称其为可移植的，移植一个程序的工作量要远小于开发它的工作量才有意义。显然一个编译程序要可移植，则其前端与后端的界面要清晰、简单，这样仅需改写后端即可。改写后亦可通过交叉编译的方法得到。63.编译程序生成器：根据语言要求、设计实现的算法，能自动产生编译程序的工具软件。可图示为：64.3.确定编译方法：本课程要介绍若干方法，但不可能全采用，只能根据语言特点采用其中一种或二种4.总体设计：分不分遍、分几遍、前端与后端接口并画出总框5.详细设计：进一步细划总框6.实现及调试：采用何种方式实现、分调与连调等65.本节目的：本节目的：为语言的语法描述寻求形式化工具为语言的语法描述寻求形式化工具 工具就是对程序设计语言给出精确无二工具就是对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）义的语法描述。（严谨、简洁、易读）形式化工具就是将形式语言抽象地定义形式化工具就是将形式语言抽象地定义为一个数学系统。为一个数学系统。“形式形式”是指这样的事是指这样的事实：语言的所有规则是以什麽符号串能出实：语言的所有规则是以什麽符号串能出现的方式来陈述。现的方式来陈述。3.高级语言的语法描述66.本节主要内容本节主要内容预备知识上下文无关上下文无关文法及其语言的形式定义文法及其语言的形式定义文法的等价性文法的等价性语法树及文法二义性语法树及文法二义性文法的类型文法的类型语法分析的一些思考语法分析的一些思考67.一、预备知识一、预备知识1.文法的直观概念文法的直观概念 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷多个句子的语言来讲，存在着如何给出它有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。例如：68.“我是大学生我是大学生”是汉语的一个句子是汉语的一个句子对该句子我们可以通过下列一组规则描述：句子=主语谓语 主语=代词名词 代词=我你他 名词=王明大学生工人英语 谓语=动词直接宾语 动词=是学习 直接宾语=代词名词有了这组规则以后，可按如下方式导出句子：先找=左端的带有句子的规则，并将它用 =右端的符号串代替，于是表示成：69.句子句子 主语主语谓语谓语 然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词，那么得到：主语主语谓语谓语 代词代词谓语谓语 依此类推，句子“我是大学生”的全部导出过程是：句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 70.“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据。换句话说，这些规则看成是一种元语言，用它描述汉语，仅仅涉及汉语句子的结构描述。这里“”读作“导出导出”或或“派生出派生出”。而“:=”（通常又简记为“”）读作“定义为定义为”或“由组成”，而每一条规则又称作是产生式产生式或重写式。这样的一种描述形式就称作是BNF（Backus-Naur Form）。71.v例：赋值表达式可描述为 =|a1|b123|salary|stu_age 18|123|4.5|+|-|*|/72.2.语言概述语言概述语言是由句子组成的集合。语言是由句子组成的集合。汉语汉语-所有符合汉语语法的句子的全体。所有符合汉语语法的句子的全体。英语英语-所有符合英语语法的句子的全体。所有符合英语语法的句子的全体。程序设计语言程序设计语言-所有符合该语言语法的程序的全体。所有符合该语言语法的程序的全体。每个句子构成的规则每个句子构成的规则研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系73.研究程序设计语言研究程序设计语言 每个程序构成的规则每个程序构成的规则 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面:语法语法(Syntax)-表示构成语言句子的各个记号之表示构成语言句子的各个记号之 间的组合规则间的组合规则 语义语义(Semantics)-表示各个记号的特定含义。表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）（各个记号和记号所表示的对象之间的关系）语用语用(Pragmatics)-表示在各个记号所出现的行表示在各个记号所出现的行 为中，它们的来源、使用和影响。为中，它们的来源、使用和影响。74.每每种种语语言言具具有有两两个个可可识识别别的的特特性性，即即语语言的形式和该形式相关联的意义。言的形式和该形式相关联的意义。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意意义义。幽幽默默、双双关关语语和和谜谜语语就就是是利利用用这这两两方面意义间的差异。方面意义间的差异。75.如如果果不不考考虑虑语语义义和和语语用用，即即只只从从语语法法这这一一侧侧面面来来看看语语言言，这这种种意意义义下下的的语语言言称称作作形形式式语语言言。形形式式语语言言抽抽象象地地定定义义为为一一个个数数学学系系统统。该该数数学学系系统统称称为为文文法法。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则描描述述什什麽麽符符号号串串以以什什么么方方式式出出现现。形形式式语语言言理理论论是是对对符符号号串串集集合合的的表表示示法法、结结构构及及其其特特性性的的研研究究，是是程程序序设设计计语语言言语语法法分分析析研研究究的基础。的基础。76.3.有关定义和记号有关定义和记号回顾回顾符号：可以相互区别的记号（元素）。符号：可以相互区别的记号（元素）。字母表字母表：符号（元素）的非空有穷集合。：符号（元素）的非空有穷集合。符号串符号串(字字)：由字母表：由字母表 中的符号组成的任何有中的符号组成的任何有穷序列称为该字母表上的符号串。穷序列称为该字母表上的符号串。空字空字(没有没有符号的符号串符号的符号串)是是 上的符号串；上的符号串；若若x是是 上的符号串上的符号串,a是是 的元素的元素,则则xa是是 上上 的符号串的符号串；y是是 上的符号串上的符号串,当且仅当它可以由当且仅当它可以由和和 导出。导出。例如：例如：=a,b =a,b ,a,b,aa,ab,aabba ,a,b,aa,ab,aabba都都是是 上的符号串上的符号串77.符号串符号串s的前缀：符号串的前缀：符号串s的任何首部。的任何首部。如如:、b、ba、都是符号串都是符号串banana的前缀的前缀.符号串符号串s的后缀：符号串的后缀：符号串s的任何尾部。的任何尾部。如如:、a、na、都是符号串都是符号串banana的后缀的后缀.符号串符号串s的子串：从的子串：从s中删去一个前缀和一个后缀中删去一个前缀和一个后缀得到的符号串得到的符号串.如如:ana是符号串是符号串banana的一个子串的一个子串.符号串符号串s的真前缀：的真前缀：xs且且x的任何前缀的任何前缀x。s的真后缀，真子串可以类似地定义。的真后缀，真子串可以类似地定义。78.符号串的运算：符号串的运算：符号串的长度：符号串中符号的个数符号串的长度：符号串中符号的个数.符号串符号串s 的长度的长度 记为记为|s|。的长度为的长度为0连接：符号串连接：符号串x x、y y的连接的连接,是把是把y y的符号写在的符号写在x x的符号的符号 之后得到的符号串之后得到的符号串xy xy 如如 x=ab,y=cd x=ab,y=cd 则则 xy=abcd xy=abcd 又如又如a=a a=a 方幂：符号串自身连接方幂：符号串自身连接n n次得到的符号串次得到的符号串 a an n 定义为定义为 aaaa aaaa n n个个a a a a0 0=,a=,a1 1=a,a=a,a2 2=aa=aa 79.符号串集合：若集合符号串集合：若集合A中所有元素都是某字母中所有元素都是某字母表表 上的符号串，则称上的符号串，则称A为字母表为字母表 上的符号上的符号串集合。串集合。符号串集合符号串集合A和和B的乘积：的乘积：AB=xy|xxy|x A A且且y y B B 若若 集合集合A=ab,cdeab,cde B=0,10,1 则则 AB=ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 的闭包：的闭包：上的一切符号串（包括上的一切符号串（包括）组成）组成的集合，记为的集合，记为 *。的正闭包：的正闭包：上的上的除除外外的所有符号串组的所有符号串组成的集合，记为成的集合，记为+。80.例：例：=a,b=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,+=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,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言。是一个语言，即 也是一个语言。82.二、上下文无关文法及其语言的形式定义二、上下文无关文法及其语言的形式定义1.如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示；以将句子逐一列出来表示；如果语言是无穷的，找出语言的有穷表示。如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途径：语言的有穷表示有两个途径：生成方式生成方式：语言中的每个句子可以用严格定义的：语言中的每个句子可以用严格定义的规则来构造。规则来构造。识别方式：用一个过程，当输入的一任意串属于识别方式：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答语言时，该过程经有限次计算后就会停止并回答“是是”，若不属于，要麽能停止并回答，若不属于，要麽能停止并回答“不是不是”，要麽永远继续下去。，要麽永远继续下去。83.文法是从生成方式描述语言的，而自动机则是从识别的角度来描述语言的。本节仅介绍有关文法的概念。前面关于“我是大学生”及“赋值表达式”的例子中，涉及到如下的概念：l所表示的是一个类类概念，通常称作语法范畴语法范畴或语法变量，如果用一个符号来代替,也称为非终结符非终结符(nonterminal)。所有规则中的非终结符构成了一个非空有穷集，记为V VN N。l上述两例中的“句子”及“赋值表达式”显然是最大的语法范畴，也是我们最感兴趣的非终结符，通常称作开始符号，记为S S。l“大学生”、“我”、“是”、“a”、“+”等表示的是一个具体概念，用一个符号来表示，则称为终结符终结符(terminal)。所有这样的符号同样构成了一个非空有穷集，记为V VT T。l我、8等称作产生式(production)。所有产生式的集合显然是有穷的，记为P。这样我们可以将文法抽象为如下的一个数学系统：84.2.文法的形式定义文法的形式定义一个文法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=S0S1,S01 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.G：SaASaAb Aab Aab AaA AaAb A A .GS.GS：SaSSaSb Aab AaA Aab AaAb A A .GSGS：SaSSaSb Aab|aA Aab|aAb|元元符号：=|=|习惯表示：大写英文字母：非终结符/集合 字母表中靠前的小写英文字母：终结符 字母表中靠后的小写英文字母：字符串87.v上下文无关文法：它所定义的语法范畴是完全独立于这种范畴所能出现的环境。程序设计语言的词：a+b/3 a10)，则记为，则记为 v+w，v推导出推导出w，或，或w归约到归约到v。若有。若有v+w，或或v=w，则记为，则记为v*w。例：例：G G：S0S1，S01 S 0S1 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S+00001111 S*S 00S11*00S1190.(3)最左（最右）推导最左（最右）推导最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，都是对，都是对中的最左（右）非终结中的最左（右）非终结符进行替换。符进行替换。最右推导被称为最右推导被称为规范推导规范推导。也就是说，规范。也就是说，规范推导具有最右性。推导具有最右性。规范推导的逆过程称为规范推导的逆过程称为规范规约规范规约。也就是说，。也就是说，规范规约具有最左性。规范规约具有最左性。由规范推导所得的句型称为由规范推导所得的句型称为规范句型。规范句型。91.4.句型、句子句型、句子句型：句型：有文法有文法G，若，若S *x，x(V(VN NVVT T)*,则称则称x是文是文法法G的句型。的句型。句子：句子：有文法有文法G，若，若S *x，且，且xVVT T*，则称，则称x是文法是文法G的句子。的句子。例例1 1：G G：S0S1，S01 S 0S1 00S11 000S111 00001111 G的句型:S,0S1,00S11,000S111,00001111 G的句子:00001111,0192.例例2：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|a这个文法都能推导出什么句子？EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a用符号用符号a a，+，*，(和和)构成的算术表达式构成的算术表达式思考：写出一个不同的文法，同样能够产生这些句子思考：写出一个不同的文法，同样能够产生这些句子93.5.语言的定义语言的定义 由文法G生成的语言记为L(G),它是文法G的所有句子的集合。L(G)=x|S+x,S为开始符号,且x VT*例例1 G1 G：S0S1，S01 L(G)=0n1n|n1 例例2 2 文法文法GSGS：（1 1）SaSBESaSBE（2 2）SaBESaBE（3 3）EBBEEBBE（4 4）aBabaBab（5 5）bBbbbBbb（6 6）bEbebEbe（7 7）eEeeeEee L（G）=anbnen|n1 这个文法生成什么语言？这个文法与前面见过的文法有什么不同？94.S a S BE (SaSBE)a aBEBE (SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)类似推导可以看出类似推导可以看出a,b,e在句子中出现的顺序及个数满足在句子中出现的顺序及个数满足L(G)当然要进一步说明：当然要进一步说明：G G生成的每个句子都在生成的每个句子都在L(G)L(G)中中 L(G)L(G)中的每个句子确实能被中的每个句子确实能被G G生成生成95.使用产生式(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。也能证明，对于n1，串anbnen是唯一形式的终结符号串。96.三、文法的等价性三、文法的等价性1.定义：定义：若若L(GL(G1 1)=L(G)=L(G2 2)，则称文法，则称文法G G1 1和和G G2 2是等价的。是等价的。如文法如文法G1A：A0R 与与 G2S：S0S1 等价等价 A01 S01 RA1因为因为L（G1）=L（G2）=0n1n n1。97.2.关于文法等价变换的几个定理关于文法等价变换的几个定理(1)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2的开始符号不出现在任何产生式的右部。例1：G1:EE+EE*E(E)iG2:SEEE+EE*E(E)i具体做法：加一条单个非产生式SE即可。(2)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2的每个非终结符都能导出一个终结符号串。可给出如下证明：98.v证明：令=AAtG1&tVT+；递归扩充：=WWx&x(VT)+由于G1的非终结符号是有穷的，上述过程一定是收敛的；从G1的VN中删除不包含在中的非终结符，并从其产生式集中删除其左部或右部中包含不属于中的符号的产生式，这样得到的文法即为所要的G2。99.例：G1A:ABeddD Bb DEaADDB EDaEb =B =BA=A,B,到此为止；于是D,E及相关D,E的产生式均可删除，得到：G2A:ABed Bb 可以证明L(G1)=L(G2)。类似还可以给出如下定理：(3)对任一文法G1都可以构造文法G2，使得L(G1)=L(G