第三章词法分析.ppt

《第三章词法分析.ppt》由会员分享，可在线阅读，更多相关《第三章词法分析.ppt（128页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上机上机词法分析词法分析已知待分析的语言子集的词法：已知待分析的语言子集的词法：.关键字：关键字：main if else int while char 均均为小写。为小写。.专用符号：专用符号：=+-*/=!=;,()3、其他标记、其他标记ID和和NUM通过以下正通过以下正则式定义：则式定义：ID:letter(letter|digit)*NUM:digitdigit*lettera|b|c|d|z|A|B|C|Zdigit 0|1|2|3|4|5|6|7|8|94 4、空格由空白、制表符、换行、空格由空白、制表符、换行符组成，用来分隔符组成，用来分隔IDID、NUMNUM、专专用符号与关键

2、字，词法分析阶段用符号与关键字，词法分析阶段常被忽略。常被忽略。各种单词符号对应的种别码如下各种单词符号对应的种别码如下表：表：单词符单词符号号种别码种别码 单词符单词符号号种别码种别码 单词符单词符号号种别码种别码main1+22;31 int2-2332 char3*24=34else5(26=35while6)27=36ID1028!=37NUM2029=21,30实验目的、要求实现的功能实验目的、要求实现的功能输入：源程序文件输入：源程序文件输出：二元组（输出：二元组（syn,token或或sum)构成的序列构成的序列（文件），其中：（文件），其中：syn为单词种别码，为单词种别码，t

3、oken为存放的单词自身字符串，为存放的单词自身字符串，sum为整型常量。为整型常量。实验目的实验目的:设计、编制并调试一个词法分析程设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。序，加深对词法分析原理的理解。上机上机2 2 语法分析语法分析已知待分析的已知待分析的C语言子集的语法，用语言子集的语法，用EBNF表示如下：表示如下：main();|ID=if(条件条件)while()+|-*|/ID|NUM|()|=|=|!=实验目的：编制一个语法分析程序，实现对词实验目的：编制一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和法分析程序所提供的单词序列进行语法检查

4、和结构分析。结构分析。在上机在上机(一一)词法分析的基础上词法分析的基础上,采用递归子程采用递归子程序法或其他适合的语法分析方法序法或其他适合的语法分析方法,实现其语法实现其语法分析程序。要求编译后能检查出语法错误。分析程序。要求编译后能检查出语法错误。第三章第三章 词法分析及词法分析程序词法分析及词法分析程序有限自动机有限自动机FAFA确定的有限自动机确定的有限自动机DFADFA非非确定的有限自动机确定的有限自动机NFANFA文法是语言的生成系统，自动机是文法是语言的生成系统，自动机是语言的生成、识别系统语言的生成、识别系统。自动机自动机图灵机图灵机线性有界自动机线性有界自动机下推下推自动机

5、自动机有限自动机有限自动机一、概述一、概述理解一篇文章（或程序）：单词级别作为起点。理解一篇文章（或程序）：单词级别作为起点。编译程序也是在单词级别上来分析和翻译源程序。编译程序也是在单词级别上来分析和翻译源程序。词法分析是编译的基础。词法分析是编译的基础。编译过程的第一步。其功能为：编译过程的第一步。其功能为：依此扫描字符串形式的源程序中的各个字符，根据依此扫描字符串形式的源程序中的各个字符，根据语言词法规则，识别出其中的单词，并将其转换为语言词法规则，识别出其中的单词，并将其转换为内部编码形式的单词符号串作为输出。内部编码形式的单词符号串作为输出。通常采用二元式来表示一个单词符号的内部编码

6、。通常采用二元式来表示一个单词符号的内部编码。词法分析词法分析符号串序列符号串序列二元码序列二元码序列词法分析程序又称为扫描器，一般应完成以词法分析程序又称为扫描器，一般应完成以下任务下任务：1 1）识别出源程序中的单词符号，并将其转换为内部）识别出源程序中的单词符号，并将其转换为内部编码形式；编码形式；2 2）删除无用的空白字符、回车字符以及其它非实质）删除无用的空白字符、回车字符以及其它非实质性字符；删除注释。性字符；删除注释。3 3）进行预处理工作。）进行预处理工作。4 4）进行词法检查，报告所发现的错误。）进行词法检查，报告所发现的错误。视编译工作流程的组织，一些编译程序在词法分析视编

7、译工作流程的组织，一些编译程序在词法分析时，还要将所识别出的标识符填到符号表中。时，还要将所识别出的标识符填到符号表中。1 1、词法分析程序与语法分析程序的接口、词法分析程序与语法分析程序的接口1 1）词法分析与语法分析完全融合）词法分析与语法分析完全融合 词法分析基于正规文法词法分析基于正规文法(前后文无关文法前后文无关文法的特例的特例)进行进行,不特别把单词符号的规则分离不特别把单词符号的规则分离出来而统一作为语法规则来处理。出来而统一作为语法规则来处理。(2)(2)词法分析作为语法分析的子程序词法分析作为语法分析的子程序源程序源程序字符串字符串词法分析程序语法分析程序语法分析程序取取单单

8、词词回送回送单词单词(3(3）词法分析与语法分析完全分开）词法分析与语法分析完全分开 词法分析器读入整个源程序字符序列，识词法分析器读入整个源程序字符序列，识别单词，加工成等价的内部中间表示别单词，加工成等价的内部中间表示(二元码序二元码序列列)，语法分析器从中读单词进行语法分析。，语法分析器从中读单词进行语法分析。文件构成：文件构成：（单词类别，单词属性）（单词类别，单词属性）源程序源程序字符串字符串词法分析程序词法分析程序单词流单词流语法分析程序语法分析程序把把词法分析安排为独立的一个阶段，词法分析安排为独立的一个阶段，可使编译程序结构简洁、清楚，改进可使编译程序结构简洁、清楚，改进编译程

9、序的效率，建立自动词法分析编译程序的效率，建立自动词法分析工具，增强编译程序的可移植性。工具，增强编译程序的可移植性。2 2、源程序的输入及预处理、源程序的输入及预处理首先将源程序文本进行预处理：剔除无用的空首先将源程序文本进行预处理：剔除无用的空白符、跳格、注释、回车、换行符，再将预处白符、跳格、注释、回车、换行符，再将预处理结果装入扫描缓冲区，在其中识别单词。理结果装入扫描缓冲区，在其中识别单词。词法分析器调用预处理子程序，预处理子程序词法分析器调用预处理子程序，预处理子程序处理出一串确定长度的输入字符，将其装进词处理出一串确定长度的输入字符，将其装进词法分析器指定的缓冲区中。扫描器在此缓

10、冲区法分析器指定的缓冲区中。扫描器在此缓冲区中直接进行单词识别。中直接进行单词识别。起点指起点指示器示器（指（指向新单词的向新单词的首字符首字符搜索指示搜索指示器器（向前搜（向前搜索以寻找单词索以寻找单词的终点的终点3、单词的表示和词法分析程序的实现、单词的表示和词法分析程序的实现单词的种类单词的种类1）关键字：）关键字：if,else,for 等。等。2）标识符：用来命名程序中出现的变量、数组、函）标识符：用来命名程序中出现的变量、数组、函数、过程、标号等。数、过程、标号等。3）运算符：）运算符：+、-、*、/、=、1)b=100 二元式表示如下：二元式表示如下：单词单词 二元式二元式 if

11、 (3,if)(5,()a (1,指向指向a的符号表的入口）的符号表的入口）(4,)1 (2,1)(5,)b (1,指向指向b的符号表的入口）的符号表的入口）=（4，=）100 （2，100）类别编码：标识符类别编码：标识符1 常数常数2 关键字关键字3 运算符运算符 4 界码界码 5使用助记符使用助记符 if(a1)b=100 二元式表示如下：二元式表示如下：单词单词 二元式二元式 if (IF,)(LP,)a (ID,a）(GE,)1 (INT,1)(RP,)b (ID,b）=（EQ，）100 （INT，100）二、正规文法和状态转换图二、正规文法和状态转换图程序设计语言的单词能用正规文法

12、来描述程序设计语言的单词能用正规文法来描述:字母字母 数字数字 字母字母字母、数字为字母、数字为VT有限自动机是识别或生成正规语言的识别器。有限自动机是识别或生成正规语言的识别器。有限自动机的直观图示，有限个结点组成的有有限自动机的直观图示，有限个结点组成的有向图。向图。结点代表状态，用圆圈表示。状态之间用箭弧结点代表状态，用圆圈表示。状态之间用箭弧连接，箭弧上的标记代表在输出结状态下可能连接，箭弧上的标记代表在输出结状态下可能出现的输入符号（类）。一张转换图只包含有出现的输入符号（类）。一张转换图只包含有限个状态，至少一个初态（带初箭头圆圈），限个状态，至少一个初态（带初箭头圆圈），若干个终

13、态（双圈）。若干个终态（双圈）。如箭弧上可以标记如箭弧上可以标记，称为转换图。，称为转换图。状态的转换状态的转换（1）后继状态为自身。）后继状态为自身。（2）后继状态为一个。）后继状态为一个。（3）后继状态为若干个。后继状态为若干个。状态转换图中每一条箭弧表示一个转换关系。状态转换图中每一条箭弧表示一个转换关系。S1S2S0aS3S3babbaba用右用右线性文法构造状态转换图线性文法构造状态转换图右右线性文法线性文法G=(VN,VT,P,S),有有k个个VN，则，则状状态转换图有态转换图有K+1个状态。个状态。S为初态结点，增加为初态结点，增加一个终态结点。一个终态结点。（1）对产生式对产生

14、式AaB,从结点从结点A引一条箭弧到引一条箭弧到结点结点B，并用符号并用符号a标记此箭弧。标记此箭弧。（2）对产生式对产生式Aa，从，从结点结点A引一条箭弧到引一条箭弧到终态结点终态结点Z,并用并用a标记这条箭弧。标记这条箭弧。GZ:Z 0A A 0A|1B B 1A|BZA0011ZZA001B1规范句型规范句型Z=0A=00A=001B=001Z=001*利用状态图识别字符串利用状态图识别字符串 从从状态图的初态出发，沿着某路径达到终态状态图的初态出发，沿着某路径达到终态结点，将路径上每一条箭弧上的标记字符依结点，将路径上每一条箭弧上的标记字符依次连接，即为状态转换图所能识别的全部符次连接

15、，即为状态转换图所能识别的全部符号串，这些符号串所组成的集合就是该状态号串，这些符号串所组成的集合就是该状态转换图所识别的语言。转换图所识别的语言。在在利用利用M对符号串对符号串w进行识别的过程进行识别的过程中，中，M中每一次状态转换都模拟了中每一次状态转换都模拟了G中的一次直接推导。中的一次直接推导。用用M对符号串进行识别的方法是一个对符号串进行识别的方法是一个自顶向下的分析方法。自顶向下的分析方法。用左用左线性文法构造状态转换图线性文法构造状态转换图左线性文法左线性文法G=(VG=(VN N,V,VT T,P,S),P,S),有有k k个个V VN N，则状态则状态转换图有转换图有K+1K

16、+1个状态。个状态。S S为终态结点，增加一为终态结点，增加一个初态结点个初态结点R R。（1 1）对产生式对产生式Aa,Aa,从初态结点从初态结点R R引一条箭引一条箭弧到结点弧到结点A A，并用符号并用符号a a标记此箭弧。标记此箭弧。（2 2）对产生式对产生式ABaABa，从结点从结点B B引一条箭弧引一条箭弧到结点到结点A,A,并用并用a a标记这条箭弧。标记这条箭弧。GS:S S1S1 S U1 S U1 U U0 U U0 U 0 U 0RU001S100011=U0011=U011=U11=S1=S在利用在利用M M对符号串对符号串w w进行识别的过程中，进行识别的过程中，M M

17、中每一次状态转换都模拟了中每一次状态转换都模拟了G G中的一次中的一次直接归约。直接归约。用用M M对符号串进行识别的方法是一个自对符号串进行识别的方法是一个自底向上的分析方法。底向上的分析方法。状态转换图的一种实现状态转换图的一种实现状态矩阵法状态矩阵法为程序设计语言的每一类单词建立一张状态为程序设计语言的每一类单词建立一张状态转换图，并合并为一张统一的状态图，据此转换图，并合并为一张统一的状态图，据此构造词法分析程序。构造词法分析程序。用状态矩阵表示状态转换图。用状态矩阵表示状态转换图。状态转换矩阵状态转换矩阵 B11 B12 B1mB=B21 B22 B2m .Bn1 Bn2 Bnm 行

18、行:状态状态S1,S2,Sn列列:输入符号输入符号a1,a2,amBij=BSi,aj:指示后继状态指示后继状态Sk和扫描器应完成的语义动和扫描器应完成的语义动作。作。S1S2.Sna1 a2 am031dd.2.d4EEd5+|-6dddG的状态转换图的状态转换图CurStat=0;/*状态矩阵驱动程序状态矩阵驱动程序*/FlagOfFS=NoneSeen;/*终态标志终态标志*/if(CurChar=EOF)return 0;While(CurChar!=EOF)if(Stat=TransMatCurStatCurChar)!=NULL)CurStat=Stat;advance();if(

19、CurStat是终态是终态)FlagOfFS=HasSeen;记下输入串中的当前位置及该状态相记下输入串中的当前位置及该状态相 关联的动作关联的动作;else if(FlagOfFS=NoneSeen)报告词法错误报告词法错误:略过当前词文及输入字符略过当前词文及输入字符;CurStat=0;else 回退到最近经历的那个终态回退到最近经历的那个终态 的的 输入字符位置输入字符位置;执行所记录的该终态的相关动作执行所记录的该终态的相关动作;Static int CurrentState;int LEX(void)int ch;CurrentState=0;while(CurrentState!

20、=EndState)ch=GetChar();EXCUTE(CurrentState,ch);return Class;int EXCUTE(int state,int symbol)switch(state)case 0:switch(symbol)case DIGIT:n=0;p=0;e=1;w=d;CurrentState=1;Class=ClassNo;break;case POINT:w=0;n=0;p=0;e=1;CurrentState=3;Class=ClassNo;break;Default:HandleOtherWord();Class=ClassOther;Current

21、State=EndState;break;Case 1:switch(symbol)case DIGIT:break;return CurrentState;三、有限自动机三、有限自动机FA1、确定的有限自动机、确定的有限自动机定义：一个确定的有限自动机是一个五元组：定义：一个确定的有限自动机是一个五元组：MD=(K,f,S0,Z)其中：其中：S:状态的非空有穷集状态的非空有穷集：输入字母表输入字母表f:是一个从是一个从K 到到K的单值映射的单值映射S0S是唯一的初态是唯一的初态Z：终止状态集，终止状态集，Z S状态转换图的一种形式描述。状态转换图的一种形式描述。对映射对映射f的定义进行扩充为

22、的定义进行扩充为K*：(1)f(S,)=S;(2)f(S,aw)=f(f(S,a),w)a,w *X=a1a2a3 f(S0,a1)=S1 f(S1,a2)=S2 f(S2,a3)=S3 f(S0,x)=f(S0,a1a2a3)=f(f(S0,a1),a2a3)=f(S1,a2a3)=f(f(S1,a2),a3)=f(S2,a3)=f(f(S2,a3),)=f(S3,)=S3一个一个DFA可表示成一个状态转换图可表示成一个状态转换图（转换图）或状态转换矩阵（转换图）或状态转换矩阵设设MD=(K,f,S0,Z),其中：其中：K=S0,S1,S2,S3=a,bf(S0,a)=S1 f(S0,b)=

23、S2f(S1,a)=S3 f(S1,b)=S2f(S2,a)=S1 f(S2,b)=S3f(S3,a)=S3 f(S3,b)=S3S0=S0 Z=S3用状态转换图、状态转换矩阵表示该用状态转换图、状态转换矩阵表示该DFAb bb bS1S1S2S2b ba aS0S0a aS3S3a ab ba ab bS1S1S2S2b ba aS0S0a aS3S3a ab ba aabS0S1S2S1S3S2S2S1S3S3S3S3输入输入状态状态b初始状态初始状态S0 S0 终止状态终止状态S3S3DFA M 能接受的符号串能接受的符号串x*:将初态到某一终态路径将初态到某一终态路径上的标记符顺次连接

24、上的标记符顺次连接 f(S0,x)=S S Z 当当S0 Z时时,被被M所接受。所接受。定义：若定义：若定义：若定义：若MD=(S,f,S0,Z)MD=(S,f,S0,Z)是一个是一个是一个是一个DFA,DFA,则该则该则该则该DFADFA所接收所接收所接收所接收的语言为能被该自动机所接收的符号串的集合，记为的语言为能被该自动机所接收的符号串的集合，记为的语言为能被该自动机所接收的符号串的集合，记为的语言为能被该自动机所接收的符号串的集合，记为L(M)L(M)L(M)=x|f(S0,x)Z，x*S0S1aaM1=(K,f,S0,Z)K=(S0,S1)=a S0=S0 Z=S0,S1f(S0,a

25、)=S1 f(S1,a)=S1 S1S0aa,bM2=(K,f,S0,Z)K=S0,S1=a,b S0=S0 Z=S1f(S0,a)=S1 f(S1,a)=S1 f(S1,b)=S1S1abM2=(K,f,S0,Z)K=S1 S0=S1 Z=S1f(S1,a)=S1 f(S1,b)=S12、非确定的有限自动机、非确定的有限自动机NFA定义：一个定义：一个NFA是一个五元组：是一个五元组：MN=（K，f，S0,Z）K、Z的的 定义同定义同DFAS0：初始状态集初始状态集S0 Kf是一个从是一个从K 到到2K的一个映射，的一个映射，K K的一个子的一个子集集如如 f(S0,a)=S1,S2扩充扩充

26、f的定义域到的定义域到K*:(1)f(S,)=S(2)f(S,aw)=f(f(S,a),w)a,w *f(S,a)=Sk1,Sk2,Skm定义定义 f(Sk1,Sk2,Skm,w)=f(Ski,w)有有 f(S,aw)=f(f(S,a),w)=f(Ski,w)对对f和和f可不加以区分。可不加以区分。mi=1mi=1为为NFA M所接受的符号串所接受的符号串x*：集合集合f(S0,x)中含有终态集中含有终态集Z中的状态。中的状态。NFA M所接受或识别的语言：所接受或识别的语言：L(M)=x|f(S0,x)Z,x*CABUa aaaAUa B Ua C Ua或或U aA U aB U aC1b3

27、a2bbb从某当前状态在某输入字符进行状态的转换时从某当前状态在某输入字符进行状态的转换时,下一状态可能不止一个下一状态可能不止一个,难于自动分析。难于自动分析。符号串符号串bbbNFA与与DFA的区别的区别1）NFA有一个或多个初始状态。有一个或多个初始状态。2）NFA的转换函数是一个多值函数。的转换函数是一个多值函数。NFA与与DFA的联系的联系DFADFA是是NFANFA的一个特例。的一个特例。常用有限自动机常用有限自动机FAFA来泛指来泛指NFANFA和和DFA,DFA,可以证明可以证明DFADFA和和NFANFA是等价的，故是等价的，故FAFA常被理解为常被理解为DFA.DFA.定义

28、：设定义：设A1与与A2是同一字母表是同一字母表上的有限自动上的有限自动机，若机，若L（A1）=L（A2），），则称则称A1与与A2等价。等价。任任一一不确定的不确定的NFA MN,它所识别的语言为它所识别的语言为L（MN），），则必存在一确定的有限自动机则必存在一确定的有限自动机DFA MD,它所识别的语言它所识别的语言L（MD）恰为恰为L（MN），），即即L（MD）=L（MN）。）。3、NFA的确定化的确定化定义：对于字母表定义：对于字母表上的任一上的任一NFA必存在必存在上上与之等价的与之等价的DFA。多个初态多个初态多映射函数多映射函数让对应的让对应的DFA模拟模拟NFA的工作过程。的

29、工作过程。NFA确定化确定化1.如如NFA的的全部初态全部初态为为S1,S2,Sn,则令则令DFA的初的初态为态为S0=S1,S2,Sn2.设设QSi,Si+1,Sj是是DFA的一个状态，若的一个状态，若对某符号对某符号a，在，在NFA中有中有 fN(Si,Si+1,Sj,a)=Si,Si+1,Sk则令则令fD(Si,Si+1,Sj,a)=Si,Si+1,Sk为为DFA的一个转换函数，即的一个转换函数，即Si,Si+1,Sk为为DFA当前状态的一个当前状态的一个后继状态。后继状态。3.重复第重复第2步，直到不再出现新的状态为止。步，直到不再出现新的状态为止。4.上面所得的所有状态构成上面所得的

30、所有状态构成DFA的状态集的状态集K，转换函数构成，转换函数构成DFA的的f，DFA的字母表仍的字母表仍然是然是NFA的的。5.凡是含有凡是含有NFA终态的状态均为终态的状态均为DFA的终的终态。态。S0bS1aS2bbb4、具有、具有动动作的作的FA含有含有弧的弧的自动机称为自动机称为自动机。自动机。FA:S0S1FA非非FA DFA 最小化最小化10111213141516171819BEGINENDll,ddd=FA:五元式五元式M=(K,f,S0,Z)f:K()到到2k的一个映射，状态矩阵加上的一个映射，状态矩阵加上列列。对符号串的连接并不产生实质性的影响。对符号串的连接并不产生实质性

31、的影响。f(S,x):K*到到2K的映射的映射,符号串符号串x中可能含有若干个中可能含有若干个cS2S1bS0aS3b-CLOSURE(q)从给定的状态从给定的状态q出发，仅经过若干条出发，仅经过若干条箭弧所能达到的状态组成箭弧所能达到的状态组成的集合，约定的集合，约定q本身包含在此集合中。本身包含在此集合中。-CLOSURE(Sk1,Sk2,Skm)=-CLOSURE(Ski)-CLOSURE(S0)=S0,S1,S2,S3-CLOSURE(S1)=S1-CLOSURE(S2)=S2,S3-CLOSURE(S1,S2)=S1,S2,S3cS2S1bS0aS3bi=1m对于对于SK,a及及w

32、w*P=f(f(S,w),a)qf(S,w)(1)f(S,)=-CLOSURE(S)-CLOSURE(S)(2)(2)f(S,waf(S,wa)=)=-CLOSURE(P)=-CLOSURE(f(q,a)f(S0,)=-CLOSURE(S0)=S0,S1,S2,S3f(S0,a)=-CLOSURE(f(f(S0,),a)=-CLOSURE(fS0,S1,S2,S3,a)=-CLOSURE(S0 )=S0,S1,S2,S3f(S0,ac)=-CLOSURE(f(f(S0,a),c)=-CLOSURE(f(S0,S1,S2,S3,c)=-CLOSURE(f(S0,c)f(S1,c)f(S2,c)f

33、(S3,c)=-CLOSURE(S2 )=S2,S3qcS2S1bS0aS3bf(S0,)=S1,S2 f(S0,)=-CLOSURE(S0)=S0,S1,S2,S3f(q,a)与与f(q,a)不一定相等。不一定相等。具有具有动作的动作的NFA所接受或识别的语言所接受或识别的语言L(M)=w|f(S0,w)Z5、具有、具有动作的动作的NFA的确定化的确定化具有具有动作的动作的NFA：M=(K,f,S0,Z)构造相应的构造相应的DFA：M=(K,f,q0,Z)从从S0出发，将仅通过任意条出发，将仅通过任意条箭弧所能达到的状态所箭弧所能达到的状态所组成的集合（即组成的集合（即-CLOSURE(S0

34、)作为作为q0,然后分别把从然后分别把从q0出发，经过对输入符号出发，经过对输入符号a 的状态转移所能达到的状态（包含转移后再经的状态转移所能达到的状态（包含转移后再经箭箭弧所能达到的状态）组成的集合作为弧所能达到的状态）组成的集合作为M的状态，直的状态，直到不再有新状态出现为止。到不再有新状态出现为止。cS2S1bS0aS3bq0=-CLOSURE(S0)=S0,S1,S2,S3f(q0,a)=-CLOSURE(f(q0,a)=-CLOSURE(f(S0,S1,S2,S3,a)=-CLOSURE(S0)=q0f(q0,b)=-CLOSURE(f(q0,b)=-CLOSURE(f(S0,S1,

35、S2,S3,b)=-CLOSURE(S1,S3)=S1,S3f(q0,c)=-CLOSURE(f(q0,c)=-CLOSURE(f(S0,S1,S2,S3,c)=-CLOSURE(S2)=S2,S3=q1=q2f(q1,a)=-CLOSURE(f(S1,S3,a)=-CLOSURE()=f(q1,b)=-CLOSURE(f(S1,S3,b)=-CLOSURE(S1,S3)=q1f(q1,c)=-CLOSURE(f(S1,S3,c)=f(q2,a)=f(q2,b)=f(q2,c)=q2q0q2caq1bbc6、自动机的化简、自动机的化简-自动机的最小化自动机的最小化等价状态：若从两状态等价状态：

36、若从两状态Si、Sj出发能导出的出发能导出的所有符号串的集合相等，即所有符号串的集合相等，即L(Si)=L(Sj),则称则称Si和和Sj是是等价状态。等价状态。等价状态对识别符号串所起的作用相等等价状态对识别符号串所起的作用相等,应加应加以合并。以合并。S0SiSjbbabSk1)K=K1K2 K1为终态集合，为终态集合，K2为非终态集合。为非终态集合。L(K1)=,L(K2)2）处理每个集合处理每个集合KK1K2K3如如 f(K1,a)=K1j f(K2,a)=K2j f(K3,a)=K3j3）合并等价状态。）合并等价状态。4）删除无用状态、死状态。）删除无用状态、死状态。从考虑哪些状态不可

37、以合并在一起的角度来解决问题。从考虑哪些状态不可以合并在一起的角度来解决问题。等价类，则S1、S2、S3仍放在同一集合中，否则需要再分为不同的集合。DFADFA最小化算法最小化算法无用状态无用状态从从开始状态出发不可能到达的状态。开始状态出发不可能到达的状态。S0S1S2ab死死状态：若对任何输入符号，状态状态：若对任何输入符号，状态Si,都都不可能到达终止态，则不可能到达终止态，则Si,为死为死状态。状态。S0aS2bS3bS1ab无关状态：无关状态：无用状态无用状态 死状态死状态FAFA的化简就是合并等价状态，删除无用状态的化简就是合并等价状态，删除无用状态和死状态。和死状态。bS0abS

38、1S3S4baaaS2S5accK=0,1,2,3,4 5=K1 K2f(0,a)=1 K1f(1,a)=2 K1f(2,a)=2 K1 f(3,a)=4 K1 f(4,a)=4 K1f(0,b)=3 K1 f(1,b)=3 K1 f(2,b)=f(3,b)=1 K1 f(4,b)=K1=0,1,2,3,4=0,1,3 2,4=K11K12 K=K11 K12 K2对于对于K11:f(0,a)=1 K11 f(1,a)=2K12 f(3,a)=4K12 K11=0 1,3=K111 K112对于对于K112=1,3:f(1,b)=3 f(3,b)=1 f(1,c)=f(3,c)=f(1,a)=

39、2 f(3,a)=4 K112不能再分不能再分对于对于K12=2,4:f(2,a)=2 f(4,a)=4 f(2,b)=f(4,b)=f(2,c)=5 f(4,c)=5K12 也不能再分也不能再分K=0 1,3 2,4 5=K111 K112 K12 K2 0 1,3 2,4 50ba1,3ba2,45ac0ba1,3ba2,45ac四、正规四、正规(则则)表达式与正规（则）集表达式与正规（则）集3 3型文法和有限自动机在描述同一语言的意义下是等价的。型文法和有限自动机在描述同一语言的意义下是等价的。正则表达式：描述正则表达式：描述3 3型语言的有用工具。型语言的有用工具。（1 1）比用正则文

40、法定义语言的方式更直观。）比用正则文法定义语言的方式更直观。（2 2）易于构造高效的识别程序。）易于构造高效的识别程序。（3 3）可以由某正则表达式可以由某正则表达式 自动构造识别程序。自动构造识别程序。（4 4）可用于其它各信息流的处理）可用于其它各信息流的处理,如某些模式识别如某些模式识别问题、问题、文献目录检索、正文编辑程序等。文献目录检索、正文编辑程序等。1 1、正则表达式与正则集的定义、正则表达式与正则集的定义字母表字母表上的正则式是由上的正则式是由上的字符及上的字符及.、*、|、（和）组、（和）组成的表达式。正则式成的表达式。正则式e描述的集合称为正则集。描述的集合称为正则集。(1

41、)是一个正是一个正则式式,相相应的正的正则集集为空集。空集。(2)是一个正是一个正则式式,相相应的正的正则集集为。(3)对于每一于每一a,a是一个正则式是一个正则式,相相应的正的正则集集为a。(4)若若r,s是正是正则式式,且相且相应的正的正则集集为Lr及及Ls,则 a (r).(s)是正则式是正则式,相应的正则集为相应的正则集为LrLs;b (r)|(s)是正则式是正则式,相应的正则集为相应的正则集为LrLs;c (r)*是是正则式是是正则式,相应的正则集为相应的正则集为Lr*。例例 1=0，1 （0|1）、）、(0|1)*是是1上的正则式。上的正则式。2=a,b a*,(ab)*,ab*,

42、b(ab)*,a|ba*,a(a|b)*是是2上的正则式。上的正则式。3=A,B,0,1,则则（A|B)(A|B|0|1)*是是3上的正上的正则则 式。式。正则式正则式 正则集正则集a*L(a*)=an|n0=,a,aa,aaa.(ab)*,ab,abab,ababab,ab*a,ab,abb,abbb,abbbb,b(ab)*b,bab,babab,bababab,a|ba*a,b,ba,baa,baaa,baaaa,a(a|b)*a,aa,ab,aaa,abb,aab,aba,abaa,ID:letter(letter|digit)*NUM:digitdigit*KEY:BEGIN|END

43、|IF|THEN|ELSERELOP:|=优先级别：优先级别：*.|使用圆括号规定运算顺序使用圆括号规定运算顺序 (a|b)*abb a|ba*如果两个正则表达式如果两个正则表达式r和和s表示的正则集相同表示的正则集相同,则称它们则称它们是等价的。是等价的。例例 a(ba)*=(ab)*a (a*b*)*=(a|b)*正则表达式的性质正则表达式的性质零正则式零正则式:r|=|r=r r=r=单位正则式单位正则式:r=r=r交换律交换律:r|s=s|r结合律结合律:(r|s)|t=r|(s|t)(rs)t=r(st)分配律分配律:r(s|t)=rs|rt (s|t)|r=sr|tr 正则式与语法

44、规则的联系正则式与语法规则的联系一个正则式的值是正则集一个正则式的值是正则集,实际上是正则语言实际上是正则语言的另一种表示法。的另一种表示法。正则表达式与有限自动机的等价性正则表达式与有限自动机的等价性正则表达式转换为有限自动机正则表达式转换为有限自动机 对任意的对任意的FA M，存在一个正则表达式，存在一个正则表达式e,使得使得L(e)=L(M)。反之，对一正则表达式反之，对一正则表达式e,存在一个存在一个FA M，使得使得 L（M）=L(e)。2、正则文法转换为正则式、正则文法转换为正则式a)a)如正则语言较简单且易于用正则式表示，如正则语言较简单且易于用正则式表示，则先求正则语言，再将之

45、转换为正则式。则先求正则语言，再将之转换为正则式。XaX|bXaX|bL(G)=L(G)=b,ab,aab,aaabb,ab,aab,aaab,相应的正则式为：相应的正则式为：a a*b b都是描述正则集的工具。对任意一个正则文法，存都是描述正则集的工具。对任意一个正则文法，存在同一语言的正则式，反之，亦成立。在同一语言的正则式，反之，亦成立。b)解方程法解方程法用用+代替代替|，用，用=代替代替如有如有XaX|b,则有则有 X=aX+b X=a*b如有如有X Xa|b,则有则有 X=Xa+b X=ba*正则文法正则文法GS SaA A abA A a 将文法写成方程组形式将文法写成方程组形式

46、 S=aA (1)A=abA+a (2)得得 A=(ab)*a S=a(ab)*a3、正则表达式转换为、正则表达式转换为FA-Thompson法法（1 1）正则表达式转换为有限自动机）正则表达式转换为有限自动机 对任意的对任意的FA M FA M，存在一个正则表达式存在一个正则表达式e,e,使得使得L(e)=L(M)L(e)=L(M)。反之，对一正则表达式反之，对一正则表达式e,e,存在一个存在一个FA MFA M，使得使得 L L（M M）=L(eL(e)。r是是上一个运算符个数为上一个运算符个数为n的正则式。的正则式。（1）n=0时时 a.r=S0Sfb.r=S0c.r=a aS0aSf(

47、2)当当n=1,2,k-1时时,r相应的相应的NFA均能作出均能作出,则当则当n=k时时R=r1|r2或或r=r1r2或或r=r1*r1转换得到的转换得到的NFA为为M1 r2转换得到的转换得到的NFA为为M2 a.r=r1|r2SfS0S01Sf1S02Sf2M1M2b.r=r1r2S01Sf1M1S02Sf2M2c.r=r1*S0S01Sf1Sf构造与正则表达式构造与正则表达式(0|1)*0|(00)*等价的等价的FA(1)构造与构造与0等价的等价的NFA M1。(2)构造与构造与1等价的等价的NFA M2。(3)构造与构造与0|1等价的等价的NFA M3。(4)构造与构造与(0|1)*等

48、价的等价的NFA M4。(5)构造与构造与(0|1)*0等价的等价的NFA M5。(6)构造与构造与00等价的等价的NFA M6。(7)构造与构造与(00)*等价的等价的NFA M7。(8)构造与构造与(0|1)*0|(00)*等价的等价的NFA M8。构造与正则表达式构造与正则表达式(0|1)*0|(00)*等价的等价的FA与与0|1等价的等价的NFA 等价的等价的NFA M3S2S10S3S41S5S6S4S1S3S5S71S8S2S60与与(0|1)(0|1)*等价的等价的NFA NFA 等价的等价的NFA M4NFA M4S4S1S3S5S71S2S60S8S9S100S15S11S1

49、2S13S14S16S17S1800构造与正则表达式构造与正则表达式(0|1)*0|(00)*等价的等价的FA构造与正则表达式构造与正则表达式(0|1)*0|(00)*等价的等价的FAS0S100,1凭理解直接构造出来凭理解直接构造出来 正确性正确性?较复杂的正则式采用上述方法机械构造较复杂的正则式采用上述方法机械构造拓广拓广转换图转换图每条弧可以用正则式作标记。每条弧可以用正则式作标记。1）将正则式表示为拓广转换图，然后对正则）将正则式表示为拓广转换图，然后对正则式分裂、加新结，逐步将此图转变成：每式分裂、加新结，逐步将此图转变成：每条弧标记条弧标记为为的的一个字符或一个字符或。2）将上面得

50、到的将上面得到的M确定化。确定化。输入：正则式输入：正则式R 输出：输出：NFA或或DFA引入初始结点引入初始结点X,终止结点终止结点Y.拓广状态转换图。拓广状态转换图。XYR有限自动机转换为正则表达式有限自动机转换为正则表达式1）拓广转换图。）拓广转换图。在在M的转换图上加两个结，的转换图上加两个结，一个为一个为X结，另一个为结，另一个为Y结。结。X结用结用弧连到弧连到M的所有初态的所有初态，从，从M的所有终态结连到的所有终态结连到Y结。结。2）按图）按图3.16的规则消结消弧，直到只剩下的规则消结消弧，直到只剩下X结结和和Y结为止。结为止。正则文法转换为有限自动机正则文法转换为有限自动机对