第3章词法分析.ppt

第第3章章 词法分析词法分析学习目标学习目标:v掌掌握握：词词法法分分析析程程序序的的构构造造方方法法，正正规规式式和和正正规规文文法法到到有有穷穷自自动动机机的的转转换换，N NFAFA到到DFADFA的的转转换换、DFADFA的的化化简简v理解：理解：正规文法、正规式、正规文法、正规式、DFADFA的概念、的概念、NFANFA的概念的概念v了解：词法分析程序的自动构造工具了解：词法分析程序的自动构造工具v词法分析（词法分析（lexical analysislexical analysis）任务：逐个读入源程序字符并按照构词规则切分任务：逐个读入源程序字符并按照构词规则切分成一系列单词。成一系列单词。词法分析是编译过程中的一个阶段，在语法分析词法分析是编译过程中的一个阶段，在语法分析前进行。也可和语法分析结合在一起作为一遍，前进行。也可和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词供语法分析使用。单词单词是语言中具有独立意义的是语言中具有独立意义的最小单位最小单位，包，包括保留字、标识符、运算符、标点符号和常括保留字、标识符、运算符、标点符号和常量等。量等。3.1 3.1 词法分析程序的功能词法分析程序的功能3.1 词法分析程序的功能（续）词法分析程序的功能（续）源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokenget token.主要任务：主要任务：读源程序，产生单词符号读源程序，产生单词符号 输入是以字符串形式的源程序输入是以字符串形式的源程序输出是以单词符号或单词符号表示的源程序输出是以单词符号或单词符号表示的源程序v词法分析程序：执行词法分析的程序。词法分析程序：执行词法分析的程序。3.2 3.2 单词符号及输出单词的形式单词符号及输出单词的形式1.语言的单词符号语言的单词符号语言的单词符号是指具有独立意义的最小语法单位。语言的单词符号是指具有独立意义的最小语法单位。程序语言的单词符号一般可分为程序语言的单词符号一般可分为5种：种：1基本字（关键字）：如基本字（关键字）：如 else，while，if等等2标识符：用来表示常量、变量、过程等名字标识符：用来表示常量、变量、过程等名字3常数：各种类型的常数常数：各种类型的常数,如如3.14，TRUE等等4运算符：如运算符：如+，*，/5界符：如逗号，分号，括号等界符：如逗号，分号，括号等3.2 3.2 单词符号及输出单词的形式单词符号及输出单词的形式2.词法分析程序输出单词的形式词法分析程序输出单词的形式n 二元式（二元式（单词种别单词种别，单词自身的值单词自身的值）u种别表示单词种类，是语法分析需要的信息种别表示单词种类，是语法分析需要的信息u自身值是编译其他阶段需要的信息自身值是编译其他阶段需要的信息种别编码种别编码(常用整数编码常用整数编码)方方法法一一：按按单单词词的的5 5大大种种类类每每种种一一个个码码，例例如如标标识识符符为为l l，常常数数为为2 2，基基本本字字为为3 3，运运算算符符为为4 4，界界符符为为5 5。方方法法二二：每每个个基基本本字字一一个个编编码码；所所有有标标识识符符为为一一个个编编码码；常常数数按按类类型型分分类类，每每类类一一个个编编码码；每每个个运算符一个编码；每个界符一个编码。运算符一个编码；每个界符一个编码。3.2 单词符号及输出单词的形式单词符号及输出单词的形式单词自身值单词自身值如如一一个个种种别别只只含含一一个个单单词词符符号号，则则该该单单词词符符号种别编码就完全代表它自身的值。号种别编码就完全代表它自身的值。如如一一种种别别含含多多个个单单词词符符号号，则则对对于于每每个个单单词词符符号号，除除了了种种别别编编码码还还要要给给出出单单词词符符号号自自身身值。值。p对基本字对基本字,运算符运算符,界符一般是一符一种别。界符一般是一符一种别。p标识符自身值就是自身的字符串。标识符自身值就是自身的字符串。p常数自身值就是常数本身的二进制。常数自身值就是常数本身的二进制。v假定基本字、运算符和界符都是一符一种别。假定基本字、运算符和界符都是一符一种别。v例：例：if(a1)b=100;词法分析后输出的单词序列是词法分析后输出的单词序列是:(2,)if(29,)(10,a)a(23,)(11,1的二进制的二进制)1(30,)(10,b)b(17,)=(11,100的二进制的二进制)100(26,);标识符种别编码：标识符种别编码：10 10 常数的种别编码：常数的种别编码：1111基本字种别编码：基本字种别编码：2 2赋值号种别编码：赋值号种别编码：1717大于号种别编码：大于号种别编码：2323分号的种别编码：分号的种别编码：2626左括号种别编码：左括号种别编码：2929右括号种别编码：右括号种别编码：3030例如例如 源程序源程序if i=5 then x=y;种别编码：标识符为种别编码：标识符为1，常数为，常数为2，基本字为，基本字为3，运算符为运算符为4，界符为，界符为5词法分析后输出的单词序列是词法分析后输出的单词序列是:(3,if)(1,指向指向i的符号表入口的符号表入口)(4,=)(2,5)(3,then)(1,指向指向x的符号表入口的符号表入口)(4,=)(1,指向指向y的符号表入口的符号表入口)(5,;)3.3 3.3 语言单词符号的两种定义方式语言单词符号的两种定义方式n定义方式定义方式:正规文法正规文法 正规式正规式(Regular Expression)(Regular Expression)v作用作用:描述单词的构成规则描述单词的构成规则,基于这类描述工具建立基于这类描述工具建立词法分析技术词法分析技术,进而实现词法分析程序的自动构造。进而实现词法分析程序的自动构造。v多数程序设计语言的多数程序设计语言的单词符号单词符号都能用正规文法或正都能用正规文法或正规式来定义。规式来定义。3.3.1 3.3.1 正规文法正规文法n正规文法回顾正规文法回顾p文法的任一产生式文法的任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中其中A,BVA,BVN N,aVaVT T ABaABa或或AaAa，其中其中A A,BVBVN N ,aVaVT T p正规文法描述的是正规文法描述的是V VT T*上上的的正规语言正规语言例如例如 :用用l l表示表示a az z中的任一英文字母，中的任一英文字母，d d表示表示0 09 9中任一数字中任一数字描述标识符的正规文法为描述标识符的正规文法为 llll lld dll dd 描述无符号整数的正规文法描述无符号整数的正规文法 dddd 3.3.1 正规文法（续）正规文法（续）3.3.2 正规式正规式(正则表达式正则表达式)与正规集与正规集v正规式表示一个字符串集合即正规集。正规式表示一个字符串集合即正规集。v正规集是正规语言的另一种表示法。正规集是正规语言的另一种表示法。一、一、设有字母表设有字母表=a1,a2,an，在字母表上的，在字母表上的正规式和它所表示的正规集定义如下：正规式和它所表示的正规集定义如下：1.和和都是都是上的正规式，它所表示的正规集分上的正规式，它所表示的正规集分别为别为和和即空集；即空集；2.任任何何，是是上上的的正正规规式式，它它所所表表示示的的正正规集为；规集为；3.假假定定1和和2都都是是上上的的正正规规式式，他他们们所所表表示示的的正正规规集集分分别别为为(1)和和(2)，那那么么，以以下下也也都是正规式和它们所表示的正规集；都是正规式和它们所表示的正规集；正规式正规式正规集正规集12(1)(2)e12(1)(2)1(1)4.仅由仅由有限次有限次使用上述三步定义的表达式才是使用上述三步定义的表达式才是上上的正规式，仅由这些正规式所表示的字符串集才是的正规式，仅由这些正规式所表示的字符串集才是上的正规集。上的正规集。其中其中v“”读为读为“或或”“”读为读为“连接连接”；v“”读为读为“闭包闭包”(任意有限次的自重复连接任意有限次的自重复连接)。v 规定算符的优先顺序为规定算符的优先顺序为“”、“”、”。v 连接符连接符“”一般可省略不写。一般可省略不写。v“”、“”和和“”都是左结合的。都是左结合的。3.3.2 正规式与正规集正规式与正规集(续续)例例1 1，令，令=a=a，bb，上的正规式和相应的上的正规式和相应的正规集有正规集有正规式正规式正规集正规集a aaaa a b b a,b a,babab abab(a(a b)(ab)(a b)b)aa,ab,ba,bbaa,ab,ba,bb a a ,a,aaa,aa,任意任意个个a a串串(a a b)b),a,b,aa,aba,b,aa,ab 所有由所有由a a 和和b b组成的串组成的串 3.3.2 正规式与正规集正规式与正规集(续续)v例例2 2 =l=l，dd，r=l(lr=l(l d)d)定义的正规集定义的正规集:l,ll,ld,ldd,l,ll,ld,ldd,（标识符）（标识符）v例例3 3 =d=d，.，e e，+，-,-,则则 上的正规式上的正规式 d d(.(.dddd)(e(+)(e(+-)-)dddd)表示的是无符号数的集合。表示的是无符号数的集合。其中其中d d为为0 09 9的数字。的数字。v若两个正规式若两个正规式e1e1和和e2e2所表示的正规集相同所表示的正规集相同,则说明则说明e1e1和和e2e2等价等价,写作写作e1=e2e1=e2。例如：例如：e1=(ae1=(a b)b)，e2=b e2=b a a二、两二、两 个个 正正 规规 式式 等等 价价3.3.2 正规式与正规集正规式与正规集(续续)三、正规式的代数性质三、正规式的代数性质设设 A，B，C 是正规式，正规式服从的代数规律是正规式，正规式服从的代数规律1.AB=BA “或或”满足交换律满足交换律2.A(BC)=(AB)C “或或”的结合律的结合律3.(AB)C=A(BC)“连接连接”的结合律的结合律4.A(BC)=ABAC5.(AB)C=ACBC分配分配律律5.A=A=A 是是“连接连接”的恒等元素的恒等元素6.A=A A|=A|A =(A|)7.(A)=A 3.3.2 正规式与正规集正规式与正规集(续续)3.3.3 正规文法和正规式间的转换正规文法和正规式间的转换正规文法与正规式都是描述正规集的工具。正规文法与正规式都是描述正规集的工具。对任意一个正规文法，存在一个定义同一语对任意一个正规文法，存在一个定义同一语言的正规式言的正规式对任意一个正规式，存在一个定义同一语言对任意一个正规式，存在一个定义同一语言的正规文法的正规文法将将正正规规文文法法中中的的每每个个非非终终结结符符表表示示成成关关于于它它的的一一个个正正规规式式方方程程即即“|”用用“+”替替换换，“-”用用“=”替替换换，获得一个联立方程组。，获得一个联立方程组。依依据据求求解解规规则则和和正正规规式式代代数数性性质质，求求的的只只剩剩一一个个开始符号开始符号定义的正定义的正规规式式,且不含且不含非终结符。非终结符。正正规规文法到正文法到正规规式的转换规则式的转换规则:文法产生式文法产生式解（正解（正规规式）式）规则规则1 1AxB ByAxB By（A=xBA=xB，B=yB=y）A=xyA=xy规则规则2 2AxA|y (A=xA+y)AxA|y (A=xA+y)AAx|y (A=Ax+y)AAx|y (A=Ax+y)A=xA=x*y yA=yxA=yx*规则规则3 3Ax AyAx AyA=x|yA=x|y1.1.正规文法到正规式的转换正规文法到正规式的转换例：将文法例：将文法GS转换成正规式转换成正规式 G：Sa A|a AdA|d先由产生式得先由产生式得:S=aA+a A=dA+d=d*d将将A代入代入S中得中得:S=a（d*d)+a利用正利用正规规式变换得式变换得S=a(d*d+)=ad*说明说明:d*d|=(|d|dd|)d|=d|dd|=d*所求正规式为所求正规式为ad*例：将文法例：将文法GZ转换成正规式转换成正规式 G：Z0A A0A|0B B 1A|先由产生式得先由产生式得:B=1A|将将B代入代入A中得中得:A=0A|0(1A|)A=0A|01A|0=(0|01)A|0利用规则利用规则（A-xA|y）得得:A=(0|01)*0 将将A代入代入Z中得中得:Z=0(0|01)*0即为所求正规式即为所求正规式例：将描述标识符的文法转换成正规式例：将描述标识符的文法转换成正规式 l|l|d 提取公因子提取公因子:=l|(l|d)=(l|d)|l利用规则利用规则(A-Ax|y)得得:=l(l|d)*即为所求正规式即为所求正规式将将上的一正规式上的一正规式r r转换成文法转换成文法G=(VG=(VN N,V,VT T,S,P),S,P)方法方法V VT T=,=,首先形规则首先形规则SrSr,S,S为为G G的开始符的开始符不断利用下面的规则做变换不断利用下面的规则做变换,直到直到每个产生式最多每个产生式最多含有一个终结符为止含有一个终结符为止原产生式原产生式变换后产生式变换后产生式规则规则1 1AxyAxyAxB ByAxB By规则规则2 2AxAx*y yAxA Ay AxA Ay 即即AxA|yAxA|y规则规则3 3Ax|yAx|yAx AyAx Ay其中其中B B为一新非终结符为一新非终结符2.2.正规式到正规文法的转换正规式到正规文法的转换例例1 将将R=a(a|d)*转换成相应的正规文法转换成相应的正规文法令转换成文法令转换成文法G=(VN,VT,P,S)其中其中VT=a,d，文法开始符为文法开始符为S首先形成首先形成Sa(a|d)*,然后变换然后变换SaA A(a|d)*A(a|d)A|AaA|dA|最终有产生式：最终有产生式：SaA，A，AaA，AdA例例:将将R=(a|b)(aa)*(a|b)转换成相应的正规文法转换成相应的正规文法令转换成文法令转换成文法G=(VN,VT,P,A)其中其中VT=a,b，文法开始符为文法开始符为A首先形成首先形成A(a|b)(aa)*(a|b),然后变换然后变换A(a|b)B B(aa)*(a|b)BaaB|(a|b)最终产生式：最终产生式：AaB,AbB,BaC,Ba,Bb,CaBBaC|a|b CaB3.4 有穷自动机有穷自动机(也称有限自动机也称有限自动机)v是具有离散输入与输出系统的一种抽象数学模型是具有离散输入与输出系统的一种抽象数学模型v作用作用:能准确地识别正规集，即识别正规文法所定能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合义的语言和正规式所表示的集合v意义意义:为词法分析程序的自动构造提供了理论基础。为词法分析程序的自动构造提供了理论基础。v分类分类:确定的有穷自动机确定的有穷自动机(Deterministic Finite Automata)(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机(Nondeterministic Finite Automata)(Nondeterministic Finite Automata)3.4.1 确定的有穷自动机（确定的有穷自动机（DFA）一一.定义定义:一个一个DFA MDFA M是一个五元组是一个五元组:M=M=（Q Q，f f，S S，Z Z）1.1.Q Q是一有穷状态集，每个元素称为一个状态是一有穷状态集，每个元素称为一个状态2.2.是是一一个个有有穷穷字字母母表表，每每个个元元素素称称为为一一个个输输入入字符字符3.3.f f是是一一个个从从QQQQ的的单单值值映映射射。f(qf(qi i,a,a)=)=q qj j意意味味着着当当前前状状态态为为q qi i、输输入入字字符符为为a a时时，将将转转换换到到下一状态下一状态q qj j(唯一的后继状态）唯一的后继状态）4.4.SQSQ，是是唯一唯一的初态。的初态。5.5.Z Z Q,Q,是是一一个个终终态态集集，终终态态也也称称为为可可接接受受状状态态或结束状态。至少由一个终止状态组成。或结束状态。至少由一个终止状态组成。例例DFA M=DFA M=（SS，U U，V V，Q,aQ,a，b,f,S,Qb,f,S,Q）其中其中f f定义为：定义为：f f（S S，a a）=U=Uf f（S S，b b）=V=V f f（V V，a a）=U=Uf f（V V，b b）=Q=Q f f（U U，a a）=Q=Qf f（U U，b b）=V=V f f（Q Q，a a）=Q=Qf f（Q Q，b b）=Q=Q3.4.1 确定的有穷自动机（续）确定的有穷自动机（续）二二.DFA表示成状态转换图表示成状态转换图(Transition Diagram)每个状态对应图中的一个结点：每个状态对应图中的一个结点：初态为唯一初态结点，用初态为唯一初态结点，用=标记；标记；终态对应终态结点，用终态对应终态结点，用双圈双圈表示。表示。若若有有f(qi,a)=qj，则则从从结结点点qi到到结结点点qj画画标标记为记为a的的有向弧有向弧。3.4.1 确定的有穷自动机（续）确定的有穷自动机（续）例例DFA M=DFA M=（SS，U U，V V，Q,aQ,a，b,f,S,Qb,f,S,Q）f f（S S，a a）=U=Uf f（S S，b b）=V=V f f（V V，a a）=U=Uf f（V V，b b）=Q=Q f f（U U，a a）=Q=Qf f（U U，b b）=V=V f f（Q Q，a a）=Q=Qf f（Q Q，b b）=Q=Q状态转换图表示为状态转换图表示为:bSUVQaaaba，bb三三.DFA表示成状态转换矩阵（转换表）表示成状态转换矩阵（转换表）例例DFA M=DFA M=（SS，U U，V V，Q,aQ,a，b,f,S,Qb,f,S,Q）f f（S S，a a）=U=Uf f（S S，b b）=V=V f f（V V，a a）=U=Uf f（V V，b b）=Q=Q f f（U U，a a）=Q=Qf f（U U，b b）=V=V f f（Q Q，a a）=Q=Qf f（Q Q，b b）=Q=Q字符字符状态状态0001行表示状态，用行表示状态，用双箭头双箭头“=”“=”标标明初态；否则第明初态；否则第一行即是初态一行即是初态列表示输入字符列表示输入字符相应状态行和输相应状态行和输入字符列下的新入字符列下的新状态，即状态，即k k行行a a列列为为f(k,a)f(k,a)的值的值相应终态行在表相应终态行在表的右端标以的右端标以1 1，非终态标以非终态标以0 0四四.DFA识别识别(接受接受)字符串字符串对于对于*中的任何字符串中的任何字符串，若存在一条从，若存在一条从初态结到某一终态结的通路，且该通路上初态结到某一终态结的通路，且该通路上所有弧的标记符连接成的字符串等于所有弧的标记符连接成的字符串等于，则称则称可以为可以为 DFA M所识别所识别若若DFA M的初态结同时又是终态结，则的初态结同时又是终态结，则可为可为M所识别。所识别。3.4.1 确定的有穷自动机（续）确定的有穷自动机（续）例：证明例：证明 t=baab 被如下的被如下的 DFA 所接受所接受DFA M=（S,U,V,Q,a,b,f,S,Q）其中其中 f 定义为：定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V,b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q3.4.1 确定的有穷自动机（续）确定的有穷自动机（续）证明：证明：f（S，baab）=f（f（S，b），），aab）=f（V，aab）=f（f（V，a），），ab）=f（U，ab）=f（f（U，a），），b）=f（Q，b）=QQ属于终态。得证。属于终态。得证。bSUVQaaaba，bb六六.确定的有穷自动机（确定的有穷自动机（DFA）识别的语言）识别的语言vDFA M=（Q，f，S，Z）所能接受）所能接受的符号串的全体记为的符号串的全体记为 L(M)L(M)=x|f(S,x)Z,x bq0q1q2abaa，b所识别的语言为所识别的语言为ba*3.4.1 确定的有穷自动机（续）确定的有穷自动机（续）v结论：结论：上一个字符串集上一个字符串集 V 是正规集，当且是正规集，当且仅当，存在一个仅当，存在一个 上的确定有穷自动机上的确定有穷自动机 M，使得，使得 V=L(M)。3.4.1 确定的有穷自动机（续）确定的有穷自动机（续）3.4.2 非确定的有穷自动机（非确定的有穷自动机（NFA）一一.NFA的定义的定义 一个不确定的有穷自动机一个不确定的有穷自动机M M是一个五元组：是一个五元组：M=M=（Q Q，f f，S S，Z Z），其中），其中1.1.Q Q是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；2.2.是是一一个个有有穷穷字字母母表表，它它的的每每个个元元素素称称为为一一个个输入字符；输入字符；3.3.f f是是一一个个从从QXQX*至至Q Q的的子子集集的的映映射射；f(qi,af(qi,a)=)=某某些状态的集合些状态的集合 4.4.S S Q Q，是一个是一个非空初态集非空初态集5.5.Z Z Q Q，是一个终态集。是一个终态集。二二.NFA.NFA表示为状态转换图和转换表表示为状态转换图和转换表例例 NFA M=NFA M=（SS，P P，Z,0Z,0，1,f,S1,f,S，P,ZP,Z）其中）其中 f f（S S，0 0）=P =P f f（S S，1 1）=S=S，ZZ f f（Z Z，0 0）=P=P f f（Z Z，1 1）=P=P f f（P P，1 1）=Z=Z矩阵表示矩阵表示:01SPS,ZPZZPP001SPZ00,1111状态图表示状态图表示:3.4.2 非确定的有穷自动机（续）非确定的有穷自动机（续）说明：因为说明：因为NFANFA的转换函数的转换函数f f为为Q Q *到到Q Q的子集的子集的一种映射，所以的一种映射，所以NFANFA中可以中可以有有 转移转移例：例：123abc3.4.2 非确定的有穷自动机（续）非确定的有穷自动机（续）三三.NFA识别的字符串识别的字符串对对于于*中中的的任任何何字字符符串串t，若若存存在在一一条条从从某某一一初初态态结结到到某某一一终终态态结结的的通通路路，且且该该通通路路上上所所有有弧弧的的标标记记字字依依次次连连接接成成的的串串等等于于t，则则称称t可可以以被被 NFA M所识别。所识别。若若M的的某某个个初初态态结结又又是是终终态态结结，或或者者存存在在一一条条从从某某个个初初态态结结到到某某个个终终态态结结的的通通路路，那那么么为为M所识别。所识别。123abc3.4.2 非确定的有穷自动机（续）非确定的有穷自动机（续）SPZ00,1111状态图表示状态图表示:描述的语言为：描述的语言为：1*（1|01）（）（0|1）1）*串串101识别通路识别通路四四.NFA M.NFA M 所能识别的符号串的全体记为所能识别的符号串的全体记为L(M),L(M),即为所即为所识别的语言。识别的语言。3.4.2 非确定的有穷自动机（续）非确定的有穷自动机（续）五五.NFA.NFA与与DFADFA的关系的关系NFANFA弧弧上上的的标标记记可可以以是是*中中的的一一个个字字，而而不不一一定定是是单个字符；单个字符；DFADFA是是NFANFA的特例的特例.对对 于于 任任 何何 两两 个个 有有 穷穷 自自 动动 机机 M M和和 MM，如如 果果L(M)=L(M)L(M)=L(M)，则称，则称M M与与MM是等价的是等价的对对 于于 每每 个个 NFA M存存 在在 一一 个个 DFA M，使使 得得 L(M)=L(M)。亦即。亦即DFA与与NFA描述能力相同。描述能力相同。3.4.2 非确定的有穷自动机（续）非确定的有穷自动机（续）NFANFA很难用计算机程序模拟很难用计算机程序模拟.DFADFA作为词法分析模型作为词法分析模型.六六.利用利用DFADFA构造词法分析程序方法构造词法分析程序方法从语言的单词描述中可直接构造出从语言的单词描述中可直接构造出NFANFA将将NFANFA确定化为确定化为DFADFA对对DFADFA进行化简进行化简对对DFADFA的的每每个个状状态态编编码码，形形成成词词法法分分析析程程序序3.4.2 非确定的有穷自动机（续）非确定的有穷自动机（续）3.4.3 3.4.3 由正规表达式由正规表达式R构造构造NFAv等价性等价性1.1.对于对于上的一个上的一个NFA MNFA M，可以构造一个，可以构造一个上的上的正规式正规式R,R,使得使得L(R)=L(M)L(R)=L(M)。2.2.对于对于上的一个正规式上的一个正规式R R，可以构造一个，可以构造一个上上的的NFA MNFA M，使的，使的L(M)=L(R)L(M)=L(R)。一一.从从正规式正规式构造构造NFANFA方法方法（1 1）引进初始节点）引进初始节点X,X,终止节点终止节点Y Y，R R表示成拓广转换图表示成拓广转换图（2 2）分析）分析R R的语法结构，用如下规则构造的语法结构，用如下规则构造NFANFA对于对于R=R=,构造的构造的NFANFA为为:yx 对于对于R=R=a,aa,a 构造的构造的NFANFA为为:yxa ayx对于对于R=R=,构造的构造的NFANFA为为:3.4.3 由正规表达式由正规表达式R构造构造NFA（续）（续）复合正规式复合正规式R的构造规则的构造规则先构造如右边的先构造如右边的NFA：yxR R然后按下述三种情况进行分解，直至每条弧上然后按下述三种情况进行分解，直至每条弧上标记都为一个基本字符为止。标记都为一个基本字符为止。e e1 1Xye=e1|e2e e2 2X1e e1 1ye2e=e1e2X1ye1e=e1*(3)整个分裂过程中，所有新结点采用不同名字，整个分裂过程中，所有新结点采用不同名字，XY保留保留3.4.3 由正规表达式由正规表达式R构造构造NFA（续）（续）例：为例：为 R=(a|b)*abb构造构造 NFA M，使得，使得L(M)=L(R)X(a|b)*abbYX (a|b)*1a 2bb 3 YX 4 1 b 3 a 2 b a|b YX 4 1 b 3 a 2 b a b Y3.4.4 NFA确定化为确定化为DFA的方法的方法一一.从从NFA构造构造DFA的算法的算法子集法子集法1.子集构造法基本思想子集构造法基本思想 用子集构造用子集构造NFA M的状态转换矩阵，即列出它的的状态转换矩阵，即列出它的每个子集及该子集相对于每个输入符号的后继子每个子集及该子集相对于每个输入符号的后继子集。让集。让DFA 的每个状态对应的每个状态对应NFA 的一个子状态集的一个子状态集合。即合。即DFA用它的一个状态记录在用它的一个状态记录在NFA读入一个读入一个输入符号后可能达到的所有状态。输入符号后可能达到的所有状态。ABaaNFANFA状转换态图状转换态图bbb3.4.4 NFA确定化为确定化为DFA的方法（续）的方法（续）abAA,BBBA,BA,B A,BA,B输入输入状态子集状态子集DFA的状态转换矩阵的状态转换矩阵ab02112222输入输入状态状态NFA的状态转换矩阵的状态转换矩阵原原NFA的初态仍作为的初态仍作为DFA的初态，含有原的初态，含有原NFA 的终的终态的所有子集都是态的所有子集都是DFA的终态，即初态为的终态，即初态为0，终态为，终态为1和和2。2.NFA构造等价构造等价DFA子集法子集法 输入：一个输入：一个NFA N 输出：一个接受（识别）相同语言的输出：一个接受（识别）相同语言的DFA M 方法：利用构造方法：利用构造-closure的方法将的方法将NFA确定化为确定化为DFA 消除消除弧弧3.4.4 NFA确定化为确定化为DFA的方法（续）的方法（续）状态合并状态合并aijkmabn（a）i,jmkaabn（b）3.4.4 NFA确定化为确定化为DFA的方法（续）的方法（续）0123aabc（c）01,23abc（d）3.-closure相关概念相关概念(1)设设I I是是NFANFA的状态子集，则的状态子集，则-closure(I I)定义：是定义：是状状态态I I中的任何状态中的任何状态s s以及从以及从s s出发经任意条出发经任意条弧而能弧而能到达的状态的集合。到达的状态的集合。IIS2S2S1S1S3S3-Closure(I)即即DFA的一个状态的一个状态3.4.4 NFA确定化为确定化为DFA的方法（续）的方法（续）设设I=0，则，则_closure(I)=例：例：NFA M100124536789ababb74,2,1,0,(2)Ia子集。子集。I是是NFA一一状状态态子子集集，由由I中中的的状状态态出出发发，经经过过一一条条a弧弧可可能能到到达达的的状状态态的的集集合合称称为为I后后继子集即继子集即f（I，a），则），则Ia=_closure(f(I,a)3.4.4 NFA确定化为确定化为DFA的方法（续）的方法（续）例：例：I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；f(1,2,a)=5,4,3-closure(5,3,4)=5,4,3,6,2,8,7；12534687aa a3.4.4 NFA确定化为确定化为DFA的方法（续）的方法（续）Ib =_closure(例例NFA:100124536789ababb设设I=0,1,2,4,7则则Ia =_closure()3,8=3,8,6,7,1,2,4 5 6,)=5,7,2,1,43.4.4 NFA确定化为确定化为DFA的方法（续）的方法（续）4.4.构造构造DFADFA的状态集的算法的状态集的算法 假设假设NFA N=(Q,f,S,Z)NFA N=(Q,f,S,Z)构造构造DFADFA为为 D=(Q,f,S,Z)D=(Q,f,S,Z)的基本方法是：的基本方法是：u首先求首先求-closure(S)作为作为D D的初态的初态S,S,然然后从后从SS出发，经过对输入符号出发，经过对输入符号aa的状的状态转移所能到达的状态所组成的集合作为态转移所能到达的状态所组成的集合作为M M的新状态即的新状态即-closure(f(S,a)，如此重复，如此重复，直到不再有新的状态出现。直到不再有新的状态出现。u具体的算法描述具体的算法描述3.4.4 NFA确定化为确定化为DFA的方法（续）的方法（续）(1)(1)开始，开始，DFA MDFA M中状态中状态QQ、ZZ为空集为空集(2)S=-closure(s),(2)S=-closure(s),并将并将SS置为未标记（新）状态，置为未标记（新）状态，加入到加入到QQ中中(3)(3)如果如果QQ中存在未标记状态中存在未标记状态T=qT=q1 1,q,q2 2,q,qn n,则进行如下变换则进行如下变换（以求得（以求得ff(T,a)(T,a)（aa ）,即即DFADFA中中T T的后继状态的后继状态U U）。）。U=TU=Ta a 即即-closure(-closure(f f(T,a)(T,a)）U=-closure(f(q1,a)U=-closure(f(q1,a)f(q2,a)f(qn,a)if if（U U不在不在QQ中）中）thenthen将将U U做为未被标记的子集加入做为未被标记的子集加入QQ中中,f(T,a),f(T,a)添加添加M M中中 if Uif U中至少含有一个元素是中至少含有一个元素是N N的终态，的终态，U U添加到添加到ZZT T置标记置标记(4)(4)重复（重复（3 3），直到），直到QQ中没有未标记状态中没有未标记状态(5)(5)重命名重命名QQ中的状态，获得等价的中的状态，获得等价的DFADFANFA N=(Q,f,S,Z)构造构造DFA为为 M=(Q,f,S,Z)-closure(f(Ti,a)-closure(f(Ti,b)T0=-closure(0)=0,1,2,4,71,2,3,4,6,7,8加入为加入为T11,2,4,5,6,7 加入为加入为T2T1=1,2,3,4,6,7,81,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7,9 加入为加入为T3T2=1,2,4,5,6,71,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2T3=1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在已存在T11,2,4,5,7,10 加入为加入为T4T4=1,2,4,5,7,10 1,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2100124536789ababb5.重新命名重新命名DFA的状态的状态得到得到DFA的状态转换矩阵和转换图如下的状态转换矩阵和转换图如下:S a b0 1 21 1 32 1 23 1 44 1 240b213bbaaababa000013.4.5 DFA化简（化简（DFA最小化）最小化）DFA 化化简简：是是指指寻寻找找一一个个状状态态数数比比DFA M少少的的DFA M,使得使得L(M)=L(M)v最少状态最少状态DFA需满足条件需满足条件没有多余状态没有多余状态(死状态死状态)没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）3.4.5 DFA的化简（续）的化简（续）多多余余状状态态：从从开开始始状状态态出出发发任任何何可可识识别别输输入入串串都都无无法到达的状态。法到达的状态。等价状态等价状态：两个状态两个状态s和和t等价的条件是等价的条件是:设设DFA M=(Q,f,S0,F),对对任任何何a*,f(s,a)F,当当且且仅仅当当f(t,a)F。即即如如果果从从状状态态s出出发发能能读读出出某某字字符符串串a而而停停止止于于终终态态，同同样样，从从t出出发发也也能能读读出出a而停止于终态。而停止于终态。n可可区区别别状状态态：不不等等价价状状态态。如如终终态态与与非非终终态态是是可可区区别的。别的。n例如空串例如空串区分任何终态和非终态。区分任何终态和非终态。s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8转换后的转换后的DFAs1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8含多余状态的含多余状态的DFAs1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7化解的化解的DFAn消消 除除 多多 余余 状状 态态3.4.5 DFA的化简（续）的化简（续）aCDBAEFSbaaaaabbbbbba例例C C和和F F同是终态同是终态,C,C和和F F读入读入a a都到达都到达C,C,读入读入b b都到达都到达E,E,所以所以 C C和和F F等价等价S S和和C C不等价，因为不等价，因为C C是终态，而是终态，而S S不是终态不是终态n等价与不等价状态等价与不等价状态3.4.5 DFA的化简（续）的化简（续）1.DFA1.DFA的最小化基本思想的最小化基本思想u把一个把一个DFADFA的状态分成一些互不相交的子集，使的状态分成一些互不相交的子集，使得任何两个术语不同的子集的状态都是可区别得任何两个术语不同的子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。的，而同一子集中的任何两个状态都是等价的。u然后在每个子集中任取一个状态作然后在每个子集中任取一个状态作“代表代表”，而删去子集中其余状态，并把射向其余状态的而删去子集中其余状态，并把射向其余状态的箭弧都改