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

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

1、第3章词法分析第1页，共118页，编辑于2022年，星期一第第3 3章词法分析章词法分析1.1.本章介绍编译第一个阶段词法分析的本章介绍编译第一个阶段词法分析的设计原理和设计方法设计原理和设计方法，要求明确此阶段的要求明确此阶段的任务任务。2.2.理解通常的单词理解通常的单词分类和构词规则分类和构词规则。3.3.会使用单词的会使用单词的描述和识别描述和识别机制。机制。4.4.要求掌握要求掌握正规文法、状态图、正规文法、状态图、DFADFA、NFANFA、正规式和正规、正规式和正规集集的基本概念和它们之间的关系。的基本概念和它们之间的关系。5.5.掌握词法分析程序的掌握词法分析程序的手工手工实现

2、方法。实现方法。6.6.掌握词法分析程序的掌握词法分析程序的自动自动构造原理。构造原理。教学目标教学目标第2页，共118页，编辑于2022年，星期一3.1 3.1 词法分析的任务词法分析的任务3.2 3.2 词法分析程序的输出形式词法分析程序的输出形式3.3 3.3 词法分析程序的设计与实现词法分析程序的设计与实现3.4 3.4 正规式与有穷自动机正规式与有穷自动机3.5 3.5 词法分析程序的自动生成工具词法分析程序的自动生成工具LEXLEX3.6 PL/03.6 PL/0编译程序的词法分析编译程序的词法分析教学内容教学内容第3页，共118页，编辑于2022年，星期一（1 1）分析和识别单词

3、及属性，分析和识别单词及属性，包括识别包括识别语言的语言的关键字关键字、标识符、常数、运算符等、标识符、常数、运算符等；（2 2）跳过各种分隔符，如空格，回车，制表符等；跳过各种分隔符，如空格，回车，制表符等；（3 3）删除注释；）删除注释；（4 4）进行词法检查，报告所发现的错误；）进行词法检查，报告所发现的错误；（5 5）建立符号表。）建立符号表。3.13.1词法分析的任务词法分析的任务第4页，共118页，编辑于2022年，星期一main()/*ADD*/int x=10,y=20,sum;sum=x+y;main、(、)、int、x、=、10、,、y、=、20、,、sum、;、sum、=

4、、x、+、y、;、词法分析词法分析 第5页，共118页，编辑于2022年，星期一实现方案：实现方案：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析词法分析S.P.(符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串优点优点:结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺点：效率低S.P.(字符串)词法分词法分析程序析程序语法分语法分析程序析程序取单词取单词单词单词第6页，共118页，编辑于2022年，星期一单词的种类单词的种类（1 1）关键）关键字：字：if、for、while（2 2）标识符：标识符：（3 3）常数：常数：

5、（4 4）运算符：运算符：+、-、*（5 5）分界符：）分界符：,、;、(、)3.23.2词法分析程序的输出形式词法分析程序的输出形式第7页，共118页，编辑于2022年，星期一词法分析程序的输出形式词法分析程序的输出形式-二元式二元式单词类别单词类别 单词的属性值单词的属性值单词类别可以用整数编码表示单词类别可以用整数编码表示:一类一种或一字一种一类一种或一字一种单词类别单词类别关键字关键字标识符标识符常数常数运算符运算符分界符分界符编码编码1 12 23 34 45 5第8页，共118页，编辑于2022年，星期一表3.1 int x=10,y=20,sum;词法分析的结果单词类别单词类别单

6、词的属性值单词的属性值1int2指向指向x的符号表入口指针的符号表入口指针4=3105,2指向指向y的符号表入口指针的符号表入口指针4=3205,2指向指向sum的符号表入口指针的符号表入口指针5;表表3.1intx=10,y=20,sum;词法分析的结果词法分析的结果第9页，共118页，编辑于2022年，星期一3.33.3词法分析程序的设计与实现词法分析程序的设计与实现词法规则词法规则状态图状态图词法分析程序词法分析程序第10页，共118页，编辑于2022年，星期一结点结点代表状态，用圆圈表示，为非终结符代表状态，用圆圈表示，为非终结符有向弧有向弧表示状态转移表示状态转移弧上的标记弧上的标记

7、表示在射出弧的结点状态下可能出现的输入字符，表示在射出弧的结点状态下可能出现的输入字符，为终结符为终结符1.状态图：状态图：为识别单词而专门设计的有向图，为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。是设计词法分析程序的一种好途径。SUVZ111000一张状态图包含有穷个状态，一张状态图包含有穷个状态，只能有一个只能有一个初态初态，至少要有一，至少要有一个个终态终态（用双圈表示）（用双圈表示）3.3.1 3.3.1 正规文法及其状态图正规文法及其状态图第11页，共118页，编辑于2022年，星期一【例例3.1】某语言的标识符可使用以下正规文法某语言的标识符可使用以下正规文法GS

8、来定义：来定义：SlAA|lA|dAla,b,z，d1,2,9试构造此文法的状态图。试构造此文法的状态图。SAll|d状态图可识别单词状态图可识别单词第12页，共118页，编辑于2022年，星期一2.由正规文法构造状态图由正规文法构造状态图（1）对于右线性文法）对于右线性文法步骤步骤1增加结点增加结点Z为终态；为终态；步骤步骤2将每个非终结符号设置为一个对应的状态；将每个非终结符号设置为一个对应的状态；步骤步骤3对于对于Aa，引一条从，引一条从A到到Z的弧，弧上标记为的弧，弧上标记为a；而对于而对于AaB，引一条从，引一条从A到到B的弧，弧上标记为的弧，弧上标记为a。SlAA|lA|dAl|d

9、AZSlAZll|d第13页，共118页，编辑于2022年，星期一（2）对于左线性文法）对于左线性文法步骤步骤1增加结点增加结点S为初态；为初态；步骤步骤2将每个非终结符号设置为一个对应的状态；将每个非终结符号设置为一个对应的状态；步步骤骤3对对于于Aa，引引一一条条从从S到到A的的弧弧，弧弧上上标标记记为为a；而而对对于于ABa，引一条从，引一条从B到到A的弧，弧上标记为的弧，弧上标记为a。Al|Al|Adl|dASlSlAA|lA|dA第14页，共118页，编辑于2022年，星期一词法规则词法规则状态图状态图词法分析程序词法分析程序3.3.2 3.3.2 词法分析程序的实现词法分析程序的实

10、现（1 1）根据词法规则写出正规文法；根据词法规则写出正规文法；（2 2）将正规文法转换成状态图；将正规文法转换成状态图；（3 3）将状态图转换成流程图。将状态图转换成流程图。第15页，共118页，编辑于2022年，星期一 标识符标识符 关键字关键字(标识符的子集）标识符的子集）常数常数 运算符运算符 +、*、=分界符分界符 ,、;【例例3.23.2】假设某种语言的单词符号的子集有：假设某种语言的单词符号的子集有：试构造此语言子集的词法分析程序。试构造此语言子集的词法分析程序。第16页，共118页，编辑于2022年，星期一（1 1）根据词法规则写出正规文法根据词法规则写出正规文法字母字母|字母

11、字母|数字）数字）数字数字|数字数字+|*|,|;=第17页，共118页，编辑于2022年，星期一标识符标识符出口出口S1非字母数字非字母数字字母字母字母、数字字母、数字无符号整数无符号整数出口出口S2非数字非数字数字数字数字数字单字符分界符单字符分界符出口出口S3其他字符其他字符+*=,;双字符分界符双字符分界符出口出口S4其他字符其他字符5=非非=字母字母|字母字母|数字）数字）数字数字|数字数字+|*|+|*|,|;=（2 2）将正规文法转换成状态图将正规文法转换成状态图第18页，共118页，编辑于2022年，星期一合并合并 将初始状态合并为一个唯一的初态；将初始状态合并为一个唯一的初态

12、；化简调整状态冲突并对冲突状态重新编号；化简调整状态冲突并对冲突状态重新编号；如有必要，增加出错状态。如有必要，增加出错状态。第19页，共118页，编辑于2022年，星期一标识符标识符无符号整数无符号整数单界符单界符双界符双界符S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+*，（）出口出口4其他字符其他字符5=非非=出错出错其他其他读字符读字符查保留字表查保留字表返回返回S合并后的状态图合并后的状态图第20页，共118页，编辑于2022年，星期一（3 3）将状态图转换成流程图，如图）将状态图转换成流程图，如图3.53.5写出词法分析程序写

13、出词法分析程序第21页，共118页，编辑于2022年，星期一3.5字母表字母表,定义在定义在 上的正规式和正规集递归定义如下上的正规式和正规集递归定义如下:1.1.和和 都是都是 上的正规式上的正规式,它们所表示的正规集分别为它们所表示的正规集分别为:和和;2.2.任何任何a a ,a,a是是 上的正规式上的正规式,它所表示的正规集为它所表示的正规集为:a;:a;3.3.假定假定U U和和V V 上的正规式上的正规式,它们所表示的正规集分别记为它们所表示的正规集分别记为L(e1)L(e1)和和L(e2),L(e2),那么那么e1|e2,e1e1|e2,e1e2e2和和e1e1*也都是也都是 上

14、的正规式上的正规式,它们所表示的它们所表示的 正规集分别为正规集分别为L(e1)L(e1)L(e2)L(e2)、L(e1)L(e1)L(e2)L(e2)和和(L(e1)(L(e1)*4.4.任何任何 上的正规式和正规集均由上的正规式和正规集均由1 1、2 2和和3 3产生。产生。3.43.4正规表达式与有穷自动机正规表达式与有穷自动机3.4.1 3.4.1 正规式与正规集正规式与正规集第22页，共118页，编辑于2022年，星期一正规式中的运算符：正规式中的运算符：|-或（选择）或（选择）-连接连接*或或-重复重复（）（）-括号括号运算符的优先级：运算符的优先级：先先*,后后,最后最后|在正规

15、式中可以省略在正规式中可以省略.正规式相等正规式相等这两个正规式表示的语言相等这两个正规式表示的语言相等第23页，共118页，编辑于2022年，星期一【例例3.3】设设=a,b正规式正规式正规集正规集ba*所有以所有以b为首后跟任意多个为首后跟任意多个a的符号串的符号串a(a|b)*所有以所有以a为首的符号串为首的符号串(a|b)*abb所有以所有以abb为尾的为尾的a，b符号串符号串(a|b)*(aa|bb)(a|b)*所有含有两个相继的所有含有两个相继的a或相继的或相继的b的符号串的符号串(aa|ab|ba|bb)*空串和任何长度为偶数的符号串空串和任何长度为偶数的符号串(a|b)(a|b

16、)(a|b)*任何长度大于等于任何长度大于等于2的符号串的符号串第24页，共118页，编辑于2022年，星期一【例例3.3】使用正规式来表示例使用正规式来表示例3.2中的相应单词符号。中的相应单词符号。字母字母|字母字母|数字）数字）数字数字|数字数字+|*|+|*|,|;=标识符：标识符：l(l|d)*无符号整数：无符号整数：dd*单界符：单界符：+|*|,|;双界符：双界符：=第25页，共118页，编辑于2022年，星期一设设r，s，t均是正规式，则有以下性质：均是正规式，则有以下性质：（1）交换律：）交换律：r|s=s|r（2）结合律：）结合律：r|(s|t)=(r|s)|t(rs)t=

17、r(st)（3）分配律：）分配律：(r|s)t=rt|st（4）同一律：）同一律：r=r=r第26页，共118页，编辑于2022年，星期一1.正规文法正规文法正规式正规式规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xyA=xA=x*y yA=x|yA=x|y步骤步骤1将每条产生式改写为正规式；将每条产生式改写为正规式；步步骤骤2用用代代入入法法解解正正规规式式方方程程组组，最最后后只只剩剩下下一一个个开开始始符号定义的正规式，其中不含非终结符。符号定义的正规式，其中不含非终结符。3.4.2

18、 3.4.2 正规文法与正规式正规文法与正规式第27页，共118页，编辑于2022年，星期一【例例3.5】GS:SaA|aAdA|d规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xyA=xA=x*y yA=x|yA=x|yS=aA|aA=d*d代入代入:S=ad*d|aad*第28页，共118页，编辑于2022年，星期一2.正规式正规式正规文法正规文法步骤步骤1构造构造Sr步骤步骤2不断利用表不断利用表3.4的规则做变换的规则做变换,直到每个产生式最多含有直到每个产生式最多含有一个终结符为止

19、一个终结符为止规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xyA=xA=x*y yA=x|yA=x|y第29页，共118页，编辑于2022年，星期一【例例3.6】求正规式求正规式(a|b)(a|b|0|1)*对应的正规文法对应的正规文法S(a|b)(a|b|0|1)*S(a|b)AaA|bA|0A|1A|GS：SaA|bAAaA|bA|0A|1A|A(a|b|0|1)*第30页，共118页，编辑于2022年，星期一下面是用正规式表示的变量声明：下面是用正规式表示的变量声明：(int|flo

20、at)id(,id)*请请改改用用上上下下文文无无关关文文法法表表示示，也也就就是是写写一一个个上上下下文文无无关关文文法法，它和该正规式等价。它和该正规式等价。(int|float)id(,id)*D(int|float)LLid(,id)*DintL|floatLLL,id|idGD：DintL|floatLLL,id|id第31页，共118页，编辑于2022年，星期一3.4.3 3.4.3 有穷自动机有穷自动机标识符标识符无符号整数无符号整数单界符单界符双界符双界符S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+*，（）出口出口4其他

21、字符其他字符5=非非=出错出错其他其他读字符读字符查保留字表查保留字表返回返回S状态图的形式化描述第32页，共118页，编辑于2022年，星期一有穷自动机是一种有穷自动机是一种数学模型数学模型，具有离散的输入与输出，系统可处，具有离散的输入与输出，系统可处于有穷状态中的任何一个于有穷状态中的任何一个它能准确地它能准确地识别正规集识别正规集，即识别正规文法所定义的语言和正规式所，即识别正规文法所定义的语言和正规式所表示的集合表示的集合引入有穷自动机这个理论，正是为引入有穷自动机这个理论，正是为词法分析程序的自动构造词法分析程序的自动构造寻找特殊的方法和工具寻找特殊的方法和工具有穷自动机分为两类：

22、有穷自动机分为两类：确定的有穷自动机确定的有穷自动机（DFADFA）(Deterministic Finite Automata)(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机（NFANFA）(Nondeterministic Finite Automata)(Nondeterministic Finite Automata)第33页，共118页，编辑于2022年，星期一2 2型文法型文法（不确定（不确定的下推自动机）的下推自动机）1 1型文法型文法（不确定（不确定的界限自动机）的界限自动机）0 0型文法型文法（图灵机）（图灵机）3 3型文法

23、型文法（有限（有限自动机）自动机）第34页，共118页，编辑于2022年，星期一1.确定的有穷自动机（确定的有穷自动机（DFA）M=(,Q,f,S,Z)：有穷字母表，它的每个元素称为一个输入符号：有穷字母表，它的每个元素称为一个输入符号Q：有穷集，它的每个元素称为一个状态：有穷集，它的每个元素称为一个状态SK，是唯一的初态，是唯一的初态Z K是一个终态集，终态也称可接受状态或结束状态是一个终态集，终态也称可接受状态或结束状态f是转换函数，是是转换函数，是QQ上的单值映射：上的单值映射：f（q1，a）=q2第35页，共118页，编辑于2022年，星期一状态转移函数状态转移函数f可用一矩阵来表示：

24、可用一矩阵来表示：输入输入字符字符状态状态ab012132213333例如例如:M:M:（0,1,2,3,a,b,0,1,2,3,a,b,f，0，3）f（0，a）=1f（0，b）=2f（1，a）=3f（1，b）=2f（2，a）=1f（2，b）=3f（3，a）=3f（3，b）=3所谓确定的状态机，其确定性表现在状态转移函数是单值函数！字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。M=(,Q,f,S,Z)第36页，共118页，编辑于2022年，星期一一个DFA也可以用一状态转换图表示：输入 字符 状态 a b 0 1 2 1 3 2 2 1 3

25、3 3 3DFA的状态图表示：1032aabba,bba字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。第37页，共118页，编辑于2022年，星期一换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串，则称为DFA M（接受）识别。DFA MDFA M所接受的语言为：所接受的语言为：L(M)=|L(M)=|f(S,)=S)=Sn,n,S Sn n ZZDFA MDFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)L(M)若若M M的初态结点同时为终态，或者存在一条从初态到某个终态结点的的初

26、态结点同时为终态，或者存在一条从初态到某个终态结点的通路，通路，则则为为M M所识别。所识别。第38页，共118页，编辑于2022年，星期一 （0，abaab）=（1，baab）=（2，aab）=（1，ab）=（3，b）=3(接受接受)DFADFA的状态图表示：的状态图表示：1032aabba,bba （0，abab）=（1，bab）=（2，ab）=（1，b）=2(拒绝拒绝)对于符号串对于符号串abaababaab对于符号串对于符号串abababab第39页，共118页，编辑于2022年，星期一f是一个多值函数，是从是一个多值函数，是从Q*到到Q的子集的映射：的子集的映射：f：Q2Q其中其中2

27、Q是是Q的幂集，即的幂集，即Q中所有子集组成的集合。中所有子集组成的集合。2.不确定的有穷自动机（不确定的有穷自动机（NFA）M=(,Q,f,S,Z)有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的个后继状态，即状态的转向是不确定的第40页，共118页，编辑于2022年，星期一例：例：NFAN=(a,b,c,1,2,3,4,f,1,4)符号符号状态状态abc142，322433，44第41页，共118页，编辑于2022年，星期一对于对于*上的任何符号串上的任何符号串，若存在一条从某一初

28、态到某一，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接成的终态的通路，且该通路上所有弧的标记字符依次连接成的串等于串等于，则称，则称 可以被可以被NFAN所识别或接受。所识别或接受。若若N的初态结点同时为终态，或者存在一条从初态到某个终的初态结点同时为终态，或者存在一条从初态到某个终态结点的态结点的 通路，则通路，则 为为N所识别。所识别。NFAN所能识别的符号串的全体记为所能识别的符号串的全体记为L(N)，称为，称为NFAN所识别的语言所识别的语言 第42页，共118页，编辑于2022年，星期一上例题相应的状态图为：1234abacacN所接受的语言（正规式）R=

29、aa*b|ac*c|符号 状态 a b c 1 4 2，3 2 2 4 3 3，4 4 第43页，共118页，编辑于2022年，星期一能接受能接受0001111010001110000001(0|1)(0|1)*(000|111)(0|1)(000|111)(0|1)*不能接受不能接受0001100第44页，共118页，编辑于2022年，星期一画出能够识别画出能够识别C C语言注释语言注释/*/*/的的DFADFA12453othersothers/*/6othersothersall all第45页，共118页，编辑于2022年，星期一12453othersothers/*/状态状态1：注释

30、开始状态。：注释开始状态。状态状态2：进入注释体前的中间状态。：进入注释体前的中间状态。状态状态3：表明目前正在注释体中的状态。：表明目前正在注释体中的状态。状态状态4：离开注释前的中间状态。：离开注释前的中间状态。状态状态5：注释结束状态，即接受状态。：注释结束状态，即接受状态。第46页，共118页，编辑于2022年，星期一q用于某些重要软件的设计和构造用于某些重要软件的设计和构造设计和检查数字电路行为的软件设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它结构的出现频扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件率的软件;验证所有只有有限多个不同状态的

31、系统的软件，这类系统包验证所有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。括通信协议和信息安全交换协议。有穷自动机的其它应用有穷自动机的其它应用阅读两篇论文阅读两篇论文基于协议分析状态机的入侵检测系统基于协议分析状态机的入侵检测系统有限自动机在有限自动机在BBS信息监测系统中的运用信息监测系统中的运用第47页，共118页，编辑于2022年，星期一 已证明：非确定的有穷自动机与确定的有穷自动机从功能上来已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：说是等价的，也就是说，我们能够从：NFANDFAM构造成一个使得使得L(M)=

32、L(N)DFA是是NFA的特例。有一种算法，将的特例。有一种算法，将NFA转换成接受同样语言的转换成接受同样语言的DFA.第48页，共118页，编辑于2022年，星期一 已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：价的，也就是说，我们能够从：NFAMDFAM构造成一个使得使得L(M)=L(M)DFA是是NFA的特例。有一种算法，将的特例。有一种算法，将NFA转换成接受同样语言的转换成接受同样语言的DFA.这种算法称为这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一不唯一3

33、.NFA的确定化的确定化第49页，共118页，编辑于2022年，星期一从从NFANFA的矩阵表示中可以看出，表项通常是一状态的集合，的矩阵表示中可以看出，表项通常是一状态的集合，而在而在DFADFA的矩阵表示中，表项是一个状态。的矩阵表示中，表项是一个状态。NFANFA到相应的到相应的DFADFA的构造的基本思路是：的构造的基本思路是：DFADFA的每一个状态对的每一个状态对应应NFANFA的一组状态的一组状态.符号符号状态状态abc142，322433，441234abacac第50页，共118页，编辑于2022年，星期一(1)合并如果有 ，则把S2合并到S1S S1 1S S2 2转换需解

34、决的问题：转换需解决的问题：ijkmaban（a）i,jmkaabn（b）第51页，共118页，编辑于2022年，星期一(2)状态合并0123aabc（a）01,23abc（b）第52页，共118页，编辑于2022年，星期一定义定义1状态集合状态集合I I的的-闭包，表示为闭包，表示为-closure(I)-closure(I)若若qIqI，则，则qq-closure(I)-closure(I)；若若qIqI，则从，则从q q出发经过任意条出发经过任意条 弧而能到达的任何状态弧而能到达的任何状态qq都都属于属于-closure(I)-closure(I)。为了使得为了使得NFANFA确定化，我

35、们首先给出两个定义确定化，我们首先给出两个定义：_closure(I)IIS2S2S1S1S3S3第53页，共118页，编辑于2022年，星期一例：例：如图所示的状态图：如图所示的状态图：令令I=1，求求-closure（I）=？156432aaa根据定义：根据定义：-closure（I）=1，3课堂练习：令I=1,2，求-closure（I）=？第54页，共118页，编辑于2022年，星期一I I是状态集，由是状态集，由I I中的状态出发，经过一条中的状态出发，经过一条a a弧可能到弧可能到达的状态的集合称为达的状态的集合称为movemove（I I，a a），则），则I Ia a=_clo

36、sure(move(I,a)=_closure(move(I,a)定义定义2I Ia a子集子集第55页，共118页，编辑于2022年，星期一例：令 I=1 Ia=-closure(move（I，a）)=-closure(f（1，a）=-closure(2，4）=2，4，6根据定义根据定义1 1，2 2，可以将上述的，可以将上述的MM确定化（即可构造出状态确定化（即可构造出状态转换矩阵）转换矩阵）156432aaa课堂练习：课堂练习：令令I=1,2,3求求IaIa=？第56页，共118页，编辑于2022年，星期一课堂练习：课堂练习：令令I=1I=1，设，设SS=-closure=-closur

37、e（I I），求），求SS？SSa a=？将从状态将从状态S S出发经过任意条出发经过任意条 弧所能弧所能到达的状态作为到达的状态作为DFADFA的初态的初态S S 从从S S 出发，把遇到输入符号出发，把遇到输入符号a a所转所转移到的后继状态集作为移到的后继状态集作为DFADFA的新状的新状态态如此重复，直到不再有新的状态出如此重复，直到不再有新的状态出现为止现为止 NFA转换为转换为DFA的思想的思想1234abacac第57页，共118页，编辑于2022年，星期一 IIaIbIc 1,42,3 2,3243,4 224 4 3,43,4（1 1）构造一张表，它共有）构造一张表，它共有+

38、1+1列列（2 2）第一行第一列为）第一行第一列为-closure(S)-closure(S)（3 3）求）求IaIa（4 4）重复步骤（）重复步骤（3 3）（5 5）将状态子集重新命名）将状态子集重新命名1234abacac第58页，共118页，编辑于2022年，星期一将求得的状态转换矩阵重新编号将求得的状态转换矩阵重新编号DFAM状态转换矩阵：状态转换矩阵：符号状态abc0 2 341221_3344第59页，共118页，编辑于2022年，星期一DFAM的状态图：的状态图：注意：包含原初始状态注意：包含原初始状态1的状态子集为的状态子集为DFAM的初态的初态包含原终止状态包含原终止状态4的

39、状态子集为的状态子集为DFAM的终态。的终态。014231,42,342acabbc3,41234abacac第60页，共118页，编辑于2022年，星期一课堂练习4f35621iaaaabbbbstart第61页，共118页，编辑于2022年，星期一 等价的DFAaCDBAEFSbaaaaabbbbbabFstart第62页，共118页，编辑于2022年，星期一4.DFA的最小化的最小化如果不同的如果不同的DFA能识别相同的语言，则称它们是等价的能识别相同的语言，则称它们是等价的DFA。在等价的在等价的DFA中，如果某一个中，如果某一个DFA的状态数是最少的，则这个的状态数是最少的，则这个D

40、FA是是最简的。最简的。对于任一个对于任一个DFA，存在一个唯一的状态最少的等价的，存在一个唯一的状态最少的等价的DFA最简的最简的DFA它没有多余它没有多余状态和等价状态状态和等价状态第63页，共118页，编辑于2022年，星期一定义定义1多余状态：多余状态：从开始状态出发从开始状态出发,任何输入串也不能到达的状态任何输入串也不能到达的状态01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s101s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例例:画状态图可画状态图可以看出以看出s4,s6,s8为不可达状为不

41、可达状态应该消除态应该消除第64页，共118页，编辑于2022年，星期一定义定义2等价状态等价状态状态状态s和和t的等价条件是的等价条件是:状态状态S和和T必须同时为终态或非终态必须同时为终态或非终态对于所有输入符号，对于所有输入符号，S和和T必须转换到等价的状态里必须转换到等价的状态里第65页，共118页，编辑于2022年，星期一把把DFA的状态划分成一些不相交的子集的状态划分成一些不相交的子集任何不同的两个子集的状态都是可区分的任何不同的两个子集的状态都是可区分的同一子集中的任何两个状态都是等价的同一子集中的任何两个状态都是等价的5724361srartaaaaaaabbbbbbbDFA最

42、小化算法的基本思想最小化算法的基本思想(没有多余状态没有多余状态)：第66页，共118页，编辑于2022年，星期一解解:(一一)区分终态与非终态区分终态与非终态12345663731546737414212ab区号区号123123456637315467374142ab区号区号（1）将所有状态分成两个子集：终态集和非终态集）将所有状态分成两个子集：终态集和非终态集（2）把等价的状态构成一个子集，若不等价继续划分）把等价的状态构成一个子集，若不等价继续划分（3）结束后，重新标号或从每个子集中选一个状态做代表）结束后，重新标号或从每个子集中选一个状态做代表第67页，共118页，编辑于2022年，星

43、期一123456637315467374142ab12431243123456637315467374142ab5区号区号区号区号第68页，共118页，编辑于2022年，星期一将区号代替状态号得将区号代替状态号得:12345ab521435523115 5243aaaaabbbbb化简后的有穷自动机具有较少的状态，实现起来更加简洁。化简后的有穷自动机具有较少的状态，实现起来更加简洁。第69页，共118页，编辑于2022年，星期一3.4.4 3.4.4 正规式与正规式与有穷自动机的等价性有穷自动机的等价性（1）对于字母表）对于字母表上的上的NFAM，可以构造一个，可以构造一个上的正规式上的正规式

44、R，使得，使得L(R)=L(M)；（2）对于字母表）对于字母表上的每个正规式上的每个正规式R，可以构造一个，可以构造一个上的上的NFAM，使得使得L(M)=L(R)。第70页，共118页，编辑于2022年，星期一1.NFAM正规式正规式R(1)(1)在在M上加两个结点上加两个结点S,ZS,Z，从，从S S结点用结点用弧到弧到M的所有初态，从的所有初态，从M的所有终态用的所有终态用到到Z结成与结成与M等价等价的的M，M只有一个初态只有一个初态S和一个和一个终态终态Z.例例:M M:03214starta,ba,ba,bbbaa解解:(1)(1)加加S ZS ZS03412Zaa,ba,ba,ba

45、bb第71页，共118页，编辑于2022年，星期一(2)逐步消去逐步消去M中的所有结点中的所有结点,直至剩下直至剩下S和和Z结点结点,在消在消结过程中结过程中,逐步用正规式来标记弧逐步用正规式来标记弧,规则如下规则如下:1 1.对于对于代之为代之为2 2.对于对于 代之为代之为 3 3.对于对于代之为代之为R R1 1R R2 21 12 23 33 31 1R R1 1R R2 21 12 22 21 1R R2 2R R1 1R R2 2R R1 1|R R1 1R R3 31 12 23 33 31 1R R1 1R R2 2R R3 3R R2 2第72页，共118页，编辑于2022年

46、，星期一(2)(2)消除消除M M中的所有结点中的所有结点a|bx024yaabba|ba|bx0yaa(a|b)*bb(a|b)*a|b解解:(1)(1)加加xyxyx03412yaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*第73页，共118页，编辑于2022年，星期一2.正规式正规式RNFAM（1）对对NFAM构构造造一一个个广广义义的的状状态态图图，其其中中只只有有一一个个初初态态S和和终终态态Z，连接，连接S和和Z的有向弧标记为正规式。的有向弧标记为正规式。（2）对对正正规规式式依依次次进进行行分分解解，分分解解的的过过程程是是一一个个不不断断加加入入结结点点和

47、和弧弧的的过过程程，直直到到转转换换图图上上的的所所有有弧弧标标记记上上都都是是字字母母表表上上的的元元素素或或 为为止。止。第74页，共118页，编辑于2022年，星期一若若s,ts,t为为上的正规式上的正规式(a)(a)对于正规式对于正规式R=stR=stx xy yststx xy ys st tt t(b)(b)对于正规式对于正规式R=s|tR=s|tx xy ys|ts|tx xy ys st t(c)(c)对于正规式对于正规式R=rsR=rs*t tx xy yrsrs*t tx xy yrt tts第75页，共118页，编辑于2022年，星期一AZS(a|b)*abb例例:为为R

48、=(a|b)abbR=(a|b)abb构造构造NFA,NFA,使得使得L(N)=L(R)L(N)=L(R)*SZbabABbaZbbSa|bAa第76页，共118页，编辑于2022年，星期一3.4.5 3.4.5 正规文法与正规文法与有穷自动机的等价性有穷自动机的等价性（1）对对于于NFAM，存存在在一一个个右右线线性性文文法法（左左线线性性文文法法）G，使使得得L(G)=L(M)；（2）对对于于右右线线性性文文法法（左左线线性性文文法法）G，可可以以构构造造一一个个NFAM，使使得得L(M)=L(G)。第77页，共118页，编辑于2022年，星期一1.NFA正规文法正规文法（1 1）NFAN

49、FA的字母表为文法的终结符号集；的字母表为文法的终结符号集；（2 2）NFANFA的状态集为文法的非终结符号集；的状态集为文法的非终结符号集；（3 3）NFANFA的初态对应于文法的开始符号；的初态对应于文法的开始符号；（4 4）NFANFA的转换函数的转换函数f(A,t)=Bf(A,t)=B，写成一个产生式，写成一个产生式AtBAtB；（5 5）对）对NFANFA的终态的终态Z Z，增加一个产生式，增加一个产生式ZZ。ABt第78页，共118页，编辑于2022年，星期一例例:给出如图给出如图NFANFA等价的正规文法等价的正规文法G GABCDaaabbbbG=（A，B，C，D，a，b，P，

50、A）其中其中P:AaBAbDBbCCaACbDCDaBDbDD第79页，共118页，编辑于2022年，星期一（1 1）文法的终结符号集为）文法的终结符号集为NFANFA的字母表；的字母表；（2 2）文法的非终结符号集为）文法的非终结符号集为NFANFA的状态集；的状态集；（3 3）文法的开始符号作为）文法的开始符号作为NFANFA的初态；的初态；（4 4）对文法中形如）对文法中形如AtBAtB的产生式，其中的产生式，其中t t为终结符或为终结符或，A A和和B B为非终结符，构造为非终结符，构造NFANFA的一个转换函数的一个转换函数f(A,t)=Bf(A,t)=B；（5 5）对文法中形如）对