词法分析课件

第三章词法分析3.1词法分析概述3.2词法分析程序的设计3.3正规式与有限自动机3.4词法分析程序的实现3.5词法分析器的自动生成10/1/20231中南大学软件学院陈志刚第三章词法分析3.1词法分析概述8/8/20231中南大3.1词法分析概述一、词法分析程序的任务二、词法分析程序的功能三、词法分析程序的安排四、词法分析程序的实现方式五、词法分析程序的输出形式10/1/20232中南大学软件学院陈志刚3.1词法分析概述一、词法分析程序的任务8/8/20232词法分析程序词法分析是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍。输入：源程序字符串输出：等价的属性字序列（内部表示形式）3.1词法分析概述10/1/20233中南大学软件学院陈志刚词法分析程序词法分析是编译过程中的一个阶段，在语法分析前进行一、词法分析程序的任务从左至右逐个字符地扫描源程序，产生一个个单词符号。把作为字符的源程序改造为单词符号串组成的中间程序，执行词法分析任务的程序称为词法分析器或称扫描器。3.1词法分析概述10/1/20234中南大学软件学院陈志刚一、词法分析程序的任务3.1词法分析概述8/8/20234二、词法分析程序的功能词法分析程序主要执行以下功能：读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）；把单词变换成长度统一的且为定长的属性字；其他功能：滤掉空格，跳过注释、换行符某些预加工处理3.1词法分析概述10/1/20235中南大学软件学院陈志刚二、词法分析程序的功能词法分析程序主要执行以下功能：3.1三、词法分析程序的安排常常把词法分析程序作为独立的一遍或作为被语法分析程序所调用的子程序。1、作为独立的一遍：语法分析前进行词法分析，把单词符号串形成中间文件存贮。3.1词法分析概述10/1/20236中南大学软件学院陈志刚三、词法分析程序的安排常常把词法分析程序作为独立的一遍或作为三、词法分析程序的安排2、作为被语法分析器词用的子程序：

3.1词法分析概述10/1/20237中南大学软件学院陈志刚三、词法分析程序的安排2、作为被语法分析器词用的子程序：3相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。四、词法分析程序的实现方式3.1词法分析概述10/1/20238中南大学软件学院陈志刚相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序相对独立方式当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。源程序词法分析程序语法分析程序Tokengettoken….四、词法分析程序的实现方式3.1词法分析概述10/1/20239中南大学软件学院陈志刚相对独立方式当采用递归下降分析等技术实现一趟编译程序时常采用完全独立方式采用词法分析工作完全独立的原因：简化设计，降低语法分析的复杂性提高编译效率增加编译系统的可移植性源程序词法分析程序语法分析程序属性字序列….四、词法分析程序的实现方式3.1词法分析概述10/1/202310中南大学软件学院陈志刚完全独立方式采用词法分析工作完全独立的原因：源程序词法分析程单词--是程序语言的基本语法符号。如：基本字、标识符、常数、运算符、界符等。词法分析器中单词的输出形式：（单词类别、单词内部码值）五、词法分析程序的输出形式3.1词法分析概述10/1/202311中南大学软件学院陈志刚单词--是程序语言的基本语法符号。五、词法分析程序的输出形式词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词自身的值）单词种别：表示单词种类，常用整数编码，它是语法分析需要的单词自身的值：是编译中其他阶段所需要的信息如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。五、词法分析程序的输出形式3.1词法分析概述10/1/202312中南大学软件学院陈志刚词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词语言的单词符号单词符号是程序语言的基本语法单位，一般分为下面5种：关键字（基本字）：（个数确定，可全体编为一类，也可一字一类)标识符：（个数不确定，作为一类）常数：各种类型的常数。(个数不确定，按类型分类)运算符：如+、-、*、/、<等。(个数确定，一符一类)界符：如，、；、（、）、:等。(个数确定,一符一类)注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。五、词法分析程序的输出形式3.1词法分析概述10/1/202313中南大学软件学院陈志刚语言的单词符号单词符号是程序语言的基本语法单位，一般分为下面例：若分类表为：试分析输入串：IFa1>0 THENb1:=c1*d1ELSEb1:=5经词法分析后的输出。五、词法分析程序的输出形式3.1词法分析概述10/1/202314中南大学软件学院陈志刚例：若分类表为：五、词法分析程序的输出形式3.1词法分析概解：输出的单词串为：五、词法分析程序的输出形式3.1词法分析概述10/1/202315中南大学软件学院陈志刚解：输出的单词串为：五、词法分析程序的输出形式3.1词法分一、状态转换图状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结状态下可能出现的输入字符或字符类。一个状态转换图只包含有限个状态，有一个初态，终态用双圈表示。一个状态转换图可识别一定的字符串。

SIE字母数字字母或数字状态都是非终结符号S：开始状态E：终止状态，用双圈表示I：标识符状态3.2词法分析程序的设计例1：10/1/202316中南大学软件学院陈志刚一、状态转换图状态转换图是一张有限方向图。用结点代表状态，状一、状态转换图例2：例3：10/1/202317中南大学软件学院陈志刚一、状态转换图例2：例3：8/8/202317中南大学软件学方法：每个结点对应一段程序，前面状态结的程序调用其后继结点的程序。例1：二、状态转换图的实现PROCEDUREProc0;Getchar;casecharof‘A’…‘Z’:proc1;‘0’…‘9’:proc2;otherwiseerror;endofcase;10/1/202318中南大学软件学院陈志刚方法：每个结点对应一段程序，前面状态结的程序调用其后继结点的为了描述方便，引入一些标准过程（函数）与变量:1.全程字符变量Char：存放最新读入的源程序字符；2.字符串TOKEN：存放构成单词符号的字符串；3.过程GETChar：读入一个源程序字符，放入Char中，搜索指针前移；4.过程GETNBC：反复调用GETChar，直接读入的Char<>’’为止；5.过程CONCAT：把Char中字符连到TOKEN末尾去；6.函数Letter/digit：判别Char中是否为字母/数字；7.过程Return(c,val);8.过程Retract：搜索器指针回拔一个字符。

二、状态转换图的实现10/1/202319中南大学软件学院陈志刚为了描述方便，引入一些标准过程（函数）与变量:二、状态转换图例2：PROCEDUREPro0;BEGINGetchar;IFcharIN[‘A’..‘Z’]thenpro1elseerror;END;Procedurepro1;begingetchar;whilecharIN[‘A’..‘Z’,‘o’..‘g’]DObeginconcat;getchar;End;pro2;End;procedurepro2;beginretract;return(101,TOKEN);end;10/1/202320中南大学软件学院陈志刚例2：PROCEDUREPro0;8/8/202320中三、为正则文法构造状态转换图什么是正则文法？（U::=T或U::=WT）步骤如下：以S为开始状态作结点；把文法中的每一个非终结符号作为状态结点；对于形如Q::=T的每个规则，引一条开始状态S到状态Q的弧，弧上标记为T；对于形如Q::=RT的规则引一条从状态R到Q的弧，弧上标记为T，其中R为非终结符号，T为终结符号。以识别符号为终止状态。10/1/202321中南大学软件学院陈志刚三、为正则文法构造状态转换图什么是正则文法？（U::=T构造状态转换图举例例如：对于正则文法G[Z]：Z::=Za|Aa|BbA::=Ba|aB::=Ab|bSABabSABaZZaSABabZbaabaaaba(1)(2)(3)10/1/202322中南大学软件学院陈志刚构造状态转换图举例例如：对于正则文法G[Z]：SABabSA四、应用状态转换图识别句子如果x是相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤如下:(1)从开始状态开始，以它作为当前状态，并从x的最左字符开始重复步骤2，直到到达x的右端为止；(2)扫描x的下一字符，在当前状态射出的各个弧中找出标记有该字符的弧，并沿此弧前进，以达到的状态作为下一当前状态。步骤2存在的两种可能：可能找不到一条弧的标记与当前字符相同；总能找到一个弧，其标记与当前字符相同。10/1/202323中南大学软件学院陈志刚四、应用状态转换图识别句子如果x是相应文法的句子便必须能从开应用状态转换图识别句子举例例如：对于正则文法G[Z]：Z::=Za|Aa|BbA::=Ba|aB::=Ab|babSABabZbaaabSABabZbaa(1)识别字符串ababaaaFba,b(2)识别字符串bababbb10/1/202324中南大学软件学院陈志刚应用状态转换图识别句子举例例如：对于正则文法G[Z]：abS状态转换图识别句子的实质是一个规约过程，运用自底向上的识别算法：如：SA与AZ表示：a直接规约为A，Aa直接规约为Z。从开始状态S出发逐步到达终止状态Z的过程，也是从终结符号串出发，规约到非终结符号的过程。10/1/202325中南大学软件学院陈志刚状态转换图识别句子的实质是一个规约过程，运用自底向上的识别算对句子ababaaa的分析步骤当前状态输入的其余部分SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZababaaaABABAZZ(a)分析过程(b)语法树10/1/202326中南大学软件学院陈志刚对句子ababaaa的分析步骤当前状态输入的其余部分五、用状态转换图为正则语言构造正则文法从上面状态转换图，可得到相应的正则文法：G[Z]:Z::=CbC::=Bb|bB::=AbA::=Ba|aSABCZabbbba例如：正则语言{(ab)nb2|n≥0}基于其句子的一般形式，为其构造状态转换图：10/1/202327中南大学软件学院陈志刚五、用状态转换图为正则语言构造正则文法从上面状态转换图，可得六、转换系统定义：转换系统是具有下列三个特征的状态转换图，即1)开始状态S和终止状态Z唯一;2)无弧进入S，也无弧自Z射出；3)可能存在标记为空串（ε）的弧。转换系统与状态转换图的区别：ε弧SS1S2ZεεAZ2Z1εε10/1/202328中南大学软件学院陈志刚六、转换系统定义：转换系统是具有下列三个特征的状态转换图，即一、基本概念二、确定有穷状态自动机（DFA）三、非确定有穷状态自动机（NFA）四、NFA和DFA的转换五、正规式和有限自动机的等价性六、DFA的化简3.3正规式与有限自动机10/1/202329中南大学软件学院陈志刚一、基本概念3.3正规式与有限自动机8/8/202329中一、基本概念1.字母表Σ：元素的非空有限集合。如Σ={‘A’,‘B’,‘O’}2.字符：字母表Σ的一个元素称为一个字符（符号）3.Σ上的字：Σ上字符的有穷序列；例：Σ={a,b,c}4.空字ε：不含任何字符的字5.字的长度：|α|6.Σ上字的全体：Σ*7.字的连接：字α与字β的连接记为αβ3.3正规式与有限自动机10/1/202330中南大学软件学院陈志刚一、基本概念3.3正规式与有限自动机8/8/202330中一、基本概念8.字的方幂：字α的n次连接称为α的n次方幂,记为,特别地=ε9.字的集合A与B的乘积：记作,其中10.Σ*子集的方幂：Aº={ε},A1=A,…,11.Σ*子集的正则闭包：12.Σ*子集的闭包：3.3正规式与有限自动机10/1/202331中南大学软件学院陈志刚一、基本概念3.3正规式与有限自动机8/8/202331中正规式与正规集正规集是字母表Σ上的一个特殊字集，通常我们借助正规式来描述它。关于正规式与正规集的定义是递归的。1.ε和φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和φ2.任何a∈Σ,a是Σ上的正规式，它所表示的正规式为{α}3.假定u和v是正规式，它们所代表的正规集分别是L(u)和L(v)，则u|v,uv,u*都是Σ上的正规式，它们所表示的正规集分别为L(u)∪L(v),L(u)L(v),L(u)*仅由有限次使用上述三步而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集10/1/202332中南大学软件学院陈志刚正规式与正规集8/8/202332中南大学软件学院陈志刚正规式与正规集优先级递增：|(或)，·（直接），*,（正规式） ∪,∩,*’,（正规集）例1.Σ={0,1}，则正规式有0,1,ε,1*,|0|,…，正规集有{0},{1},{ε},φ,{1}*,…若两个正规式所表示的正规集相同，则认为二者等价才是Σ上的正规集10/1/202333中南大学软件学院陈志刚正规式与正规集8/8/202333中南大学软件学院陈志刚正规式的性质：1．交换律：U|V=V|U证：L(u|v)=L(u)∪L(v)=L(v)∪L(u)=L(v|u)因此，u|v=v|u 2．结合律：(u|v)|w=u|(v|w),(uv)w=u(vw)3．分配律：u(v|w)=uv|uw,(u|v)w=u(vw)4． εu=uε=u证：L(εu)=L(ε)L(u)=L(u)0L(u)=L(u)

10/1/202334中南大学软件学院陈志刚正规式的性质：8/8/202334中南大学软件学院陈志刚二、确定型有穷状态自动机一个确定的有穷自动机（DFA）D是一个五元组：D=（K，Σ，M，S，F）其中K：有穷非空的状态集合；Σ：有穷非空的输入符号字母表；

M：转换函数，是在K×Σ→K上的映像，即，如M(ki,a)=kj,(ki∈K,kj∈K)就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；S∈K是唯一的一个初态；F

K是非空的终态集合。10/1/202335中南大学软件学院陈志刚二、确定型有穷状态自动机一个确定的有穷自动机（DFA）D是一例1．DFAM=({0,1,2},{a,b},f,0,{2})，其中δ(s,a)=S,δ(s,b)=2,s=0,1,2注：一个DFA可表示为一个状态转换矩阵，行表示状态，列表示输入字符，矩阵元素M[s,a]的值为δ(s,a)。例2．二、确定型有穷状态自动机10/1/202336中南大学软件学院陈志刚例1．DFAM=({0,1,2},{a,b},f,一个DFAM也可用一张状态转换图表示，DFA的每个状态对于状态转换图的一个接点，图中箭弧上的标记为输入字符，若δ(s,a)=S’，则从状态s画一条箭弧到S’，弧上标记为a。对Σ*中的任何字α，若存在一条从初态到某一终态的道路，且这条路上所有弧上标记连接成的字等于α，则称α可为DFAM所识别，或称DFAM可读出（或接受、识别）字α。DFAM识别的字的全体记为L(M)。二、确定型有穷状态自动机10/1/202337中南大学软件学院陈志刚一个DFAM也可用一张状态转换图表示，DFA的每个状态对于如果一个DFAM的输入字母表为∑，则我们也称M是∑上的一个DFA。可以证明：∑上的一个子集是正规的，当且仅当存在∑上的DFAM，使得V=L（M）。DFA的确定性表现在映射δ：S×Σ→S是一个单值函数。也就是说，对任何状态s∈S和输入符号a∈Σ，δ(s,a)唯一地确定了下一状态。特别地，若DFAM的初态同时又是终态，改DFAM可识别空字ε。显然，若DFAM中字母表Σ含n个字母，则任何一个状态顶多只有n条发出弧。

二、确定型有穷状态自动机10/1/202338中南大学软件学院陈志刚如果一个DFAM的输入字母表为∑，则我们也称M是∑上的一个从状态转换图构造有穷状态自动机例如：从下面状态图构造DFADFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）其中M定义为：M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z abSABabZbaa10/1/202339中南大学软件学院陈志刚从状态转换图构造有穷状态自动机例如：从下面状态图构造DFAa运行DFA与识别一个字符串扩充的映像M定义：M(R,ε)=RM(R,Tt)=M(M(R,T),t)，其中t∈Σ*，T∈Σ以上两个式子的含义是什么？定义：对于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，则称符号串t可被DFAD所接受。运行一个DFA的过程：识别一个符号串是否被接受10/1/202340中南大学软件学院陈志刚运行DFA与识别一个字符串扩充的映像M定义：8/8/2023举例如前例：DFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z 则：M(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(A,baa)=M(B,aa)=M(A,a)=Z10/1/202341中南大学软件学院陈志刚举例如前例：DFAD=（{S，Z，A，B}，{a，b}正则集正则集：L(D)，是一个DFA接受的字符串集合正则语言与正则集：L(G)=L(D)最小状态自动机：状态个数最少，唯一如何减少自动机的状态数而不改变自动机所接受的语言呢？10/1/202342中南大学软件学院陈志刚正则集正则集：L(D)，是一个DFA接受的字符串集合8/8/如何在计算机内表示映像？映像M：含义？映像在计算机内的表示法：矩阵表示法表结构表示法10/1/202343中南大学软件学院陈志刚如何在计算机内表示映像？映像M：含义？8/8/202343中DFA的矩阵表示法字符状态abSABabZbaa矩阵行代表状态，列代表输入字符，矩阵元素是映像得到的新状态。10/1/202344中南大学软件学院陈志刚DFA的矩阵表示法字符状态abSABabZbaa矩阵行代表表结构表示法状态名射出的弧数标记1指向的下一状态1…标记K指向的下一状态k对每一个状态结点而言若某结点有K个射出的弧，则相应表长为2k+210/1/202345中南大学软件学院陈志刚表结构表示法状态名射出的弧数标记1指向的下一状态1…标记K指引入M(R,T)是K×Σ到K的单值函数，即唯一确定下一状态如果在当前状态下，同一个输入字符确定的下一状态不止一个呢？如V::=UTW::=UTUWVTTabSABabZbaaaa例如：文法G3.2:Z::=Za|Aa|BbA::=Ba|Za|aB::=Ab|Ba|b三、非确定有穷状态自动机10/1/202346中南大学软件学院陈志刚引入M(R,T)是K×Σ到K的单值函数，即唯一确定下一状态U一个非确定的有穷自动机（NFA）D是一个五元组：N=（K，Σ，M，S，F）其中K：有穷非空的状态集合；Σ：有穷非空的输入字母表；M：转换函数，是在K×Σ到K的子集所组成集合的映像，M(R,T)={Q1,Q2,….Qn}S

K是非空的初态集合；F

K是非空的终态集合.三、非确定有穷状态自动机10/1/202347中南大学软件学院陈志刚一个非确定的有穷自动机（NFA）D是一个五元组：N=（K，ΣDFA与NFA的区别DFANFA开始状态唯一一个或多个映像单个状态状态集合10/1/202348中南大学软件学院陈志刚DFA与NFA的区别DFANFA开始状态唯一一个或多个映像单举例前述文法G3.2对应的自动机NFAN=({S,A,B,Z},{a,b},M,{S},{Z})其中M：M(S,a)={A}M(S,b)={B}M(A,a)={Z}M(A,b)={B}M(B,a)={A,B}M(B,b)={Z}M(Z,a)={A,Z}abSABabZbaaaa10/1/202349中南大学软件学院陈志刚举例前述文法G3.2对应的自动机NFAN=({S,A,B,扩充映像定义：M(R,ε)={R}R为任意的状态M(R,Tt)=M(Q1,t)∪M(Q2,t)∪…∪M(Qn,t)其中t∈Σ*，T∈Σ，M(R,T)={Q1,Q2,….Qn}M(R,Tt)=M({Q1,Q2,…,Qn},t)=∪M(Qi,t)10/1/202350中南大学软件学院陈志刚扩充映像定义：8/8/202350中南大学软件学院陈志举例(字符串被NFA所接受)对于输入字符串babbabb，运行G3.2的NFA步骤当前状态输入的其余部分可能的后继选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ10/1/202351中南大学软件学院陈志刚举例(字符串被NFA所接受)对于输入字符串babbabb，运运行NFA运行NFA：识别一个字符串是否被NFA所接受，是否能达到终态集合中的某个状态实质：用自底向上方法识别句子状态转换的下一状态不唯一，如何解决？10/1/202352中南大学软件学院陈志刚运行NFA运行NFA：识别一个字符串是否被NFA所接受，是否单状态M(R,T)={Q1,Q2,…,Qn}变为M(R,T)=[Q1,Q2,…,Qn]（单状态）表示当前状态为R输入字符T时，下一状态可能是这些状态中的某一状态。10/1/202353中南大学软件学院陈志刚单状态M(R,T)={Q1,Q2,…,Qn}变为M(R,怎样把NFA变为DFA?定理3.6NFAN=(K,Σ,M,S,F)对应DFAN’=(K’,Σ,M’,S’,F’)其中K’是有穷非空状态集合，由k的一切子集组成；用[Q1,Q2,…,Qm]表示K’的元素，Qi∈KM’([R1,R2,…,Ri],T)=[Q1,Q2,….Qj]S’=[S1,S2,…,Sn]F’={[Sj,Sk,…,Sl]|[Sj,Sk,…,Sl]∈K’,[Sj,Sk,…,Sl]∩F≠φ

}则L(N)=L(N’)四、NFA与DFA的转换10/1/202354中南大学软件学院陈志刚怎样把NFA变为DFA?定理3.6NFAN=(K,Σ举例例:为NFAN=({S,A,B,Z},{a,b},M,{S},{Z})构造DFA.设它对应的DFAN’=(K’,{a,b},M’,[S],F’)abSABabZbaaaaK’={[S]}M([S],a)=[A]M([S],b)=[B]K’={[S],[A],[B]}M([A],a)=[Z]M([A],b)=[B]M([B],a)=[AB]M([B],b)=[Z]K’={S],[A],[B],[Z],[AB]}M([Z],a)=[AZ]M([Z],b)=φM([AB],a)=[ABZ]M([AB],b)=[BZ]K’={S],[A],[B],[Z],[AB],[AZ],[BZ],[ABZ]}M([AZ],a)=[AZ]M([AZ],b)=[B]M([BZ],a)=[ABZ]M([BZ],b)=[Z]M([ABZ],a)=[ABZ]M([ABZ],b)=[BZ]10/1/202355中南大学软件学院陈志刚举例例:为NFAN=({S,A,B,Z},{a,b},举例（续1）输入状态ab[S][A][B][A][Z][B][B][AB][Z][Z][AZ][AB][ABZ][BZ][AZ][AZ][B][BZ][ABZ][Z][ABZ][ABZ][BZ]abSABabZbaaaa根据左边状态转换矩阵，可以得到DFAN’的状态集合（表的左列状态），即K’={[S],[A],[b],[Z],[AB],[AZ],[BZ],[ABZ]}10/1/202356中南大学软件学院陈志刚举例（续1）输入ab[S举例（续2）SBABABZAZBZAZbbbbbbbaaaaaaaa开始状态:[S]终止状态:[Z],[AZ],[BZ],[ABZ]根据上面状态转换矩阵，同时可以得到N’的映像函数，根据该映像可以画出它的状态转换图（如下）。终态集合中的元素为：由新映像得到的状态、且这些状态包含原NFAN的终态集合中的状态。10/1/202357中南大学软件学院陈志刚举例（续2）SBABABZAZBZAZbbbbbbbaaaa1．Σ上NFAM所能识别的字的全体是Σ上的一个正规集证明：设转换图中每条弧上可用一个正规式作标记，让NFAM的转换图中加进两节点X和Y，形成新的NFAM’，从X画ε弧指向原NFAM的所有初态，从原NFAM的所有终态画ε弧指向Y，显然L(M)=L(M’)然后，对NFAM’消结，直至只剩下X、Y两个结点为止，符上标记为一正规式。所以，NFAM’识别的为一正规式；NFAM识别的是一正规集。

五、正规式和有限自动机的等价性10/1/202358中南大学软件学院陈志刚1．Σ上NFAM所能识别的字的全体是Σ上的一个正规集五、正消结规则为五、正规式和有限自动机的等价性10/1/202359中南大学软件学院陈志刚消结规则为五、正规式和有限自动机的等价性8/8/202359例1.消结点⑤五、正规式和有限自动机的等价性例2.消结点①10/1/202360中南大学软件学院陈志刚例1.消结点⑤五、正规式和有限自动机的等价性例2.消结点①82．对于Σ上的每个正规集V，存在一个Σ上的DFAM，使得V=L(M)。证明：第一步，用替代办法构造一个NFAM’，使V=L(M’)，因为正规集V可用正规式u来描述，而u由一系列单个字符连接而成，故可用下述方法分解之：五、正规式和有限自动机的等价性SZe1e2SZe1e2SZe1|e2SZ{e}SZ

SZe1e2e10/1/202361中南大学软件学院陈志刚2．对于Σ上的每个正规集V，存在一个Σ上的DFAM，使得具体方法：构造如下转换图：逐步分解，便可得到一个NFAM’，有L(u)=V=L(M’)。例1．第二步，把NFAM’确定化为DFAM，得证。五、正规式和有限自动机的等价性10/1/202362中南大学软件学院陈志刚具体方法：构造如下转换图：五、正规式和有限自动机的等价性8/举例例：正则表达式(A|B){A|B|0|1}的转换系统的构造过程如下：SZ(A|B){A|B|0|1}SZ(A|B){A|B|0|1}SZAB

A|B|0|1SZAB

10AB10/1/202363中南大学软件学院陈志刚举例例：正则表达式(A|B){A|B|0|1}的转换系统的构概念1.假设I是NFAM’的状态集的一个子集，我们定义ε-CLOSURE(I)为（I的ε-闭包）。（1）若S∈I，则S∈ε-CLOSURE(I)（2）若S∈I，则从s出发经过任意条ε弧而达到的状态s’，有s’∈ε-CLOSURE(I)例1.五、正规式和有限自动机的等价性若I={1,3}，则ε-CLOSURE(I)={1,3,2,8}10/1/202364中南大学软件学院陈志刚概念1.假设I是NFAM’的状态集的一个子集，我们定义ε概念2.假定I是M’的状态子集，a是Σ中的字符，定义Ia=ε-CLOSURE(J),其中J是I中任意状态出发（跳过前面任意多条ε弧），经过一条a弧而能达到的状态结的全体。例2．同例1DFA，Ia={5,6,2}利用概念1和概念2，便可把NFA确定化。五、正规式和有限自动机的等价性10/1/202365中南大学软件学院陈志刚概念2.假定I是M’的状态子集，a是Σ中的字符，定义Ia=五、正规式和有限自动机的等价性令，构造一张如下的表，此表第0列为状态子集I，第1至m列分别为状态子集，设第一行第0列为ε-CLOSURE(X),，其中X为NFAM’的初态，求出第一个的，如果某个Iai(i=1,…,m)未曾在第0列中列出，则把Iai补入状态子集集合I中，即列于第0列新的一行。重复上述各步，直至所有行的Iai(i=1,…,m)均在第0列I中出现过为止。这种循环必将在有限步内中止。（因为S是有限状态集，所以S中状态的组合数也是有限的）

10/1/202366中南大学软件学院陈志刚五、正规式和有限自动机的等价性令，构造显然，这张表可以看成一个状态转换表，也就是说可把I中每个子集看成一个状态，而状态转换表唯一地刻划了一个DFAM，其初态为该表的第1行第0列，含有原NFAM’终态的子集为新的终态。（证毕）推论：一个子集是正规的，当且仅当它可由一个DFA（或NFA）所识别。五、正规式和有限自动机的等价性10/1/202367中南大学软件学院陈志刚显然，这张表可以看成一个状态转换表，也就是说可把I中每个子集例：设计一个DFAM，它识别二进制偶数（不以0开头的无符号数）解：1． 写出正规式1（1|0）*02． 画出NFAM’

细化为：3.确定化为DFAM五、正规式和有限自动机的等价性10/1/202368中南大学软件学院陈志刚例：设计一个DFAM，它识别二进制偶数（不以0开头的无符号五、正规式和有限自动机的等价性或：10/1/202369中南大学软件学院陈志刚五、正规式和有限自动机的等价性或：8/8/202369中南大举例正则表达式{a}|{(a|b)a}的相应转换系统与状态转换图的构造过程。AB{a}|{(a|b)a}AB{(a|b)a}{a}ABDCa(a|b)a

ABDCaa

Eab(a)(b)(c)(d)开始状态：A终止状态：B10/1/202370中南大学软件学院陈志刚举例正则表达式{a}|{(a|b)a}的相应转换系统与状态转前例续NFAN=({A,C,D,E},{a,b},M,{A,C,D},{A,C,D})M:M(A,a)={C,E}M(A,b)={E}M(C,a)={C}M(D,a)={E}M(D,b)={E}M(E,a)={D}ABDCaa

EabACaaa

b(e)(f)DaEab开始状态：A,B终止状态：B,C,D开始状态：A,C,D终止状态：A,C,D10/1/202371中南大学软件学院陈志刚前例续NFAN=({A,C,D,E},{a,b},正则表达式的值与有穷自动机所接受的语言定理3.11：上的NFAA所接受的字符串集合L(A)是上的某个正则表达式e的值，即L(A)=|e|。例:NFAN相应的状态转换图为图(a)，则N所接受的语言为合成所得到的正则表达式{(aa|bb)|(ab|ba){aa|bb}(ab|ba)}的值。ZTab,baab,baaa,bbaa,bb(a)ZTab|baab|baaa|bbaa|bbXY

(b)10/1/202372中南大学软件学院陈志刚正则表达式的值与有穷自动机所接受的语言定理3.11：上的N前例续正则表达式与有穷状态自动机是等价的。Zaa|bbXY

(ab|ba){aa|bb}(ab|ba)XY(d)(c){(aa|bb)|(ab|ba){aa|bb}(ab|ba)}10/1/202373中南大学软件学院陈志刚前例续正则表达式与有穷状态自动机是等价的。Zaa|bbXY字符串W把状态P和状态Q区别开：等价状态：无法区别开的两个状态基本思想：把状态集划分成互不相交的子集，使子集中的状态是等价的化简DFA的算法步骤：划分状态集合并状态:取每组状态中的代表状态，删去其他等价状态若有死状态或不可达状态，则把它们删去。死状态：无法达到终止状态的非终止状态不可达状态：不能从开始状态达到它的那些状态六、DFA的化简10/1/202374中南大学软件学院陈志刚字符串W把状态P和状态Q区别开：六、DFA的化简8/8/20举例划分状态集为{4}和{0,1,2,3}对于{0,1,2,3}和输入字符a和b:M(0,a)={1}M(1,a)={1}M(2,a)={1}M(3,a)={1}M(0,b)={2}M(1,b)={3}M(2,b)={2}M(3,b)={4}只有状态3在输入为b时映像的后继状态不在{0,1,2,3}中，因此该状态集划分为{3}和{0,1,2}对于{0,1,2}:状态1在输入为b时的后继状态不在{0,1,2}中，因此划分为{1}和{0,2}02314bbbbbaaaaa对于{0,2}:对于相同输入字符，该子集中每一状态映像得到的后继状态都相同，因此不再可划分最后划分为：{4}{3}{1}{0,2}六、DFA的化简10/1/202375中南大学软件学院陈志刚举例划分状态集为{4}和{0,1,2,3}02314bbb举例（续1）对于划分结果{4},{3},{1},{0,2}，把{0,2}合并为一个状态，其状态转换图如图：0213aaaabbb02314bbbbbaaaaab六、DFA的化简10/1/202376中南大学软件学院陈志刚举例（续1）对于划分结果{4},{3},{1},{0,构造词法分析程序的方法用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如，C语言直接编写词法分析程序。利用自动生成工具LEX自动生成词法分析程序。3.4词法分析程序的实现10/1/202377中南大学软件学院陈志刚构造词法分析程序的方法用手工方式，即根据识别语言单词的状态转词法分析程序实现中要考虑的问题确定实现词法分析程序的执行方式确定属性字的结构缓冲区预处理，超前搜索,关键字的处理，符号表的实现查找效率，算法的优化实现词法错误处理3.4词法分析程序的实现10/1/202378中南大学软件学院陈志刚词法分析程序实现中要考虑的问题确定实现词法分析程序的执行方式属性字词法分析程序对说明部分不做语义处理。词法分析程序输出属性字一般采用下面的形式：（符号类，符号值）属性字是符号的机内表示，有统一固定的长度3.4词法分析程序的实现10/1/202379中南大学软件学院陈志刚属性字词法分析程序对说明部分不做语义处理。3.4词法分析程源程序的输入在内存开辟缓冲区，将程序文本放进该缓冲区预处理：删除无用字符等词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。起始指针搜索指针3.4词法分析程序的实现10/1/202380中南大学软件学院陈志刚源程序的输入在内存开辟缓冲区，将程序文本放进该缓冲区起始指针超前搜索词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。3.4词法分析程序的实现10/1/202381中南大学软件学院陈志刚超前搜索词法分析程序在读取单词时，为了判断是否已读入整个单词关键字的识别与查表算法对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。查找算法：线性查找折半查找Hash函数3.4词法分析程序的实现10/1/202382中南大学软件学院陈志刚关键字的识别与查表算法对于关键字，先把它们当成标识符，然后去出错处理对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。3.4词法分析程序的实现10/1/202383中南大学软件学院陈志刚出错处理对定义外的（如，对首字符不是字母的，不是数字的，不是使用状态图设计词法分析程序多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言都可以被状态图识别。使用状态图设计词法分析程序的步骤如下：对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图对状态图的每一个终点编一段相应的子程序。3.4词法分析程序的实现10/1/202384中南大学软件学院陈志刚使用状态图设计词法分析程序多数语言的词法规则可用正则文法和正201字母字母|数字其它3456数字数字其它+-78*/9101113<=>:;1617其它13=举例10/1/202385中南大学软件学院陈志刚201字母字母|数字其它3456数字数字其它+-78*/91本节讨论：用正规式描述单词符号，并研究如何从正规产生识别这些单词符号的词法分析程序。3.5词法分析器的自动生成10/1/202386中南大学软件学院陈志刚本节讨论：3.5词法分析器的自动生成8/8/202386中一、LEX语言一个LEX语言程序经过编译后得到的结果程序，其作用相当于一个DFA，可用来识别和产生单词也就是说其功能即为一个词法分析器。10/1/202387中南大学软件学院陈志刚一、LEX语言一个LEX语言程序经过编译后得到的结果程序，其一个LEX源程序包括两部分：辅助定义式和识别规则1、辅助定义式D1→R1

Dn→Rn其中Ri为正规式，只允许出现∑上字符D1,…,Di-1；Di为这个正规式Ri的简名例1．Letter→A|B|…|ZDigit→0|1|…|9Id→Letter(Letter|Digit)*...10/1/202388中南大学软件学院陈志刚一个LEX源程序包括两部分：辅助定义式和识别规则.8/8/22.识别规则P1{A1}...Pm{Am}其中，Pi称为词形，为正规式(∑∪{D1,…,Dm})Ai称为词形Pi的动作（程序）显然：一个LEX源程序产生的词法分析器只能识别形如Pi的单词。10/1/202389中南大学软件学院陈志刚2.识别规则8/8/202389中南大学软件学院陈志刚二、LEX的实现LEX编译程序的目的是把一个LEX程序改造为一个词法分析器L，这个词法分析器