编译原理第三章资料课件

编译原理编译原理第三章第三章词法分析词法分析王金伟计算机与信息工程学院天津师范大学TJNU-COCIE-WJW22024/7/21第三章第三章词法分析词法分析n3.1对于词法分析器的要求对于词法分析器的要求n3.2词法分析器的设计词法分析器的设计n3.3正规表达式与有限自动机正规表达式与有限自动机n3.4词法分析器的自动产生（词法分析器的自动产生（LEX）TJNU-COCIE-WJW32024/7/21n词法分析的任务词法分析的任务从左至右逐个字符的对源程序进行扫描，产生从左至右逐个字符的对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改一个个的单词符号，把作为字符串的源程序改造成为由单词符号串组成的程序造成为由单词符号串组成的程序n词法分析器：词法分析器：执行词法分析的程序执行词法分析的程序输入：源程序输入：源程序输出：单词符号输出：单词符号n词法分析器的构造方法词法分析器的构造方法手工方法手工方法：根据词法直接编程序：根据词法直接编程序(有限自动机有限自动机)自动方法自动方法：利用一些工具：利用一些工具LexTJNU-COCIE-WJW42024/7/213.1对词法分析器的要求对词法分析器的要求源程序源程序词法分析器词法分析器单词符号单词符号1.单词符号概念单词符号概念指语言中具有独立意义的最小的语法符号指语言中具有独立意义的最小的语法符号例例例例：C=A*3.14+5单词：单词：C，A变量变量3.14,5常数常数=，*，+算符算符一、一、词法分析器的功能和输出形式词法分析器的功能和输出形式TJNU-COCIE-WJW52024/7/212.单词的种类单词的种类（1）基本字（保留字，关键字）基本字（保留字，关键字）由程序语言定义的具有固定意义的标识符。由程序语言定义的具有固定意义的标识符。用户不能用来表示变量名，函数名等标识符用户不能用来表示变量名，函数名等标识符例例例例：C语言中的语言中的“if”“else”“while”（2）标识符标识符用户使用的，用来表示各种名字，变量名，函数用户使用的，用来表示各种名字，变量名，函数名等名等TJNU-COCIE-WJW62024/7/212.单词的种类（续）单词的种类（续）（3）常数常数整型、实型、逻辑、字符整型、实型、逻辑、字符例：例：1000，3.14，TRUE，“Abcd”（4）运算符运算符+、-、*、/（5）界符界符，；（）（）TJNU-COCIE-WJW72024/7/21词法分析器输出的单词符号常常用词法分析器输出的单词符号常常用二元式二元式来表示：来表示：二、二、单词的表示形式单词的表示形式TJNU-COCIE-WJW82024/7/211.单词种别单词种别通常用通常用整数编码整数编码来表示来表示（1）关键字，运算符，界符关键字，运算符，界符n一字一种编码（处理起来比较方便）一字一种编码（处理起来比较方便）n n例例例例：if，else，(，+，（2）常数常数n按类型分别给出编码按类型分别给出编码例例例例：整型，实型，布尔型，：整型，实型，布尔型，（3）标识符标识符n统归一种，只给一个编码统归一种，只给一个编码n n例例例例：变量名，函数名等都是一种编码：变量名，函数名等都是一种编码TJNU-COCIE-WJW92024/7/211.单词种别（续）单词种别（续）注意注意注意注意：(1)若一个种别只包含一个单词符号（一种一字），若一个种别只包含一个单词符号（一种一字），对于该单词符号，种别编码就可以代表它自身了。对于该单词符号，种别编码就可以代表它自身了。例如例如例如例如：关键字，运算符，界符：关键字，运算符，界符(2)若一个种别包含有多个单词符号（一种多字），若一个种别包含有多个单词符号（一种多字），对于该种别的每个单词符号，除了给出种别编码，对于该种别的每个单词符号，除了给出种别编码，还需给出单词符号的属性值还需给出单词符号的属性值例如例如例如例如：整型常数，实型常数，布尔常数，标识符：整型常数，实型常数，布尔常数，标识符TJNU-COCIE-WJW102024/7/212.单词符号的属性信息单词符号的属性信息单词符号的属性单词符号的属性：指单词符号的特性或特征：指单词符号的特性或特征单词符号的属性值单词符号的属性值：反映单词特性或特征的值：反映单词特性或特征的值TJNU-COCIE-WJW112024/7/212.单词符号的属性信息（续）单词符号的属性信息（续）属性值的表示方法属性值的表示方法：（1）基本字，运算符，界符（一字一种）基本字，运算符，界符（一字一种）n只给其种别编码，不给出它的属性值只给其种别编码，不给出它的属性值n n例例例例：基本字：基本字while表示成：表示成：（2）常数常数n表示成标准的二进制形式表示成标准的二进制形式n n例例例例：1024表示成：表示成：（3）标识符标识符n用字符串编码或对应的符号表项地址用字符串编码或对应的符号表项地址n n例例例例：name表示成：表示成：或或TJNU-COCIE-WJW122024/7/21例例例例1 1：FORTRAN编译程序的词法分析器，在扫描输编译程序的词法分析器，在扫描输入串：入串：IF（5.EQ.M）GOTO100输出的单词如下：输出的单词如下：单词符号单词符号nIFn左括号左括号n整常数整常数n等号等号n标识符标识符n右括号右括号nGOTOn标号标号三、三、例子例子TJNU-COCIE-WJW132024/7/21例例例例2 2：考虑下面：考虑下面C+的一段代码：的一段代码：while(i=j)i-;经词法分析器处理后，将被转换成如下单词符号序列：经词法分析器处理后，将被转换成如下单词符号序列：单词符号单词符号nwhilen(nin=，-njn)nin-n；TJNU-COCIE-WJW142024/7/213.2词法分析器的设计词法分析器的设计源程序源程序预处理预处理子程序子程序输入输入缓冲区缓冲区扫描器扫描器扫描缓冲区扫描缓冲区输入输入列表列表单词符号单词符号一、一、词法分析器的结构词法分析器的结构TJNU-COCIE-WJW152024/7/211.输入缓冲区、预处理子程序输入缓冲区、预处理子程序（1）输入源程序文本，放入输入缓冲区中，词）输入源程序文本，放入输入缓冲区中，词法分析工作可在这个输入缓冲区中工作法分析工作可在这个输入缓冲区中工作（2）剔除无用的空白，跳格）剔除无用的空白，跳格(TAB)，回车，换行，回车，换行等编辑性字符；若空白符号为单词符号的界符，等编辑性字符；若空白符号为单词符号的界符，就将若干空白和并为就将若干空白和并为1个个（3）剔除注释行，比如）剔除注释行，比如/*/（4）如果是）如果是FORTRAN语言，区分标号区、续语言，区分标号区、续行区和给出句末符行区和给出句末符（5）源程序的出错列表打印）源程序的出错列表打印（6）将预处理好的子程序放到扫描缓冲区中）将预处理好的子程序放到扫描缓冲区中TJNU-COCIE-WJW162024/7/212.扫描缓冲区、扫描器扫描缓冲区、扫描器（1）扫描缓冲区）扫描缓冲区n设两个半区，可互补使用设两个半区，可互补使用n设两个指针设两个指针起点指针：指出正在识别单词起点位置起点指针：指出正在识别单词起点位置搜索指针：向前搜索以寻找单词终点搜索指针：向前搜索以寻找单词终点（2）扫描器：扫描缓冲区，直接进行单词的识别）扫描器：扫描缓冲区，直接进行单词的识别前半区前半区后半区后半区起点指针起点指针搜索指针搜索指针TJNU-COCIE-WJW172024/7/21源程序源程序预处理预处理子程序子程序输入输入缓冲区缓冲区扫描器扫描器扫描缓冲区扫描缓冲区输入输入列表列表单词符号单词符号二、二、词法分析器的工作过程词法分析器的工作过程TJNU-COCIE-WJW182024/7/211.超前搜索超前搜索(1)关键字的识别关键字的识别前提：允许用户使用基本字（关键字）前提：允许用户使用基本字（关键字）例例例例：试分析下面：试分析下面FORTRAN的几个语句的几个语句（1）DO99K=1，10（2）IF(S.EQ.M)GOTO55（3）DO99K=1.10（4）IF(S)=55超前扫描很多字符，直到扫描到可以肯定词性的超前扫描很多字符，直到扫描到可以肯定词性的地方为止地方为止PROGRAMSUMS=0DO99I=1,100S=S+I99CONTINUEEND三、三、单词符号的识别单词符号的识别TJNU-COCIE-WJW192024/7/211.超前搜索法（续超前搜索法（续1）(2)标识符的识别标识符的识别一般是以一般是以字母字母开头后跟开头后跟数字数字/字母字母的字符串，后边的字符串，后边一般都有算符和界符，比较好识别一般都有算符和界符，比较好识别(3)常数的识别常数的识别例例例例：对于：对于FORTRAN5.EQ.M（5=M）5.E08（5*108)直到超前扫描到字母直到超前扫描到字母Q时才能确定时才能确定5的词性的词性3HABC（“ABC”）3H是词头，代表长度为是词头，代表长度为3的字符串常数的字符串常数TJNU-COCIE-WJW202024/7/211.超前搜索法（续超前搜索法（续2）(4)算符和界符的识别算符和界符的识别应将那些由多个字符复合成的算符和界符拼成一个应将那些由多个字符复合成的算符和界符拼成一个单词符号单词符号例例例例：+-=TJNU-COCIE-WJW212024/7/212.直接分析法直接分析法（1）基本思想基本思想根据读来的第一个字符的种类分别转到各种根据读来的第一个字符的种类分别转到各种子程序处理。这些子程序功能就是识别以相子程序处理。这些子程序功能就是识别以相应字符开头的各种单词。应字符开头的各种单词。（2）方法方法以以FORTRAN语言为例，分成几种情况语言为例，分成几种情况以字母开头的以字母开头的基本字、标识符、格式说明符，基本字、标识符、格式说明符，nIFnWHILETJNU-COCIE-WJW222024/7/212.直接分析法（续直接分析法（续1）以小数点开头的以小数点开头的n.34.EQ.TRUE.FALSE.等等以数字开头的以数字开头的n常数、格式语句、重复说明常数、格式语句、重复说明nWRITE(6,10)X,Y10FORMAT(2X,F10.4,F9.3)以以*开头的开头的：*除此之外除此之外：都是一个基本字符表示一个单词：都是一个基本字符表示一个单词TJNU-COCIE-WJW232024/7/21子子程程序序1子子程程序序2子子程程序序3子子程程序序4子子程程序序5下一个语句下一个语句字符是否读来字符是否读来该字符是什么该字符是什么读读一一个个符符号号字母字母数字数字*其他其他出口出口否否是是2.直接分析法（续直接分析法（续2）分析流程图分析流程图TJNU-COCIE-WJW242024/7/213.状态转换图法状态转换图法(1)状态转换图状态转换图：一张有限方向图：一张有限方向图(2)状态转换图的功能状态转换图的功能识别（接受）一定的符号串（单词）识别（接受）一定的符号串（单词）TJNU-COCIE-WJW252024/7/213.状态转换图法（续状态转换图法（续1）(3)状态转换图的结构状态转换图的结构结点结点：代表状态，用圆圈表示：代表状态，用圆圈表示箭弧箭弧：状态之间用箭弧连接：状态之间用箭弧连接箭弧上的标记箭弧上的标记：代表在射出节点下可能出现的：代表在射出节点下可能出现的字符或字符串字符或字符串例例例例：注意注意注意注意：一个完整的状态转换图有：一个完整的状态转换图有n个状态，其中有个状态，其中有一个初态，至少要有一个终态一个初态，至少要有一个终态(用双圆圈表示用双圆圈表示)TJNU-COCIE-WJW262024/7/213.状态转换图法（续状态转换图法（续2）(4)举例举例例例例例1 1：构造一个识别标识符的状态转换图：构造一个识别标识符的状态转换图解：解：其中其中“*”表示在该状态下多读进一个字符表示在该状态下多读进一个字符识别：识别：name1TJNU-COCIE-WJW272024/7/213.状态转换图法（续状态转换图法（续3）例例例例2 2：构造一个识别整数的状态转换图，说说识：构造一个识别整数的状态转换图，说说识别别256过程过程解：解：TJNU-COCIE-WJW282024/7/213.状态转换图法（续状态转换图法（续4）例例例例3 3：识别识别FORTRAN实型常数的状态转换图实型常数的状态转换图解：解：实数：小数形式：实数：小数形式：3.413.4 34.指数形式：指数形式：3E+05即即3X105TJNU-COCIE-WJW292024/7/21四、四、综合例子综合例子用状态转换图法，构造一个识别某一个简单语用状态转换图法，构造一个识别某一个简单语言（言（SL）的所有单词符号的词法分析器）的所有单词符号的词法分析器TJNU-COCIE-WJW302024/7/21单词符号单词符号种别编码种别编码助记符号助记符号内码值内码值DIMIFDOSTOPEND标识符标识符常数（整型）常数（整型）=+*,（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-内部字符串内部字符串标准二进制标准二进制-1、SL的单词符号及其内部表示（的单词符号及其内部表示（P42)TJNU-COCIE-WJW312024/7/212.为了讨论方便，对为了讨论方便，对SL加三点限制加三点限制（1）所有基本字都规定为保留字（用户不能）所有基本字都规定为保留字（用户不能用它们来定义标识符的，避免超前搜索用它们来定义标识符的，避免超前搜索）（2）对基本字只构造一个基本字表，不构造）对基本字只构造一个基本字表，不构造其状态转换图（只要识别出是一个标识符，其状态转换图（只要识别出是一个标识符，就去查基本字表看看是否是基本字）就去查基本字表看看是否是基本字）（3）对基本字，标识符和常数之间要留有间）对基本字，标识符和常数之间要留有间隔符（避免超前搜索）隔符（避免超前搜索）TJNU-COCIE-WJW322024/7/213.构造能够识别构造能够识别SL单词单词的状态转换图的状态转换图(P43)TJNU-COCIE-WJW332024/7/214.状态转换图的程序实现状态转换图的程序实现思路思路：为每个状态结点都编写一个子程序：为每个状态结点都编写一个子程序首先，设以下一些变量或过程首先，设以下一些变量或过程ch:字符变量字符变量,存放最新读进的源程序字符存放最新读进的源程序字符strToken:字符数组字符数组,存放构成单词符号的字符串存放构成单词符号的字符串GetChar:子程序过程子程序过程,将下一输入字符读到将下一输入字符读到ch中中,搜索指搜索指示器前移一字符位置示器前移一字符位置GetBC:子程序过程子程序过程,检查检查ch中的字符是否为空白中的字符是否为空白,若是若是,则调用则调用GetChar直至直至ch中进入一个非空白字符中进入一个非空白字符Concat:子程序过程子程序过程,将将ch中的字符连接到中的字符连接到strToken之之后后.例如例如,假定假定strToken原来的值为原来的值为“AB”,而而ch中存放中存放着着C,经调用经调用Concat后后,strToken的值就变为的值就变为“ABC”TJNU-COCIE-WJW342024/7/21IsLetter和和IsDigit:布尔函数过程布尔函数过程,他们分别判断他们分别判断ch中的字符是否为字母和数字中的字符是否为字母和数字Reserve:整型函数过程整型函数过程,对对strToken中的字符串查中的字符串查找保留字表找保留字表,若它是一个保留字则返回它的编码，若它是一个保留字则返回它的编码，否则返回否则返回0值（假定值（假定0不是保留字的编码）不是保留字的编码）Retract:子程序过程子程序过程,将搜索指示器回调一个字位将搜索指示器回调一个字位置，将置，将ch置为空白字符置为空白字符InsertId:整型函数过程整型函数过程,将将strToken中的标识符插中的标识符插入符号表入符号表,返回符号表指针。返回符号表指针。InsertConst:整型函数过程整型函数过程,将将strToken中的常数中的常数插入到常数符号表插入到常数符号表,放回常数表针放回常数表针TJNU-COCIE-WJW352024/7/21然后，对每个状态编写一个对应的程序然后，对每个状态编写一个对应的程序(1)对于不含回路的状态结点，采用分叉法对于不含回路的状态结点，采用分叉法例例例例：GetChar();If(IsLetter()状态状态j对应的程序段对应的程序段Elseif(IsDigit()状态状态k对应的程序段对应的程序段Elseif(ch=/)状态状态l对应的程序段对应的程序段Else错误处理错误处理TJNU-COCIE-WJW362024/7/21(2)对于含有回路的状态结点，对应一个对于含有回路的状态结点，对应一个while语句语句例例例例：(3)对于终态结点，用对于终态结点，用return(code,value)其中，其中，code是单词的种别编码，是单词的种别编码，value是单词符是单词符号的属性值，或无定义。号的属性值，或无定义。GetChar();while(IsLetter()orIsDigit()GetChar();状态状态j对应的程序段对应的程序段TJNU-COCIE-WJW372024/7/215.状态转换图对应的词法分析程序伪代码状态转换图对应的词法分析程序伪代码（P45-46）TJNU-COCIE-WJW382024/7/21第第1次上机作业次上机作业根据根据编译原理编译原理P45-46页的词法分析程序伪代页的词法分析程序伪代码，用码，用C语言实现，要求语言实现，要求：输入输入：由：由P43页表页表3.1中的单词，按词法规则组成中的单词，按词法规则组成的语句序列（或用文件存储，相当于源程序）的语句序列（或用文件存储，相当于源程序）例如：例如：IFi0i=1输出输出：打印单词的种别（用表：打印单词的种别（用表3.1中的助记符）中的助记符）和单词的属性值（表和单词的属性值（表3.1中的内码值）中的内码值）每行一词，格式每行一词，格式单词单词1：单词单词2：例如：例如：IF:TJNU-COCIE-WJW392024/7/213.3正规表达式与有限自动机正规表达式与有限自动机为了更好地使用状态图构造词法分析程序，为了为了更好地使用状态图构造词法分析程序，为了讨论词法分析程序的自动生成，需要将状态转换讨论词法分析程序的自动生成，需要将状态转换图的概念形式化图的概念形式化词法分析器的构造的基本思路：词法分析器的构造的基本思路：程序语言的描述程序语言的描述词法规则词法规则正规表达式正规表达式有限自动机有限自动机词法分析程序词法分析程序TJNU-COCIE-WJW402024/7/211.字母表字母表（基本字符集）（基本字符集）一个非空的由有限元素组成的集合，每个元素称一个非空的由有限元素组成的集合，每个元素称为一个符号，为一个符号，一般用一般用表示表示例例例例：=a,b,c=a,b,c 元素：元素：a a，b b，c c 注注注注:不同语言有不同的字母表不同语言有不同的字母表例例例例：C C语言的字母表中包含：字母语言的字母表中包含：字母AZ,azAZ,az，数字，数字0909，标点，标点,.+-*/,.+-*/等等一、一、基本概念基本概念TJNU-COCIE-WJW412024/7/212.字母表字母表上的一个上的一个符号串（字）符号串（字）由字母表由字母表中的符号所构成的一个有穷序列，一般中的符号所构成的一个有穷序列，一般用小写字母用小写字母x,y表示表示例例例例：aa，ab，abc，注注注注：(1)符号的顺序不同代表不同的符号串符号的顺序不同代表不同的符号串例如例如abba(2)不包含任何字符的序列称为空字，用不包含任何字符的序列称为空字，用来表示来表示TJNU-COCIE-WJW422024/7/213.字字(符号串符号串)的连接的连接设设x和和y是两个字是两个字(符号串符号串)，则定义，则定义xy为他们的连接为他们的连接例例例例：ab和和ba连接是连接是abba注注注注:(1)是连结运算的恒等元素是连结运算的恒等元素x=x=x(2)字字(符号串符号串)的的n次连接次连接xn=xxxxn个个规定规定x0=x1=x，x2=xx，x3=xxx例例例例：x=ab，则，则x0=，x1=ab，x2=abab，x3=abababTJNU-COCIE-WJW432024/7/214.集合的集合的(连接连接)积积设设U和和V是两个是两个“字字(符号串符号串)的集合的集合”，则定义则定义UV为他们的为他们的(连接连接)积积UV=xy|x U且且y V例例例例：设：设U=a,ab,V=b,ba,则则UV=ab,aba,abb,abba注注注注：(1)集合的集合的(连接连接)积不满足交换率积不满足交换率UVVU(2)集合的集合的(连接连接)积满足结合率积满足结合率(UV)W=U(VW)TJNU-COCIE-WJW442024/7/215.集合集合V的的n次次(连接连接)积记为：积记为：Vn=VVVVn个个规定规定V0=例例例例：设：设V=a,b，那么，那么V0=V1=a,bV2=VV=aa,ab,ba,bbV3=VVV=V2V=aaa,aba,baa,bba,aab,abb,bab,bbbV4=VVVV=V3V=TJNU-COCIE-WJW452024/7/216.闭包闭包设设V是一个字（符号串）的集合，是一个字（符号串）的集合，则则V的闭包定义为的闭包定义为V*，V*=V0V1V2注注注注：闭包闭包V*中的每个字都是由中的每个字都是由V中的字经过中的字经过有限次连接而成的有限次连接而成的7.正则闭包正则闭包V+的定义为的定义为V+=VV*TJNU-COCIE-WJW462024/7/218.*定义（定义（的闭包）的闭包）用用*来表示来表示上所有字的全体，空字上所有字的全体，空字也包括在其中也包括在其中*=012例例例例：设：设=a，b，求，求*=,a,b,aa,ab,ba,bb,aaa,注注注注:(1)用用来表示不含任何元素的集合，称为空集，即来表示不含任何元素的集合，称为空集，即(2)，之间的区别之间的区别：空字；：空字；：空集；：空集；：仅含有空字的集合：仅含有空字的集合TJNU-COCIE-WJW472024/7/21词法分析器需要识别语言中具有不同特征的字词法分析器需要识别语言中具有不同特征的字例如：例如：例如：例如：识别识别“标识符标识符”、识别、识别“数数”，等等。，等等。我们可以把具有相同特征的字放在一起组成一个集我们可以把具有相同特征的字放在一起组成一个集合，即所谓的合，即所谓的正规集正规集然后使用一种形式化的方法来表示正规集，即所谓然后使用一种形式化的方法来表示正规集，即所谓的的正规式正规式 注意注意注意注意：正规式是描述单词结构的一种形式；正规式是描述单词结构的一种形式；正规集是该类单词的全集。正规集是该类单词的全集。二、二、正规式与正规集正规式与正规集TJNU-COCIE-WJW482024/7/211.正规式正规式与与正规集正规集的定义（递归的定义方法）的定义（递归的定义方法）(1)和和是是上的正规式上的正规式,它们所表示的正规集分别为它们所表示的正规集分别为和和(2)任何任何a,是是上的一个正规式上的一个正规式,他所表示的正规集为他所表示的正规集为a(3)假定假定U和和V都是都是上的正规式，他们所表示的正规集分别记为上的正规式，他们所表示的正规集分别记为L(U)和和L(V)，那么，那么(a)(U|V)是正规式，所表示的正规集为是正规式，所表示的正规集为L(U)L(V)(b)(UV)是正规式，所表示的正规集为是正规式，所表示的正规集为L(U)L(V)（连接积）（连接积）(c)(U)*是正规式，所表示的正规集为是正规式，所表示的正规集为(L(U)*（闭包）（闭包）仅由有限次使用仅由有限次使用(1)(2)(3)所得到的表达式才是所得到的表达式才是上的正规式，上的正规式，仅由这些正规式所表示的字集才是仅由这些正规式所表示的字集才是上的正规集。上的正规集。注注注注：|(或或)、(连接连接)、*(闭包闭包,任意有限次的自重复连接任意有限次的自重复连接)运算的优先级为：运算的优先级为：“*”“”“|”TJNU-COCIE-WJW492024/7/212.举例举例例例例例1 1.令令=a,b正规式正规式正规集正规集aba|bab(a|b)(a|b)a*(a|b)*ba*a(a|b)*(a|b)*(aa|bb)(a|b)*aba,babaa,ab,ba,bb,a,aa,任意个任意个a的串的串,a,b,aa,ab,所有所有a,b组成的串组成的串b,ba,baa,baaa,上以上以a为首的字的全体为首的字的全体上含有上含有aa或或bb的字的全体的字的全体TJNU-COCIE-WJW502024/7/21例例例例2 2.令令=A，B,0,1正规式正规式正规集正规集AB01A|B0|1(A|B|0|1)(A|B|0|1)*(A|B)(A|B|0|1)*(0|1)(0|1)*AB01A,B0,1A,B,0,1上字的全体，包含空字上字的全体，包含空字上上“标识符标识符”的全体的全体上上“数数”的全体的全体(不包含空字不包含空字)TJNU-COCIE-WJW512024/7/213.两个正规式的等价两个正规式的等价若两个正规式若两个正规式U和和V所表示的正规集相同，则认为二所表示的正规集相同，则认为二者等价，记为：者等价，记为：U=V例例例例：证明：证明b(ab)*=(ba)*b证明：因为，证明：因为，L(b(ab)*)=L(b)L(ab)*)=b,ab,abab,=b,bab,babab,又因为，又因为，L(ba)*b)=L(ba)*)L(b)=,ba,baba,b=b,bab,babab,因此，因此，L(b(ab)*)=L(ba)*b)所以，所以，b(ab)*=(ba)*b(证毕）证毕）TJNU-COCIE-WJW522024/7/214.正规式的性质正规式的性质设设U，V，W是上的是上的正规式，则正规式，则(1)U|V=V|U或的交换律或的交换律(2)U|(V|W)=(U|V)|W或的结合律或的结合律(3)U(VW)=(UV)W连接积的结合律连接积的结合律(4)U(V|W)=(UV)|(UW)分配律分配律(V|W)U=VU|WU(5)U=U=UTJNU-COCIE-WJW532024/7/21(1)U|V=V|U或的交换律或的交换律证明：因明：因为，L(U|V)=L(U)L(V)又因为，又因为，L(V|U)=L(V)L(U)=L(U)L(V)因为，因为，L(U|V)=L(V|U)所以，所以，U|V=V|UTJNU-COCIE-WJW542024/7/21(2)U|(V|W)=(U|V)|W或的结合律或的结合律证明：证明：因因为，L(U|(V|W)=L(U)L(V|W)=L(U)L(V)L(W)又因为，又因为，L(U|V)|W)=L(U|V)L(W)=L(U)L(V)L(W)因此，因此，L(U|(V|W)=L(U|V)|W)所以，所以，U|(V|W)=(U|V)|W(3)(4)(5)留给同学们课下证明留给同学们课下证明TJNU-COCIE-WJW552024/7/21下面，我们把状态转换图再形式化一下下面，我们把状态转换图再形式化一下及所谓的及所谓的有限自动机有限自动机有两种：有两种：l确定的有限自动机（确定的有限自动机（DFA）（DeterministicFiniteAutomata)l非确定的有限自动机（非确定的有限自动机（NFA）（Non-deterministicFiniteAutomata)TJNU-COCIE-WJW562024/7/211.定义定义：一个确定有限自动机（：一个确定有限自动机（DFA）M是一个五元式：是一个五元式：M=(S,f,s0,F)，其中，其中1)S是一个有限的状态集合，它的每个元素我们称为是一个有限的状态集合，它的每个元素我们称为一个状态一个状态2)是一个有穷的输入符号的字母表，它的每个元素是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符我们称为一个输入字符3)f是从是从SS的单值部分映射的单值部分映射4)s0是是S的一个元素，为初始状态，它是唯一的的一个元素，为初始状态，它是唯一的5)状态集合状态集合F是终止状态的集合，它是是终止状态的集合，它是S的子集的子集(可空可空)三、三、确定的有限自动机（确定的有限自动机（DFA）（DeterministicFiniteAutomata)TJNU-COCIE-WJW572024/7/21注意注意注意注意：1)所谓的自动机不是指一台实际的机器，而是一所谓的自动机不是指一台实际的机器，而是一种数学模型（集合，函数，序列种数学模型（集合，函数，序列），利用它），利用它模拟计算机识别的功能模拟计算机识别的功能2)所谓确定性是指，所谓确定性是指，f(s,a)=s是单值函数。是单值函数。对对任何状态任何状态s S，和输入符号，和输入符号a，f(s,a)唯一唯一的确定下一个状态的确定下一个状态3)所谓有限性是指，所谓有限性是指，S是一个有限的状态集合，并是一个有限的状态集合，并且且是一个有限的输入符号的字母表是一个有限的输入符号的字母表4)用上述用上述5条，来定义一个条，来定义一个DFA，来完成识别一个，来完成识别一个序列是否被机器所接受序列是否被机器所接受TJNU-COCIE-WJW582024/7/21例例例例：设一个奇偶校验器，其功能是，用来识别由：设一个奇偶校验器，其功能是，用来识别由1和和0组成组成的序列是否含有奇数个的序列是否含有奇数个1。解：设解：设DFAM=(S,f,s0,F)来表示奇偶校验器，其中来表示奇偶校验器，其中1)S：EVEN，ODD2)：0，13)f:f(EVEN,0)=EVENf(EVEN,1)=ODDf(ODD,0)=ODDf(ODD,1)=EVEN4)s0:EVEN5)F:ODD注意注意注意注意：如果一个序列使自动机从开始状态出发，最后达：如果一个序列使自动机从开始状态出发，最后达到一个终态，那么该输入序列就被该自动解接受到一个终态，那么该输入序列就被该自动解接受（识别，读出），否则将被拒绝。（识别，读出），否则将被拒绝。TJNU-COCIE-WJW592024/7/21例例例例：1101110EVENODDEVENEVENODDEVENODDODDf:f(EVEN,0)=EVENf(EVEN,1)=ODDf(ODD,0)=ODDf(ODD,1)=EVEN1101110TJNU-COCIE-WJW602024/7/212.DFAM的表示方法的表示方法(1)状态转换矩阵表示法状态转换矩阵表示法(用一个用一个“表表”来表示来表示)设矩阵的行表示状态，列表示输入字符，矩阵元素是设矩阵的行表示状态，列表示输入字符，矩阵元素是f（s，a）的值）的值例例例例：设：设DFAM=(0,1,2,3,a,b,f,0,3)，其中，其中f:f(0,a)=1,f(0,b)=2f(1,a)=3,f(1,b)=2f(2,a)=1,f(2,b)=3f(3,a)=3,f(3,b)=3输入字符输入字符状态状态ab012313132233TJNU-COCIE-WJW612024/7/21(2)用状态转换图来表示用状态转换图来表示例例例例：设：设DFAM=(0,1,2,3,a,b,f,0,3)，其中，其中f:f(0,a)=1,f(0,b)=2f(1,a)=3,f(1,b)=2f(2,a)=1,f(2,b)=3f(3,a)=3,f(3,b)=3TJNU-COCIE-WJW622024/7/213.DFAM的识别功能的识别功能对于对于*中任何字中任何字，如果存在一条从初态结点到，如果存在一条从初态结点到某个终态结点的道路，这条路上所有的标识符某个终态结点的道路，这条路上所有的标识符连成的字等于连成的字等于，则，则可被可被DFAM所识别所识别(接受，接受，读出读出)例例例例：*=aa,bb,ab,baa,aba,bbb,bba,TJNU-COCIE-WJW632024/7/21注意注意注意注意：(1)若若M的初态结点同时又是终态节点，则空字可的初态结点同时又是终态节点，则空字可被被M识别识别(2)DFAM所能识别的字的全体记为所能识别的字的全体记为L(M)(3)如果一个如果一个DFAM的输入字母表为的输入字母表为，则我们称，则我们称M是是上的一个上的一个DFA(4)若若V是是上的一个正规集，当且仅当存在一个上的一个正规集，当且仅当存在一个上的上的DFAM，使得，使得V=L(M)TJNU-COCIE-WJW642024/7/211.定义定义:一个非确定有限自动机（一个非确定有限自动机（NFA）M是一个五元式是一个五元式M=(S,f,S0,F)，其中，其中1)S是一个有限的状态集合，它的每个元素我们是一个有限的状态集合，它的每个元素我们称为一个状态称为一个状态2)是一个有限的输入符号的字母表，它的每个是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符元素我们称为一个输入字符3)f是从是从S*2S 的部分映射，其中，的部分映射，其中，2S表示表示S的的幂集合（所有幂集合（所有S的子集组成的集合）的子集组成的集合）（f是非单值的是非单值的M是非确定）是非确定）4)状态集合状态集合S0是初始状态集合，它是是初始状态集合，它是S的子集的子集5)状态集合状态集合F是终止状态的集合，它是是终止状态的集合，它是S的子集的子集四、四、非确定的有限自动机非确定的有限自动机(NFA)（Non-deterministicFiniteAutomata)TJNU-COCIE-WJW652024/7/212.NFAM表示方法表示方法(1)用状态矩阵表示用状态矩阵表示例例例例：设：设NFAM=(0,1,2,a,b,f,0,1,2)，其中，其中f:f(0,aa)=1,f(0,bb)=2f(0,a)=0,f(0,b)=0f(1,a)=1,f(1,b)=1f(2,a)=2,f(2,b)=2字字状态状态aabbab0121-2-012012TJNU-COCIE-WJW662024/7/21(2)用状态转换图表示用状态转换图表示例例例例：设：设NFAM=(0,1,2,a,b,f,0,1,2)，其中，其中f:f(0,aa)=1,f(0,bb)=2f(0,a)=0,f(0,b)=0f(1,a)=1,f(1,b)=1f(2,a)=2,f(2,b)=2TJNU-COCIE-WJW672024/7/213.NFAM识别条件识别条件对于对于*中的任何字中的任何字若存在一条从某一个初态若存在一条从某一个初态到某一个终态的通路且这条路上所有弧的标记到某一个终态的通路且这条路上所有弧的标记字连接成的字等于字连接成的字等于，则，则可被可被NFAM识别识别(读出，接受读出，接受)4.有限自动机的等价有限自动机的等价对任何两个有限的自动机对任何两个有限的自动机M1和和M2，若有，若有L(M1)=L(M2)，则称，则称M1与与M2等价。等价。TJNU-COCIE-WJW682024/7/21注注注注:(1)若若M的某些结点既是初态结点又是终态结的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点，或者存在一条从某初态结点到某个终态结点的点的通路，那么空字通路，那么空字可为可为M所识别所识别(2)DFA是是NFA的一个特例，对于每个的一个特例，对于每个NFAM存存在一个在一个DFAM使得使得L(M)=L(M)，也就是说，也就是说M和和M是等价的是等价的TJNU-COCIE-WJW692024/7/21定理定理1：对于任何：对于任何上上NFAM都可构造一个都可构造一个上的正上的正规式规式V，使得，使得L(V)=L(M)其中，其中，L(M)是是上上NFAM所能识别的字的全体，所能识别的字的全体，L(V)是是上的正规集上的正规集五、五、正规式与有限自动机的等价性正规式与有限自动机的等价性TJNU-COCIE-WJW702024/7/21问题问题：如何由一个：如何由一个NFAM，构造一个正规式，构造一个正规式V方法：方法：(1)在在M转换图上加进转换图上加进X结点和结点和Y结点，从结点，从X结点用结点用弧弧连接连接M的所有初态结点，的所有初态结点，M的所有终态结的所有终态结点用弧点用弧连接到连接到Y，得到一个，得到一个NFAM，且，且L(M)=L(M)(2)使用替换规则逐步消去使用替换规则逐步消去M的所有结点，直到只的所有结点，直到只剩下剩下X结点和结点和Y结点，在消去过程中，逐步使用结点，在消去过程中，逐步使用正规式来标记箭弧正规式来标记箭弧TJNU-COCIE-WJW712024/7/21替换规则：替换规则：TJNU-COCIE-WJW722024/7/21例例例例：对于一个：对于一个上的上的NFAM，构造一个正规式，构造一个正规式V，使得，使得L(M)=L(V)TJNU-COCIE-WJW732024/7/21第二步第二步，消去结点，消去结点1第三步第三步，消去结点，消去结点0第一步第一步：加入：加入X结点和结点和Y结点得到一个结点得到一个M，且，且L(M)=L(M)TJNU-COCIE-WJW742024/7/21定理定理2.对于对于上的每一个正规式上的每一个正规式V，存在一个，存在一个上的上的DFAM，使得，使得L(M)=L(V)问题问题：如何由一个正规式：如何由一个正规式V，构造一个，构造一个DFAM思路思路：分两步走：分两步走1.根据根据V，构造一个，构造一个NFAM，使得，使得L(M)=L(V)2.将将M确定化，变为确定化，变为DFAMTJNU-COCIE-WJW752024/7/21方法方法：第一步第一步，在，在上构造一个上构造一个NFAM(1)构造一个拓广的转换图构造一个拓广的转换图TJNU-COCIE-WJW762024/7/21(2)使用分裂规则对使用分裂规则对V进行分裂，加进新结点，直到进行分裂，加进新结点，直到把图转换成每条弧上标识为把图转换成每条弧上标识为上的一个字符或上的一个字符或最后得到一个最后得到一个NFAM且且L(M)=L(V)TJNU-COCIE-WJW772024/7/21第二步第二步，把，把M确定化确定化定义定义1某个状态集某个状态集I的的(空字空字)闭包：闭包：_CLOSURE(I)是一个状态集，由两部分组成是一个状态集，由两部分组成:n状态集状态集I中的所有状态。中的所有状态。n从从I中的状态出发经过任意条中的状态出发经过任意条弧，所能到达的状态的全体。弧，所能到达的状态的全体。定义定义2某个状态集某个状态集I的的a弧转换：弧转换：move(I,a)是一个状态集，是从是一个状态集，是从I中的状态出发经过一条中的状态出发经过一条a弧到达的弧到达的状态的全体。状态的全体。定义定义3Ia=_CLOSURE(move(I,a)是一个状态集。是一个状态集。TJNU-COCIE-WJW782024/7/21例例例例：有如下一个：有如下一个NFAN的状态转换图的状态转换图假定假定I=1,2，求，求Ia=？解：解：move(I,a)=Ia=_CLOSURE(J)=1a a5438267a aa a4,5,35,6,2,4,7,3,8a aa aa a5436278J=TJNU-COCIE-WJW792024/7/21例例例例3 3：有如下一个状态转换图：有如下一个状态转换图已知已知K=5,4,1求求Ka，Kb解：求解：求KaJ=5,3Ka=_CLOSURE(J)=5,3,1求求KbJ=5,2,4Kb=_CLOSURE(J)=5,2,4,1,6,YX12a a56b ba ab b43a aa ab bb bYTJNU-COCIE-WJW802024/7/21(1)基本思想基本思想:把把NFA的一些状态，即状态子集，合并为的一些状态，即状态子集，合并为DFA的一个状态。的一个状态。子集法子集法TJNU-COCIE-WJW812024/7/21(2)具体做法：具体做法：假设有一个假设有一个NFAN，=a1ak，初始状态集是，初始状态集是S0，用子集法把用子集法把N转换为转换为DFAM。第一步第一步：构造一张表：构造一张表第二步：第二步：将表中出现的每个状态子集看成一个状态，该表就将表中出现的每个状态子集看成一个状态，该表就是所求是所求DFAM的状态转换表，其中的状态转换表，其中uM的初态是该表的首行首列那个状态的初态是该表的首行首列那个状态uM的终态是那些含有原来的终态是那些含有原来NFA终态的状态子集所对应的状态终态的状态子集所对应的状态IIa1Iak状态子集状态子集状态子集状态子集状态子集状态子集_CLOSURE(S0)k+1列列TJNU-COCIE-WJW822024/7/21例例例例1 1：假设有一个：假设有一个NFAN，S0=1，F=4，=a,b用子集法把用子集法把N转换为转换为DFAM。解：第一步，构造一张表。解：第一步，构造一张表。IIaIb1,2,42,42,42,43332,43TJNU-COCIE-WJW832024/7/21第二步，将表中的每个状态子集看成一个状态，得到第二步，将表中的每个状态子集看成一个状态，得到DFAM的状态转换表。的状态转换表。状态状态ab012111222IIaIb1,2,42,42,42,43332,43012111222状态状态abTJNU-COCIE-WJW842024/7/21例例例例2 2：设：设=a，b，有，有上的一个正规式上的一个正规式(a|b)*(aa|bb)(a|b)*，构造，构造NFAM，并且确定化，并且确定化解：解：第一步第一步，构造一个，构造一个NFAMTJNU-COCIE-WJW852024/7/21TJNU-COCIE-WJW862024/7/21得到一个得到一个NFAM且且L(M)=L(V)TJNU-COCIE-WJW872024/7/21第二步第二步，用子集法对，用子集法对M进行确定化进行确定化构造一张表构造一张表IIa=_CLOSURE(J)Ib=_CLOSURE(J)J=5,3J=5,4X,5,15,3,15,3,15,3,15,4,15,4,15,4,15,3,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,4,1,6,Y5,4,1,6,Y5,4,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,6,YJ=5,3J=5,4J=5,2,3J=5,2,4J=5,2,3,6J=5,4,6J=5,3,6J=5,2,4,6J=5,3,6J=5,2,4,6J=5,2,3,6 J=5,4,6TJNU-COCIE-WJW882024/7/21IIa=_CLOSURE(J)Ib=_CLOSURE(J)X,5,15,3,15,4,15,3,1,2,6,Y5,4,1,2,6,Y5,4,1,6,Y5,3,1,6,Y5,3,15,3,1,2,6,Y5,3,15,3,1,2,6,Y5,3,1,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,15,4,15,4,1,2,6,Y5,4,1,6,Y5,4,1,2,6,Y5,4,1,2,6,Y5,4,1,6,Y把每个子集看成一个状态，得到一个把每个子集看成一个状态，得到一个DFAM，且且L(M)=L(M)sab012345613136632254554012345612325134455366TJNU-COCIE-WJW892024/7/21sab012345613136632254554TJNU-COCIE-WJW902024/7/211.化简的概念化简的概念寻找一个状态比寻找一个状态比DFAM少的少的DFAM，使得，使得L(M)=L(M)六、六、确定有限自动机的化简（最少化）确定有限自动机的化简（最少化）TJNU-COCIE-WJW912024/7/212.两个状态等价的概念两个状态等价的概念设设s和和t是是M两个不同的状态，从两个不同的状态，从s出发能读出出发能读出某个字而停于终态，那么同样，从某个字而停于终态，那么同样，从t出发也能出发也能读出同一个字而停在终态，反之亦可读出同一个字而停在终态，反之亦可3.两个状态是可区别的两个状态是可区别的若若DFAM的两个状态的两个状态s和和t不等价，则称这两不等价，则称这两个状态是可区别的个状态是可区别的注注注注：终态和非终态是可区别的，因为终态可：终态和非终态是可区别的，因为终态可以读出空字以读出空字，而非终态不能读出空字，而非终态不能读出空字TJNU-COCIE-WJW922024/7/214.化简化简DFA的一般步骤的一般步骤(1)检查状态转换函数是否为全函数。检查状态转换函数是否为全函数。所谓全函数，是指每个状态对每个输入符号都有转换所谓全函数，是指每个状态对每个输入符号都有转换若不是全函数，可以引入一个若不是全函数，可以引入一个“死状态死状态”d，d对所有对所有输入符号都转换到输入符号都转换到d，如果状态，如果状态s对输入符号对输入符号a没有转没有转换，那么加上从换，那么加上从s到到d的的a转换。转换。(2)用化简算法进行化简用化简算法进行化简(3)去掉死状态去掉死状态TJNU-COCIE-WJW932024/7/215.DFA化简算法化简算法(1)基本思想基本思想把把M的状态集分割为一些不相交的子集，的状态集分割为一些不相交的子集，使得使得任何不同的两个子集状态都是任何不同的两个子集状态都是可区别可区别的的，而同而同一个子集中的任何状态都是一个子集中的任何状态都是等价等价的的，最后让每，最后让每个子集选一个代表，同时消去其他等价状态个子集选一个代表，同时消去其他等价状态TJNU-COCIE-WJW942024/7/21(2)化简算法化简算法对对M的状态集的状态集S进行划分：进行划分：把把S的终态和非终态分开，分成终态集和非终态集，形的终态和非终态分开，分成终态集和非终态集，形成基本成基本分划分划，显然这两个子集是，显然这两个子集是可区别的可区别的。假定到某个时候假定到某个时候含有含有m m个子集，个子集，记记=I=I(1)(1),I,I(2)(2),I I(m)(m)并且，属于不同子集的状态是并且，属于不同子集的状态是可区别的可区别的。检查检查中的每个中的每个I I(i)(i)看能否进一步划分：看能否进一步划分：对于某个对于某个I I(i)(i)另另I I(i)(i)=q=q1 1,q,q2 2,q,qk k 若存在一个输入字符若存在一个输入字符a a使得使得I I(i)(i)a a不全包含在现行不全包含在现行的某的某个子集个子集I I(j)(j)中，就将中，就将I I(i)(i)一分为二一分为二TJNU-COCIE-WJW952024/7/21 例如例如例如例如，假定状态，假定状态s s1 1和和s s2 2经经a a弧分别到达状态弧分别到达状态t t1 1和和t t2 2，而，而t t1 1和和t t2 2属于现行属于现行的两个不同的子集，那就将的两个不同的子集，那就将I I(i)(i)分成两半分成两半I I(i1)(i1)和和I I(i2)(i2)使得一半含有使得一半含有s s1 1：I I(i1)(i1)=s|s=s|s I I(i)(i)且且s s经经a a弧到达弧到达t t1 1所在的子集中的某状态所在的子集中的某状态 另一半含有另一半含有s s2 2：I I(i2)(i2)=I=I(i)(i)-I-I(i1)(i1)注意注意注意注意：由于由于t t1 1和和t t2 2是可区别的，即存在一个字是可区别的，即存在一个字w w，t t1 1将读出