《ch2 词法分析.ppt》由会员分享，可在线阅读，更多相关《ch2 词法分析.ppt（167页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2章章词法分析词法分析数计学院数计学院张晓红张晓红2023/1/41词法分析词法分析l第一第一阶段：保段：保证构构词的正确的正确l输入：字符流入：字符流l输出：出：单词流流l分析的依据：分析的依据：词法法规则（如：（如：标识符被定符被定义为字母开字母开头的字母数字串）的字母数字串）l主要任主要任务：分离并分离并输出出单词（保（保证单词符合符合词法法规则）；）；输出出单词的的值和种和种类。构造符号表、常量表；构造符号表、常量表；发现并并报告告词法法错误。概述概述l构造构造编译程序程序,必必须了解源了解源语言的言的词法法规则、语法法规则、语义规则。l正正则表达式（表达式（2.1）是一种描述是一
2、种描述词法法规则的有效的有效工具工具。l有有穷自自动机（机（2.2）是是一一种种识别正正则表达式所描表达式所描述述单词的有效工具。的有效工具。单词单词识别的过程识别的过程(1）把）把单词的的结构用构用正正规式表达式式表达式描述描述；(2）把正）把正规式式转换为一一个不确定的有个不确定的有穷自自动机机NFA；(3）把）把NFA转换为相相应的确定的有的确定的有穷自自动机机DFA；(4）基于）基于DFA构造构造词法分析程序法分析程序。本章内容本章内容l正正则表达式表达式lFA概述概述lDFA定定义lNFA定定义lNFA的确定化（的确定化（NFA到到DFA的的转换）lDFA的最小化的最小化l正正则表达
3、式与表达式与NFA的的转换lDFA在在计算机中的表示算机中的表示l模模拟DFAl模模拟NFAl词法分析的法分析的实现正规文法正规文法l某种程序某种程序设计语言中的言中的所有所有单词构成一种构成一种语言言。l正正规表达式表达式是描述是描述词法分析所要法分析所要识别的的单词的的结构构和好、集合一和好、集合一种工具。种工具。有关概念有关概念l字母表字母表/符号符号集集：是符号的有：是符号的有穷非空集合。非空集合。l汉语符号表包括符号表包括：汉字、数字、字、数字、标点符号等点符号等l语言符号表包括言符号表包括：字母、数字、若干：字母、数字、若干专用符号以及用符号以及main、if等保留字。等保留字。l
4、符号符号：符号表中的元素。：符号表中的元素。l符号串符号串：符号表的符号：符号表的符号组成的任何有成的任何有穷序列。序列。l例：例：=0=0，1 1 符号集符号集 符号串有符号串有：0 0，1 1，0000，0101，1010，1111l例：例：=a=a，b b，c c 符号集符号集符号串有符号串有：a a，b b，c c，abab，aacaaaca有关概念有关概念l符号串的符号串的长度度：符号串：符号串x有有m个符号，个符号，则长度就度就为m，表示，表示|x|=m。l如：如：ababa则长度是度是5l空符号串空符号串：不含任何符号的符号串，用：不含任何符号的符号串，用表示表示|=0。符号串的
5、运算符号串的运算l(1)符号串的符号串的头（前（前缀）和尾（后）和尾（后缀）设z=xy，则x是是z的的头，y是是z的的尾尾。l例：例：设z=abc则z的的头是：是：，a，ab，abc则z的尾是：的尾是：，c，bc，abcl(2)符号串的符号串的固有固有头和固有尾和固有尾设z=xy符号串，若符号串，若x非空，非空，则y是是固有尾固有尾；若若y非空，非空，则x是是固有固有头。l例：例：设z=abc则z的固有的固有头是：是：，a，ab则z的固有尾是：的固有尾是：，c，bc符号串的运算符号串的运算l(3)符号串的符号串的连接（并置）接（并置）设x,y是符号串是符号串,连接接xy是是y符号写在符号写在x
6、符号之后。符号之后。l例：例：x=ab,y=MN则xy=abMNl显然：然：x=x=xl(4)符号串的符号串的方方幂设x是符号串，是符号串，则z=xxxx，称，称z为x的方的方幂,记z=xn。l因此因此,x0=,x1=x,x2=xx,x3=xxxl显然然,n0时,有有xn=xxn-1xn-1x符号串的运算符号串的运算l(5)符号串的符号串的集合集合若集合若集合A中的一切中的一切元素都是元素都是某符号集上的某符号集上的符号串符号串，则称称A为该符号集上的符号串集合。符号集上的符号串集合。l(6)符号串符号串集合的乘集合的乘积（笛卡（笛卡尔积）AB=AB=xy|x A且且y bl例：例：A=a,b
7、，B=c,d则AB=ac，ad，bc，bdl(7)符号串符号串集合的方集合的方幂同一符号串集合的乘同一符号串集合的乘积。A0=,A1=A,A2=AA,A3=A2A符号串的运算符号串的运算l(8)闭包（包（*）符号表符号表，用，用*表示表示上所有有上所有有穷长的的串集串集合合，*称称为的的闭包。包。*=0 1 2.n例：符号表例：符号表=0,1则*=,0,1,00,01,10,11,000,001,010符号串的运算符号串的运算l(9)正正闭包包(+)+=1 2.n+称称的正的正闭包。包。用用+表示表示上所有非空有上所有非空有穷长的串集合的串集合。l显然：然：*0+l+*例：符号表例：符号表=0
8、,1则*=0,1,00,01,10,11,000,001,010正规表达式正规表达式正规式正规式正规集正规集和和a（a）ae1和e2(e1)e1|e2e1e2e1*L(e1)和L(e2)L(e1)L(e1)L(e2)L(e1)L(e2)(L(e1)*正规式与正规集的定义：设字母表为，辅助字母表=、|、*、（、）正规表达式正规表达式l l la aa alb bb bl-l(a)a (a)a 一个正一个正规式可以表示若干个符号串式可以表示若干个符号串,l(b)b (b)b 其正其正规集就是集就是这些符号串的集合些符号串的集合la|b a,ba|b a,blab abab abla a*,a,aa
9、,aaa,aaaa,a,aa,aaa,aaaa,.lb b*,b,bb,bbb,bbbb,b,bb,bbb,bbbb,.l-l(a|b)(a|b)*a a和和b b组成的所有串成的所有串la a*|b|b*,a,aa,aaa,aaaa,a,aa,aaa,aaaa,.,b,bb,bbb,bbbb,.,b,bb,bbb,bbbb,.labaaba*以以abab开开头后接若干个后接若干个(包括包括0 0个个)a)a组成的串成的串l(a|b)(a|b)*(aa|bb)(a|b)(aa|bb)(a|b)*上所有含有两个相上所有含有两个相继的的a或两个相或两个相继的的b的的a和和b组成成的串。的串。正规表
10、达式正规表达式l例：令d、e、，则上的正规式d*(.dd*|)(e(+|-|)dd*|)表示的是所有无符号数。l其中：d为09中的数字。l比如：2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。正规表达式正规表达式l设A，B，C为正规式，正规式服从代数规律有：lA|B=B|AlA|(B|C)=(A|B)|ClA(BC)=(AB)ClA(B|C)=AB|AC(B|C)A=BA|CAlA=A=Al(A*)*=A*lA*=|AA*l(AB)*A=A(BA)*l(A|B)*=(A*B*)*=(A*|B*)*lA=b|aA当且当且仅当当A=a*b有穷自动机有穷自动机 FAl有有
11、穷自自动机机FA：l是一种是一种自自动识别装置装置，能正确，能正确识别正正规集集；l是是词法分析程序的工具和方法法分析程序的工具和方法，可自，可自动识别(且是正确且是正确识别）正）正规集。集。l有有穷自自动机机FA分分为：l确定的确定的有有穷自自动机机(DFA）l不确定的不确定的有有穷自自动机机(NFA）有穷自动机有穷自动机 FAl输入符号串入符号串“Iamateacher.”l初始状初始状态0出出发。l状状态1识别：单词“a”l状状态2识别：单词“am”120Ia_I3m_4_5am6a确定的有穷自动机确定的有穷自动机DFAl一个确定的有一个确定的有穷自自动机机DFAM是一个五元是一个五元组
12、：M=(Q，t，q0，F），），其中：其中：lQ是一个有是一个有穷状状态集集，每个元素表示一个状，每个元素表示一个状态；l是一个有是一个有穷字母表字母表，每个元素是一个，每个元素是一个输入字符；入字符；lt是是转换函数函数，是在，是在QQ上的映象，如：上的映象，如：t(qi，a)=qj(qi,qj Q)；含义：当前状态为qi，输入字符a，转换为qj状态lq0是是初初态，q0 Q；lF Q，是是终态集集。l“确定确定”：下一个下一个输入字符惟一地确定了下一个当前状入字符惟一地确定了下一个当前状态.确定的有穷自动机确定的有穷自动机DFAl例：DFA的M：M(S,U,V,Q,a,b,f,S,Q)其中
13、f为：f(S,a)=U,f(S,b)=V,f(U,a)=Qf(U,b)=V,f(V,a)=U,f(V,b)=Qf(Q,a)=Q,f(Q,b)=Q不确定的有穷自动机不确定的有穷自动机NFAl一个不确定的有穷自动机NFAM是一个五元组:M=(Q，t，S，F），其中：Q是一个有穷状态集，每个元素表示一个状态；是一个有穷字母表，每个元素是一个输入字符；t是一个从Q*到Q上的子集的映射；t：Q*2kSQ，是一个非空初态集；FQ，是一个终态集。NFA和和DFA的差别的差别lDFA有一个有一个初始状初始状态，NFA有一个有一个初始状初始状态集集；lDFA的映射是的映射是单值映射，映射，NFA的映射是的映射是
14、多多值映射映射；lDFA不允不允许空空转换，NFA允允许空空转换。不确定的有穷自动机不确定的有穷自动机NFAl例：一个NFAM：M(0,1,2,3,4,a,b,f,0,2,4)其中：f(0,a)=0,3f(2,b)=2f(0,b)=0,1f(3,a)=4f(1,b)=2f(4,a)=4f(2,a)=2f(4,b)=4状态转换图l方法如下：l图的结点表示状态；l初始态用“”或“”表示；l终态点用“”或“”表示；l若f(Ki，a)=Kj，则从状态点Ki到Kj画弧，标记为a。状态转换图l例：DFA的M(S,U,V,Q,a,b,f,S,Q)其中f为：f(S,a)=U,f(S,b)=V,f(U,a)=Q
15、f(U,b)=V,f(V,a)=U,f(V,b)=Qf(Q,a)=Q,f(Q,b)=QUVQaa,bbbbSaa状态转换图状态转换图例例：一个：一个NFAM:M(0,1,2,3,4,a,b,f,0,2,4)其中：其中：f(0,a)=0,3f(2,b)=2 f(0,b)=0,1f(3,a)=4 f(1,b)=2f(4,a)=4 f(2,a)=2f(4,b)=403412abbba,ba,ba,b说明：一个初态，二个终态。说明：一个初态，二个终态。DFA是是NFA的特例的特例。状态转换矩阵状态转换矩阵l方法方法：l行行表示表示状状态l列列表示表示输入字符入字符l元素元素表示相表示相应状状态行和行和
16、输入字符下的入字符下的新状新状态。状态转换矩阵例：DFA的MS,U,V,Q,a,b,f,S,Q)其中f为：f(S,a)=Uf(S,b)=Vf(U,a)=Qf(U,b)=Vf(V,a)=Uf(V,b)=Qf(Q,a)=Qf(Q,b)=QQQQQUVVQUVUSba字符状态状态转换矩阵例：一个NFA，M(0,1,2,3,4,a,b,f,0,2,4)其中：f(0,a)=0,3f(2,b)=2f(0,b)=0,1f(3,a)=4f(1,b)=2f(4,a)=4f(2,a)=2f(4,b)=4ab00,30,11222234444字符状态构形和移动构形和移动l构形：构形：(q,w）lq表示一个状表示一个
17、状态lW是待是待扫描的描的输入串入串l初始构形：初始构形：(q0,w）lq0表示一个初始状表示一个初始状态lW是整个是整个输入串入串l终止构形：止构形：(q,）lq表示一个表示一个终止状止状态l是空串是空串构形和移动构形和移动l移移动：(q,aw）(q,w）lq q为当前状当前状态lawaw为当前待当前待输入串入串lt(q,a)=qt(q,a)=ql表示当前状表示当前状态q q下下输入入a a后到达新状后到达新状态q q，识别了符号了符号a a。接受(识别）的概念l自自动识别单词l对于*中的任何字符串w，若存在一条初态到某一终态的路，且这条路上所有弧的标记符连接成的字符串等于w，则称w可为FA
18、M所接受/识别。l即：FAM=Q,q0,t,F中中w满足足w*，(q0,w）*(q,）,q F时，称为w可为FAM所接受/识别。l若M的初态同时又是终态，则空字可为M所接受。FAM识别的语言识别的语言L(M)lFAM=Q,q0,t,F所所识别的的语言言L(M):L(M)=w|w*，(q0,w）*(q,）,q FFAM所接受/识别的符号串的集合。接受(识别）的理解l设QK，函数f(Q,)=Q，则输入字符串是空串，并停留在原状态上。l输入字符串t(t表示成Tt1形式，T，t1*），在DFAM上运行(移动）的定义为：f(Q,Tt1）=f(f(Q,T),t1），其中QK。Q：当前状态Tt1：当天待输入
19、串f(Q,T)：转换后新状态t1：剩余待输入串接受(识别）的理解l例如：baab字符串被DFA所接受，DFA见上例。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)=Q(Q是终态）lDFAM所能接受的字符串的全体记为L(M）称为语言(也即句子的集合）UVSQaaa,bbbbaaFA的等价性的等价性l对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的。例：例：DFAA=(q0，q1，a，b，t，q0，q0)t(q0，a)=q1，t(q1，b)=q0DFAB=(q0,q1,q2，a
20、，b，t,q0,q0,q2)t(q0,a)=q1，t(q1,b)=q2，t(q2,a)=q1L(A)=L(B)=(ab)n|n0l对于每个NFAM，存在一个DFAM，使得L(M)=L(M)。01ab01ab2aNFA转换为等价的转换为等价的DFA(NFA确定化确定化)lNFADFA(子集法）子集法）l子集构造法lDFA的一个状态是NFA的一个状态集合l读了输入a1 a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk12a开始开始0abbNFA转换为等价的转换为等价的DFAlNFADFA(子集法）子集法）l子集构造法lDFA的一个状态是NFA的一个状态集合l读
21、了输入a1 a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk12a开始开始0abb00,1aNFA转换为等价的转换为等价的DFAlNFADFA(子集法）子集法）l子集构造法lDFA的一个状态是NFA的一个状态集合l读了输入a1 a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk12a开始开始0abb00,1abNFA转换为等价的转换为等价的DFAlNFADFA(子集法）子集法）l子集构造法lDFA的一个状态是NFA的一个状态集合l读了输入a1 a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s
22、2,sk12a开始开始0abb00,1abaNFA转换为等价的转换为等价的DFAlNFADFA(子集法）子集法）l子集构造法lDFA的一个状态是NFA的一个状态集合l读了输入a1 a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk12a开始开始0abb00,1aba0,2bNFA转换为等价的转换为等价的DFAlNFA确定化的确定化的两个步两个步骤(回回顾DFA定定义）：）：l计算下一状算下一状态转移移时：l消除消除状状态转移：移：-closure(T)l消除多于一个的下一状消除多于一个的下一状态转移：移：move(S,a)NFA转换为等价的转换为等价的DFA
23、l-closure(s)：l从状从状态s出出发，不，不经任何字符达到的状任何字符达到的状态的集合。的集合。l包括包括s和和弧到达的新状弧到达的新状态s，以及新状，以及新状态s的的弧到达弧到达的新状的新状态，直到集合不再增大。，直到集合不再增大。l用集合用集合S表示。表示。S=-closure(s)=s f(s,)其中其中f(s)是是NFA中从状中从状态s出出发，仅沿沿弧到达的状弧到达的状态集合。集合。NFA转换为等价的转换为等价的DFANFA转换为等价的转换为等价的DFAl-closure(T)l定定义:l表示从表示从NFA状状态集合集合T的每一状个的每一状个态出出发，沿，沿弧能弧能够到达的所
24、有状到达的所有状态集合。集合。l用集合用集合S表示。表示。lS=-closure(T)=-closure(t,)t TlS=T(f(t,)其中其中f(t,)是是NFA中从状中从状态t出出发，仅沿沿弧到达的状弧到达的状态集合。集合。NFA转换为等价的转换为等价的DFAl算法算法S=T；/结果集合包括果集合包括T集合本身集合本身do S=S；S=S(f(t,)(t S)/T的任一状的任一状态出出发，沿，沿弧能弧能够到达的所有到达的所有状状态while(S=S);NFA转换为等价的转换为等价的DFANFA转换为等价的转换为等价的DFAlDFA的的转移函数移函数move(T,a)l定定义：l表示从状表
25、示从状态集集T的任何一个状的任何一个状态出出发，沿，沿a弧弧转移能移能够到达的所有状到达的所有状态构成的状构成的状态集合集合J。l用集合用集合J表示。表示。J=move(T,a)，即，即J=f(t,a)，t TNFA转换为等价的转换为等价的DFANFA转换为等价的转换为等价的DFAlDFA的状的状态集合：要在集合：要在move(T,a)的基的基础上求上求_closure。即即f(S,a)=_closure(f(t,a)其中其中S是是NFA的状的状态集，集，a。NFA转换为等价的转换为等价的DFANFA转换为等价的转换为等价的DFAl实现从从NFA构造构造DFA的算法的算法-子集构造法子集构造法
26、l已知：已知：一个一个NFAM(,0,),其中其中l是一个有限状是一个有限状态集合。集合。l是一个字母表，它的每个元素称是一个字母表，它的每个元素称为一个一个输入符号。入符号。l0，0称称为初始状初始状态。l，称，称为终结状状态集合。集合。l是一个从是一个从 到的到的子集的映射子集的映射，即，即：NFA转换为等价的转换为等价的DFAl从从NFA构造一个等价的构造一个等价的DFAM=(S,S0,St,),其中其中lS是一个是一个有限状有限状态集合，集合，用用DFA的一个状的一个状态s表示表示NFA的一个状的一个状态子集子集Tj。S=T0，T1，T2TjlDFA与与NFA字母表相同字母表相同。lS
27、0 S，S0为初始状初始状态。S0=-closure(0）lSt，St称称为终结状状态集合集合。是。是包含原包含原终止状止状态的的所有新状所有新状态的集合。的集合。l是一个从是一个从到的到的单值映射映射，表示状，表示状态与状与状态之之间的的转换关系。关系。算法 从NFA构造DFA(子集法）输入输入 NFA NNFA N输出输出 等价的等价的DFA DDFA D。初态含有初态含有NFANFA初态初态，终态集是含有终态集是含有NFANFA终态的状态集合终态的状态集合方法方法 用下述过程构造用下述过程构造DFA DFA：S0=-closure(s0)S0=-closure(s0)作为作为初始状态初始
28、状态加入加入DstatesDstates，且，且尚未标记尚未标记;T=S0;T=S0;while(while(TDstatesTDstates&T T尚未标记尚未标记）标记标记T T;for(for(每一个输入字符每一个输入字符a a）U=U=-closure(-closure(move(Tmove(T，a)a););if(U if(U！DstatesDstates）then then U U加入加入DstatesDstates，且尚未标记，且尚未标记;DtranTDtranT，a=Ua=U;-记录状态转移记录状态转移 T=DstatesT=Dstates中的下一个状态。中的下一个状态。有限自
29、动机的确定化有限自动机的确定化例 构造NFA的DFANFA状态图：有限自动机的确定化有限自动机的确定化1 1、-closure(0)-closure(0)=0,1,2,4,7=0,1,2,4,7 =S1 S1 S1S2S3S2S3S2S4S2S5S2S32 2、标记、标记S1S1：-closure(-closure(move(S1,amove(S1,a）)=1,2,)=1,2,3 3,4,6,7,4,6,7,8 8=S2S2S1S2S2S3S2S3S2S4S2S5S2S32 2、标记、标记S1S1：-closure(-closure(move(S1,bmove(S1,b）)=1,2,4,)=1
30、,2,4,5 5,6,7,6,7=S3=S3S1S2S3S2S3S2S3S2S4S2S5S2S33 3、标记、标记S2S2：-closure(-closure(move(S2,a)move(S2,a)=1,2,)=1,2,3 3,4,6,7,4,6,7,8 8=S2=S2S1S2S3S2S3S2S3S2S4S2S5S2S33 3、标记、标记S2S2：-closure(-closure(move(S2,b)move(S2,b)=1,2,4,)=1,2,4,5 5,6,7,6,7,9 9=S4S4S1S2S3S4S2S3S2S3S2S4S2S5S2S34 4、标记、标记S3S3：-closure(
31、-closure(move(S3,a)move(S3,a)=1,2,)=1,2,3 3,4,6,7,4,6,7,8 8=S2=S2S1S2S3S4S2S3S2S3S2S4S2S5S2S34 4、标记、标记S3S3：-closure(-closure(move(S3,b)move(S3,b)=1,2,4,)=1,2,4,5 5,6,7=S3,6,7=S3S1S2S3S4S2S3S2S3S2S4S2S5S2S35 5、标记、标记S4S4：-closure(-closure(move(S4,a)move(S4,a)=1,2,)=1,2,3 3,4,6,7,4,6,7,8 8=S2=S2S1S2S3S
32、4S2S3S2S3S2S4S2S5S2S35 5、标记、标记S4S4：-closure(-closure(move(S4,b)move(S4,b)=1,2,4,)=1,2,4,5 5,6,7,6,7,1010=S5S5S1S2S3S4S5S2S3S2S3S2S4S2S5S2S36 6、标记、标记S5S5：-closure(-closure(move(S5,a)move(S5,a)=1,2,)=1,2,3 3,4,6,7,4,6,7,8 8=S2=S2S1S2S3S4S5S2S3S2S3S2S4S2S5S2S36 6、标记、标记S5S5：-closure(-closure(move(S5,b)m
33、ove(S5,b)=1,2,4,)=1,2,4,5 5,6,7=S3,6,7=S3S1S2S3S4S5S2S3S2S3S2S4S2S5S2S3-closure(0)=0,1,2,4,7*S1-closure(move(S1,a)=3,8,6,7,1,2,4*S2-closure(move(S1,b)=5,6,7,1,2,4*S3-closure(move(S2,a)=3,8,6,7,1,2,4 S2-closure(move(S2,b)=5,9,6,7,1,2,4*S4-closure(move(S3,a)=3,8,6,7,1,2,4 S2-closure(move(S3,b)=5,6,7,1
34、,2,4 S3-closure(move(S4,a)=3,8,6,7,1,2,4 S2-closure(move(S4,b)=5,10,6,7,1,2,4*S5-closure(move(S5,a)=3,8,6,7,1,2,4 S2-closure(move(S5,b)=5,6,7,1,2,4 S3识别abb和abab：1 a 2 b 4 b 5 接受 1 a 2 b 4 a 2 b 5 不接受 过程总结：过程总结：NFADFA最小最小DFA输入符号abS1S2S3S2S2S4S3S2S3S4S2S5S5S2S324开始开始a1abbab3ba12开始开始a0abbab识别语言识别语言(a|b
35、)*ab 的的自动机自动机子集构造法不一定得到最简子集构造法不一定得到最简DFADFADFA的化简的化简l1定定义:所所谓一个一个DFAM的化的化简是指是指寻找一个状找一个状态数比数比较少的少的DFAM,使使L(M)=L(M)。l2化化简方法方法:（分割法）（分割法）l化化简后的有限自后的有限自动机中没有机中没有多余状多余状态，同，同时没有没有等价等价状状态。l因此化因此化简有限自有限自动机的方法有两个：机的方法有两个：l消除多余状消除多余状态l合并等价状合并等价状态DFA的化简的化简l多余状多余状态（直接清除）：（直接清除）：l不可到达的状不可到达的状态：从有限自从有限自动机的开始状机的开始
36、状态出出发，任，任何何输入串也不能到达的状入串也不能到达的状态，（没有入，（没有入边的非初始状的非初始状态）。）。l死状死状态：即不是即不是终态且且对所有所有输入字符均入字符均转向其自身，向其自身，（不指向其他状（不指向其他状态的非的非终止状止状态）。）。DFA的化简的化简l等价状等价状态：l也称也称不可区分的状不可区分的状态。l在有限自在有限自动机中，两个状机中，两个状态p和和q等价等价应满足如下条件：足如下条件：（a）一致性条件一致性条件：状：状态p和和q必必须同同时为终止状止状态或或为非非终止状止状态。（b）蔓延性条件蔓延性条件：对于所有于所有输入符号，状入符号，状态p和和q必必须转换到
37、等价的状到等价的状态。l状状态p和和q是可区分是可区分（即（即不等价不等价的）的）：l对于任何两个状于任何两个状态p和和q，若从一状，若从一状态出出发接受接受输入字入字符串符串，而从另一状，而从另一状态出出发不接受不接受；l或者从或者从p和和q出出发输入字符串入字符串，到达不同的接受状，到达不同的接受状态。DFA的化简的化简l合并等价状合并等价状态的方法的方法-分割法分割法l算法的核心算法的核心：把：把DFAM的状的状态集集K分成若干个不相交的分成若干个不相交的子集。其中状子集。其中状态集中的任意两个状集中的任意两个状态都是等价的。都是等价的。l具体方法具体方法：构造一：构造一张表，表，对每一
38、个状每一个状态对（si,sj）（）（il添加状添加状态Z作作为终止状止状态;lVn Z=Kl开始符号开始符号S对应的状的状态就是初始状就是初始状态s0;lf:UaV=f(U,a)=VlUa=f(U,a)=Z正规文法到正规文法到NFAl例：正例：正规文法文法G:(Vn,Vt,P,S)lVn=S,NlVt=+,-,dlP=S+NS-NSdNSdNdNNdlSl转换为：NFAM:(K,f,s0,Z)l=Vt=+,-,dl添加状添加状态Z作作为终止状止状态;lK=Vn Z=S,N,Zl初始状初始状态S;lf:f(S,+)=Nf(S,-)=Nf(S,d)=Nf(S,d)=Zf(N,d)=Nf(N,d)=
39、ZNFA到正规文法到正规文法lNFAM:(K,f,s0,Z)l正正规文法文法G:(Vn,Vt,P,S)l=VtlK=Vn(K-Z=Vn?)ls0=S;l添加添加产生式：生式：ZlP:f(U,a)=V=UaVf(U,a)=Z=UaNFA到正规文法到正规文法l例：例：NFAM:(K,f,s0,Z)lK=S,A,B,Cl=x,ylf=ls0=SlZ=B,Cl正正规文法文法G:(Vn,Vt,P,S)lVt=x,ylVn=K=S,A,B,ClS=s0;l添加添加产生式：生式：BClP:SxASyBAxBAyAAAyCBxCByCBYa正规表达式与正规表达式与NFA的的等价性l对于上的每个正规式R，可以构
40、造一个上的NFAM，使得L(M)=L(R)。l对于上的NFAM，可以构造一个上的正规式R，使得L(R)=L(M)。正规表达式到正规表达式到NFAl1、构造开始状、构造开始状态S和和终止状止状态Z：l2、按照、按照替替换规则对正正规表达式表达式R，逐步，逐步进行分解。行分解。l3、直到所有的弧上都是、直到所有的弧上都是单个符号或者个符号或者为止。止。SZR正规式正规式R R到到 NFA MNFA M的的简化替换规则简化替换规则：2 2对于对于代之为：代之为：R R1 1R R1 1|R|R2 2 R R2 21 12 21 12 2代之为：代之为：R R2 2 R*R*2 23 3对于对于1 1
41、2 21 13 32 2R RX Xy yR R1 1R R2 2R R1 1R R2 2代之为：代之为：1 1对于对于1 12 21 13 32 2正规表达式到正规表达式到NFA例1：L(R)=(a|b)*abb，构造NFA使L(N)=L(R)解：xy(a|b)*abbxyabba|bxyabbabxyababbyababbxy(a|b)*(aa|bb)(a|b)*xy(a|b)*aa|bb(a|b)*xyaabba|ba|b例2：L(R)=(a|b)*(aa|bb)(a|b)*构造L(N)使与L(R)等价。xya baaabbb-+a baaabbb 正规式，构造NFA为：或：对应正规式，
42、构造NFA为：对应正规式a，构造NFA为：s,t是正规式，相应NFA为N(s),N(t)，则正规式R=s|t，构造NFA(R)为：xyxyxyaxyN(s)N(t)正规表达式到正规表达式到NFAl从正规式R构造NFA完整规则如下：s,t是正规式，相应NFA为N(s),N(t)，则正规式R=st，构造NFA(R)为：xyN(t)N(s)s,t是正规式，相应NFA为N(s),N(t)，则正规式R=s*，构造NFA(R)为：xyN(s)正规表达式到正规表达式到NFAl正正规表达式到表达式到NFA转换的的递归算法：算法：ProcedureFSM(EXPR:reg-expr;P,Q:state)VarA
43、:state;BeginIfEXPR=then什么也不做ElseIfEXPR=thent(P,)=Q;ElseIfEXPR=athent(P,a)=Q;正规表达式到正规表达式到NFAElseIfEXPR=(X)thenFSM(X,P,Q);ElseIfEXPR=XYthen 连接BeginA:=newstate;FSM(X,P,A);FSM(Y,A,Q);End正规表达式到正规表达式到NFAElseIfEXPR=X|Ythen选择BeginFSM(X,P,Q);FSM(Y,P,Q);End正规表达式到正规表达式到NFAElseIfEXPR=X*then 闭包BeginA:=newstate;F
44、SM(,P,A);FSM(X,A,A);FSM(,A,Q);EndEnd正规表达式到正规表达式到NFA1 19 9开始开始 0 0a ab b a ab b6 67 78 82 23 34 45 5 r r9 9r r7 7r r8 8r r4 4r r3 3r r5 5r r6 6*)(r r2 2r r1 1a a|b ba ab b(a a|b b)*abab的分解的分解正规表达式到正规表达式到NFA1 19 9开始开始 0 0 a ab b6 67 78 8a ab b2 23 34 45 5 r r9 9r r7 7r r8 8r r4 4r r3 3r r5 5r r6 6*)(r
45、 r2 2r r1 1a a|b ba ab b(a a|b b)*abab的分解的分解正规表达式到正规表达式到NFA 1 19 9开始开始 0 0a ab b a ab b6 67 78 82 23 34 45 5 r r9 9r r7 7r r8 8r r4 4r r3 3r r5 5r r6 6*)(r r2 2r r1 1a a|b ba ab b(a a|b b)*abab的分解的分解正规表达式到正规表达式到NFA1 19 9开始开始 0 0a ab b a ab b6 67 78 82 23 34 45 5 r r9 9r r7 7r r8 8r r4 4r r3 3r r5 5r
46、 r6 6*)(r r2 2r r1 1a a|b ba ab b(a a|b b)*abab的分解的分解正规表达式到正规表达式到NFA1 19 9开始开始 0 0a ab b a ab b6 67 78 82 23 34 45 5 r r9 9r r7 7r r8 8r r4 4r r3 3r r5 5r r6 6*)(r r2 2r r1 1a a|b ba ab b(a a|b b)*abab的分解的分解正规表达式到正规表达式到NFA1 19 9开始开始 0 0a ab b a ab b6 67 78 82 23 34 45 5 r r9 9r r7 7r r8 8r r4 4r r3
47、3r r5 5r r6 6*)(r r2 2r r1 1a a|b ba ab b(a a|b b)*abab的分解的分解正规表达式到正规表达式到NFA1 19 9开始开始 0 0a ab b a ab b6 67 78 82 23 34 45 5 r r9 9r r7 7r r8 8r r4 4r r3 3r r5 5r r6 6*)(r r2 2r r1 1a a|b ba ab b(a a|b b)*abab的分解的分解正规表达式到正规表达式到NFA(a a|b b)*abab的两个的两个NFANFA的比较的比较1 12 2开始开始a a0 0a ab bb b1 19 9开始开始 0
48、0a ab b a ab b6 67 78 82 23 34 45 5 手工构造手工构造:算法构造算法构造:NFA到正规表达式到正规表达式l1、拓广拓广NFA：添加新的开始状添加新的开始状态S和和终止状止状态Z，S与原开与原开始状始状态用用 连接，接，Z与原所有与原所有终止状止状态用用 连接接l2、使用替、使用替换规则消去所有消去所有节点和点和连接接。l3、直到只有直到只有S和和Z，弧上的表达式即，弧上的表达式即为转换后的后的正正规表达式表达式R。NFA到正规表达式到正规表达式l方法方法：在每一条弧上用一个正：在每一条弧上用一个正规式作式作标记。l规则：a.123R1R213R1R2b.12R
49、1R221R1|R221R1+R2或c.321R1R2R331R1R2*R3例2:L(M)如下图：求正规式R，使L(R)=L(M).解：aba,baba,bxyya|bxa|byx(a|b)(a|b)*因此：L(R)=(a|b)(a|b)*03412aabba,ba,ba,b例3：M状态图如下：求正规式R，是L(R)=L(M).解：加x,y结点。a,b03412aabba,ba,bxy042aabba,ba,bxya,ba,b0aa(a|b)*bb(a|b)*xyy(a|b)*(aa|bb)(a|b)*x所以 L(R)=(a|b)*(aa|bb)(a|b)*正规文法和正规式的等价性正规文法和正
50、规式的等价性l程序程序设计语言中的言中的单词既能用正既能用正规文法表示文法表示，又又能用正能用正规式来表示式来表示。正规文法正规文法:l|ll|l l|d|ll|d|l|d|d d|dd|d l l表示表示a-za-z中的任何英文字母中的任何英文字母d d表示表示0-90-9中的任何数字中的任何数字正规式正规式:标识符标识符:e1=e1=字母字母(字母字母|数字数字)*)*无符号整数无符号整数:e2=dd*e2=dd*正规文法和正规式的等价性正规文法和正规式的等价性l一个正规语言可以由正规文法定义，也可以用正规式定义。l对于任意一个正规文法，存在一个定义同一语言的正规式。l对每一个正规式，存在