1、2022-12-81 1 1词法分析词法分析q掌握：词法分析程序的构造，正规式和掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换正规文法到有穷自动机的转换，NFANFA到到DFADFA的转换、的转换、DFADFA的化简的化简q理解：正规文法、正规式、理解：正规文法、正规式、DFADFA的概念、的概念、NFANFA的概念的概念q了解：词法分析程序的自动构造工具了解：词法分析程序的自动构造工具2022-12-82 2 2$1 词法分析的基本概念词法分析的基本概念1.1 词法分析的意义词法分析的意义q识别单词、并标记单词的属性、再转换成统一识别单词、并标记单词的属性、再转换成统一长度的属
2、性字长度的属性字q其它任务其它任务q词法分析是语法分析的一部分词法分析是语法分析的一部分2022-12-83 3 31.2 词法分析的输入和输出词法分析的输入和输出q源程序的输入源程序的输入 缓冲区：一分为二的区域缓冲区：一分为二的区域q词法分析的输出词法分析的输出v保留字保留字v标识符标识符v常量常量v运算符运算符v界符界符q二元组输出（单词类别，单词值）二元组输出（单词类别，单词值）2022-12-84 4 4q例：假定单词类型用整数编码：标识符例：假定单词类型用整数编码：标识符为为1，常数为，常数为2，保留字为，保留字为3，运算符为，运算符为4，分解符为分解符为5。则语句。则语句 if（
3、bc9）ya；q二元式形式的单词序列如下：二元式形式的单词序列如下：（3，if）（5，（）2022-12-85 5 51.3 词法分析实现方法词法分析实现方法q把词法分析作为单独一遍独立出来。使词法分把词法分析作为单独一遍独立出来。使词法分析和语法分析完全独立析和语法分析完全独立q把词法分析工作穿插在语法分析过程中，即作把词法分析工作穿插在语法分析过程中，即作为语法分析的子程序为语法分析的子程序2022-12-86 6 6$2 正规文法和有限自动机正规文法和有限自动机2.1 正规文法、正规集、正规式正规文法、正规集、正规式q正规文法（正规文法（3型文法）型文法）q正规集：有正规文法产生的语言正
4、规集：有正规文法产生的语言v正规集是集合，有穷或无穷，可以通过正规正规集是集合，有穷或无穷，可以通过正规式来形式化的表示式来形式化的表示2022-12-87 7 7q例如例如:用用l l表示表示azaz中的任一英文字母，中的任一英文字母，d d表示表示0909中任一数字。中任一数字。v描述标识符的正规文法为：描述标识符的正规文法为：l lll l ld dll dd v描述无符号整数的正规文法：描述无符号整数的正规文法：d ddd 2022-12-88 8 8q正规式的定义（递归）：正规式的定义（递归）：设设A是非空的有限字母表，是非空的有限字母表，Aai|i1,2,n,则：则：1 、和和ai
5、都是都是上的正规式。上的正规式。2 若若、是正规式，则是正规式，则|、*、*都都 是正规式是正规式3正规式只能通过有限次使用正规式只能通过有限次使用1、2规则获得规则获得说明说明:算符的优先顺序算符的优先顺序:.和和都是左结合都是左结合q仅由字母表仅由字母表Aai|i1,2,n上的正规式上的正规式 所组成的语言称谓正规集，记为所组成的语言称谓正规集，记为 L（）2022-12-89 9 9正规式正规式正规集正规集(1)(1)12(1)(2)1.2(1)(2)1(1)2022-12-8101010q举例：举例：令令=a a，bb，上的正规式和相应的正规集有上的正规式和相应的正规集有正规式正规式正
6、规集正规集a aaaa a b ba,ba,babab abab(a(a b)(ab)(a b)b)aaaa,abab,baba,bb,bba a ,a,a,aaaa,任意个任意个a a串串(a a b)b),a,b,a,b,aaaa,abab 所有由所有由a a和和b b 组成的串组成的串 2022-12-8111111q 正规式的代数性质正规式的代数性质设设 r，s，t 是正规式，正规式服从的代数规律是：是正规式，正规式服从的代数规律是：vrs=sr“或或”满足交换律满足交换律vr(st)=(rs)t“或或”的结合律的结合律v(r s)t=r(s t)“连接连接”的结合律的结合律vr(st
7、)=r sr tv(rs)t=r ts t分配分配律律vr=r=r 是是“连接连接”的恒等元的恒等元素素vr r r=rr=r “或或”的抽取律的抽取律 vr r=r r rrrr 2022-12-8121212q程序中的单词都能用正程序中的单词都能用正规规式来定义式来定义 令令l l为为azaz的字母，的字母，d d为为0909的数字的数字ve e1 1=l(l|d)=l(l|d)*e e1 1表示标识符集合表示标识符集合ve e2 2=dddd*e e2 2表示无符号整数表示无符号整数注：注：l lll l ld dll dd q正规式比正规文法更容易让人理解单词是按怎正规式比正规文法更容
8、易让人理解单词是按怎样的规律构成的，且可以从某个正规式自动地样的规律构成的，且可以从某个正规式自动地构造识别程序。构造识别程序。2022-12-81313132.2 正规文法和正规式间的转换正规文法和正规式间的转换q等价性：等价性：v对任意一个正规文法，存在一个定义同对任意一个正规文法，存在一个定义同一语言的正规式一语言的正规式v对任意一个正规式，存在一个定义同一对任意一个正规式，存在一个定义同一语言的正规文法语言的正规文法2022-12-8141414q将将上的一个正规式上的一个正规式r r转换成文法转换成文法G=(VG=(VN N,V,VT T,S,P),S,P)v V VT T=,=,首
9、先形成产生式首先形成产生式Sr,SSr,S为为G G的开始符的开始符v 不断利用下面的规则做变换不断利用下面的规则做变换,直到每个产生式直到每个产生式最多含有一个终结符为止最多含有一个终结符为止原产生式原产生式变换后产生式变换后产生式规则规则1 1AAxyxyAAxB xB ByBy规则规则2 2AxAx*y yAAxA xA AyAy规则规则3 3Ax|yAx|yAx AyAx Ay其中其中B B为一新非终结符为一新非终结符2022-12-8151515例例:将将R=a(a|d)*转换成相应的正则文法转换成相应的正则文法令转换成文法令转换成文法G=(VN,VT,P,S)其中其中VT=a,d，
10、文法开始符为文法开始符为S首先形成首先形成Sa(a|d)*,然后变换然后变换SaA A(a|d)*A(a|d)A AAaA AdA最终有产生式：最终有产生式：SaA，A，AaA，AdA2022-12-8161616q将正规文法转换成正规式将正规文法转换成正规式v将每条产生式改写为正规式将每条产生式改写为正规式v用代入法解正规式方程组用代入法解正规式方程组v最后只剩下一个开始符号定义的正最后只剩下一个开始符号定义的正规规式式,其中不含其中不含非终结符非终结符q正正规规文法到正文法到正规规式的转换规则式的转换规则:文法产生式文法产生式正正规规式式规则规则1 1 AAxB xB ByByA=A=xy
11、xy规则规则2 2 AAxAxA|y|yA=xA=x*y y规则规则3 3 Ax AyAx AyA=x|yA=x|y2022-12-8171717例：将文法例：将文法GS转换成正规式转换成正规式 G：Sa A|a AdA|d先由产生式得先由产生式得:S=aA|a A=d*d将将A代入代入S中得中得:S=ad*d|a利用正利用正规规式变换得式变换得S=a(d*d|)=ad*说明说明:d*d|=(|d|dd|)d|=d|dd|=d*所求正规式为所求正规式为ad*2022-12-81818182022-12-8191919根据规则根据规则2：AAxAxA|y|yA=xA=x*y y2022-12-8
12、202020$3 有穷自动机有穷自动机(也称有限自动机也称有限自动机)q是一种识别装置是一种识别装置q作用作用:能准确地识别正规集，即识别正规文法所能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合定义的语言和正规式所表示的集合q意义意义:为词法分析程序的自动构造寻找特殊的方为词法分析程序的自动构造寻找特殊的方法和工具。法和工具。q分类分类:确定的有穷自动机确定的有穷自动机(Deterministic Finite Automata)Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机(NondeterministicNondeter
13、ministic Finite Automata)Finite Automata)2022-12-82121212022-12-82222223.1 确定的有穷自动机（确定的有穷自动机（DFA）q 定义定义:一个一个DFA M是一个五元组是一个五元组:M=（K，f，S，Z）1.K是一个有穷集，它的每个元素称为一个状态是一个有穷集，它的每个元素称为一个状态2.是一个有穷字母表，它的每个元素称为一个输是一个有穷字母表，它的每个元素称为一个输入字符入字符3.f是一个从是一个从 K K的的单值单值部分映射部分映射,即即 f(ki,a)=kj，意味着当前状态为意味着当前状态为ki，输入字符为输入字符为a
14、时，将转换到下一状态时，将转换到下一状态kj4.SK，是是唯一唯一的初态的初态5.Z K,是一个终态集，终态也称为可接受状态是一个终态集，终态也称为可接受状态或结束状态。或结束状态。2022-12-8232323q例：例：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）=
15、Q=Q2022-12-8242424qDFA表示成状态转换图表示成状态转换图(Transition Diagram)v每个状态对应图中的一个结点：每个状态对应图中的一个结点：初态为唯一初态结点，用初态为唯一初态结点，用=标记；标记；终态对应终态结点，用双圈表示。终态对应终态结点，用双圈表示。v若有若有f(ki,a)=kj，则从结点则从结点ki到结点到结点kj画标记为画标记为a的弧。的弧。2022-12-8252525q例例 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
16、，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，bb2022-12-8262626qDFA表示成状态转换矩阵表示成状态转换矩阵abSUVUQVVUQQQQ字符字符状态状态0001行表示状态，用行表示状态，用双箭头双箭头“=”“=”标标明初态；否则第明初态；否则第一行即是初态一行即是初态列表示输入字符列表示输入字符相应状态行和输相应状态行和输入字符列下的新入字符列下的新状态，即状态，即k k行行a a列列为为
17、f(k,a)f(k,a)的值的值相应终态行在表相应终态行在表的右端标以的右端标以1 1，非终态标以非终态标以0 02022-12-8272727qDFA识别识别(接受接受)的字符串的字符串v对于对于*中的任何字符串中的任何字符串t，若存在一条从初态若存在一条从初态结到某一终态结的通路，且该通路上所有弧的结到某一终态结的通路，且该通路上所有弧的标记符连接成的字符串等于标记符连接成的字符串等于t，则称则称t可以为可以为 DFA M所识别所识别v若若DFA M的初态结同时又是终态结，则的初态结同时又是终态结，则可为可为M所识别。所识别。bSUVQaaaba，bbbaab为为DFA所接受所接受2022
18、-12-8282828例：证明例：证明t=baab被下图的被下图的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）=QQ属于终态。属于终态。得证。得证。2022-12-8292929qDFA的行为很容易用程序来模拟的行为很容易用程序来模拟vK:=S；vc:=getchar;vwhile ceof do v v K:=f(K,c);v c:=getchar;v;vif K is in Z then return(yes)velse return(no)2022-12-8
19、303030vDFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M).v结论：结论：上一个符上一个符号号串集串集V 是正规的，当且是正规的，当且仅当存在一个仅当存在一个 上的确定有穷自动机上的确定有穷自动机M，使使得得 V=L(M)q确定性确定性表现在表现在:转换函数转换函数f:KK是一个是一个单值单值函数，函数，也就是说，对任何状态也就是说，对任何状态kK，和输入符号和输入符号a，f(k,a)唯一地确定了下一个状态。唯一地确定了下一个状态。2022-12-83131312022-12-83232322022-12-83333333.2 不确定的有穷自动机不确定的有穷自动机q
20、NFA的定义的定义一个不确定的有穷自动机一个不确定的有穷自动机M M是一个五元组：是一个五元组：M=M=（K K，f f，S S，Z Z），），其中其中:2022-12-8343434q例例 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矩阵表示矩阵表示:01SP S,ZPZZP P001SPZ00,1111状态图表示状态图表示:2022-12-8353535qNFA
21、识别的字符串识别的字符串v对于对于*中的任何字符串中的任何字符串t，若存在一条从若存在一条从某一某一初态结初态结到到某一终态结某一终态结的通路，且该通路上所有的通路，且该通路上所有弧的标记字依次连接成的串（不理睬那些标记弧的标记字依次连接成的串（不理睬那些标记为为的弧）等于的弧）等于t，则称则称t可以被可以被 NFA M所识别。所识别。vNFA M NFA M 所能识别的符号串的全体记为所能识别的符号串的全体记为L(M)L(M)2022-12-8363636qNFANFA与与DFADFA的等价性的等价性vDFADFA是是NFANFA的特例的特例v对于任何两个有穷自动机对于任何两个有穷自动机 M
22、 M和和MM，如果如果L(M)=L(M)L(M)=L(M)，则称则称M M与与MM是等价的是等价的v对于每个对于每个NFA MNFA M，存在一个与其等价的存在一个与其等价的DFA MDFA M2022-12-83737373.3 NFA到到DFA的转换的转换qNFA确定化的算法确定化的算法由由NFA M=(S,f,S0,Z)构造一个等价的构造一个等价的 DFA M=(Q,I0,F)1.取取I0=S0，2.若状态集若状态集Q中有状态中有状态Ii=s0,s1,sj,skS,0 k j;而且而且M机中有机中有f(s0,s1,sj,a)=f(s0,a)f(s1,a)f(sj,a)=s0,s1,st=
23、It，若若It不在不在Q中，则将中，则将It加入加入Q。2022-12-8383838 3.重复步骤重复步骤2，直到，直到Q中无新状态加入为止。中无新状态加入为止。4.取终态取终态F=I|I Q,且且I Z 注：注：1)上述过程可在有限步内完成，因为上述过程可在有限步内完成，因为M机状态的幂集机状态的幂集是有限的；是有限的；2)上述过程也可用表格法来描述，其中列是字符集上述过程也可用表格法来描述，其中列是字符集 中的字符；行是中的字符；行是Q中的各状态，开始仅包含中的各状态，开始仅包含I0状态，随状态，随着算法的执行，着算法的执行，Q的状态逐渐增多直止不再增多为止；的状态逐渐增多直止不再增多为
24、止；表格元素就是表格元素就是 映射函数。映射函数。3)NFA确定化的实质是以原有状态集上的覆盖片确定化的实质是以原有状态集上的覆盖片(COVER)作为作为DFA上的一个状态，将原状态间的转换上的一个状态，将原状态间的转换改为覆盖片间的转换，从而将不确定问题确定化。改为覆盖片间的转换，从而将不确定问题确定化。4)通常，经确定化后，状态数增加，而且可能出现一通常，经确定化后，状态数增加，而且可能出现一些等价状态，这时需要化简些等价状态，这时需要化简2022-12-8393939例例 设设NFA M(q0,q1,0,1,f,q0,q1)f映射为映射为 字字符符状态状态01q0 q0 q1q1 q0，
25、q1 q0q0q1110002022-12-8404040q例例 把上例的把上例的NFA确定化确定化v1.M的初态：的初态：I0=q0。则则Q中就有了中就有了I0状态状态v2.由由Q中的状态中的状态I0=q0，查看查看M机，有：机，有：v f(q0,0)=q0、f(q0,1)=q1=I1v此时，此时，Q=I0,I1v3.由由Q中的状态中的状态I1=q1，查看查看M机，有：机，有：v f(q1,0)=q0,q1 =I2、f(q1,1)=q0=I0v此时，此时，Q=I0,I1,I2v3.由由Q中的状态中的状态I2=q0,q1，查看查看M机，有：机，有：v f(q0,q1,0)=q0,q1、f(q0
26、,q1,1)=q0,q1=I2v此时，此时，Q=I0,I1,I2v4.F=I1,I2q0q1000112022-12-8414141qNFA经过确定化后，变为：经过确定化后，变为：vDFA M=(I0,I1,I2,0,1,f,I0,I1,I2）Q01I0=q0I0=q0I1=q1I1=q1I2=q0,q1 I0=q0I2=q0,q1 I2=q0,q1 I2=q0,q1 2022-12-8424242I0I111000I21状态转换图如下：01I0I0I1 I1 I2I0I2I2I22022-12-84343433.4 确定有限自动机的化简确定有限自动机的化简q化简的任务化简的任务:去掉多余状态
27、，合并等价状态去掉多余状态，合并等价状态q多余状态多余状态：从开始状态出发无法到达的状态。：从开始状态出发无法到达的状态。q等价状态等价状态：两个状态：两个状态s和和t等价的条件是等价的条件是:1.一致性条件一致性条件状态状态s和和t必须同为可接受状态必须同为可接受状态或不可接受状态或不可接受状态2.蔓延性条件蔓延性条件对于对于所有所有输入符号输入符号,状态状态s和状和状态态t必须转换到等价的状态里必须转换到等价的状态里q可区别状态可区别状态：不等价状态。如终态与非终态是：不等价状态。如终态与非终态是可区别的。可区别的。2022-12-8444444aCDBAEFSbaaaaabbbbbabq
28、例例vC C和和F F同是终态同是终态,C C和和F F读入读入a a都到达都到达C,C,读入读入b b都到达都到达E,E,所以所以C C和和F F等价等价vS S和和C C不等价，因为不等价，因为C C是终态，而是终态，而S S不是终态不是终态2022-12-8454545q“分割法分割法”DFADFA的最小化算法的最小化算法:把一个把一个DFADFA的状态分成一些不相交的子集，的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的而同一子集中的任何两个状态都是等价的.2022-12-8464646q状
29、态等价：设状态等价：设DFA M中有两个状态中有两个状态s,tq s,t 等价：等价：v(s,w)*(s1,)同时同时(t,w)*(t1,)，s1,t1都是终态，都是终态，w VT*，即如果从状态即如果从状态s出发能出发能读出某个字读出某个字w而停于终态，从而停于终态，从t出发也能读出同出发也能读出同样的字样的字w而停于终态，则称而停于终态，则称s,t 等价。等价。q s,t可区别可区别：v如果如果s,t不等价，则称为不等价，则称为s,t可区别可区别2022-12-8474747q确定有限自动机的化简算法确定有限自动机的化简算法1.把状态集把状态集S划分为终态集和非终态集：划分为终态集和非终态
30、集：0 I01,I02，I01属于非终态集属于非终态集,I02属于终态集。因属于终态集。因为终态能识别为终态能识别，而非终态不能，所以它们是可区，而非终态不能，所以它们是可区别的；别的；2.假定经过假定经过k次划分后：次划分后：kIk0,Ik1Ikm.这这m个子集之间可区分，子集内部还是否可以划分？个子集之间可区分，子集内部还是否可以划分？v任取一个子集任取一个子集Iki=s1,s2,sk,若存在某读入字符若存在某读入字符a，使使f(Iki,a)的结果不是全部包含在的结果不是全部包含在k的某个子集中，则的某个子集中，则说明说明Iki中有不等价的状态，还要进一步划分。中有不等价的状态，还要进一步
31、划分。v对对k中所有子集都进行测试，以完成一次划分。中所有子集都进行测试，以完成一次划分。2022-12-8484848注：注：1）当一个自动机没有任何多余的状态，并）当一个自动机没有任何多余的状态，并且它的状态中没有两个是互相等价的时，我们且它的状态中没有两个是互相等价的时，我们说这个有限自动机是化简了的。说这个有限自动机是化简了的。2）可以通过消除多余状态，合并等价状态）可以通过消除多余状态，合并等价状态而转化成一个最小化的与之等价的有限自动机。而转化成一个最小化的与之等价的有限自动机。2022-12-8494949q例：设有一例：设有一DFA 的状态转换图如下，试的状态转换图如下，试化简
32、之化简之 0 1 2 3 5 4 6 a a a a a a a b b b b b b b2022-12-8505050q解：解：1.把把M的状态分为两组：终态集，非终态集的状态分为两组：终态集，非终态集00,1,2,3,4,5,62.a)考察非终态集：考察非终态集：f(0,1,2,a)=1,3 不属于不属于0的任何一个子集，的任何一个子集，所以所以0，1，2要分开要分开得到：得到：11，0,2，3,4,5,6再看：再看：f(0,2,a)=1属于属于1的子集的子集 f(0,2,b)=2,5不属于不属于1的任何子集，所的任何子集，所以以0,2要分开要分开得到：得到：11，0，2，3,4,5,6
33、2022-12-8515151解解：（续）（续）2.b)考察终态集：考察终态集：f(3,4,5,6,a)=3,6包含于包含于1“的子集的子集3,4,5,6 f(3,4,5,6,b)=4,5包含于包含于1“的子集的子集3,4,5,6所以所以3,4,5,6不可再划分不可再划分3.整个划分为整个划分为4个组：个组：21,0,2,3,4,5,64.令状态令状态3代表代表3,4,5,6，把原来到达状态，把原来到达状态4，5，6的弧都导入的弧都导入3，并删除，并删除4，5，6。得：。得：2022-12-8525252即为化简了的即为化简了的DFA 0 1 2 a a b b 3 a a b b 0 1 2
34、 3 5 4 6 a a a a a a a b b b b b b b2022-12-85353533.5 正规式与有限自动机之间的关系正规式与有限自动机之间的关系q关系定理关系定理q定理：定理：上的上的NFA M所能识别的语言所能识别的语言L(M)可可以用以用 上的正规式来表示。即：对上的正规式来表示。即：对 上的上的NFA M，可构造一个正规式可构造一个正规式，使得使得L()=L(M)q定理：定理：上任何正规式上任何正规式 ，存在，存在DFA M使得使得L(M)=L()。即：由即：由 正规式正规式 可以可以构造一个构造一个DFA M，使得使得L(M)L()2022-12-8545454q
35、有限自动机有限自动机M向正规式向正规式 的转换的转换1)把状态转换图的概念拓广，令每条弧上都可以把状态转换图的概念拓广，令每条弧上都可以用一个正规式作标记。用一个正规式作标记。2)在在M的转换图上加两个结点：的转换图上加两个结点：x,y。从从 x用用 弧连弧连接到接到M的所有初态结点；从的所有初态结点；从M的终态结点用的终态结点用 弧弧连接到连接到y。这个新的这个新的NFA为为M，且且L(M)=L(M)3)通过引入的通过引入的3条有限自动机替换规则逐步消去条有限自动机替换规则逐步消去M中的所有结点，直到只剩下中的所有结点，直到只剩下x和和y为止。这样为止。这样，在在x至至y的弧线上的标记就是的
36、弧线上的标记就是 上的正规式，也就上的正规式，也就是是M接受的正规式。接受的正规式。注：注：在消除结点过程中，逐步用正规式来标记弧在消除结点过程中，逐步用正规式来标记弧。2022-12-8555555有限自动机替换规则有限自动机替换规则 1 1 1 1 132|2 23 12*22022-12-8565656q例例 将下面的将下面的DFA M所接受的语言表示为所接受的语言表示为正规式正规式111113200 00 0 xy2022-12-8575757x0 310|0101|1000|1100|11y x 0 y00|11(10|01)(00|11)*(01|10)x y (10|01)(00
37、|11)*(01|10)|(00|11)*2022-12-85858583.6 正规式与有限自动机之间的关系正规式与有限自动机之间的关系q正规式正规式 向确定有限自动机向确定有限自动机M的转换的转换 1)由正规式由正规式 构造一个如下仅有两个结点构造一个如下仅有两个结点x,y的状态图。的状态图。2)按所引入的按所引入的3条正规式分裂规则分裂条正规式分裂规则分裂 。3)重复步骤重复步骤2直到每个弧上的标记是直到每个弧上的标记是 上的一个字上的一个字符或为符或为 止。止。4)将所得的将所得的NFA M(因为包含因为包含 弧弧)进行确定化就得进行确定化就得到到DFA。x y 2022-12-8595
38、959正规式分裂规则正规式分裂规则 1 12|1 22 1 12*121212022-12-8606060q正规式正规式 向确定有限自动机向确定有限自动机M的转换的转换 注：这里将注：这里将NFA M进行确定化与前面所讲的进行确定化与前面所讲的子集法确定化是一回事。不过，这里的子集法确定化是一回事。不过，这里的NFA M中含有中含有 弧，所以在求覆盖片时应考虑弧，所以在求覆盖片时应考虑 弧。弧。方法是求方法是求 闭包闭包(-closure)，将此闭包将此闭包(状态状态子集子集)作为作为DFA的一个状态使用，而将的一个状态使用，而将NFA上的状态间转换变为闭包间的转换，使得不上的状态间转换变为闭
39、包间的转换，使得不确定的自动机确定化。确定的自动机确定化。2022-12-8616161q例：根据正规式例：根据正规式(a|b)*(aa|bb)(a|b)*,构构造造DFA M，使之等价使之等价 x y (a|b)*(aa|bb)(a|b)*1y(a|b)*(a|b)*2 x(aa|bb)1y 2 xaa 5 bba|b 6 a|b 1y 2 xa 5 ba 6 abb34ab2022-12-8626262q对含有对含有 弧的弧的NFA进行确定化进行确定化(1)闭包闭包v 闭包闭包是可以从某状态或某些状态通过是可以从某状态或某些状态通过 弧所能到达的所弧所能到达的所有状态的集合。有状态的集合。
40、v状态集合状态集合I的的 闭包闭包(-closure(I)形式定义如下：形式定义如下：(a)若若s I，则则s -closure(I)(b)若若s I，那么从那么从s出发经过任意段的出发经过任意段的 弧所能达到的弧所能达到的任意状态任意状态s都属于都属于-closure(I)IIS2S2S1S1S3S3_ Closure(I)2022-12-8636363设设I=0，则则_closure(I)=q例例NFA:100124536789ababb74,2,1,0,2022-12-8646464(2)闭包间转换闭包间转换v设设-closure(I)q0,q1,qn，当读入字母当读入字母表中字母表中字
41、母a时，它转换到另一闭包时，它转换到另一闭包 -closure(J),记为记为Iav -closure(J)的组成的组成 J=f(q0,a)f(q1,a)f(qn,a)对得到的对得到的J按按 闭包的定义求闭包的定义求-closure(J)vIa=_closure(J)=_closure(Move(I,a)2022-12-8656565Ib =_closure(q例例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,42022-12-8666666(3)对含有对含有 弧的弧的NFA进
42、行确定化进行确定化 设设由由NFA M=(S,f,S0,Z)构造一个等价的构造一个等价的 DFA M=(Q,I0,F）(a)I0 -closure(S0),I0 Q(b)若状态集若状态集Q中有状态中有状态Ii=s0,s1,sj,skS,0 k j;且有且有It=-closure(f(Ii,a),若若It不在不在Q中，则将中，则将It加入加入Q。(c)重复步骤重复步骤2，直到，直到Q中无新状态加入。中无新状态加入。(d)取终态取终态F=I|I Q,且且I Z 2022-12-86767670,1,7,2,45,6,7,1,2,4 T28,3,6,7,1,2,4 T110,5,6,7,1,2,41
43、0,5,6,7,1,2,4 T48,3,6,7,1,2,4 T19,5,6,7,1,2,45,6,7,1,2,4 T28,3,6,7,1,2,4 T15,6,7,1,2,49,5,6,7,1,2,4 T38,3,6,7,1,2,4 T18,3,6,7,1,2,45,6,7,1,2,4 T28,3,6,7,1,2,4 T1IbIaI100124536789ababbT0T1T2T3T4000012022-12-8686868q 重新命名重新命名DFA的状态的状态得到得到DFA的状态转换矩阵和转换图如下的状态转换矩阵和转换图如下:S a b0 1 21 1 32 1 23 1 44 1 240b2
44、13bbaaababa000012022-12-8696969 1y2 xa 5 ba 6 abb34ab例I5=5,1,4,6,yI3=5,3,2,1,6,yI6=5,3,1,6,yI4=5,4,1,2,6,yI6=5,3,1,6,yI5=5,1,4,6,yI4=5,4,1,2,6,yI6=5,3,1,6,yI4=5,4,1,2,6,yI5=5,1,4,6,yI3=5,3,2,1,6,yI3=5,3,2,1,6,yI4=5,4,1,2,6,yI1=5,3,1I2=5,4,1I2=5,4,1I3=5,3,2,1,6,yI1=5,3,1I2=5,4,1I1=5,3,1I0=x,5,1 baI20
45、22-12-8707070Ia bI0I1I2I1I3I2I2I1I4I3I3I5I4I6I4I5I6I4I6I3I5DFA为：I0 I1 I2 I3 I4 I6 I5a b aa a babbbbba2022-12-87171713.7 3.7 正规文法和有限自动机正规文法和有限自动机q关系定理关系定理 设设G=(VN,VT,P,S)是正规文法，则存在一个有是正规文法，则存在一个有限自动机限自动机M=(Q,f,q0,Z)使得使得L(G)=L(M)。q 注：注：1)正规文法分为右线性文法和左线性文法。但对一正规文法分为右线性文法和左线性文法。但对一个正规文法，不能既是左线性，又是右线性。个正规
46、文法，不能既是左线性，又是右线性。2)对每个有限自动机对每个有限自动机 M，都存在一个右线性正规都存在一个右线性正规文法文法GR和左线性正规文法和左线性正规文法GL，使得使得 L(M)=L(GR)=L(GL)2022-12-8727272q右线性文法转换为等价自动机右线性文法转换为等价自动机 设有右线性文法：设有右线性文法：G=(VN,VT,P,S)，将将其转换为自动机其转换为自动机M=(Q,f,q0,Z)。转换步转换步骤如下：骤如下：1)将将VN中的每个非终结符视为状态符号，并增中的每个非终结符视为状态符号，并增加一个新的终结状态符号加一个新的终结状态符号T，即令即令Q=VNT;同时，令同时
47、，令 VT，q0 S;若若P中含有中含有S ，则令则令Z=S,T，否则令否则令 Z=T；2022-12-87373732)P中的产生式用如下映射中的产生式用如下映射f来代替。来代替。a)对于对于P中每一条形如中每一条形如 A1 aA2的产生式，在的产生式，在M中设为中设为 f(A1,a)=A2.b)对于对于P中每一条形如中每一条形如 A1 a的产生式，在的产生式，在M中设为中设为 f(A1,a)=T.c)对对 上的所有上的所有a，取取 f(T,a)=,即在终态下有即在终态下有限自动机无动作。限自动机无动作。2022-12-8747474q例例 有文法有文法G=(S,A,B,a,b,c,P,S)
48、，其其中产生式中产生式P:S aS|aB BbB|bA A cA|c 构造与之等价的构造与之等价的FA。解：构造自动机解：构造自动机M=(Q,f,q0,Z)1)增加一个新的终结状态符号增加一个新的终结状态符号T，Q=S,B,A,T a,b,c，q0 S，Z=T2022-12-8757575 2)f：f(S,a)=S f(S,a)=B f(B,a)=B f(B,b)=A f(A,c)=A f(A,c)=T显然，这是一个显然，这是一个NFA。其状态转换图为：其状态转换图为：BTac A Sbabc2022-12-8767676q例：设文法例：设文法G=(S,A,B,a,b,P,S)G=(S,A,B
49、,a,b,P,S)，则有自动机则有自动机M=(S,A,B,T,a,b,f,S,T)M=(S,A,B,T,a,b,f,S,T)产生式产生式转换函数转换函数SaAf(S,a)=Af(S,a)=ASbBf(S,b)=Bf(S,b)=BS f(S,)=Tf(S,)=TAaBf(A,a)=Bf(A,a)=BAbAf(A,b)=Af(A,b)=ABaSf(B,a)=Sf(B,a)=SBbAf(B,b)=Af(B,b)=AB f(B,)=Tf(B,)=T2022-12-8777777q有限自动机向右线性文法的转换有限自动机向右线性文法的转换 设有限自动机设有限自动机M=(S,f,s0,Z),右线性文法右线性
50、文法Rg=(VN,VT,P,s0),则：则：1)若若s0 Z，则则P是由以下规则定义的产生式集合是由以下规则定义的产生式集合:a)若若M中有映射中有映射f(Ai,a)=Aj,则则P中有中有AiaAjb)若若AjZ,则则P中增加产生式中增加产生式Aia，即即Aia|aAj 2)若若s0Z,除了上述映射所构成产生式之外除了上述映射所构成产生式之外，还还有映射有映射f(s0,)=s0,此时需要在此时需要在P中增加产生式：中增加产生式：s0|s0，以以s0代替代替s0作为开始符号作为开始符号。2022-12-8787878q例：写出例：写出DFA M=(A,B,C,D,0,1,f,A,B)相应的右线性
