第3讲词法分析PPT讲稿.ppt

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

1、第3讲词法分析第1页，共94页，编辑于2022年，星期一3.1 词法分析程序的设计词法分析程序的设计词法分析（词法分析（lexical analysis）逐个读入源程序字符并按照构词规则切分成一系逐个读入源程序字符并按照构词规则切分成一系 列单词。列单词。词法分析是编译过程中的一个阶段，在语法分词法分析是编译过程中的一个阶段，在语法分 析前进行。也可以和语法分析结合在一起作为析前进行。也可以和语法分析结合在一起作为 一遍，由语法分析程序调用词法分析程序来获一遍，由语法分析程序调用词法分析程序来获 得当前单词供语法分析使用。得当前单词供语法分析使用。单词单词是语言中具有独立意义的是语言中具有独立

2、意义的最小单位最小单位，包，包括保留字、标识符、运算符、标点符号和常量括保留字、标识符、运算符、标点符号和常量等。等。第2页，共94页，编辑于2022年，星期一一、词 法 分 析 程 序源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokenget token.主要任务：主要任务：读源程序，产生单词符号读源程序，产生单词符号 其他任务：其他任务：滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序，追踪换行标志，复制出错源程序，宏展开，宏展开，第3页，共94页，编辑于2022年，星期一二、二、单单 词词 符符 号号单词符号一般可分为下列五种：单词符号

3、一般可分为下列五种：1、基本字、基本字（关键字关键字）：）：begin,end,if,while,var 等等2、标识符、标识符：各种名称，如常量名、变量名、过程名等：各种名称，如常量名、变量名、过程名等3、常数、常数（量）：（量）：25,3.1415,TRUE,“ABC”等等4、运算符、运算符：如：如+，-，*，/，201:=202*203试分析输入串：试分析输入串：IF a10 THEN b1:=c1*d1 ELSE b1:=5经词法分析后的输出。经词法分析后的输出。第6页，共94页，编辑于2022年，星期一解：输出的单词串为：解：输出的单词串为：(1,_)(101,a1)(201,_)(

4、102,0)(2,_)(101,b1)(202,_)(101,c1)(203,_)(101,d1)(3,_)(101,b1)(202,_)(102,5)第7页，共94页，编辑于2022年，星期一词法分析工作独立的原因：词法分析工作独立的原因：简化设计简化设计改进编译效率改进编译效率增加编译系统的可移植性增加编译系统的可移植性 第8页，共94页，编辑于2022年，星期一3.2 单单 词词 的的 描描 述述 工工 具具正规文法：正规文法：文法文法G=（VN，VT，P，S），），P中每一产生中每一产生式的式的形式都为：形式都为：AaB AaB 或或 AaAa，（右线型文法右线型文法）或或 ABa A

5、Ba 或或 AaAa，（左线型文法左线型文法）其中：其中：AVAVN N ，BVBVN N ，aV aVT T第9页，共94页，编辑于2022年，星期一一、一、几几 类类 单单 词词 的的 描描 述述标识符标识符：标识符标识符 l|l字母数字字母数字 字母数字字母数字 l|d|l字母数字字母数字|d 字母数字字母数字 无符号整数无符号整数：无符号整数无符号整数 d|d无符号整数无符号整数运算符运算符：运算符运算符+|-|*|/|=|界符界符：界符界符,|;|(|)|其中：其中：l 表示字母；表示字母；d表示数字表示数字第10页，共94页，编辑于2022年，星期一无符号实数无符号实数：无符号实数

6、无符号实数 d 余留无符号数余留无符号数|.十进小数十进小数|e指数部分指数部分 余留无符号数余留无符号数 d 余留无符号数余留无符号数|.十进小数十进小数|e指数部分指数部分|十进小数十进小数 d 余留十进小数余留十进小数余留十进小数余留十进小数 e指数部分指数部分|d 余留十进小数余留十进小数|指数部分指数部分 d 余留整指数余留整指数|s整指数整指数整指数整指数 d 余留整指数余留整指数余留整指数余留整指数 d 余留整指数余留整指数|其中其中s表示正或负号。表示正或负号。如如 25.55e+5 和和 2.1第11页，共94页，编辑于2022年，星期一二、正二、正 规规 式式(regula

7、r expression)定义定义（正规式正规式和它所表示的和它所表示的正规集正规集）：）：设字母表为设字母表为，辅助字母表，辅助字母表 =，。1、和和 都是都是 上的正规式，它们所表示的上的正规式，它们所表示的 正规集分别为正规集分别为 和和 ；2、任何、任何 a ，a 是是 上的一个正规式，它所上的一个正规式，它所 表示的正规集为表示的正规集为 a；第12页，共94页，编辑于2022年，星期一3、假定假定e1和和e2都是都是 上的正规式，它们所表示的正规集分别上的正规式，它们所表示的正规集分别为为L(e1)和和L(e2)，那么，那么，(e1),e1 e2,e1 e2,e1 也都是正规也都是

8、正规式式,它们所表示的正规集分别为它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和和(L(e1)。4、仅由有限次使用上述三步骤而定义的表达式才是、仅由有限次使用上述三步骤而定义的表达式才是 上的正规上的正规式，仅由这些正规式所表示的字集才是式，仅由这些正规式所表示的字集才是 上的正规集。上的正规集。第13页，共94页，编辑于2022年，星期一其中其中“”读为读为“或或”（也有使用（也有使用“+”代替代替“”的）；的）；“”读为读为“连接连接”；“”读为读为“闭包闭包”(即，任意有限次的自重复连接即，任意有限次的自重复连接)。在不致混淆时，括号可省去。在不致混淆时

9、，括号可省去。规定算符的优先顺序为规定算符的优先顺序为“”、“”、“”。连接符连接符“”一般可省略不写。一般可省略不写。“”、“”和和“”都是左结合的。都是左结合的。第14页，共94页，编辑于2022年，星期一例例4.2 令令=a，b，上的正规式和相应的正规上的正规式和相应的正规集的例子有：集的例子有：正规式正规式正规集正规集a a a b a,b ab ab(a b)(a b)aa,ab,ba,bb a ,a,aa,；任意个；任意个 a 的串的串(a b),a,b,aa,ab ,所有由所有由 a 和和 b 组成的串组成的串(a b)(aa bb)(a b)上所有含有两个相继上所有含有两个相继

10、 的的 a 或或两个相继的两个相继的 b 组成组成 的串的串 第15页，共94页，编辑于2022年，星期一例例 =l，d，r=l(l d)定义的正规集定义的正规集:l,ll,ld,ldd,（标识符）标识符）例例4.3 =d，.，e，+，-,则则 上的正规上的正规式式 d(.dd )(e(+-)dd )表示的表示的是无符号数的集合。其中是无符号数的集合。其中d为为09的数字。的数字。第16页，共94页，编辑于2022年，星期一 例：正规式例：正规式(1+10)*的正规集是什么？的正规集是什么？解：正规式解：正规式(1+10)*所表述的句子是：所表述的句子是：,1,10,110,101,11,11

11、10,1011,1,10,110,101,11,1110,1011,该正规式代表所有以该正规式代表所有以1开始且没有两个连续的开始且没有两个连续的0的的0，1串的集合。串的集合。第17页，共94页，编辑于2022年，星期一 例：最多只有两个相继的例：最多只有两个相继的1的的0，1串的正串的正规表达式。规表达式。解：对不包含相继的解：对不包含相继的1的所有的所有0和和1字符串的字符串的集合，正规表达式为：集合，正规表达式为：1(0+01)*或或(0+10)*1包含最多一对相继的包含最多一对相继的1的所有的所有0和和1字符串的集字符串的集合，正规表达式为：合，正规表达式为：(0+10)*11(0+

12、01)*所以，正规表达式为：所以，正规表达式为：1(0+01)*+(0+10)*1+(0+10)*11(0+01)*第18页，共94页，编辑于2022年，星期一三、三、正正 规规 式式 等等 价价若两个正规式若两个正规式e1和和e2所表示的所表示的正规集相同正规集相同,则说则说e1和和e2等价等价,写写作作e1=e2。例如：例如：e1=(a b)，e2=b a又如：又如：b(ab)=(ba)b(a b)=(a b)第19页，共94页，编辑于2022年，星期一四、四、正正 规规 式式 的的 运运 算算 律律设设 r,s,t 为正规式，正规式服从的代数规律有：为正规式，正规式服从的代数规律有：1、

13、r s=s r“或或”服从交换律服从交换律2、r(s t)=(r s)t“或或”的可结合律的可结合律3、(rs)t=r(st)“连接连接”的可结合律的可结合律4、r(s t)=rs rt (s t)r=sr tr 分配律分配律 5、r=r,r =r 是是“连接连接”的恒等元素的恒等元素6、r r=r r =r rr“或或”的抽取律的抽取律第20页，共94页，编辑于2022年，星期一五、正规文法和正规式的等价变换五、正规文法和正规式的等价变换对对 上的正规式上的正规式 r,存在一个存在一个G=(VN,VT,P,S)使得使得 L(G)=L(r)，反之亦然。反之亦然。第21页，共94页，编辑于202

14、2年，星期一1.将将 正正 规规 式式 转转 换换 成成 正正 规规 文文 法法 VT=,S VN，生成正规产生式生成正规产生式 S r (1)对形如对形如 A xy 的的正规产生式：正规产生式：A xB B y （B VN）(2)对形如对形如Ax y的的正规产生式：正规产生式：A xA A y (3)对形如对形如Ax y的的正规产生式正规产生式:A x A y 不断应用上述规则做变换，直到每个产生式最多含一个不断应用上述规则做变换，直到每个产生式最多含一个终结符。终结符。第22页，共94页，编辑于2022年，星期一例：将例：将 r=a(a d)转换成相应的正规文法。转换成相应的正规文法。GS

15、:SaA AaA AdA AVT=a,d Sa(a d)SaAA(a d)A(ad)A AAaA AdA第23页，共94页，编辑于2022年，星期一2.将将 正正 规规 文文 法法 转转 换换 成成 正正 规规 式式 文法产生式文法产生式文法产生式文法产生式 正规式正规式正规式正规式 （1）A xB,B y A=xy（2）A xA y A=x y（3）A x y A=x y第24页，共94页，编辑于2022年，星期一Gs:S aA A aA A dA S a A a A d S=aA a A =aA dA a d =(a d)A(a d)=(a d)(a d)S=a(a d)(a d)a =a

16、(a d)(a d)=a(a d)R=a(a d)第25页，共94页，编辑于2022年，星期一有文法有文法GS:SaS,SaB,BbC,CaC,Ca第26页，共94页，编辑于2022年，星期一3.3 有有 穷穷 自自 动动 机机确定的有穷自动机（确定的有穷自动机（DFA）不确定的有穷自动机（不确定的有穷自动机（NFA）NFA DFA 的转换的转换DFA的化简的化简第27页，共94页，编辑于2022年，星期一状态转换图（状态图）状态转换图（状态图）状态转换图是一张有限方向图。用结点代表状态，状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表状态之间用箭弧连接

17、，箭弧上的标记（字符）代表在射出状态下可能出现的输入字符或字符类。在射出状态下可能出现的输入字符或字符类。一个状态转换图只包含有限个状态，有一个初态一个状态转换图只包含有限个状态，有一个初态（用（用标识标识），至少有一个终态（用双圈表示）。），至少有一个终态（用双圈表示）。ST字母字母字母或数字字母或数字S：初态；：初态；T：终态；：终态；第28页，共94页，编辑于2022年，星期一一、一、DFA 的的 定定 义义 DFADFA定义定义定义定义：一个确定的有穷自动机（：一个确定的有穷自动机（DFA）M是一个五元是一个五元组：组：M=（K，f，S，Z）其中其中:1 1。K K 是一个有穷集，是一

18、个有穷集，状态集状态集,它的每个元素称为一个状态；它的每个元素称为一个状态；2 2。是一个有穷字母表，它的每个元素称为一个输入符号，所以也称是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为为输入符号表输入符号表；3 3。f f 是是转换函数转换函数，是在，是在 KK 上的映射，即，如上的映射，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为 a 时，时，将转换为下一个状态将转换为下一个状态 kj，我们把我们把 kj 称作称作 k ki 的一个后继状态；的一个后继状态；4。S SK K 是唯一的一个是唯一的一个初态初态；

19、5 5。Z Z K 是一个是一个终态集终态集，终态也称，终态也称可接受状态可接受状态或或结束状态结束状态。第29页，共94页，编辑于2022年，星期一1.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）=Q第30页，共94页，编辑于2022年，星期一2.DFA 的的 状状 态态 图图 表示表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V,b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUV

20、Qaaaba，bb第31页，共94页，编辑于2022年，星期一3.DFA 的的 矩矩 阵阵 表表 示示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q字符字符状态状态0100第32页，共94页，编辑于2022年，星期一*上的符上的符号号串串 t 在在 M 上运行上运行一个输入符一个输入符号号串串t，（，（我们将它表示成我们将它表示成t1tx的形式，其中的形式，其中t1，tx*）在）在DFA M上上运行运行的定义为：的定义为：f（Q，t1tx）=f（f（Q，t1），），tx）其中其中QK扩充转换函数扩充转换函数f f

21、，是是K*K上的映射，且：上的映射，且：f（Q，）=Q递归定义递归定义第33页，共94页，编辑于2022年，星期一4.*上的符上的符号号串串 t 被被 M 接受接受对于对于*中的任何字符串中的任何字符串t，若存在一条从初态结点到某若存在一条从初态结点到某一终态结点的道路，且这条路上所有弧的的标记符连一终态结点的道路，且这条路上所有弧的的标记符连接成的字符串等于接成的字符串等于t，则称则称t可为可为DFA M所接受，若所接受，若M的的初态结点同时又是终态结点，则空字初态结点同时又是终态结点，则空字()可为可为M所所接受接受（识识别别）。）。若若 t *，f(S，t)=P，其中其中 S 为为 DF

22、A M 的开始状态，的开始状态，P Z，Z为终态集。为终态集。则称则称 t 为为 DFA M所所接受接受（识别识别）。）。第34页，共94页，编辑于2022年，星期一例：证明例：证明 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）=Q第35页，共94页，编辑于2022年，星期一bSUVQaaaba，bb证明：证明：f（S，baab）=f（f（S，b），），aab）=f（V，aab）=f（

23、f（V，a），），ab）=f（U，ab）=f（f（U，a），），b）=f（Q，b）=QQ属于终态。得证。属于终态。得证。第36页，共94页，编辑于2022年，星期一5.确定的有穷自动机（确定的有穷自动机（DFA）接受的语言）接受的语言DFA M=（K，f，S，Z）所能接所能接受的符号串的全体记为受的符号串的全体记为 L(M)L(M)=x|f(S,x)Z,x 结论：结论：上一个字符串集上一个字符串集 V 是正规的，是正规的，当且仅当，存在一个当且仅当，存在一个 上的确定有穷上的确定有穷自动机自动机 M，使得使得 V=L(M)。第37页，共94页，编辑于2022年，星期一DFA M=（K，f，S，

24、Z）的行为的模拟程序的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c);if K=then break else c:=getchar;if K is in Z then return(yes)else return(no)第38页，共94页，编辑于2022年，星期一二、不确定的有穷自动机二、不确定的有穷自动机NFA定义定义N=(K，f，S，Z)，其中其中K为状态为状态的有的有穷非空穷非空集集，为为有穷输入有穷输入字母表字母表，f为映射为映射函数函数，f:K *2K，S K是初是初始状始状态态集集，Z K为终为终止状止状态集态集。第39页，共94页，

25、编辑于2022年，星期一1.状状 态态 图图 表表 示示例例:NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中：f（S，0）=P f（S，1）=S，Zf（P，1）=Z f（Z，0）=Pf（Z，1）=PSPZ00,1111第40页，共94页，编辑于2022年，星期一2.矩矩 阵阵 表表 示示简化为简化为例：例：NFA N=（S，P，Z，0，1，f，S，P，Z）其中：其中：f（S，0）=P f（S，1）=S，Z f（P，1）=Z f（Z，0）=P f（Z，1）=P第41页，共94页，编辑于2022年，星期一*上的符上的符号号串串t在在NFA N上运行。上运行。*上的符上的符号号串串t被被

26、NFA N接受（识别）。接受（识别）。具有具有 转移的不确定的有穷自动机转移的不确定的有穷自动机 NFAf为为 K （）到）到2K的的映射。的的映射。对任何一个具有对任何一个具有 转移的不确定的有穷自动机转移的不确定的有穷自动机NFA N，一定存在一个不具有一定存在一个不具有 转移的不确定的有穷自动转移的不确定的有穷自动机机NFA，使得，使得L(M)=L(N)。第42页，共94页，编辑于2022年，星期一例：例：NFA N01234aabba,ba,ba,bN所能识别的那些含有相继两个所能识别的那些含有相继两个a或相继两个或相继两个b的串。的串。第43页，共94页，编辑于2022年，星期一NF

27、A与DFA的区别NFA有一个开始状态集，而有一个开始状态集，而DFA只有一只有一个初态；个初态；NFA的映射是多值映射，而的映射是多值映射，而DFA是一个是一个单值映射；单值映射；第44页，共94页，编辑于2022年，星期一三、三、NFA 的的 确确 定定 化化DFA是是NFA的特例的特例.对每个对每个NFA M一定存一定存在一个在一个DFA ，使得，使得 L(M)=L(M)。对每个对每个NFA M存在着与之存在着与之等价等价的的DFA M 。与某一与某一NFA等价的等价的DFA不唯一。不唯一。第45页，共94页，编辑于2022年，星期一1.定义对状态集合定义对状态集合I的几个有关运算的几个有

28、关运算1 状态集合状态集合 I 的的 -闭包，表示为闭包，表示为 -closure(I)，定义为一定义为一状态集，是状态集状态集，是状态集 I 中的任何状态中的任何状态 R 经经任意条任意条 弧弧而能而能到达的状态的集合。到达的状态的集合。状态集合状态集合I的任何状态的任何状态 R 都属于都属于 -closure(I)。2 状态集合状态集合 I 的的 a 弧转换，表示为弧转换，表示为 move(I,a)定义为状态定义为状态集合集合 J，其中其中 J 是所有那些可从是所有那些可从 I 的某一状态经过的某一状态经过一条一条 a 弧弧而到达的状态的全体。而到达的状态的全体。3 定义：定义：Ia =-

29、closure(J)，其中：，其中：J=move(I,a)第46页，共94页，编辑于2022年，星期一例例I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；move(1,2,a)=5,4,3-closure(5,3,4)=5,4,3,6,2,8,7；15243687aaa第47页，共94页，编辑于2022年，星期一2.NFA 到 DFA 的 等 价 变 换 算 法假设假设 NFA N=(K,f,K0,Kt)按如下办法构造按如下办法构造一个一个 DFA M=(S,d,S0,St)，使得使得L(M)=L(N)：1.M的状态集的状态集S由由K的一些子集组成。用的一些

30、子集组成。用S1 S2.Sj表表示示S的元素，其中的元素，其中S1,S2,.Sj是是K的状态。并且约定，状的状态。并且约定，状态态S1,S2,.Sj是按某种规则排列的，即对于子集是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，来说，S的状态就是的状态就是S1 S2；第48页，共94页，编辑于2022年，星期一2.M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是；3.转换函数是这样定义的：转换函数是这样定义的：D(S1,S2,.,Sj,a)=R1,R2,.,Rt其中其中：R1,R2,.,Rt=-closure(move(S1,S2,.,Sj,a)4.S0=-closure

31、(K0)为为M的开始状态；的开始状态；5.St=Si,Sk,.,Se|Si,Sk,.,Se S 且且 Si,Sk,.Se Kt 第49页，共94页，编辑于2022年，星期一构造构造NFA N的状态的状态K的子集的算法：的子集的算法：假定所构造的子集族为假定所构造的子集族为C，即即C=(T1,T2,.TI),其中其中T1,T2,.TI为状态为状态K的子集。的子集。1.开始，令开始，令-closure(K0)为为C中唯一成员，中唯一成员，并且它是未被标记的。并且它是未被标记的。第50页，共94页，编辑于2022年，星期一2.while（C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标

32、记T；for 每个输入字母每个输入字母a do U:=-closure(move(T,a)；if U不在不在C中中 then 将将U作为未标作为未标记的子集加在记的子集加在C中中 第51页，共94页，编辑于2022年，星期一例，将下图的例，将下图的NFA N转换成转换成DFA M023456789101bbbaaNFA N第52页，共94页，编辑于2022年，星期一023456789101bbbaa-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(0)=0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7 加入为T2T1

33、=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,6,7,10 加入为T4T4=1,2,4,5,6,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2第53页，共94页，编辑于2022年，星期一-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(0)=0,1,2,4,71,2,

34、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,6,7,10 加入为T4T4=1,2,4,5,6,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2初态终态b02134abaaaabbbDFA M第54页，共94页，编辑于2022年，星期一将下图将下图NFA

35、确定化：确定化：SQVUZ0，110，1110001第55页，共94页，编辑于2022年，星期一四、四、DFA 的最小化（化简）的最小化（化简）最小状态最小状态DFA没有多余状态没有多余状态(死状态死状态)没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）两个状态两个状态s和和t等价：满足等价：满足一致性一致性同是终态或同是非终态同是终态或同是非终态蔓延性蔓延性从从s出发读入某个出发读入某个a a和和从从 t出发出发读入某个读入某个a到达的状到达的状态等价。态等价。第56页，共94页，编辑于2022年，星期一消消 除除 多多 余余 状状 态态s1 s5s2 s7s2 s5s5

36、 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7第57页，共94页，编辑于2022年，星期一如图，状态0和4是可区别的。状态2和3是可区别的，因为读入b后分别到达2和4，而2和4不是等价的。DFA Mb02134abaaaabbb第58页，共94页，编辑于2022年，星期一对于一

37、个对于一个DFA M=DFA M=（K,f,kK,f,k0 0,k,kt t)，存在一个存在一个最小状最小状态态DFA M=（K K,f,f,k,k0 0,k,kt t)，使使L(M)=L(M).算法的核心：算法的核心：把把M的状态集的状态集K分成不相交的子集分成不相交的子集。结论结论接受接受L的最小状态有穷自动机不计同构是唯一的。的最小状态有穷自动机不计同构是唯一的。第59页，共94页，编辑于2022年，星期一最小化方法最小化方法-分割法分割法把一个把一个DFA（不含多余状态）的状态分（不含多余状态）的状态分成一些不相交的子集，使得任何不同的成一些不相交的子集，使得任何不同的两个子集的状态都

38、是可区分的，而同一两个子集的状态都是可区分的，而同一个子集中的任何两个状态都是等价的。个子集中的任何两个状态都是等价的。第60页，共94页，编辑于2022年，星期一将下图中的将下图中的DFA M最小化最小化1,2 3,4 5 6,71,2 3 4 5 6,713546aaaaabbbbb 1,2,3,4,5,6,7Ia:6,7,1,4,7,4,4Ib:3,3,5,6,3,1,21,2,3,4 5,6,71352746aaaaaaabbbbbbb第61页，共94页，编辑于2022年，星期一五、五、正规式正规式和有穷自动机的等价性和有穷自动机的等价性1.对于对于上的上的NFA M，可以构造一个，可

39、以构造一个上的正规式上的正规式R,R,使得使得L(R)=L(M)。2 2.对于对于上的一个正规式上的一个正规式R，可以构造，可以构造一个一个上的上的NFA M，使得，使得L(M)=L(R)。第62页，共94页，编辑于2022年，星期一1.对于对于上的上的NFA M，可以构造一个，可以构造一个上的正上的正规式规式R,R,使得使得L(R)=L(M)。第一步：在第一步：在M的状态转换图上的状态转换图上加进两个结点加进两个结点，一个为，一个为x结点，结点，一个为一个为y结点。从结点。从x结点用结点用弧连接到弧连接到M的的所有初态结点所有初态结点，从从M的的所有终态结点所有终态结点用用弧连接到弧连接到y

40、结点。形成一个与结点。形成一个与M等价的等价的M,M只有只有一个初态一个初态x和和一个终态一个终态y。第二步：逐步消去第二步：逐步消去M中的所有结点，直至只剩下中的所有结点，直至只剩下x和和y。（消去规则见下页）消去规则见下页）最后最后x和和y结点间的弧上的标记则为所求的正规式结点间的弧上的标记则为所求的正规式R。第63页，共94页，编辑于2022年，星期一123R1R213R1 R213R1R213R1|R2123R1R3R213R1 R2*R3第64页，共94页，编辑于2022年，星期一例：求该求该NFA所对应的正规式所对应的正规式R.03124a,baaa,ba,bbb第65页，共94页

41、，编辑于2022年，星期一03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy第66页，共94页，编辑于2022年，星期一a|b024a|baaa|bbbxy0a|baa(a|b)*bb(a|b)*xy第67页，共94页，编辑于2022年，星期一0a|baa(a|b)*bb(a|b)*xyxy(a|b)*(aa|bb)(a|b)*0a|bxyaa(a|b)*|bb(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*第68页，共94页，编辑于2022年，星期一2 2.对于对于上的一个正规式上的一个正规式R，可以构造一个，可以构造一个上的上的NF

42、A M，使得，使得L(M)=L(R)。(1)R=,任一具有空终态集的任一具有空终态集的NFA M(2)R=，NFA M=(k0,f,k,f,k0 0,kk0 0):):f f（k k0 0,a),a)对于对于 所有所有a 都没定义。都没定义。(3)R=a,NFA M=,NFA M=(k0,k1,f,k,f,k0 0,kk1 1):f():f(k0,a)=k1xyk0k1a ak0第69页，共94页，编辑于2022年，星期一 (4)R=R1|R2,分别将步骤（分别将步骤（1）（）（2）（）（3）应用到）应用到R1,R2 产生产生M1=(K1,1,f,f1,k,k1,F,F1),M2=(K2,2,

43、f,f2,k,k2,F,F2),),其中其中K K1,K,K2不相交不相交.则，则，NFA M=NFA M=(K1 K2 k0,f,k,f,k0,F),F)，k k0是新增加的状态符号是新增加的状态符号:=1 2；f f=f=f1 f f2 f(kf(k0,)=k)=k1,k,k2；F=F1 F2k0k1M1M1k2M2M2第70页，共94页，编辑于2022年，星期一 (5)R=R1 R2,分别将步骤分别将步骤(1)(2)(3)应用到应用到R1,R2 产生产生M1=(K1 1,1 1,f,f1 1,k,k1 1,F,F1 1),M2=(K2 2,2 2,f,f2 2,k,k2 2,F,F2 2

44、),),K K1 1,K,K2 2不相交不相交.则，则，NFA MNFA M =(K1 1 K2 2,1 1 2 2,f,f,k k1,F,F2 2 ):):f f=f1=f1 f2f2 对对F F1 1中的所有终态中的所有终态k k有：有：f1(k,f1(k,)=k2 2 。k1M1M1k2M2M2第71页，共94页，编辑于2022年，星期一(6)R=R*,分别将步骤分别将步骤(1)(2)(3)应用到应用到R 产生产生M1=(K1 1,f,f1 1,k,k1 1,F,F1 1).).则，则，NFA M=NFA M=(K1 k0 0，kf f,f,f,k k0 0,k kf f):):k0 0

45、，kf f是新增加的状态符号，是新增加的状态符号，f f=f=f1 1 f(f(k0 0,)=)=kf f，f(f(k k0 0,)=)=k k1 1 f(f(k,)=)=kf f ：k k F F1 1 f(k,)=k1：k F F1 1k1M1M1kfk0kf第72页，共94页，编辑于2022年，星期一例例:为为 R=(a|b)*abb 构造构造NFA N，使得使得 L(N)=L(R)。23a54bR=(a|b)*abbR=(a|b)*abbR=(a|b)*abb2354ab16第73页，共94页，编辑于2022年，星期一R=(a|b)*abbR=(a|b)*abb继续加上abb即可得到结

46、果。2354ab162354ab1607第74页，共94页，编辑于2022年，星期一R=(a|b)*abb继续对abb进行分解。xjyabbiabxjyabbia|bxiy(a|b)*abb第75页，共94页，编辑于2022年，星期一为正规式为正规式 dd*(.dd*|)(e(+|-|)dd*|)构造构造NFA.1234675dd.ddee+-ddd第76页，共94页，编辑于2022年，星期一例：下图例：下图NFA所接受的字符串所接受的字符串ABaab接受字符串的接受字符串的 的的NFA第77页，共94页，编辑于2022年，星期一SCDBAaaaaabbbbb写出下图自动机所表示的语言。写出下

47、图自动机所表示的语言。第78页，共94页，编辑于2022年，星期一六、正规文法和有穷自动机间的转换六、正规文法和有穷自动机间的转换1.采用下面的规则从正规文法采用下面的规则从正规文法G=(VT,VN,S,P)直接构造一个直接构造一个有穷自动机有穷自动机NFA M=(,K,f,k0,Z)，使得：使得：L(M)=L(G)：字母表与字母表与 G 的终结符集相同，的终结符集相同，=VT；增加一个新状态增加一个新状态kf，作为作为NFA的终态，的终态，Z=kf；G中的每个非终结符作中的每个非终结符作为为M的一个状态，的一个状态，(不妨取称相同的名字不妨取称相同的名字),K=VN kf；G的开始符号为的开

48、始符号为M的开始状态，的开始状态，k0=S；对对G中的形如中的形如AaB的产生式（其中的产生式（其中a为终结符或为终结符或，A和和B为非终结符）为非终结符），构造，构造M的一个转换函数的一个转换函数f(A,a)=B；对对G中形如中形如Aa的产生式的产生式,构造构造M的一个转换函数的一个转换函数f(A,a)=Z。右线性文法右线性文法第79页，共94页，编辑于2022年，星期一例例1：与文法：与文法GS等价的等价的NFA M(右线性右线性)GS：SaASbBSAaBAbABaSBbABSABZaabbab第80页，共94页，编辑于2022年，星期一采用下面的规则将一个有穷自动机采用下面的规则将一个

49、有穷自动机NFA M转换成转换成正规文法正规文法G，使得，使得L(G)=L(M)：G的终结符集与字母表相同；的终结符集与字母表相同；M的每一个状态对应的每一个状态对应G中的每个非终结符中的每个非终结符,开始状态开始状态S是是G的开始符号的开始符号；转换函数转换函数f(A,a)=B对应对应G中的形如中的形如AaB的产生式（其的产生式（其中中a为终结符或为终结符或，A和和B为非终结符）为非终结符）；对终态结点对终态结点Z,对应对应G中形如中形如Z的产生式的产生式。第81页，共94页，编辑于2022年，星期一例例:为下面的为下面的DFA N，构造出等价的正规文法构造出等价的正规文法G。文法GA：Aa

50、B|bDBbCCaA|bD|DaB|bD|BCabADaabbb第82页，共94页，编辑于2022年，星期一SCDBAaaaaabbbbb写出下图自动机所表示的语言。写出下图自动机所表示的语言。可得可得GS:S aA|bCA aB|bS|B aB B aB|bAC aS|bDD aA|bC|第83页，共94页，编辑于2022年，星期一用消元法表示出下列文法的语言用消元法表示出下列文法的语言GS:S0A|1B|0 A0A|1B|0S B 1B|1|0第84页，共94页，编辑于2022年，星期一七、词法分析程序的自动构造工具七、词法分析程序的自动构造工具把正规式转换为一个把正规式转换为一个NFA进