第3章-词法分析课件.ppt

3/29/20231编编译译原原理理Wednesday,March 29,2023S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理3/29/20232编编译译原原理理Wednesday,March 29,2023第第3 3章词法分析章词法分析1.1.本章介绍编译第一个阶段词法分析的本章介绍编译第一个阶段词法分析的设计原理和设设计原理和设计方法计方法，要求明确此阶段的，要求明确此阶段的任务任务。2.2.理解通常的单词理解通常的单词分类和构词规则分类和构词规则。3.3.会使用单词的会使用单词的描述和识别描述和识别机制。机制。4.4.要求掌握要求掌握正规文法、状态图、正规文法、状态图、DFADFA、NFANFA、正规式和正规式和正规集正规集的基本概念和它们之间的关系。的基本概念和它们之间的关系。5.5.掌握词法分析程序的掌握词法分析程序的手工手工实现方法。实现方法。6.6.掌握词法分析程序的掌握词法分析程序的自动自动构造原理。构造原理。教学目标教学目标3/29/20233编编译译原原理理Wednesday,March 29,20233.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/29/20234编编译译原原理理Wednesday,March 29,2023（1 1）分析和识别单词及属性，分析和识别单词及属性，包括识别包括识别语言的语言的关键字关键字、标识符、常数、运算符等、标识符、常数、运算符等；（2 2）跳过各种分隔符，如空格，回车，制表符等；跳过各种分隔符，如空格，回车，制表符等；（3 3）删除注释）删除注释；（4 4）进行词法检查，报告所发现的错误；）进行词法检查，报告所发现的错误；（5 5）建立符号表。）建立符号表。3.13.1词法分析的任务词法分析的任务3/29/20235编编译译原原理理Wednesday,March 29,20233/29/20236编编译译原原理理Wednesday,March 29,2023实现方案：实现方案：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析词法分析S.P.(符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串优点优点:结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺点：效率低S.P.(字符串)词法分词法分析程序析程序语法分语法分析程序析程序取单词取单词单词单词3/29/20237编编译译原原理理Wednesday,March 29,2023单词的种类单词的种类（1 1）关键）关键字：字：if、for、while（2 2）标识符：标识符：（3 3）常数：常数：（4 4）运算符：运算符：+、-、*（5 5）分界符：）分界符：,、;、(、)3.23.2词法分析程序的输出形式词法分析程序的输出形式3/29/20238编编译译原原理理Wednesday,March 29,2023词法分析程序的输出形式词法分析程序的输出形式-二元式二元式单词类别单词类别 单词的属性值单词的属性值单词类别可以用整数编码表示单词类别可以用整数编码表示:一类一种或一字一种一类一种或一字一种单词类别单词类别关键字关键字标识符标识符常数常数运算符运算符分界符分界符编码编码1 12 23 34 45 53/29/20239编编译译原原理理Wednesday,March 29,20233/29/202310编编译译原原理理Wednesday,March 29,20233.33.3词法分析程序的设计与实现词法分析程序的设计与实现词法规则词法规则状态图状态图词法分析程序词法分析程序3/29/202311编编译译原原理理Wednesday,March 29,2023结点结点代表状态，用圆圈表示，为非终结符代表状态，用圆圈表示，为非终结符有向弧有向弧表示状态转移表示状态转移弧上的标记弧上的标记表示在射出弧的结点状态下可能出现的输入字表示在射出弧的结点状态下可能出现的输入字符，为终结符符，为终结符1.状态图：状态图：为识别单词而专门设计的有向图，为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。是设计词法分析程序的一种好途径。SUVZ111000一张状态图包含有穷个状一张状态图包含有穷个状态，只能有一个态，只能有一个初态初态，至，至少要有一个少要有一个终态终态（用双圈（用双圈表示）表示）3.3.1 3.3.1 正规文法及其状态图正规文法及其状态图3/29/202312编编译译原原理理Wednesday,March 29,20233/29/202313编编译译原原理理Wednesday,March 29,20232.由正规文法构造状态图由正规文法构造状态图（1）对于右线性文法）对于右线性文法步骤步骤1增加结点增加结点Z为终态；为终态；步骤步骤2将每个非终结符号设置为一个对应的状态；将每个非终结符号设置为一个对应的状态；步骤步骤3对于对于Aa，引一条从，引一条从A到到Z的弧，弧上标记为的弧，弧上标记为a；而而对于对于AaB，引一条从，引一条从A到到B的弧，弧上标记为的弧，弧上标记为a。SlAA|lA|dAl|dAZSlAZll|d3/29/202314编编译译原原理理Wednesday,March 29,20233/29/202315编编译译原原理理Wednesday,March 29,2023词法规则词法规则状态图状态图词法分析程序词法分析程序3.3.2 3.3.2 词法分析程序的实现词法分析程序的实现（1 1）根据词法规则写出正规文法；根据词法规则写出正规文法；（2 2）将正规文法转换成状态图；将正规文法转换成状态图；（3 3）将状态图转换成流程图。将状态图转换成流程图。3/29/202316编编译译原原理理Wednesday,March 29,2023 标识符标识符 关键字关键字(标识符的子集）标识符的子集）常数常数 运算符运算符 +、*、=分界符分界符 ,、;【例【例3.23.2】假设某种语言的单词符号的子集有：】假设某种语言的单词符号的子集有：试构造此语言子集的词法分析程序。试构造此语言子集的词法分析程序。3/29/202317编编译译原原理理Wednesday,March 29,20233/29/202318编编译译原原理理Wednesday,March 29,2023标识符标识符出口出口S1非字母数字非字母数字字母字母字母、数字字母、数字无符号整数无符号整数出口出口S2非数字非数字数字数字数字数字单字符分界符单字符分界符出口出口S3其他字符其他字符+*=,;双字符分界符双字符分界符出口出口S4其他字符其他字符5=非非=字母字母|字母字母|数字）数字）数字数字|数字数字+|*|+|*|,|;=（2 2）将正规文法转换成状态图将正规文法转换成状态图3/29/202319编编译译原原理理Wednesday,March 29,2023合并合并 将初始状态合并为一个唯一的初态；将初始状态合并为一个唯一的初态；化简调整状态冲突并对冲突状态重新编号；化简调整状态冲突并对冲突状态重新编号；如有必要，增加出错状态。如有必要，增加出错状态。3/29/202320编编译译原原理理Wednesday,March 29,2023标识符标识符无符号整数无符号整数单界符单界符双界符双界符S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+*，（）出口出口4其他字符其他字符5=非非=出错出错其他其他读字符读字符查保留字表查保留字表返回返回S合并后的合并后的状态图状态图3/29/202321编编译译原原理理Wednesday,March 29,2023（3 3）将状态图转换成流程图，如图将状态图转换成流程图，如图3.53.5写出词法分析程序写出词法分析程序3/29/202322编编译译原原理理Wednesday,March 29,20233.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,e1e2e1|e2,e1e2和和e1e1*也都是也都是 上的正规式上的正规式,它们所表示的它们所表示的 正规集分别为正规集分别为L(e1)L(e1)L(e2)L(e2)、L(e1)L(e2)L(e1)L(e2)和和(L(e1)(L(e1)*4.4.任何任何 上的正规式和正规集均由上的正规式和正规集均由1 1、2 2和和3 3产生。产生。3.43.4正规表达式与有穷自动机正规表达式与有穷自动机3.4.1 3.4.1 正规式与正规集正规式与正规集3/29/202323编编译译原原理理Wednesday,March 29,20233/29/202324编编译译原原理理Wednesday,March 29,2023【例【例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)(a|b)*任何长度大于等于任何长度大于等于2的符号串的符号串3/29/202325编编译译原原理理Wednesday,March 29,2023【例【例3.3】使用正规式来表示例】使用正规式来表示例3.2中的相应单词符号。中的相应单词符号。字母字母|字母字母|数字）数字）数字数字|数字数字+|*|+|*|,|;=标识符：标识符：l(l|d)*无符号整数：无符号整数：dd*单界符：单界符：+|*|,|;双界符：双界符：=3/29/202326编编译译原原理理Wednesday,March 29,2023设设r，s，t均是正规式，则有以下性质：均是正规式，则有以下性质：（1）交换律：）交换律：r|s=s|r（2）结合律：）结合律：r|(s|t)=(r|s)|t(rs)t=r(st)（3）分配律：）分配律：(r|s)t=rt|st（4）同一律：）同一律：r=r=r3/29/202327编编译译原原理理Wednesday,March 29,20233/29/202328编编译译原原理理Wednesday,March 29,2023【例【例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*3/29/202329编编译译原原理理Wednesday,March 29,20232.正规式正规式正规文法正规文法步骤步骤1构造构造Sr步骤步骤2不断利用表不断利用表3.4的规则做变换的规则做变换,直到每个产生式直到每个产生式最多含有一个终结符为止最多含有一个终结符为止规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=xyA=xyA=xA=x*y yA=x|yA=x|y3/29/202330编编译译原原理理Wednesday,March 29,20233/29/202331编编译译原原理理Wednesday,March 29,2023下面是用正规式表示的变量声明：下面是用正规式表示的变量声明：(int|float)id(,id)*请请改改用用上上下下文文无无关关文文法法表表示示，也也就就是是写写一一个个上上下下文文无无关关文法，它和该正规式等价。文法，它和该正规式等价。(int|float)id(,id)*D(int|float)LLid(,id)*DintL|floatLLL,id|idGD：DintL|floatLLL,id|id3/29/202332编编译译原原理理Wednesday,March 29,20233.4.3 3.4.3 有穷自动机有穷自动机标识符标识符无符号整数无符号整数单界符单界符双界符双界符S1非字母数字非字母数字字母字母字母、数字字母、数字2非数字非数字数字数字数字数字3其他字符其他字符+*，（）出口出口4其他字符其他字符5=非非=出错出错其他其他读字符读字符查保留字表查保留字表返回返回S状态图的形式化描述状态图的形式化描述3/29/202333编编译译原原理理Wednesday,March 29,2023有穷自动机是一种有穷自动机是一种数学模型数学模型，具有离散的输入与输出，具有离散的输入与输出，系统可处于有穷状态中的任何一个系统可处于有穷状态中的任何一个它能准确地它能准确地识别正规集识别正规集，即识别正规文法所定义的语言，即识别正规文法所定义的语言和正规式所表示的集合和正规式所表示的集合引入有穷自动机这个理论，正是为引入有穷自动机这个理论，正是为词法分析程序的自动词法分析程序的自动构造构造寻找特殊的方法和工具寻找特殊的方法和工具有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机（DFADFA）(Deterministic Finite Automata)(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机（NFANFA）(Nondeterministic Finite Automata)(Nondeterministic Finite Automata)3/29/202334编编译译原原理理Wednesday,March 29,20232 2型文法型文法（不确定（不确定的下推自动机）的下推自动机）1 1型文法型文法（不确定（不确定的界限自动机）的界限自动机）0 0型文法型文法（图灵机）（图灵机）3 3型文法型文法（有限（有限自动机）自动机）3/29/202335编编译译原原理理Wednesday,March 29,20231.确定的有穷自动机（确定的有穷自动机（DFA）M=(,Q,f,S,Z)：有穷字母表，它的每个元素称为一个输入符号：有穷字母表，它的每个元素称为一个输入符号Q：有穷集，它的每个元素称为一个状态：有穷集，它的每个元素称为一个状态SK，是唯一的初态，是唯一的初态Z K是一个终态集，终态也称可接受状态或结束状态是一个终态集，终态也称可接受状态或结束状态f是转换函数，是是转换函数，是QQ上的单值映射：上的单值映射：f（q1，a）=q23/29/202336编编译译原原理理Wednesday,March 29,2023状态转移函数状态转移函数f可用一矩阵来表示：可用一矩阵来表示：输入输入字符字符状态状态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)3/29/202337编编译译原原理理Wednesday,March 29,2023一个DFA也可以用一状态转换图表示：输入 字符 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3DFA的状态图表示：1032aabba,bba字母表字母表含有含有n个个输入字符，那末输入字符，那末任何一个状态结任何一个状态结点最多有点最多有n条弧条弧射出，而且每条射出，而且每条弧以一个不同的弧以一个不同的输入字符标记。输入字符标记。3/29/202338编编译译原原理理Wednesday,March 29,2023换言之：若存在一条初始状态到某一终止状态的路径，且换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串这条路径上所有弧的标记符号连接成符号串，则称，则称为为DFA MDFA 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所识别。所识别。3/29/202339编编译译原原理理Wednesday,March 29,2023 （0，abaab）=（1，baab）=（2，aab）=（1，ab）=（3，b）=3(接受接受)DFADFA的状态图表示：的状态图表示：1032aabba,bba （0，abab）=（1，bab）=（2，ab）=（1，b）=2(拒绝拒绝)对于符号串对于符号串abaababaab对于符号串对于符号串abababab3/29/202340编编译译原原理理Wednesday,March 29,2023f是一个多值函数，是从是一个多值函数，是从Q*到到Q的子集的映射：的子集的映射：f：Q2Q其中其中2Q是是Q的幂集，即的幂集，即Q中所有子集组成的集合。中所有子集组成的集合。2.不确定的有穷自动机（不确定的有穷自动机（NFA）M=(,Q,f,S,Z)有穷自动机的不确定性表现在在某个状态下，对于某个输入有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的字符存在多个后继状态，即状态的转向是不确定的3/29/202341编编译译原原理理Wednesday,March 29,2023例：例：NFAN=(a,b,c,1,2,3,4,f,1,4)符号符号状态状态abc142，322433，443/29/202342编编译译原原理理Wednesday,March 29,2023对于对于*上的任何符号串上的任何符号串，若存在一条从某一初态到某，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接一终态的通路，且该通路上所有弧的标记字符依次连接成的串等于成的串等于，则称，则称 可以被可以被NFAN所识别或接受。所识别或接受。若若N的初态结点同时为终态，或者存在一条从初态到某的初态结点同时为终态，或者存在一条从初态到某个终态结点的个终态结点的 通路，则通路，则 为为N所识别。所识别。NFAN所能识别的符号串的全体记为所能识别的符号串的全体记为L(N)，称为，称为NFAN所识别的语言所识别的语言 3/29/202343编编译译原原理理Wednesday,March 29,2023上例题相应的状态图为：1234abacacN所接受的语言（正规式）R=aa*b|ac*c|符号 状态 a b c 1 4 2，3 2 2 4 3 3，4 4 3/29/202344编编译译原原理理Wednesday,March 29,2023能接受能接受000111110000001(0|1)(0|1)*(000|111)(0|1)(000|111)(0|1)*不能接受不能接受00011003/29/202345编编译译原原理理Wednesday,March 29,2023画出能够识别画出能够识别C C语言注释语言注释/*/*/的的DFADFA12453othersothers/*/6othersothersall all3/29/202346编编译译原原理理Wednesday,March 29,202312453othersothers/*/状态状态1：注释开始状态。：注释开始状态。状态状态2：进入注释体前的中间状态。：进入注释体前的中间状态。状态状态3：表明目前正在注释体中的状态。：表明目前正在注释体中的状态。状态状态4：离开注释前的中间状态。：离开注释前的中间状态。状态状态5：注释结束状态，即接受状态。：注释结束状态，即接受状态。3/29/202347编编译译原原理理Wednesday,March 29,2023q用于某些重要软件的设计和构造用于某些重要软件的设计和构造设计和检查数字电路行为的软件设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它结构扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件的出现频率的软件;验证所有只有有限多个不同状态的系统的软件，这类验证所有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。系统包括通信协议和信息安全交换协议。有穷自动机的其它应用有穷自动机的其它应用阅读两篇论文阅读两篇论文基于协议分析状态机的入侵检测系统基于协议分析状态机的入侵检测系统有限自动机在有限自动机在BBS信息监测系统中的运用信息监测系统中的运用3/29/202348编编译译原原理理Wednesday,March 29,2023 已证明：非确定的有穷自动机与确定的有穷自动机从功能已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：上来说是等价的，也就是说，我们能够从：NFANDFAM构造成一个使得使得L(M)=L(N)DFA是是NFA的特例。有一种算法，将的特例。有一种算法，将NFA转换成接受同样语转换成接受同样语言的言的DFA.3/29/202349编编译译原原理理Wednesday,March 29,2023 已证明：非确定的有穷自动机与确定的有穷自动机从功能已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：上来说是等价的，也就是说，我们能够从：NFAMDFAM构造成一个使得使得L(M)=L(M)DFA是是NFA的特例。有一种算法，将的特例。有一种算法，将NFA转换成接受同样语转换成接受同样语言的言的DFA.这种算法称为这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一不唯一3.NFA的确定化的确定化3/29/202350编编译译原原理理Wednesday,March 29,2023从从NFANFA的矩阵表示中可以看出，表项通常是一状态的集的矩阵表示中可以看出，表项通常是一状态的集合，而在合，而在DFADFA的矩阵表示中，表项是一个状态。的矩阵表示中，表项是一个状态。NFANFA到相应的到相应的DFADFA的构造的基本思路是：的构造的基本思路是：DFADFA的每一个的每一个状态对应状态对应NFANFA的一组状态的一组状态.符号符号状态状态abc142，322433，441234abacac3/29/202351编编译译原原理理Wednesday,March 29,2023(1)合并如果有 ，则把S2合并到S1S S1 1S S2 2转换需解决的问题：转换需解决的问题：ijkmaban（a）i,jmkaabn（b）3/29/202352编编译译原原理理Wednesday,March 29,2023(2)状态合并0123aabc（a）01,23abc（b）3/29/202353编编译译原原理理Wednesday,March 29,2023定义定义1状态集合状态集合I I的的-闭包，表示为闭包，表示为-closure(I)-closure(I)若若qIqI，则，则qq-closure(I)-closure(I)；若若qIqI，则从，则从q q出发经过任意条出发经过任意条 弧而能到达的任何状弧而能到达的任何状态态qq都属于都属于-closure(I)-closure(I)。为了使得为了使得NFANFA确定化，我们首先给出两个定义确定化，我们首先给出两个定义：_closure(I)IIS2S2S1S1S3S33/29/202354编编译译原原理理Wednesday,March 29,2023例：例：如图所示的状态图：如图所示的状态图：令令I=1，求求-closure（I）=？156432aaa根据定义：根据定义：-closure（I）=1，3课堂练习：令I=1,2，求-closure（I）=？3/29/202355编编译译原原理理Wednesday,March 29,2023I I是状态集，由是状态集，由I I中的状态出发，经过一条中的状态出发，经过一条a a弧可弧可能到达的状态的集合称为能到达的状态的集合称为movemove（I I，a a），则），则I Ia a=_closure(move(I,a)=_closure(move(I,a)定义定义2I Ia a子集子集3/29/202356编编译译原原理理Wednesday,March 29,2023例：令例：令 I=1 I=1 Ia=-closure(move Ia=-closure(move（I I，a a）)=-closure(f =-closure(f（1 1，a a）=-closure(2 =-closure(2，44）=2=2，4 4，66根据定义根据定义1 1，2 2，可以将上述的，可以将上述的MM确定化（即可构造出状态确定化（即可构造出状态转换矩阵）转换矩阵）156432aaa课堂练习：课堂练习：令令I=1,2,3求求IaIa=？3/29/202357编编译译原原理理Wednesday,March 29,2023课堂练习：课堂练习：令令I=1I=1，设，设SS=-closure=-closure（I I），求），求SS？SSa a=？将从状态将从状态S S出发经过任意条出发经过任意条 弧所弧所能到达的状态作为能到达的状态作为DFADFA的初态的初态S S 从从S S 出发，把遇到输入符号出发，把遇到输入符号a a所所转移到的后继状态集作为转移到的后继状态集作为DFADFA的新的新状态状态如此重复，直到不再有新的状态如此重复，直到不再有新的状态出现为止出现为止 NFA转换为转换为DFA的思想的思想1234abacac3/29/202358编编译译原原理理Wednesday,March 29,2023 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）将状态子集重新命名）将状态子集重新命名1234abacac3/29/202359编编译译原原理理Wednesday,March 29,2023将求得的状态转换矩阵重新编号将求得的状态转换矩阵重新编号DFAM状态转换矩阵：状态转换矩阵：符号状态abc0 2 341221_33443/29/202360编编译译原原理理Wednesday,March 29,2023DFAM的状态图：的状态图：注意：包含原初始状态注意：包含原初始状态1的状态子集为的状态子集为DFAM的初态的初态包含原终止状态包含原终止状态4的状态子集为的状态子集为DFAM的终态。的终态。014231,42,342acabbc3,41234abacac3/29/202361编编译译原原理理Wednesday,March 29,2023课堂练习4f35621iaaaabbbbstart3/29/202362编编译译原原理理Wednesday,March 29,2023 等价的DFAaCDBAEFSbaaaaabbbbbabFstart3/29/202363编编译译原原理理Wednesday,March 29,20234.DFA的最小化的最小化如果不同的如果不同的DFA能识别相同的语言，则称它们是等价的能识别相同的语言，则称它们是等价的DFA。在等价的在等价的DFA中，如果某一个中，如果某一个DFA的状态数是最少的，则这个的状态数是最少的，则这个DFA是最简的。是最简的。对于任一个对于任一个DFA，存在一个唯一的状态最少的等价的存在一个唯一的状态最少的等价的DFA最简的最简的DFA它没有多余它没有多余状态和等价状态状态和等价状态3/29/202364编编译译原原理理Wednesday,March 29,2023定义定义1多余状态：多余状态：从开始状态出发从开始状态出发,任何输入串也不能到达的状态任何输入串也不能到达的状态01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s101s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例例:画状态图可画状态图可以看出以看出s4,s6,s8为不为不可达状态应可达状态应该消除该消除3/29/202365编编译译原原理理Wednesday,March 29,2023定义定义2等价状态等价状态状态状态s和和t的等价条件是的等价条件是:状态状态S和和T必须同时为终态或非终态必须同时为终态或非终态对于所有输入符号，对于所有输入符号，S和和T必须转换到等价的状态里必须转换到等价的状态里3/29/202366编编译译原原理理Wednesday,March 29,2023把把DFA的状态划分成一些不相交的子集的状态划分成一些不相交的子集任何不同的两个子集的状态都是可区分的任何不同的两个子集的状态都是可区分的同一子集中的任何两个状态都是等价的同一子集中的任何两个状态都是等价的5724361srartaaaaaaabbbbbbbDFA最小化算法的基本思想最小化算法的基本思想(没有多余状态没有多余状态)：3/29/202367编编译译原原理理Wednesday,March 29,2023解解:(一一)区分终态与非终态区分终态与非终态12345663731546737414212ab区号区号123123456637315467374142ab区号区号（1）将所有状态分成两个子集：终态集和非终态集）将所有状态分成两个子集：终态集和非终态集（2）把等价的状态构成一个子集，若不等价继续划分）把等价的状态构成一个子集，若不等价继续划分（3）结束后，重新标号或从每个子集中选一个状态做代表）结束后，重新标号或从每个子集中选一个状态做代表3/29/202368编编译译原原理理Wednesday,March 29,2023123456637315467374142ab12431243123456637315467374142ab5区号区号区号区号3/29/202369编编译译原原理理Wednesday,March 29,2023将区号代替状态号得将区号代替状态号得:12345ab521435523115 5243aaaaabbbbb化简后的有穷自动机具有较少的状态，实现起来更加简洁。化简后的有穷自动机具有较少的状态，实现起来更加简洁。3/29/202370编编译译原原理理Wednesday,March 29,20233.4.4 3.4.4 正规式与正规式与有穷自动机的等价性有穷自动机的等价性（1）对于字母表）对于字母表上的上的NFAM，可以构造一个，可以构造一个上的正规式上的正规式R，使得，使得L(R)=L(M)；（2）对于字母表）对于字母表上的每个正规式上的每个正规式R，可以构造一个，可以构造一个上的上的NFAM，使得，使得L(M)=L(R)。3/29/202371编编译译原原理理Wednesday,March 29,20231.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,babb3/29/202372编编译译原原理理Wednesday,March 29,2023(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 23/29/202373编编译译原原理理Wednesday,March 29,2023(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)*3/29/202374编编译译原原理理Wednesday,March 29,20232.正规式正规式RNFAM（1）对对NFAM构构造造一一个个广广义义的的状状态态图图，其其中中只只有有一一个个初初态态S和终态和终态Z，连接，连接S和和Z的有向弧标记为正规式。的有向弧标记为正规式。（2）对对正正规规式式依依次次进进行行分分解解，分分解解的的过过程程是是一一个个不不断断加加入入结结点点和和弧弧的的过过程程，直直到到转转换换图图上上的的所所有有弧弧标标记记上上都都是是字字母母表表上的元素或上的元素或 为止。为止。3/29/202375编编译译原原理理Wednesday,March 29,2023若若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 tts3/29/202376编编译译原原理理Wednesday,March 29,2023AZS(a|b)*abb例例:为为R=(a|b)abbR=(a|b)abb构造构造NFA,NFA,使得使得L(N)=L(R)L(N)=L(R)*SZbabABbaZbbSa|bAa3/29/202377编编译译原原理理Wednesday,March 29,20233.4.5 3.4.5 正规文法与正规文法与有穷自动机的等价性有穷自动机的等价性（1）对对于于NFAM，存存在在一一个个右右线线性性文文法法（左左线线性性文文法法）G，使得使得L(G)=L(M)；（2）对对于于右右线线性性文文法法（左左