第3章词法分析精选文档.ppt-淘文阁

资源描述

《第3章词法分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第3章词法分析精选文档.ppt（118页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、分析程序的掌握词法分析程序的自动自动构造原理。构造原理。教学目标教学目标本讲稿第二页，共一百一十八页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编译程序的词法分析编译程序的词法分析教学内容教学内容本讲稿第三页，共一百一十八页（1 1）分析和识别单词及属性，分析和识别单词及属性，包括识别包括识别语言的语言的关键字

3、关键字、标识符、常数、运算符等、标识符、常数、运算符等；（2 2）跳过各种分隔符，如空格，回车，制表符等；跳过各种分隔符，如空格，回车，制表符等；（3 3）删除注释；）删除注释；（4 4）进行词法检查，报告所发现的错误；）进行词法检查，报告所发现的错误；（5 5）建立符号表。）建立符号表。3.13.1词法分析的任务词法分析的任务本讲稿第四页，共一百一十八页main()/*ADD*/int x=10,y=20,sum;sum=x+y;main、(、)、int、x、=、10、,、y、=、20、,、sum、;、sum、=、x、+、y、;、词法分析词法分析本讲稿第五页，共一百一十八页实现方案：实现方

4、案：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析词法分析S.P.(符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串优点优点:结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺点：效率低S.P.(字符串)词法分词法分析程序析程序语法分语法分析程序析程序取单词取单词单词单词本讲稿第六页，共一百一十八页单词的种类单词的种类（1 1）关键）关键字：字：if、for、while（2 2）标识符：标识符：（3 3）常数：常数：（4 4）运算符：运算符：+、-、*（5 5）分界符：）分界符：,、;、(、)3.23.2词法分析程序的输出形式

5、词法分析程序的输出形式本讲稿第七页，共一百一十八页词法分析程序的输出形式词法分析程序的输出形式-二元式二元式单词类别单词类别单词的属性值单词的属性值单词类别可以用整数编码表示单词类别可以用整数编码表示:一类一种或一字一种一类一种或一字一种单词类别单词类别关键字关键字标识符标识符常数常数运算符运算符分界符分界符编码编码1 12 23 34 45 5本讲稿第八页，共一百一十八页表3.1 int x=10,y=20,sum;词法分析的结果单词类别单词类别单词的属性值单词的属性值1int2指向指向x的符号表入口指针的符号表入口指针4=3105,2指向指向y的符号表入口指针的符号表入口指针4=3205

6、,2指向指向sum的符号表入口指针的符号表入口指针5;表表3.1intx=10,y=20,sum;词法分析的结果词法分析的结果本讲稿第九页，共一百一十八页3.33.3词法分析程序的设计与实现词法分析程序的设计与实现词法规则词法规则状态图状态图词法分析程序词法分析程序本讲稿第十页，共一百一十八页结点结点代表状态，用圆圈表示，为非终结符代表状态，用圆圈表示，为非终结符有向弧有向弧表示状态转移表示状态转移弧上的标记弧上的标记表示在射出弧的结点状态下可能出现的输入字符，表示在射出弧的结点状态下可能出现的输入字符，为终结符为终结符1.状态图：状态图：为识别单词而专门设计的有向图，为识别单词而专门设计的有

7、向图，是设计词法分析程序的一种好途径。是设计词法分析程序的一种好途径。SUVZ111000一张状态图包含有穷个状态，一张状态图包含有穷个状态，只能有一个只能有一个初态初态，至少要有，至少要有一个一个终态终态（用双圈表示）（用双圈表示）3.3.1 3.3.1 正规文法及其状态图正规文法及其状态图本讲稿第十一页，共一百一十八页【例例3.1】某语言的标识符可使用以下正规文法某语言的标识符可使用以下正规文法GS来定义：来定义：SlAA|lA|dAla,b,z，d1,2,9试构造此文法的状态图。试构造此文法的状态图。SAll|d状态图可识别单词状态图可识别单词本讲稿第十二页，共一百一十八页2.由正规文法

8、构造状态图由正规文法构造状态图（1）对于右线性文法）对于右线性文法步骤步骤1增加结点增加结点Z为终态；为终态；步骤步骤2将每个非终结符号设置为一个对应的状态；将每个非终结符号设置为一个对应的状态；步骤步骤3对于对于Aa，引一条从，引一条从A到到Z的弧，弧上标记为的弧，弧上标记为a；而对于而对于AaB，引一条从，引一条从A到到B的弧，弧上标记为的弧，弧上标记为a。SlAA|lA|dAl|dAZSlAZll|d本讲稿第十三页，共一百一十八页（2）对于左线性文法）对于左线性文法步骤步骤1增加结点增加结点S为初态；为初态；步骤步骤2将每个非终结符号设置为一个对应的状态；将每个非终结符号设置为一个对应的

9、状态；步步骤骤3对对于于Aa，引引一一条条从从S到到A的的弧弧，弧弧上上标标记记为为a；而而对对于于ABa，引一条从，引一条从B到到A的弧，弧上标记为的弧，弧上标记为a。Al|Al|Adl|dASlSlAA|lA|dA本讲稿第十四页，共一百一十八页词法规则词法规则状态图状态图词法分析程序词法分析程序3.3.2 3.3.2 词法分析程序的实现词法分析程序的实现（1 1）根据词法规则写出正规文法；根据词法规则写出正规文法；（2 2）将正规文法转换成状态图；将正规文法转换成状态图；（3 3）将状态图转换成流程图。将状态图转换成流程图。本讲稿第十五页，共一百一十八页标识符标识符关键字关键字(标识符

10、的子集）标识符的子集）常数常数运算符运算符 +、*、=分界符分界符 ,、;【例例3.23.2】假设某种语言的单词符号的子集有：假设某种语言的单词符号的子集有：试构造此语言子集的词法分析程序。试构造此语言子集的词法分析程序。本讲稿第十六页，共一百一十八页（1 1）根据词法规则写出正规文法根据词法规则写出正规文法字母字母|字母字母|数字）数字）数字数字|数字数字+|*|,|;=本讲稿第十七页，共一百一十八页标识符出口出口S1非字母数字非字母数字字母字母字母、数字字母、数字无符号整数出口出口S2非数字非数字数字数字数字数字单字符分界符单字符分界符出口出口S3其他字符其他字符+*=,;双字符分界符双

11、字符分界符出口出口S4其他字符其他字符5=非非=字母字母|字母字母|数字）数字）数字数字|数字数字+|*|+|*|,|;=（2 2）将正规文法转换成状态图将正规文法转换成状态图本讲稿第十八页，共一百一十八页合并合并将初始状态合并为一个唯一的初态；将初始状态合并为一个唯一的初态；化简调整状态冲突并对冲突状态重新编号；化简调整状态冲突并对冲突状态重新编号；如有必要，增加出错状态。如有必要，增加出错状态。本讲稿第十九页，共一百一十八页标识符无符号整数单界符单界符双界符双界符S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+*，（）出口出口4其他字

12、符其他字符5=非非=出错出错其他其他读字符读字符查保留字表查保留字表返回返回S合并后的合并后的状态图状态图本讲稿第二十页，共一百一十八页（3 3）将状态图转换成流程图，如图将状态图转换成流程图，如图3.53.5写出词法分析程序写出词法分析程序本讲稿第二十一页，共一百一十八页3.5字母表字母表,定义在定义在上的正规式和正规集递归定义如下上的正规式和正规集递归定义如下:1.1.和和都是都是上的正规式上的正规式,它们所表示的正规集分别为它们所表示的正规集分别为:和和;2.2.任何任何a a ,a,a是是上的正规式上的正规式,它所表示的正规集为它所表示的正规集为:a;:a;3.3.假定假定U

13、U和和V V 上的正规式上的正规式,它们所表示的正规集分别记为它们所表示的正规集分别记为L(e1)L(e1)和和L(e2),L(e2),那么那么e1|e2,e1e1|e2,e1e2e2和和e1e1*也都是也都是上的正规式上的正规式,它们所表示的它们所表示的正规集分别为正规集分别为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 正规式与正规集正规式与正规

14、集本讲稿第二十二页，共一百一十八页正规式中的运算符：正规式中的运算符：|-或（选择）或（选择）-连接连接*或或-重复重复（）（）-括号括号运算符的优先级：运算符的优先级：先先*,后后,最后最后|在正规式中可以省略在正规式中可以省略.正规式相等正规式相等这两个正规式表示的语言相等这两个正规式表示的语言相等本讲稿第二十三页，共一百一十八页【例例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)*

15、空串和任何长度为偶数的符号串(a|b)(a|b)(a|b)*任何长度大于等于2的符号串本讲稿第二十四页，共一百一十八页【例例3.3】使用正规式来表示例使用正规式来表示例3.2中的相应单词符号。中的相应单词符号。字母字母|字母字母|数字）数字）数字数字|数字数字+|*|+|*|,|;=标识符：标识符：l(l|d)*无符号整数：无符号整数：dd*单界符：单界符：+|*|,|;双界符：双界符：=本讲稿第二十五页，共一百一十八页设设r，s，t均是正规式，则有以下性质：均是正规式，则有以下性质：（1）交换律：）交换律：r|s=s|r（2）结合律：）结合律：r|(s|t)=(r|s)|t(rs)t=r(s

16、t)（3）分配律：）分配律：(r|s)t=rt|st（4）同一律：）同一律：r=r=r本讲稿第二十六页，共一百一十八页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 3.4.2 正规文

18、则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xyA=xA=x*y yA=x|yA=x|y本讲稿第二十九页，共一百一十八页【例例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)*本讲稿第三十页，共一百一十八页下面是用正规式表示的变量声明：下面是用正规式表示的变量声明：(int|float)id(,id)*请请改改用用上上下下文文无无关关文文法法表表示示，也也就

19、就是是写写一一个个上上下下文文无无关关文文法法，它和该正规式等价。它和该正规式等价。(int|float)id(,id)*D(int|float)LLid(,id)*DintL|floatLLL,id|idGD：DintL|floatLLL,id|id本讲稿第三十一页，共一百一十八页3.4.3 3.4.3 有穷自动机有穷自动机标识符无符号整数单界符单界符双界符双界符S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+*，（）出口出口4其他字符其他字符5=非非=出错出错其他其他读字符读字符查保留字表查保留字表返回返回S状态图的形式化描述本讲稿第三

20、十二页，共一百一十八页有穷自动机是一种有穷自动机是一种数学模型数学模型，具有离散的输入与输出，系统可，具有离散的输入与输出，系统可处于有穷状态中的任何一个处于有穷状态中的任何一个它能准确地它能准确地识别正规集识别正规集，即识别正规文法所定义的语言和，即识别正规文法所定义的语言和正规式所表示的集合正规式所表示的集合引入有穷自动机这个理论，正是为引入有穷自动机这个理论，正是为词法分析程序的自动构造词法分析程序的自动构造寻找特殊的方法和工具寻找特殊的方法和工具有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机（DFADFA）(Deterministic Finite Autom

21、ata)(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机（NFANFA）(Nondeterministic Finite Automata)(Nondeterministic Finite Automata)本讲稿第三十三页，共一百一十八页2 2型文法型文法（不确定（不确定的下推自动机）的下推自动机）1 1型文法型文法（不确定（不确定的界限自动机）的界限自动机）0 0型文法型文法（图灵机）（图灵机）3 3型文法型文法（有限（有限自动机）自动机）本讲稿第三十四页，共一百一十八页1.确定的有穷自动机（确定的有穷自动机（DFA）M=(,Q,f,S,Z

22、)：有穷字母表，它的每个元素称为一个输入符号：有穷字母表，它的每个元素称为一个输入符号Q：有穷集，它的每个元素称为一个状态：有穷集，它的每个元素称为一个状态SK，是唯一的初态，是唯一的初态Z K是一个终态集，终态也称可接受状态或结束状态是一个终态集，终态也称可接受状态或结束状态f是转换函数，是是转换函数，是QQ上的单值映射：上的单值映射：f（q1，a）=q2本讲稿第三十五页，共一百一十八页状态转移函数状态转移函数f可用一矩阵来表示：可用一矩阵来表示：输入输入字符字符状态状态ab012132213333例如例如:M:M:（0,1,2,3,a,b,0,1,2,3,a,b,f，0，3）f（0，a）=

23、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)本讲稿第三十六页，共一百一十八页一个DFA也可以用一状态转换图表示：输入字符状态 a b 0 1 2 1 3 2 2 1 3 3 3 3DFA的状态图表示：1032aabba,bba字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。本讲稿第三十七页，共一百

24、一十八页换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串，则称为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的初态结点同时为终态，或者存在一条从初态到某个终态结点的的初态结点同时为终态，或者存在一条从初态到某个终态结点的通通路，则路，则为为M M所识别。所识别。本讲稿第三十八页，共一百一十八页（0，abaab）=（1，baab）=（2，aab）=（1，ab

25、）=（3，b）=3(接受接受)DFADFA的状态图表示：的状态图表示：1032aabba,bba （0，abab）=（1，bab）=（2，ab）=（1，b）=2(拒绝拒绝)对于符号串对于符号串abaababaab对于符号串对于符号串abababab本讲稿第三十九页，共一百一十八页f是一个多值函数，是从是一个多值函数，是从Q*到到Q的子集的映射：的子集的映射：f：Q2Q其中其中2Q是是Q的幂集，即的幂集，即Q中所有子集组成的集合。中所有子集组成的集合。2.不确定的有穷自动机（不确定的有穷自动机（NFA）M=(,Q,f,S,Z)有穷自动机的不确定性表现在在某个状态下，对于某个输入字符有穷自动机的不

26、确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的存在多个后继状态，即状态的转向是不确定的本讲稿第四十页，共一百一十八页例：例：NFAN=(a,b,c,1,2,3,4,f,1,4)符号符号状态状态abc142，322433，44本讲稿第四十一页，共一百一十八页对于对于*上的任何符号串上的任何符号串，若存在一条从某一初态到某一，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接成的终态的通路，且该通路上所有弧的标记字符依次连接成的串等于串等于，则称，则称可以被可以被NFAN所识别或接受。所识别或接受。若若N的初态结点同时为终态，或者存在一条

27、从初态到某个终的初态结点同时为终态，或者存在一条从初态到某个终态结点的态结点的通路，则通路，则为为N所识别。所识别。NFAN所能识别的符号串的全体记为所能识别的符号串的全体记为L(N)，称为，称为NFAN所所识别的语言识别的语言本讲稿第四十二页，共一百一十八页上例题相应的状态图为：1234abacacN所接受的语言（正规式）R=aa*b|ac*c|符号状态 a b c 1 4 2，3 2 2 4 3 3，4 4 本讲稿第四十三页，共一百一十八页能接受能接受0001111010001110000001(0|1)(0|1)*(000|111)(0|1)(000|111)(0|1)*不能接受

28、不能接受0001100本讲稿第四十四页，共一百一十八页画出能够识别画出能够识别C C语言注释语言注释/*/*/的的DFADFA12453othersothers/*/6othersothersall all本讲稿第四十五页，共一百一十八页12453othersothers/*/状态状态1：注释开始状态。：注释开始状态。状态状态2：进入注释体前的中间状态。：进入注释体前的中间状态。状态状态3：表明目前正在注释体中的状态。：表明目前正在注释体中的状态。状态状态4：离开注释前的中间状态。：离开注释前的中间状态。状态状态5：注释结束状态，即接受状态。：注释结束状态，即接受状态。本讲稿第四十六页，共一百

29、一十八页q用于某些重要软件的设计和构造用于某些重要软件的设计和构造设计和检查数字电路行为的软件设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它结构的出现频扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件率的软件;验证所有只有有限多个不同状态的系统的软件，这类系验证所有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。统包括通信协议和信息安全交换协议。有穷自动机的其它应用有穷自动机的其它应用阅读两篇论文阅读两篇论文基于协议分析状态机的入侵检测系统基于协议分析状态机的入侵检测系统有限自动机在有限自动机在BBS信息监测系统中的运用信息监测

30、系统中的运用本讲稿第四十七页，共一百一十八页已证明：非确定的有穷自动机与确定的有穷自动机从功能上来已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：说是等价的，也就是说，我们能够从：NFANDFAM构造成一个使得使得L(M)=L(N)DFA是是NFA的特例。有一种算法，将的特例。有一种算法，将NFA转换成接受同样语言的转换成接受同样语言的DFA.本讲稿第四十八页，共一百一十八页已证明：非确定的有穷自动机与确定的有穷自动机从功能上已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：来说是等价的，也就是说，我们能够从：N

31、FAMDFAM构造成一个使得使得L(M)=L(M)DFA是是NFA的特例。有一种算法，将的特例。有一种算法，将NFA转换成接受同样语言的转换成接受同样语言的DFA.这种算法称为这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一不唯一3.NFA的确定化的确定化本讲稿第四十九页，共一百一十八页从从NFANFA的矩阵表示中可以看出，表项通常是一状态的集合，的矩阵表示中可以看出，表项通常是一状态的集合，而在而在DFADFA的矩阵表示中，表项是一个状态。的矩阵表示中，表项是一个状态。NFANFA到相应的到相应的DFADFA的构造的基本思路是：的构造的基本思路是：DFADFA的每一个状态

32、对应的每一个状态对应NFANFA的一组状态的一组状态.符号符号状态状态abc142，322433，441234abacac本讲稿第五十页，共一百一十八页(1)合并如果有，则把S2合并到S1S S1 1S S2 2转换需解决的问题：转换需解决的问题：ijkmaban（a）i,jmkaabn（b）本讲稿第五十一页，共一百一十八页(2)状态合并0123aabc（a）01,23abc（b）本讲稿第五十二页，共一百一十八页定义定义1状态集合状态集合I I的的-闭包，表示为闭包，表示为-closure(I)-closure(I)若若qIqI，则，则qq-closure(I)-closure(I)；若若q

33、IqI，则从，则从q q出发经过任意条出发经过任意条弧而能到达的任何状态弧而能到达的任何状态qq都都属于属于-closure(I)-closure(I)。为了使得为了使得NFANFA确定化，我们首先给出两个定义确定化，我们首先给出两个定义：_closure(I)IIS2S2S1S1S3S3本讲稿第五十三页，共一百一十八页例：例：如图所示的状态图：如图所示的状态图：令令I=1，求求-closure（I）=？156432aaa根据定义：根据定义：-closure（I）=1，3课堂练习：令I=1,2，求-closure（I）=？本讲稿第五十四页，共一百一十八页I I是状态集，由是状态集，由I I中

34、的状态出发，经过一条中的状态出发，经过一条a a弧可能到达的弧可能到达的状态的集合称为状态的集合称为movemove（I I，a a），则），则I Ia a=_closure(move(I,a)=_closure(move(I,a)定义定义2I Ia a子集子集本讲稿第五十五页，共一百一十八页例：令 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

35、,2,3求求IaIa=？本讲稿第五十六页，共一百一十八页课堂练习：课堂练习：令令I=1I=1，设，设SS=-closure=-closure（I I），求），求SS？SSa a=？将从状态将从状态S S出发经过任意条出发经过任意条弧所能弧所能到达的状态作为到达的状态作为DFADFA的初态的初态S S 从从S S 出发，把遇到输入符号出发，把遇到输入符号a a所转移所转移到的后继状态集作为到的后继状态集作为DFADFA的新状态的新状态如此重复，直到不再有新的状态出现如此重复，直到不再有新的状态出现为止为止 NFA转换为转换为DFA的思想的思想1234abacac本讲稿第五十七页，共一百一十八页

36、 IIaIbIc 1,42,3 2,3243,4 224 4 3,43,4（1 1）构造一张表，它共有）构造一张表，它共有+1+1列列（2 2）第一行第一列为）第一行第一列为-closure(S)-closure(S)（3 3）求）求IaIa（4 4）重复步骤（）重复步骤（3 3）（5 5）将状态子集重新命名）将状态子集重新命名1234abacac本讲稿第五十八页，共一百一十八页将求得的状态转换矩阵重新编号将求得的状态转换矩阵重新编号DFAM状态转换矩阵：状态转换矩阵：符号状态abc0 2 341221_3344本讲稿第五十九页，共一百一十八页DFAM的状态图：的状态图：注意：包含原初始状态注

37、意：包含原初始状态1的状态子集为的状态子集为DFAM的初态的初态包含原终止状态包含原终止状态4的状态子集为的状态子集为DFAM的终态。的终态。014231,42,342acabbc3,41234abacac本讲稿第六十页，共一百一十八页课堂练习4f35621iaaaabbbbstart本讲稿第六十一页，共一百一十八页等价的DFAaCDBAEFSbaaaaabbbbbabFstart本讲稿第六十二页，共一百一十八页4.DFA的最小化的最小化如果不同的如果不同的DFA能识别相同的语言，则称它们是等价的能识别相同的语言，则称它们是等价的DFA。在等价的在等价的DFA中，如果某一个中，如果某一个DF

38、A的状态数是最少的，则这个的状态数是最少的，则这个DFA是最简的。是最简的。对于任一个对于任一个DFA，存在一个唯一的状态最少的等价的，存在一个唯一的状态最少的等价的DFA最简的最简的DFA它没有多余它没有多余状态和等价状态状态和等价状态本讲稿第六十三页，共一百一十八页定义定义1多余状态：多余状态：从开始状态出发从开始状态出发,任何输入串也不能到达的状态任何输入串也不能到达的状态01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s101s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例例:画状态图可画状态图可以看

39、出以看出s4,s6,s8为不可达状为不可达状态应该消除态应该消除本讲稿第六十四页，共一百一十八页定义定义2等价状态等价状态状态状态s和和t的等价条件是的等价条件是:状态状态S和和T必须同时为终态或非终态必须同时为终态或非终态对于所有输入符号，对于所有输入符号，S和和T必须转换到等价的状态里必须转换到等价的状态里本讲稿第六十五页，共一百一十八页把把DFA的状态划分成一些不相交的子集的状态划分成一些不相交的子集任何不同的两个子集的状态都是可区分的任何不同的两个子集的状态都是可区分的同一子集中的任何两个状态都是等价的同一子集中的任何两个状态都是等价的5724361srartaaaaaaabbbbbb

40、bDFA最小化算法的基本思想最小化算法的基本思想(没有多余状态没有多余状态)：本讲稿第六十六页，共一百一十八页解解:(一一)区分终态与非终态区分终态与非终态12345663731546737414212ab区号区号123123456637315467374142ab区号区号（1）将所有状态分成两个子集：终态集和非终态集）将所有状态分成两个子集：终态集和非终态集（2）把等价的状态构成一个子集，若不等价继续划分）把等价的状态构成一个子集，若不等价继续划分（3）结束后，重新标号或从每个子集中选一个状态做代表）结束后，重新标号或从每个子集中选一个状态做代表本讲稿第六十七页，共一百一十八页1234566

41、37315467374142ab12431243123456637315467374142ab5区号区号区号区号本讲稿第六十八页，共一百一十八页将区号代替状态号得将区号代替状态号得:12345ab521435523115 5243aaaaabbbbb化简后的有穷自动机具有较少的状态，实现起来更加简洁。化简后的有穷自动机具有较少的状态，实现起来更加简洁。本讲稿第六十九页，共一百一十八页3.4.4 3.4.4 正规式与正规式与有穷自动机的等价性有穷自动机的等价性（1）对于字母表）对于字母表上的上的NFAM，可以构造一个，可以构造一个上的正规式上的正规式R，使得，使得L(R)=L(M)；（2）对于字

42、母表）对于字母表上的每个正规式上的每个正规式R，可以构造一个，可以构造一个上的上的NFAM，使得，使得L(M)=L(R)。本讲稿第七十页，共一百一十八页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,babb本讲稿第七十一页，共一百一十八页(2)逐步消去逐步消去M

43、中的所有结点中的所有结点,直至剩下直至剩下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本讲稿第七十二页，共一百一十八页(2)(2)消除消除M M中的所有结点中的所有结点a|bx024yaabba|b

44、a|bx0yaa(a|b)*bb(a|b)*a|b解解:(1)(1)加加xyxyx03412yaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*本讲稿第七十三页，共一百一十八页2.正规式正规式RNFAM（1）对对NFAM构构造造一一个个广广义义的的状状态态图图，其其中中只只有有一一个个初初态态S和和终态终态Z，连接，连接S和和Z的有向弧标记为正规式。的有向弧标记为正规式。（2）对对正正规规式式依依次次进进行行分分解解，分分解解的的过过程程是是一一个个不不断断加加入入结结点点和和弧弧的的过过程程，直直到到转转换换图图上上的的所所有有弧弧标标记记上上都都是是字字母母表表上上的的元

46、bSa|bAa本讲稿第七十六页，共一百一十八页3.4.5 3.4.5 正规文法与正规文法与有穷自动机的等价性有穷自动机的等价性（1）对对于于NFAM，存存在在一一个个右右线线性性文文法法（左左线线性性文文法法）G，使使得得L(G)=L(M)；（2）对对于于右右线线性性文文法法（左左线线性性文文法法）G，可可以以构构造造一一个个NFAM，使使得得L(M)=L(G)。本讲稿第七十七页，共一百一十八页1.NFA正规文法正规文法（1 1）NFANFA的字母表为文法的终结符号集；的字母表为文法的终结符号集；（2 2）NFANFA的状态集为文法的非终结符号集；的状态集为文法的非终结符号集；（3 3）NFA

47、NFA的初态对应于文法的开始符号；的初态对应于文法的开始符号；（4 4）NFANFA的转换函数的转换函数f(A,t)=Bf(A,t)=B，写成一个产生式，写成一个产生式AtBAtB；（5 5）对）对NFANFA的终态的终态Z Z，增加一个产生式，增加一个产生式ZZ。ABt本讲稿第七十八页，共一百一十八页例例:给出如图给出如图NFANFA等价的正规文法等价的正规文法G GABCDaaabbbbG=（A，B，C，D，a，b，P，A）其中其中P:AaBAbDBbCCaACbDCDaBDbDD本讲稿第七十九页，共一百一十八页（1 1）文法的终结符号集为）文法的终结符号集为NFANFA的字母表；的字母表

48、；（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）对文法中形如）对文法中形如AtAt的产生式，构造的产生式，构造NFANFA的一个转换函的一个转换函数数f(A,t)=Zf(A,t)=Z。2.正规文法正规文法NFA本讲稿第八十页，共一百一十八页例例:求与

49、文法求与文法GSGS等价的等价的NFANFA GS:SaA|bB|GS:SaA|bB|AaB|bA AaB|bA BaS|bA|BaS|bA|SZABaaabbb求得：求得：本讲稿第八十一页，共一百一十八页正规文法正规文法NFA正规式正规式654312DFA最小化最小化转换方法转换方法87本讲稿第八十二页，共一百一十八页判断题判断题1 1对任意一个右线性文法对任意一个右线性文法G G，都存在一个，都存在一个NFA MNFA M，满足，满足L(G)=L(M).L(G)=L(M).2 2对任意一个右线性文法对任意一个右线性文法G G，都存在一个，都存在一个DFA MDFA M，满足，满足L(G)=

50、L(M).L(G)=L(M).3 3对任何正规表达式对任何正规表达式e e，都存在一个，都存在一个NFA MNFA M，满足，满足L(M)=L(e).L(M)=L(e).4 4对任何正规表达式对任何正规表达式e e，都存在一个，都存在一个DFA MDFA M，满足，满足L(M)=L(e).L(M)=L(e).本讲稿第八十三页，共一百一十八页LEX源程序源程序LEX编译器编译器C程序程序3.53.5词法分析程序的自动生成工具词法分析程序的自动生成工具LEXLEXC程序程序C编译器编译器词法分析程序词法分析程序输入流输入流词法分词法分析程序析程序单词序列单词序列本讲稿第八十四页，共一百一十八页3.

展开阅读全文