编译原理 复习资料.doc

教材资料授课顺序：1教学目的：正确理解什么是编译程序；了解编译程序工作的基本过程及其各阶段的基本任务；熟悉编译程序总框；了解编译程序的生成过程和构造工具。教学重点与难点： 编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。授课学时：2学时 教学方式：多媒体讲授教学内容：第一章 引论1.1 什么是编译程序一、基本概念1、翻译程序：是指这样的一种程序，它能够把一种语言程序(源语言程序)转换成另一种功能等价的语言程序(目标语言程序)。2、编译程序是一种翻译程序，其源程序是高级语言，目标语言程序是低级语言。通常是一次性翻译方式。如TC等高级语言编译程序。3、解释程序也是一种翻译程序，它与编译程序的区别：立即执行源程序，通常是逐句翻译执行。如BASIC、SQL、JAVA的BYTECODE解释程序等。二、高级语言程序的处理过程 高级程序设计语言程序的典型处理过程如下图所示：1.2编译过程和编译程序结构一、编译过程的阶段划分 一般编译程序的工作过程按阶段进行，每个阶段将源程序从一种表示形式转换成另一种表示形式。典型的阶段划分方法是将整个编译过程分为如下六个阶段： 1、词法分析： 任务：对构成源程序的字符串进行扫描和分解，识别出单词(如标识符等)符号。输入：源程序输出：单词符号序列 例子：有待分析源程序：main() int x=10,y; 词法分析后的输出：1）保留字： main 2）界符：左圆括号 (3）界符：右圆括号)4）界符：左大括号5)保留字：int6)标识符：x7)运算符：=8)常数：10 ，界符：，9)标识符：y10)界符：；11）界符：右大括号 2、语法分析 任务：根据语言的语法规则对单词符号串(符号序列)进行语法分析，识别出各类语法短语(可表示成语法树的语法单位)，判断输入串在语法上是否正确。输入：单词序列输出：语法分析后的单词序列3、语义分析任务：按语义规则对语法分析器归约出的语法单位进行语义分析，审查有无语义错误，为代码生成阶段收集类型信息，并进行类型审查和违背语言规范的报错处理。 输入：语法分析后的单词序列 输出：语义分析后带语义信息的单词序列 4、中间代码生成（并非所有的编译程序都包含此阶段）任务：将语义分析得到的源程序变成一种结构简单、含义明确、易生成、易翻译成目标代码的内在代码形式。常用的中间代码形式是四元式（算符，运算对象1，运算对象2，结果）。 输入：语义分析后的单词序列 输出：中间代码 5、代码优化（可放到目标代码生成阶段后）任务：对中间代码或目标代码进行变换改造等优化处理，使生成的代码更高效。 输入：中间代码或目标代码 输出：优化后的中间代码或目标代码 6、目标代码生成任务：将中间代码生成特定机器上的绝对或可重定位的指令代码或汇编指令代码。 输入：语义分析后的单词序列或优化后的中间代码 输出：目标代码 二、编译程序结构上述六个阶段的任务分别由六个模块来完成。一个完整的编译程序还应包括表格管理和出错处理程序。典型编译程序结构框图如下：三、编译阶段的组合 1、前后端组合法编译前端：与源语言有关与目标机无关的部分(第1-4阶段)。编译后端：与目标机有关的部分(第6阶段)注：第5阶段置前或后端都可以。组合方式：1）同一源语言的编译前端+不同后端=不同机器上同一源语言的编译程序；2）不同源语言的编译前端生成同一种中间语言+使用共同后端=同一机器上不同语言的编译程序。 2、遍组合法遍/趟：对源程序或源程序的中间结果从头到尾扫描一次称为一遍。每一遍扫视完成一个或几个阶段的工作。一个编译程序可由一遍或多遍完成.实际编译程序分遍的主要参考因素是源语言与目标机器的特征。1.3编译技术和软件工具一、编译技术的发展 1950S早期：算术工式译成机器代码。 1950S中期：FORTRAN编译系统。 1950S末期：自动生成工具出现，如：LEX、YACC。 1960S：自展技术。 1971年：用自展技术生成PASCAL编译程序。 现代：并行编译技术。 二、编译技术与软件工具 1、先进的软件开发技术和软件工具能提高编程效率、缩短调试时间。 2、编译程序本身是一种软件工具。 3、大部分软件工具的开发常用到编译技术和方法。 4、进行源程序处理的软件工具实质上都在不同程度上用到了编译程序各个部分的技术和方法。如： （1）语言结构化编辑器（语法）； （2）语言程序调试工具（语法、语义）； （3）语言程序测试工具（静、动态测试，发现错误）； （4）高级语言之间的转换工具； （5）程序格式化工具、程序理解工具等。1.4程序设计语言规范 从支持的计算模式来看，程序设计语言（是指书写计算机程序的高级语言）规范有如下几种： 1、强制命令式语言，即过程式语言 该型 语言中，一个过程可看作是一系列动作，其动作由命令驱动，以语句形式表示，一个语句接一个语句的执行。属于这种规范的语言如PASCAL、C、FORTRAN等，C+、Ada、COBOL等也支持这种模式。本课程介绍的编译技术针对这型语句。 2、函数式语言，即应用式语言 该型语言注重程序所表示的功能，程序的开发过程是从前面已有函数出发构造出更加复杂的函数，对初始数据集进行操作，直到最后形成的函数可以得到最终结果。属于这种规范的语言如ML、LISP等。 3、基于规则（逻辑）的语言 该型语言程序的执行过程是检查一定的使能条件，满足时，则执行适当的动作。如逻辑程序设计语言PROLOG，其基本的使能条件是某种谓词逻辑表达式；再如YACC，其使能条件是程序的形式语法（BNF）。 4、面向对象语言 该型语言的主要特点是提供抽象数据类型，支持封装性、继承性和多态性。C+、Ada、Java等也支持这种模式。1.5编译程序的构造一、编译程序的构造途径 1、用某种程序语言编写； 2、用编译程序自动构造工具构造。 3、通过现有的编译基础设施进行改造和组装。二、T型图 T型图是用来表示一个编译程序所涉及到的三个方面的语言的一种工具，将源语言S通过用语言H书写的编译器翻译成目标语言T的编译程序可用如下T型图THST表示。 T型图的两种组合方式： 三、编译程序的自展 1、方法：用“滚雪球”的方式生成编译程序。 2、思想：先用目标机的汇编语言或机器语言书写源语言的一个子集的编译程序，再用这个子集作为书写语言（属于高级语言），实现源语言的编译程序。例：设 ， 目标机A的语言为A，则两层自展构造实现语言C对应A机器的编译程序过程可描述为如下： 其自展过程：用语言A编写语言C1的编译程序TAC1A；再用C1书写语言C的编译程序TC1CA；最后再将TC1CA经过TAC1A编译得到 TACA。四、编译程序的移植、自编译、交叉编译 1、移植：将某一机器(宿主机)上已有的软件移植到另一机器(目标机)上的过程。 2、自编译：用某种语言本身书写自己的编译程序的过程。 例如：在机器A上已有语言C的编译程序（将语言C翻译成A的机器码A），现希望利用此编译程序生成机器B上的语言C的编译程序（将语言C翻译成B的机器码B）。 3、交叉编译：把某源语言在宿主机上经过编译而产生目标机的汇编语言或机器语言的过程。 五、可重定向编译程序 1、由于交叉编译是在一个平台上生成另一个平台上的可执行代码的过程。交叉编译受限较多。 2、编译基础设施：为开发各种编译程序成分提供相应生成工具。 3、可重定向编译程序：能够根据不同的目标机生成相应目标代码的编译程序。它将与目标机相关的部分单独编写成不同模块，根据不同的目标机调用不同的模块。自由软件GCC(GNU工程的编译程序集合)是目前使用广泛的可重定向编译程序。 、支持可重定向编译的关键技术1）中间表示技术：区别于四元式等传统的中间表示，支持可重定向编译的中间表示应在适当的抽象层次上，向上能够支持多语言映射、向下能够适应多平台转换后宜于进行各种优化。2)机器描述技术：区别于传统的假定式体系结构抽象模型的描述技术，支持可重定向编译的机器描述机制应能描述系统和硬件的共性，又能描述它们各自的特性，且能适应于不同编译程序的处理。研究表明，基于体系结构描述语言详细地指定了体系结构是产生高质量机器级工具的关键技术。3）代码生成程序的构造技术：为简化开始过程、提高代码可靠性，支持代码生成程序的自动构造工具是关键技术和主要难点。4）目标机描述与目标代码生成的接口技术：在重定向编译程序的开始过程中，抽取一系列函数和数据结构作为目标机描述与目标代码生成的接口可以简化编译程序的开发，提高编译程序的效率。 授课顺序：2教学目的：使学生了解文法的直观描述、符号和符号串，掌握文法和语言的形式定义、文法的分类。教学重点：文法和语言的形式定义、文法的分类教学难点：文法和语言的形式定义授课学时：2学时教学方式：多媒体讲授教学内容：第三章文法和语言3.1语言概述和文法的直观概念一、基本概念 1、语言：是由句子组成的集合，是由一组符号所构成的集合。 2、汉语：所有符合汉语语法的句子的全体。 3、英语：所有符合英语语法的句子的全体。4、程序设计语言：所有该语言的程序的全体。 二、语言研究的内容 1、语法（Syntax）：每个句子构成的规律/每个程序构成的规律。表示构成语言句子的各个记号之间的组合规律。在形式语言理论中，阐明语法的工具是文法。 2、语义（Semantics）：每个句子的含义/每个程序的含义。表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）。 3、语用（Pragmatics）：每个句子和使用者的关系/每个程序和使用者的关系。表示在各个记号所出现的行为中，它们的来源、使用和影响。三、文法的直观描述 通常，用句子表述一种语言，但是句子是无穷的。 1、例子 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。下面采用EBNF来表示句子的构成规则。先给定如下一组规则：句子=主语谓语主语=代词名词代词=我你他名词=王明学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 有了这一组规则后，用它们导出句子的方式如下： 1）找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成： 句子 主语谓语 2）在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。 比如：选取了主语，并采用规则主语=代词， 那么得到： 主语谓语 代词谓语， 3）重复上述步骤。 导出句子：“你是学生”的全部动作过程是： 句子 主语谓语 代词谓语你谓语你动词直接宾语 你是直接宾语你是名词你是学生 因此，“你是学生”的构成符合上述规则，而“你学生是”不符合上述规则，因此，它不是句子。 2、文法的直观定义 上例中的规则就是我们判别句子结构合法与否的依据，可以将这些规则看成是一种元语言，用它描述汉语。由此可得文法的直观定义如下： 文法：就是这样一些规则的有穷集合，它是以有穷规则集来刻划无穷句子集合的工具。3.2符号和符号串一、基本概念 1、字母表：元素的非空有穷集，记为 。2、符号：字母表中的元素。3、符号串：符号的有穷序列。4、空符号串：什么符号也不含的符号串，记为。例： =a，b，c，d，z。a、b、c都称为符号。hello、stri、aezfg、main、fjfka都是上的符号串。二、符号串的基本操作 1、符号串的长度：符号所包含符号的个数，设x是一符号串，其长度记为|x|。 例：|hello|=5，|main|=4，| |=0。 2、符号串的连接：设x、y是两个符号串，则xy被称为x与y的连接。特别有： x=x=x=x 例：x=my，y=classmate，则xy=myclassmate。 3、符号串的方幂：设x是符号串，x自身的连接称为符号串的方幂，有： 例：x=ba， x0 = ， x1 =ba， x2 =bababa 4、符号串的集合：若集合A中元素都是某字母表上的符号串，则A是上的符号串集合。 5、符号串集合的乘积：若A、B均为上的符号串集合，则AB=xy|xA，y B 例：设A=ab，cd，B=ef，jh，则AB=abef，abjh，cdef，cdjh A=A， A=A =。 6、符号串集合的正闭包：设符号串集合A，A的正闭包记为A+，A的闭包记为A*。 例： 设=0，1，则 + =0，1，00，01，10，11，000，001。 * =，0，1，00，01，10。3.3文法和语言的形式定义一、基本概念 1、产生式 设VN，VT分别是非空有限的非终结符号集和终结符集。V= VN VT， VN VT=。所谓产生式是一个序偶对(， )，其中 V+，V*，通常表示为： 或 =，产生式也叫规则、重写规则、生成式。 例： 0|1|2|3|9 2、文法文法G是一个四元组，G=(VN，VT， P， S)。其中：VN，VT分别是非空有限的非终结符集和终结符集，且二者交集为；P为产生式集；S VN，是文法的开始符号(或识别符)，它是一个非终结符，至少要在一条规则中作为左部出现。 例：文法G=(VN，VT， P， S)，其中VN =S，B， VT =0，1，P=S 0B，B 1，B 1B。开始符为S。可用文法的通俗表示法表示如下：GS： S 0B，B 1，B 1B 这个文法表示所有形如01，011，0111，01111的串。 3、直接推导 设是文法G=(VN，VT， P， S) 的产生式， (VN VT) *，若有符号串v，w满足v=，w=，则称w是v的直接推导，或称v是w的直接归约。记作v=w。 例：现有文法GE：EE+T | T TT*F | F F(E) | i 设v=E+F*i，w=E+i*i，则有v=w或 E+F*i = E+i*i。 4、推导 如存在一直接推导序列v=0=1=2.=n=u (n0)，则称符号串u为符号串v的一个推导(或者说v是u的一个归约)，记为v=+ u；若有v=+u，且有v=u，则记作v=*u。 例：对于上例中文法GE：EE+T | T TT*F | F F(E) | i 设v=E，u=i+i*i，则有：v=+u。相应的直接推导序列为： E=E+T=E+T*F=E+F*F=T+F*F=F+F*F=F+F*i=F+i*i=i+i*i 5、句型和句子 设GS是一文法，如有 S=* x，则称x是文法GS的句型。若x是GS的句型，且x VT*，则称x是GS的句子。 6、语言 文法GS的语言是GS的所有句子构成的集合。即L(G) =x|S =*x，且xVT*。 例：文法GS：SMVD M小王|小张 V是|不是 D大学生则文法GS表示的语言可定义为： L(G) =小王是大学生，小王不是大学生，小张是大学生，小张不是大学生 MVD,M是D,M是大学生等均是GS的句型。 7、文法的等价 若L(G1) =L(G2) ,则称G1和G2是等价的。3.4文法的类型 Chomsky将文法按其所表示的语言的表达能力，由高往低分为四类：0型，1型，2型，3型文法。一、定义 （1）0型文法 如果文法G的产生式，其中 (VNVT) *， 且至少含有一个非终结符号， (VNVT) *。则称G为0型文法。0型文法又称短语结构文法。 （2）1型文法 如果0型文法G的产生式满足|=|，仅当= 时例外。则称此文法G是1型文法。1型文法也称上下文有关文法。 （3）2型文法 一个1型文法G，如果满足VN，则称为2型文法。或者说2型文法的产生式都形如A 。2型文法也称上下文无关文法。 （4）3型文法 一个2型文法G，如果产生式全都是形如 A a或A aB，其中：A、B VN ，a VT *，则G为3型文法。3型文法也称正则文法或正规文法或右线性文法。它对应有穷自动机。（5）四类文法产生对应的四类语言。 二、文法之间的关系四类文法的定义是通过逐步增加限制条件进行的。即有：3型文法2型文法1型文法0型文法。 三、例题 判断下列文法类型：例1：文法GS：S aSYZ SaYZ aYay yYyy yZyz ZYYZ zZzz 0，1例2：文法GS：S xSYZ SxYZ xYx yYyy yZyz ZYYZ zZzz 0，1例3：文法GS：SaT TbT|cT|b|c 0，1，2，3例4：文法GS：SxB|c BAz AcS 0，1，2，3授课顺序：3教学目的：使学生掌握语法树的构造、句型分析的方法，了解二义性文法的改造和有关文法实用性的一些说明。教学重点：句型分析教学难点：二义性文法的改造、句型分析授课学时：2学时教学方式：多媒体讲授教学内容：3.4 上下文无关文法及语法树 上下文无关文法有足够的能力来描述现今程序设计语言的语法结构。今后如无特别说明，“文法”一词均指上下文无关文法。一、语法树语法树也称推导树，给定文法G=(VN， VT，P，S)，对于文法G的任意一个句型都存在一个相应的语法树，它满足：(1)树中每一个结点都有一个标记，此标记是V= VNVT中的一个符号。(2)根的标记是S。(3)苦树的一结点A至少有一个子女，则AVN。(4)如结点A的子女结点从左到右次序为B1，B2.Bn，则必有产生式AB1B2.Bn。例：GS： SaAS | aASbA |SS |ba对句型aabbaa的推导过程可表示为下图所示语法树。下面两个推导过程均可由上图表示。 (1) SaASaSbASaabASaabbaSaabbaa (2) SaASaAaaSbAaaSbbaaaabbaa这说明同一语法树可以表示对同一句型不同的推导过程。 二、最左(右)推导 1、如果每一步中，都是对中最左(右)非终结符进行替换， 则称之为最左(右)推导。2、最右推导称为规范推导，由规范推导所得的句型称为规范句型。3、同一语法树最多对应唯一的最左(右)推导。4、一个句型有可能对应着不同的语法树。 例：文法GE： Ei | E+E | E*E | (E)，则句型 i*i+i可能对应着下面两个最右推导： (1) EE+EE+iE*E+iE*i+ii*i+i (2) EE*EE*E+EE*E+iE*i+ii*i+i三、二义性语法树1、如果一个文法存在某个句子对应着两棵不同的语法树，则称此文法是二义的。不存在一种算法能在有限步骤内判断一个2型文法是否是二义的。2、实际应用中，常找出一组无二义性的充分条件来构造无二义性文法。3、例子例1：下列简单算术表达式的文法是二义性文法。EE+E|E-E|E*E|E/E|(E) |id引入新的非终结符后可变换为非二义性文法。EE+T|E-T|T TT*F|T/F|F F(E) |id 例2：If语句的文法GS：Sif E then S Sif E then S else S SE Ea0|a0|b=1|b=-1|b=0假设执行下列语句前b=0，有If句子：if a0 then if a0 then b=1 else b=-1则当a=1时，b=1;当a=-1时，b=-1; 当a=0时，b=0。 通过引入新非终结符、加规则进行改造后得文法：(1)SU|M|E (2) Uif E then S (3) Uif E then M else U (4) Mif E then M else M (5) M S (6) M (7) Ea0|a0|b=1|b=-1|b=0 课堂作业：为上述改造前和和改造后的文法构造唯一的语法树。3.6句型的分析句型的分析就是识别一个符号串是否为某文法的一个句型。本课程介绍的分析算法都是从左到右的分析算法。它们分为两大类：自顶向下分析、自底向上分析一、自顶向下分析自顶向下分析：由根向下逐步建立语法树，是一个逐步推导的过程。 例：文法GS： ScAd Aab |a 对输入串cabd进行识别过程为：ScAdcabd，构造语法树步骤如图所示：识别过程也有可能是ScAdcad，此时无法识别出串cabd，需要回溯。 二、自底向上分析自底向上分析：自叶向上构造语法树，是一个逐步约的过程。自底向上分析法的核心在于寻找“可归约串”。 例：对串cabd归约过程为 cabdcAdS，构造语法树步骤如图所示： 归约过程也有可能是cabdcAbd，此时无法识别出串cabd，也需要回溯。 三、句型分析的有关问题 1、基本概念（1）令GS是一文法，是文法G的一个句型，如果有：S =* A，且A =+，则称是句型相对于非终结符A的短语，如有A，则称是相对于非终结符A或相对于规则A的直接短语(也叫简单短语)。（2）一个句型的最左直接短语称为该句型的句柄。注意： 作为短语的必须是需要分析的句型的一部分。2、例子例1：已知文法GE： EE+T | T TT*F | F F(E) | i 对于给定的句型i*i+i，指出该句型的所有短语、直接短语和句柄。 解：将句型改写为i1*i2+i3，则： 1）因 E=+i1*i2+i3， E=+i1*i2，故句型相对于E的短语有：i1*i2+i3，i1*i2。 2）因 T=+i1*i2，T=+i1，T=+i3，故句型相对于T的短语有i1*i2， i1， i3。 3）因 F=+i1，F=+i2， F=+i3，故句型相对于F的短语为：i1， i2， i3;且i1， i2， i3均为句型相对于规则Fi 的直接短语，其中i1为句柄。 下面根据语法树进行分析： 例2： GS： SaAS S a ASbA A SS A ba要求对句型aabbaa的进行分析。 解：将句型改写为a1a2b1b2a3a4，则： 1）该句型相对于S的短语： a1a2b1b2a3a4和 a4； 2）该句型相对于A的短语： a2b1b2a3和b2a3； 3）该句型相对于Sa的直接短语： a2，a4； 4）该句型相对于Aba的直接短语： b2a3； 5）句柄：a2。问题： a1、b1、b2、a3为什么不是短语？3.7文法实用性的一些说明一、有关文法的实用限制1、在实用中，文法中不得含有害规则或多余规则。2、形如UU的规则为有害规则。3、不可达规则或不可终止规则为多余规则。 例：GS：SAb|Cd Ab De CCa 二、限制使用规则 即形如A的规则，它会使有关文法的证明和讨论变得复杂。 习题讲解 P48第11题扩展： 令文法GE为：ET|E+T|E-T TF|T*F|T/F F(E) |i 要求证明F+T*F是它的一个句型，构造其语法树，并指出这个句型的所有短语、直接短语和句柄。解：1）证明：因为E E+T T+T F+T F+T*F，即有E=* F+T*F，故：F+T*F是GE的一个句型。语法树如下图所示。2）句型分析 该句型相对于E的短语： F+T*F、F； 该句型相对于T的短语： T*F、F； 该句型相对于TF的直接短语F，相对于TT*F的直接短语：T*F； 该句型的句柄：F。作业：P47练习 2、5、9、11、16授课顺序：4教学目的：让学生了解词法分析程序的概念及设计原则、单词的分类，掌握正规文法、正规式的相关概念及等价转换方法。教学重点：正规文法和正规式的相关概念及等价转换教学难点：正规文法和正规式的等价转换授课学时：2学时 教学方式：多媒体讲授教学内容：第四章词法分析4.1 词法分析程序的设计一、词法分析程序的设计思想 通常将词法分析程序（扫描器）设计为子程序形式，当语法分析程序需要单词时，则调用该子程序。 二、单词分类 通常分为5类： (1)基本字(关键字、保留字)：具有特殊含义的标识符，不作他用，有分隔语法的作用； (2)标识符：表示各种名字； (3)常量：整型、实型、布尔型、字符型； (4)运算符：算术、逻辑、关系运算符； (5)界符：包括.，;，(，)，:，等，有时也把运算符称作界符。三、词法分析程序的设计原则 (1）把扫描器当作语法分析的一个过程，当语法分析需要一个单词时，便调用扫描器。 (2)扫描器从初态出发，当识别一个单词后便进入终态，同时输出二元组。 四、词法分析程序的输出 词法分析程序扫描后输出单词序列表示为如下二元组形式： 二元组：（单词种别，单词自身值或指针） 例：若规定标识符、常数、基本字、运算符、界符的种别用整数编码分别为1、2、3、4、5，则对程序段 ： “ if k=7 then a:=b ; ” ，则其经扫描器扫描后输出的单词符号及其二元组为： 基本字if (3， if) 标识符k (1，指向k的符号表入口的指针 ) 等号= (4， =) 常数7 （2，7） 基本字then (3， then) 标识符a (1， 指向a的符号表入口的指针) 赋值号:= (4， :=) 标识符b (1， 指向b的符号表入口的指针) 分号； (5， ;)五、词法分析程序独立设计的优点 (1)使整个编译程序的结构更加简洁、清晰、条理化； (2)改进了编译程序的效率； (3）增加了编译程序的可移植性。4.2单词的描述工具一、正规文法3型文法，又称右线性文法或正规文法(Regular Grammars)，其表达式形如：AaB或Aa。正规文法描述的语言是VT*上的正规集。绝大部分程序设计语言的单词都能用正规文法来描述。 二、正规式和正规集 1、定义 正规式也称正规表达式，是表示正规集的工具，递归定义如下：1)和都是字母表S上的正规式，表示正规集为和；2)aS，a是S上的正规式，表示正规集a；3)假定e1、e2都是S上的正规式，对应正规集为L(e1)、L(e2)，则(e1)、e1|e2、e1.e2、e1*也是正规式，分别表示的正规集为L(e1)，L(e1) L(e2)，L(e1).L(e2)，和L(e1)*；4)仅由有限次运用上述步骤产生的表达式才是S上的正规式，仅由这些正规式产生的字集才是S上的正规集。 例: 设S=0，1，则有：正规式正规集000|10，101011*，1，11，111.(0|1)*，0，1，01，10. 3、正规式服从的代数规则 设r，s，t为正规式，则正规式服从如下的代数规则： r|s=s|r (或满足交换律) r|(s|t)=(r|s)|t (或满足结合律) r(st)=(rs)t (连接满足结合律) r(s|t)=rs | rt (分配律) r=r=r (是连接的恒等元素)注意： rssr r|(st)rs | rt 三、正规式和正规文法的等价性 任意一个正规语言既可以由正规式定义，也可由正规文法来定义。正规式和正规文法之间可进行等价转换。 1、正规式转换成正规文法 将S=VT上的正规式r换成正规文法G =(VN， VT，P，S)方法如下：(1)令Sr (2)对形如Axy的产生式，可分解成AxB，By (3)对形如Ax*y的产生式，可分解成为AxA， Ay(4)对形如Ax|y 的产生式，可分解为 Ax ，Ay反复利用上述规则，直至所有产生式中最多只含一个终结符。 例：将R=a(a|d)*转换成相应的正规文法。 解：步骤如下： (1) Sa(a|d)*(2) SaB， B(a|d)B， B(3) SaB， BaB ，BdB， B 相应的正规文法如(3)式所示，即GS: SaB BaB|dB| 2、正规文法转换成正规式 将正规文法G=(VN， VT，P，S)换成S=VT上的正规式r的转换规则：1）将产生式AxB By 合写为A=xy；2）将产生式AxA Ay 合写为A=x*y；3）将产生式Ax Ay 合写为A= x|y反复利用上述规则，直至只剩下一个由开始符定义的产生式，且该产生式右部不含一个非终结符。例：将正规文法GS: SdA|eB AaA|b BbB|c换成正规式。 解：步骤如下：(1)由AaA|b，将A转换成a*b；由BbB|c，将 B转换成b*c；(2)由 SdA|eB，将S可转换成(da*b)|(eb*c)故所求正规式为R=(da*b)|(eb*c)。授课顺序：5教学目的：让学生掌握DFA和NFA的定义，了解DFA和NFA的表示方法，掌握NFA与DFA的等价转换方法及DFA的化简方法。教学重点：DFA和NFA的定义、等价转换及DFA的化简教学难点：DFA和NFA的等价转换、DFA的化简授课学时：2学时 教学方式：多媒体讲授教学内容：4.3有穷自动机一、概述 有穷自动机(Finite Automata):可准确识别正规集（即识别正规文法所定义的语言和正规式所表示的集合）的一种装置。它分为两类: (1)确定的有穷自动机(Deterministic Finite Automata，简称DFA) (2)不确定的有穷自动机(Nondeterministic Finite Automata，简称NFA) 二、确定的有穷自动机(DFA) 1、定义 确定的有穷自动机表示为一个五元组：M=(K，S，f，S，Z)，其中：(1) K是一有穷状态集；(2)S是一有穷字母表，称输入符号字母表；(3) f是转换函数，是在KSK上的映射。如f(ki，a)=kj；(4) S是唯一的一个初态；(5) ZK，是一终态集，终态也称结束态或可接受态。 2、DFA的状态图表示 假设DFA M有m个状态，n个输入字符，则： (1)状态图有m个结点，每个结点最多有n条弧射出； (2)有唯一的一个初态结点，前面冠以“=”或“-”标记； (3)有若干终态结点，用双圆圈或“+”标记； 例：下图所示DFA可识别正则集L(ab*c)，如串abbc可被认别。 3、DFA的矩阵表示 (1)行表示状态； (2)列表示输入字符则； (3)矩阵元素表示相应状态行和输入字符列下新状态（即k行a列为f(k，a)的值）； (4)用“=”标记行或第一行表示初态； (5)终态行右端标以1，非终态行右端标以0。 例：上图也可表示为矩阵形式： abc SA 0A AB0B 1 4、转换函数定义扩充 方便起见，对DFA中转换函数定义进行扩充：f是转换函数，是在KS*K上的映射，有： (1) f(k1，)=k1 (2) f(k1，a)=f(f(k1，a)，)其中，k1K，aS ，S*。 5、接受(识别) 设DFA=(K，S，f，S，Z)，若f(S，)=PZ，则称符号串S*可被该DFA接受(识别)。 例:试证串abbc可被图示DFA识别。 证：f(S，abbc)=f(f(S，a)，bbc)=f(f(A，b)，bc) =f(f(A，b)，c)=f(A，c)=B由于B为终态，得证。 6、语言 确定有穷自动机M所接受的所有符号串集称为此自动机可接受的语言L(M)。 7、重要结论 (1)S上的一个字符串集VS*是正规集，当且仅当存在着一个S上的确定有穷自动机M，使得V=L(M)。 (2) DFA的确定性表现在状态转换函数是单值函数，即f(k，a)唯一确定一个后继状态。二、不确定的有穷自动机(NFA) 1、定义 不确定的有穷自动机表示为一个五元组：NFA M=(K，S，f，S，Z)，其中：(1) K是一有穷状态集(1)S是一有穷字母表，称输入符号字母表(3) f是转换函数，是在KS*K的子集上的映射。(4)S是初态集(5) ZK，是一终态集，终态也称结束态或可接受态。 例：状态图表示的NFA如下：状态图表示的DFA如下： 4、转换函数定义扩充 因为f是转换函数，是在KS*K的子集上的映射，有： (1) f(k，a)=f(k1，)f(k2，).f(kn，)其中，kiK，aS ，S*，且f(k，a)=k1，k2，.kn 5、接受(识别)设NFA=(K，S，f，S，Z)，如果z0f(S，)且z0Z，则称符号串S*可被该NFA接受(识别)。 例:试证串abc可被图示NFA识别。 证：f(S，abc)=f(A，bc)=f(A，c)f(C，c)=B，又因为B 终态集B，得证。 6、语言 不确定有穷自动机M所接受的所有符号串集称为此自动机可接受的语言L(M)。 7、重要结论 (1）对于每个NFA M，必存在一个DFA M1，使得L(M)=L(M1)； (2)对于任何两个有穷自动机M1和M2，若L(M1)=L(M2)，则称有穷自动机M1和M2等价。 三、FA到DFA的转换 1、相关概念 闭包：-closure(I)表示状态集I中任何状态A经任意条弧而能到达的状态集。 状态集I的a弧转换：表示为J=move(I，a)，J是所有那些从I中任一状态经一条a弧而到达的后继状态全体。 令:Ia=-closure(J)=-closure(move(I，a) 例：对下图NFA，取I=S，1，则-closure(I)S，1，2，J=move(I，0)=1，I0=-closure(J)=1，2 2、NFA的确定化 用造表法将NFA确定化过程如下： (0)表的第0行和第0列作标识行列的值。 (1)将-closure(I)作为表中第1行第1列。 (1)假定S=a1，a2，.an，设第i行第一列已确定状态集为I，则置该行第i列为Iai，如Iai未曾在任何行第一列出现过，则将Iai加入下一空行i+1的第一列，并在第0列标记为Ti+1。 (3)反复重复第(1)步，直至无新状态出现为止。 (4)重新命名新状态。 例：将上图所示NFA确定化(0-3步：造表)整理后得： 重新命名新状态得DFA如下图所示： 四、DFA的化简 1、相关概念 (1)一个DFA是化简(最小化)了的，即它没有多余状态且其状态中没有相互等价的。 (2)多余状态是指从自动机的开始状态出发，任何输入串也不可达的状态。 2、状态等价 在DFA中，两个状态s和t等价的条件是： (1)一致性条件：状态s和t必须同时为可接受态和不可接受态。 (2)蔓延性条件：对于所有输入符号，状态s和t必须转换到等价的状态里。 3、DFA最小化处理 对DFA最小化的本质：消除多余状态、合并等价状态。 DFA最小化具体过程：用分割法将不含多余状态的DFA分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。分割时，首先将DFA状态分成终态子集和非终态子集，再根据输出弧所达到状态的性质逐步细分。 例：对左图所示DFA最小化。 解：P0=1，2，3，4，5，6，7 根据各子集输出弧0和1所达到状态是否为终态，划分为：P1=1， 2， 3，4，5，6，7，最小化后DFA如上右图所示。授课顺序：6教学目的：让学生掌握正规文法、正规式和有穷自动机的等价转换方法，了解词法分析程序自动构造工具LEX的工作原理及基本使用方法。教学重点：正规文法、正规式和有穷自动机的等价转换教学难点：正规文法、正规式和有穷自动机的等价转换授课学时