Chapt3_词法分析

1、第第3 3章章 词法分析词法分析Never look down on yourself. 永远不要小看自己。永远不要小看自己。编译过程编译过程第第3 3章章 词法分析词法分析 （P28P28） n3.1 词法分析的功能词法分析的功能 n3.2 程序语言的单词符号种类及词法分析输出程序语言的单词符号种类及词法分析输出 n3.3 正则文法及状态图正则文法及状态图n3.4 词法分析程序的设计与实现词法分析程序的设计与实现n3.5 正则表达式正则表达式n3.6 有穷自动机有穷自动机n3.7 词法分析程序的自动生成器词法分析程序的自动生成器LEX(略略)学习重点学习重点 n1、根据状态图进行词法分析程序

2、的设计与实现、根据状态图进行词法分析程序的设计与实现n2、根据正则文法画状态图或反过来。、根据正则文法画状态图或反过来。n3、正则文法到正则表达式的转换、正则文法到正则表达式的转换n4、NFA到到DFA的转化的转化n5、根据正则表达式构造、根据正则表达式构造FA3.13.1词法分析的功能词法分析的功能（P28P28） n词法分析程序词法分析程序（或（或词法分析器词法分析器或或扫描器扫描器）：词法分）：词法分析程序是编译程序中完成词法分析任务的程序。析程序是编译程序中完成词法分析任务的程序。 源 程 序词 法 分 析 器单 词 符 号n 词法分析程序的任务词法分析程序的任务其他任务：其他任务：滤

3、掉空格，删除或跳过注释、换行符、滤掉空格，删除或跳过注释、换行符、续行符、标号等非实质性的字符，填符号表，词法续行符、标号等非实质性的字符，填符号表，词法错误检查等错误检查等主要任务：主要任务：读源程序，产生单词符号读源程序，产生单词符号3.13.1词法分析的功能词法分析的功能 n词法分析程序与语法分析程序的词法分析程序与语法分析程序的2种种接口接口方式：方式：1、词法分析作为独立的一遍、词法分析作为独立的一遍，识别出源程序中的单词，识别出源程序中的单词序列，输出到一个序列，输出到一个中间文件中间文件供语法分析程序使用。供语法分析程序使用。字符串源程序字符串源程序 词法分析器词法分析器 符号串

4、源程序符号串源程序 2、词法分析程序和语法分析程序作为同一遍、词法分析程序和语法分析程序作为同一遍。把词法。把词法分析程序设计成一个分析程序设计成一个子程序子程序，当语法分析程序需要单，当语法分析程序需要单词时，则调用词法分析程序。词时，则调用词法分析程序。字符串源程序字符串源程序 词法分析器词法分析器 语法分析器语法分析器 取符号取符号 送符号送符号 3.2 3.2 程序语言的单词符号种类及词法分析输出程序语言的单词符号种类及词法分析输出（P29P29） n单词符号单词符号是程序设计语言的基本语法单位和最小的语是程序设计语言的基本语法单位和最小的语义单位。义单位。n例例 设设PASCAL源程

5、序段：源程序段： n:=1; while n=10 do n:=n+1; 从该程序顺序找出如下单词符号：从该程序顺序找出如下单词符号： n 、:=、1、;、 while、n、=、=、!=、+等。等。 n程序语言中的保留字、分界符的数量都是确定的，程序语言中的保留字、分界符的数量都是确定的，但是标识符和无符号数的数量是不确定的。但是标识符和无符号数的数量是不确定的。 3.2 3.2 程序语言的单词符号种类及词法分析输出程序语言的单词符号种类及词法分析输出 单词类别单词类别 单词值单词值 n词法分析程序的输出形式常采用二元式词法分析程序的输出形式常采用二元式单词类别的表示：单词类别的表示：p同一类

6、单词统一用一个整数值或记号代表其属性。同一类单词统一用一个整数值或记号代表其属性。例如用例如用1表示标识符，表示标识符，2表示无符号数等表示无符号数等p对于保留字和分界符采用一个符号对应一个单词类对于保留字和分界符采用一个符号对应一个单词类别码别码 单词值的表示：单词值的表示：p 常量的二进制表示常量的二进制表示p 常量、变量等在符号表中的地址码等常量、变量等在符号表中的地址码等p 对于一符一类的保留字和分界符用空值对于一符一类的保留字和分界符用空值3.2 3.2 程序语言的单词符号种类及词法分析输出程序语言的单词符号种类及词法分析输出 n例例 设设PASCAL源程序段：源程序段： n:=1;

7、 while n=10 do n:=n+1;经词法分析器识别后其输出单词符号串如下图所示：经词法分析器识别后其输出单词符号串如下图所示： 1n 的内部码n5 1: =21 的二进制形式15 4;6w h i l e1n 的内部码n3 8 =21 0 的二进制形式1 0d o1n 的内部码n5 1: =1n 的内部码n3 1+21 的二进制形式15 4;73.3 3.3 正则文法及状态图正则文法及状态图(P30)(P30) n状态图状态图：一张有穷的有向图一张有穷的有向图u结点代表状态，用圆圈表示。结点代表状态，用圆圈表示。u状态间用有向弧线连接，连接弧状态间用有向弧线连接，连接弧上标记有符号（

8、表示在弧线射出端上标记有符号（表示在弧线射出端的状态下，读入弧线上标记的符号的状态下，读入弧线上标记的符号可转换到弧线指向的状态）。可转换到弧线指向的状态）。u状态个数是有穷的，其中状态个数是有穷的，其中有一个有一个是开始状态是开始状态，至少有一个至少有一个状态是状态是结结束状态束状态，结束状态常用，结束状态常用双圈双圈表示。表示。 SUVZ00111状态图示例状态图示例 03.3 3.3 正则文法及状态图正则文法及状态图n 用正则文法（即用正则文法（即3型文法）来描述程序设计语言的词型文法）来描述程序设计语言的词法规则。正则文法形式为：法规则。正则文法形式为：Ua|Wa或或U = a|aW

9、，其中：其中： U，WVn， a Vt。n 根据正则文法画状态图的方法根据正则文法画状态图的方法: (左线性规则左线性规则) 文法中的每个非终结符号对应状态图中的一个结点，即图中的文法中的每个非终结符号对应状态图中的一个结点，即图中的每个结点代表一个非终结符号。每个结点代表一个非终结符号。 增设一个结点代表开始状态增设一个结点代表开始状态S，而文法中的开始符号对应的结，而文法中的开始符号对应的结点为结束状态。点为结束状态。 对于文法中的每一条形如对于文法中的每一条形如Ua的规则，画一条从结点的规则，画一条从结点S指向结指向结点点U的弧线，并在弧上标记的弧线，并在弧上标记a。 对于文法中每一条形

10、如对于文法中每一条形如U =Wa的规则，画一条从结点的规则，画一条从结点W指向指向结点结点U的弧线，并在弧上标记的弧线，并在弧上标记a。 3.3 3.3 正则文法及状态图正则文法及状态图n例例3-1(P30) 设有正则文法设有正则文法GZ：ZU0|V1UZ1|1VZ0|0画出该文法对应的状态图。画出该文法对应的状态图。SUVZ000111n根据正则文法画状态图的方法根据正则文法画状态图的方法：文法中的每个非终结符号对应文法中的每个非终结符号对应状态图中的一个结点。状态图中的一个结点。增设一个结点代表开始状态增设一个结点代表开始状态S，而文法中的开始符号对应的结而文法中的开始符号对应的结点为结束

11、状态。点为结束状态。对于文法中的每一条形如对于文法中的每一条形如Ua的规则，画一条从结点的规则，画一条从结点S指向指向结点结点U的弧线，并在弧上标记的弧线，并在弧上标记a。对于文法中每一条形如对于文法中每一条形如U =Wa的规则，画一条从结的规则，画一条从结点点W指向结点指向结点U的弧线，并在的弧线，并在弧上标记弧上标记a。 3.3 3.3 正则文法及状态图正则文法及状态图n练习练习 设有正则文法设有正则文法G： =1 | 2| | 9| 0 =1 | 2 | | 9 | 0画出该文法对应的状态图。画出该文法对应的状态图。n根据正则文法画状态图的方法根据正则文法画状态图的方法：文法中的每个非终

12、结符号对应状态图中的一个结点。文法中的每个非终结符号对应状态图中的一个结点。增设一个结点代表开始状态增设一个结点代表开始状态S，而文法中的开始符号对应的结点，而文法中的开始符号对应的结点为结束状态。为结束状态。对于文法中的每一条形如对于文法中的每一条形如Ua的规则，画一条从结点的规则，画一条从结点S指向结指向结点点U的弧线，并在弧上标记的弧线，并在弧上标记a。对于文法中每一条形如对于文法中每一条形如U =Wa的规则，画一条从结点的规则，画一条从结点W指向指向结点结点U的弧线，并在弧上标记的弧线，并在弧上标记a。 3.3 3.3 正则文法及状态图正则文法及状态图n利用状态图来分析和识别字符串的方

13、法利用状态图来分析和识别字符串的方法如下：如下：1.首先首先设置开始状态设置开始状态S为当前状态为当前状态。从输入串的最左字符开始从输入串的最左字符开始重复步骤重复步骤2，直到到达输入串的右端为止。，直到到达输入串的右端为止。2.扫描输入串的下一个字符，在当前状态所射出的弧中，找出扫描输入串的下一个字符，在当前状态所射出的弧中，找出标记有该字符的弧，并沿此弧前进，过渡到下一个状态。标记有该字符的弧，并沿此弧前进，过渡到下一个状态。n若若找不到标记有该字符的弧找不到标记有该字符的弧，则说明输入串不是合法的句，则说明输入串不是合法的句子，分析过程子，分析过程失败结束失败结束；n若扫描的字符是输入串

14、的若扫描的字符是输入串的最后一个字符最后一个字符，且标记有该字符，且标记有该字符的弧线的弧线到达结束状态到达结束状态，则表示输入串是该文法的合法句子，则表示输入串是该文法的合法句子，识别过程识别过程成功成功结束；否则识别过程结束；否则识别过程失败结束失败结束。3.3 3.3 正则文法及状态图正则文法及状态图n例例3-2（P31）设有正则文法）设有正则文法GZ：ZU0|V1UZ1|1VZ0|0对句子对句子0110进行的分析。进行的分析。步骤步骤 状态状态 扫描的字符扫描的字符 余留部分余留部分1S01102V1103Z104U0 5Z ZU0Z1V100110的语法树的语法树 解：解：利用它的状

15、态图对利用它的状态图对0110进行分析的过程进行分析的过程: SUVZ00011100和和100是否是否是文法是文法G的的句子句子?3.4 3.4 词法分析程序的设计与实现词法分析程序的设计与实现（P32P32） nTEST语言的单词符号有语言的单词符号有：标识符标识符：以字母开头，后接字母或数字。如：以字母开头，后接字母或数字。如a1等等保留字保留字（它是标识符的子集）（它是标识符的子集）: if、else、for、while、do、int、read和和write无符号整数无符号整数：100、256等等单分界符单分界符：如：如+、-、*、/、（、）、；、（、）、；、,等等双分界符双分界符：=

16、、=、!=、= =等等注释符注释符：用：用/*.*/括起括起 TEST语言的词法规则语言的词法规则 =| | =| = a|b|z|A|B|Z =1|2|9|0 =+|-|*|/|=|（|）|：|，|；|! =|=|!=|= =/* =*/ n在上述规则中，标识符、无符号整数、双分界符以及注在上述规则中，标识符、无符号整数、双分界符以及注释规则表面看不是正则文法，转换可变成正则文法。释规则表面看不是正则文法，转换可变成正则文法。TEST语言的各类单词符号的正则文法语言的各类单词符号的正则文法 =a|b|Z|a|Z |0|9 =0|1|9|0|9 =+|-|*|/|=|（|）|：|，|；|! =

17、 = |!|= = * =* =/ n由于部分单分界符与双分界符或注释的首字符相同，由于部分单分界符与双分界符或注释的首字符相同，如如、.(连接连接)|(或或/选择选择)。3.5 正则表达式n 例例 设设=a,b，则有：，则有：正则表达式正则表达式e正规集正规集L(e) bL(b)=babL(ab)=L(a)L(b)=ab=aba|bL(a|b)=L(a)L(b)=ab=a,ba*L(a*)=(L(a)*=a*= ,a,aa,aaa,ba* L(ba*)=L(b)L(a*)=ba*=b,ba,baa, 3.5 正则表达式3.5 正则表达式n 正则表达式相等正则表达式相等：设：设e1和和e2都是

18、都是上的正则表上的正则表达式，若达式，若L(e1)=L(e2)，则称，则称e1和和e2等价，记为等价，记为e1=e2。n例例 判断判断a|(ba)*和和 (ba)*|a是否等价。是否等价。解：解： L(a|(ba)*)=L(a)L(ba)*)L(ba)*|a)=L(ba)*)L(a) =L(a)L(ba)*)=L(a|(ba)*)a|(ba)*=(ba)*|a3.5 正则表达式n 例例(P37) 标识符的正则表达式为：标识符的正则表达式为： =字母字母字母字母|数字数字=字母字母(字母字母|数字数字)* 带有符号的实数的正则表达式为：带有符号的实数的正则表达式为： =( |+|-)(数字数字.

19、数字数字数字数字) =( |+|-)(数字数字)*.数字数字(数字数字)*)n例例3-6(P38) 设字母表设字母表=0，求表达式，求表达式00与与000|0定义的语言。定义的语言。解：表达式解：表达式00=00*所定义的语言是所定义的语言是0n|n1表达式表达式000|0=000*|0所定义的语言是所定义的语言是0n|n1 3.5 正则表达式n设设e1、e2和和e3是是上的正则表达式上的正则表达式,则满足以下定律则满足以下定律:交换律交换律：e1|e2= e2|e1除除 e1=e1 =e1外，外，连接不满足交换律连接不满足交换律结合律结合律：(e1e2)e3=e1(e2e3) (e1|e2)

20、|e3=e1|(e2|e3) 分配律分配律：e1(e2|e3)=e1e2|e1e3 (e1|e2)e3=e1e3|e2e33.5 正则表达式n正则文法与正则表达式有等价性，即可以将正则文正则文法与正则表达式有等价性，即可以将正则文法转换成该文法的法转换成该文法的开始符号开始符号所对应的正则表达式。所对应的正则表达式。其其转换规则转换规则为为:(1) 产生式产生式U:=V，V:=, 其中其中,U,V Vn，, Vt* ，转换成正则表达式转换成正则表达式U=；若；若U:=V，V:=,则转换成正则表达式则转换成正则表达式U=(2) 产生式产生式U:=U|,转换成正则表达式转换成正则表达式U=*；产生

21、式产生式U:=U|，转换成正规表达式，转换成正规表达式U=*(3) 产生式产生式U:=|，转换成正则表达式，转换成正则表达式U=|3.5 正则表达式n例例3-7(P39) 有正则文法如有正则文法如下，将其转换下，将其转换成等价的正则成等价的正则表达式。表达式。S aS|aBB bCC aC|a解：解：由由C aC|a，有，有C=a*a由由B bC，有，有B= ba*a由由S aS|aB，有，有 S=a*aB=a*aba*a所求的正则表达式为：所求的正则表达式为： a*aba*a3.5 正则表达式n例例(P38) 标识符的文法规则如下：标识符的文法规则如下：标识符标识符 = a|b|z |标识符

22、标识符a|标识符标识符b|标识符标识符z |标识符标识符0|标识符标识符1|标识符标识符9将该文法转换成正则表达式。将该文法转换成正则表达式。解：解：由标识符由标识符 = a|b|z |标识符标识符a|标识符标识符b|标识符标识符z |标识符标识符0|标识符标识符1|标识符标识符9，有，有标识符标识符 = a|b|z |标识符标识符(a|b|z|0|1|9)，则有：，则有：标识符标识符=(a|b|c|z)(a|b|z|0|1|9)* 所求的正则表达式为：所求的正则表达式为： (a|b|c|z)(a|b|z|0|1|9)*3.6 3.6 有穷自动机有穷自动机（P39P39）n有穷自动机有穷自动机

23、(FA)不是一台具体的机器，而是一种不是一台具体的机器，而是一种具有离散输入与输出系统的数学模型。具有离散输入与输出系统的数学模型。n有穷自动机分为两种类型有穷自动机分为两种类型:确定的有穷自动机确定的有穷自动机(DFA)：是指在当前的状：是指在当前的状态下，输入一个符号，有穷自动机将转换到态下，输入一个符号，有穷自动机将转换到唯一的后继状态。唯一的后继状态。不确定的有穷自动机不确定的有穷自动机(NFA)：在当前状态下：在当前状态下输入一个符号，可能有两种或两种以上可选输入一个符号，可能有两种或两种以上可选择的后继状态。择的后继状态。 n确定的有穷自动机（确定的有穷自动机（DFA）的形式定义：

24、）的形式定义：一个确定的有穷自动机一个确定的有穷自动机M（记作（记作DFA M）是一个五元组：）是一个五元组： M=（ Q， ，q0，F，）其中：其中：Q：是一个有穷的状态集合。：是一个有穷的状态集合。 ：是一个字母表，它的每个元素称为一个输入符号。：是一个字母表，它的每个元素称为一个输入符号。 q0：q0Q，是唯一的开始状态。，是唯一的开始状态。 F：F Q，称为结束状态集合。，称为结束状态集合。 ：状态转换函数，是一个：状态转换函数，是一个QQ的的单值单值映射。映射。在确定的有穷自动机中，状态转换函数的具体形式如下：在确定的有穷自动机中，状态转换函数的具体形式如下：(q,a)=q ,其中，

25、其中，q, qQ，a。这是一个单值函数，表示在当前状这是一个单值函数，表示在当前状态为态为q下，输入符号为下，输入符号为a时，自动机时，自动机将从状态将从状态q转换到下一个状态转换到下一个状态q,q称称为为q的的后继状态后继状态。3.6 3.6 有穷自动机有穷自动机 n例例3-8(P40) 设有穷自动机设有穷自动机DFA M=(0,1,2,3，a,b,0,3,)(0,a)=1 (0,b)=2(1,a)=3 (1,b)=2(2,a)=1 (2,b)=3(3,a)=3 (3,b)=33.6 3.6 有穷自动机有穷自动机n确定的有穷自动机确定的有穷自动机M=(Q, q0,F,)可以用可以用状态图状态

26、图来来表示。表示。其对应关系为其对应关系为 ：状态图中的结点代表状态，：状态图中的结点代表状态，用圆圈表示，它与自动机用圆圈表示，它与自动机M中的状态集合中的状态集合Q相对应，相对应，其中包括开始状态其中包括开始状态q0和结束状态集合和结束状态集合F，结束状态用，结束状态用双圈表示。状态间用有向弧线连接，连接弧上标记双圈表示。状态间用有向弧线连接，连接弧上标记有符号，每条弧线对应一个状态转换函数，弧线上有符号，每条弧线对应一个状态转换函数，弧线上标记的符号集合就是字母表标记的符号集合就是字母表。 3.6 3.6 有穷自动机有穷自动机n例例3-8(P40) 设有穷自动机设有穷自动机DFA M=（

27、0,1,2,3，a,b,0,3,）(0,a)=1 (0,b)=2(1,a)=3 (1,b)=2(2,a)=1 (2,b)=3(3,a)=3 (3,b)=3画出该自动机对应的状态图。画出该自动机对应的状态图。3.6 3.6 有穷自动机有穷自动机a,b0123baaabbn 确定的有穷自动机确定的有穷自动机M=(Q, q0,F,)还可以用还可以用状态转状态转换矩阵换矩阵来表示。来表示。其对应关系为：其对应关系为：矩阵中的第一列元素矩阵中的第一列元素与自动机与自动机M中的状态集合中的状态集合Q一一对应，且一一对应，且初始状态初始状态q0是是第一列的第一个元素，右上角标记第一列的第一个元素，右上角标记

28、*的元素对应结束状的元素对应结束状态。态。状态转换矩阵的第一行元素与字母表中的每个符状态转换矩阵的第一行元素与字母表中的每个符号相对应。矩阵中的元素对应每个状态转换函数。如号相对应。矩阵中的元素对应每个状态转换函数。如果有状态转换函数果有状态转换函数(q,a)=q，其中，其中q,q Q，a，那么，就在矩阵中状态那么，就在矩阵中状态q对应的行和符号对应的行和符号a对应的列单对应的列单元中填入元中填入q 。3.6 3.6 有穷自动机有穷自动机n例例3-8(P40) 设有穷自动机设有穷自动机DFA M=（0,1,2,3，a,b,0,3,）(0,a)=1 (0,b)=2(1,a)=3 (1,b)=2(

29、2,a)=1 (2,b)=3(3,a)=3 (3,b)=3画出该自动机对应的状态转换画出该自动机对应的状态转换矩阵。矩阵。3.6 3.6 有穷自动机有穷自动机a,b0123baaabb S a b 0123* 1 2 3 2 1 3 3 3 n对对DFA的状态转换函数的扩充定义的状态转换函数的扩充定义： (q,at)=(q,a),t)其中其中a，t *，即，即t是是上的符号串。上的符号串。3.6 3.6 有穷自动机有穷自动机n对一个确定的有穷自动机对一个确定的有穷自动机M= (Q, q0,F,)以及某个以及某个符号串符号串x（ x *），如果有），如果有(q0, x)=p，且，且pF，则，则字

30、符串字符串x就被该自动机就被该自动机M所接受所接受。也就是从自动机开始。也就是从自动机开始状态开始，在读完全部输入串以后，自动机刚好到达状态开始，在读完全部输入串以后，自动机刚好到达结束状态，那么该输入串为该自动机所接受。从状态结束状态，那么该输入串为该自动机所接受。从状态图上看，如果一个字符串能被自动机接受，那么从开图上看，如果一个字符串能被自动机接受，那么从开始状态出发，则存在一条到达某一结束状态的路径，始状态出发，则存在一条到达某一结束状态的路径，且组成这条路径的弧线上标记的符号连接起来正好就且组成这条路径的弧线上标记的符号连接起来正好就是字符串是字符串x。 n例例3-9(P41) 设计

31、能接受偶数个设计能接受偶数个0和偶数个和偶数个1组成的串的有穷自动机，画出其状态图及状组成的串的有穷自动机，画出其状态图及状态转换矩阵并判别态转换矩阵并判别110101、11101能否被该自能否被该自动机接受。动机接受。 S 0 1 S *ABC B A C S S C A B SABC11010010 状态转换图状态转换图状态转换矩阵状态转换矩阵下面判别下面判别110101、11101能否被该自动机接受：能否被该自动机接受：(S，110101)=(A，10101)=(S，0101)=(B，101)=(C，01)=(A，1)= S(接受接受)(S，11101)=(A，1101)=(S，101)

32、=(A，01)=(C，1)= B(拒绝拒绝) 解：首先设计能接受偶数个解：首先设计能接受偶数个0和偶数个和偶数个1组成组成的数字串的有穷自动机如下：的数字串的有穷自动机如下：M1=（S，A，B，C，0，1， S，S，） （S，0）=B （S，1）=A （A，0）=C （A，1）=S （B，0）=S （B，1）=C （C，0）=A （C，1）=B其状态图及状态转换矩阵分别如图所示。其状态图及状态转换矩阵分别如图所示。 n一个一个确定的有穷自动机确定的有穷自动机M所接受的语言所接受的语言就是所能就是所能接受的输入串构成的集合，用接受的输入串构成的集合，用L(M)表示，有表示，有: L(M)=t |

33、(q0, t) F，t * 3.6 3.6 有穷自动机有穷自动机n确定有穷自动机的等价性确定有穷自动机的等价性：两个确定有穷自动机：两个确定有穷自动机A1和和A2，如果，如果L(A1)= L(A2)，则称自动机，则称自动机A1与与A2等等价。价。 n例例 已知：已知：DFA A=(q0,q1,a,b, ,q0,q0),其中，其中，(q0,a)=q1, (q1,b)=q0；DFA B=(q0,q1,q2,a,b, ,q0,q0,q2)，其中，其中,(q0,a)=q1,(q1,b)=q2,(q2,a)=q1。判断。判断DFA A和和DFA B是否等价？是否等价？3.6 3.6 有穷自动机有穷自动机

34、q0q1abq1abaq2q0DFA ADFA BL(A)=L(B)=(ab)n|n0，DFA A与与DFA B是等价的。是等价的。 n不确定的有穷自动机不确定的有穷自动机(NFA)的形式定义的形式定义（P42）:一个不确定的有穷自动机一个不确定的有穷自动机NFA M是一个五元式是一个五元式M=(Q， ，q0，F，)其中：其中：Q：有穷状态集：有穷状态集 ：输入字母表与空串组成的集合，输入可以是字：输入字母表与空串组成的集合，输入可以是字母表中的符号，也可以是空串母表中的符号，也可以是空串q0 ：开始状态：开始状态F：终止状态集：终止状态集F Q：状态转换函数，为：状态转换函数，为Q () 到

35、到Q的子集的子集的的多值多值映映射。射。3.6 3.6 有穷自动机有穷自动机n不确定的有穷自动机也可以用不确定的有穷自动机也可以用状态图和状态转换矩阵状态图和状态转换矩阵来表示，表示方法与确定的有穷自动机相同。来表示，表示方法与确定的有穷自动机相同。 n例例3-10(P42) 有有NFA M=(0,1,2,a,b,0,2,)其中：其中：(0,a)=2, (0,)=1,(1,b)=1,2,(2,a)=2,(2,b)=2，画出其状态图及状态转换矩阵，确定该自动，画出其状态图及状态转换矩阵，确定该自动机接收的语言。机接收的语言。3.6 3.6 有穷自动机有穷自动机该自动机接受的语言为该自动机接受的语

36、言为 L(M)= (a|bm) (a|b)n | m1,n0 021ba,bab Sab02111,22*22状态图状态图状态转换矩阵状态转换矩阵n设设(q, a)=p1,p2,pn，其中，其中a ，q, p1,p2,pn Q，对不确定的有穷自动机的状态转换函数的补充定义对不确定的有穷自动机的状态转换函数的补充定义：1) (q, )= -closure(q) 其中其中-closure(q)表示从状态表示从状态q出发，沿着出发，沿着弧到达的后弧到达的后继状态集合以及再从这些后继状态沿着继状态集合以及再从这些后继状态沿着弧所能到达的所有弧所能到达的所有状态集合。状态集合。2)(q, at)=(q,

37、 a),t)=(p1, t)(p2, t) (pn, t) 其中其中t *。3)(q1, q2,qn,x) =(q1, x) (q2, x)(qn, x) 其中其中x * ，表示从不确定自动机的状态集出发，扫，表示从不确定自动机的状态集出发，扫描字符串描字符串x后，所到达的状态集等于从当前状态集的每一后，所到达的状态集等于从当前状态集的每一个状态集出发，扫描字符串个状态集出发，扫描字符串x后所到达的状态集之和。后所到达的状态集之和。 3.6 3.6 有穷自动机有穷自动机n对某台不确定的有穷自动机对某台不确定的有穷自动机NFA M=（Q,q0,F,)及某个字符串及某个字符串 x（ x*），若有）

38、，若有(q0, x )=Q，且，且QF，则则x为为M所接受所接受。3.6 3.6 有穷自动机有穷自动机n不确定的有穷自动机不确定的有穷自动机M所接受的语言所接受的语言： L(M)=x|x*,(q0, x )=Q, 且且 QF n 非确定有穷自动机的等价性非确定有穷自动机的等价性: 两个非确定有穷自动机两个非确定有穷自动机A1和和A2 ，如果如果L(A1)= L(A2)，则称自动机，则称自动机A1与与A2等价。等价。 n设设P是一是一NFA M的状态集的状态集Q的一个子集，的一个子集，状态集状态集P的的闭包闭包 (记为记为-closure(P),P43)的计算方法的计算方法如下：如下：1）若）若

39、qP，则，则q-closure(P)，即，即P的所有成员都的所有成员都是是p的的闭包的成员闭包的成员;2）若）若qP，那么从，那么从q出发经过任意条出发经过任意条弧而能到达弧而能到达的任何状态都属于的任何状态都属于-closure(P)。3.6 3.6 有穷自动机有穷自动机n-closure(P)是状态集是状态集Q的一个子集。的一个子集。n例例3-11(P43)，对如图所示的，对如图所示的NFA M ，求，求P=1、P=2、P=1，2的的闭包。闭包。3.6 3.6 有穷自动机有穷自动机143265aaa NFA M状态图状态图 解：解：-closure(1)=1,3,4,6-closure(2

40、)=2,6-closure(1,2)=-closure(1)-closure(2)=1,3,4,62,6=1,2,3,4,6 n设设P仍是一自动机仍是一自动机M的状态集的子集，的状态集的子集， P =p1, p2,pn ， a，状态集状态集P的的a弧转换集弧转换集(记为记为Pa,P44)为：为： Pa=-closure(J) 其中其中 J=(p1, a )(p2,a)(pn,a) ，即即J是从状态子集是从状态子集P中的每一个状态出发，沿着标记中的每一个状态出发，沿着标记为为a的弧而到达的状态所组成的集合。的弧而到达的状态所组成的集合。3.6 3.6 有穷自动机有穷自动机n例例3-12(P44)

41、 对如图所示的对如图所示的NFA M ，若，若P=1，求，求Pa。3.6 3.6 有穷自动机有穷自动机143265aaaNFA M状态图状态图 解：解：Pa=-closure(J) =-closure(1, a )=-closure(2,4)=2,4,6 n根据根据NFA M=(Q,q0,F, )构造等价的构造等价的DFA M=(Q,q0,F,)的过程的过程(即即NFA的确定化的确定化，P44):1) = 2) 先求先求由由NFA M 的开始状态的开始状态q0 构成的集合构成的集合的的闭包，闭包，从而确定从而确定DFA M的开始状态的开始状态q0。3) 求开始状态求开始状态q0对每个输入符号的

42、弧转换集，若出现对每个输入符号的弧转换集，若出现不同于开始状态不同于开始状态q0的新状态，则转的新状态，则转4)。4) 求新状态对每个输入符号的弧转换集，重复该步骤，求新状态对每个输入符号的弧转换集，重复该步骤，直至没有新状态产生为止。直至没有新状态产生为止。5) 根据上面求出的各个状态确定结束状态集根据上面求出的各个状态确定结束状态集F=P|P F ，其中，其中P为为M的每个状态子集。的每个状态子集。3.6 3.6 有穷自动机有穷自动机n例例 将将NFA(见下图见下图)确定化。确定化。3.6 3.6 有穷自动机有穷自动机SZA10B C0 ,1解：将解：将NFA转换为转换为DFA的过程的过程

43、B,C,Z q3B,C q2B,C,Z q3B,C,Z q3B,C q2B,C q2B,C,Z q3B,C q2A,B,C q1 A,B,C q1S q0P1P0Pq0q1011q20q3010NFA相应的相应的DFA的状态转换图为：的状态转换图为：n例例 将将NFA(见下图见下图)确定化。确定化。3.6 3.6 有穷自动机有穷自动机解：将解：将NFA转换为转换为DFA的过程的过程NFA相应的相应的DFA的状态转换图为：的状态转换图为：B,C,Z q2B,C q1B,C,Z q2B,C,Z q2B,C q1B,C q1B,C,Z q2 B,C q1S,A,B,C q0P1P0Pn练习练习 将将

44、NFA(见下图见下图)确定化。确定化。3.6 3.6 有穷自动机有穷自动机解：将解：将NFA转换为转换为DFA的过程的过程NFA相应的相应的DFA的状态转换图为：的状态转换图为：3,4 q43,4 q4Pc4 q32 q22 q24 q33,4 q44 q32 q22,3 q12,3 q11,4 q0PbPaP1234aaaccbq0q1q2q3q4aaabbccn根据正则表达式可构造与之等价的有穷自动机，反根据正则表达式可构造与之等价的有穷自动机，反之亦然。之亦然。3.6 3.6 有穷自动机有穷自动机n根据正则表达式构造有穷自动机的分解规则（根据正则表达式构造有穷自动机的分解规则（P46）S

45、0S1S0S1S0S1a1) 与与、和和a （a ）等价的）等价的NFA分别是：分别是： 与与R1R2（或（或R1.R2 ）等价的）等价的NFA为：为：3.6 3.6 有穷自动机有穷自动机与与R1 |R2 等价的等价的NFA为：为：S0S1R1R2 S0S2S1R1 R2 S0S1R1|R2 S0S1R1 R2 与与R*（或（或R）等价的）等价的NFA为：为： S0S1R* S0S2S1 Rn例例3-13（P47） 有正则表达式有正则表达式R=(a)*(|bb)(a|b)* ，构，构造出等价的造出等价的NFA，然后转化成，然后转化成DFA。3.6 3.6 有穷自动机有穷自动机解：构造过程如下：

46、解：构造过程如下：01(a)*(|bb)(a|b)* 02(a)*31|bb (a|b)* 0231|bb a|b 45a 0231 a45a 6b b bn练习练习 构造正则表达式构造正则表达式a(ab*|ba*)*b的的NFA。 3.6 3.6 有穷自动机有穷自动机SZAbaC BbDaEbaG F n将将DFA M转换成正则表达式的方法转换成正则表达式的方法（P48）：）：3.6 3.6 有穷自动机有穷自动机填加两个新的结点填加两个新的结点S和和T，将结点，将结点S与与DFA M上的开上的开始状态结点连接，将每个结束状态结点与始状态结点连接，将每个结束状态结点与T结点用弧线结点用弧线连接

47、，所有连接弧线上均标记为连接，所有连接弧线上均标记为，从而，使，从而，使NFA M只只有一个开始状态有一个开始状态S和一个结束状态和一个结束状态T。逐步去掉逐步去掉NFA M中的结点，直到只剩下结点中的结点，直到只剩下结点S和和T。在去掉结点的过程中，逐步用正则表达式来标记弧线。在去掉结点的过程中，逐步用正则表达式来标记弧线。去掉结点的规则如下。去掉结点的规则如下。 p 连接：连接：13R1R2 123R1 R2 p选择：选择：3.6 3.6 有穷自动机有穷自动机p闭包（或重复）闭包（或重复）:12R1|R2 12R1 R2 13R* 123 Rn例例 设设NFA M的状态转换图如下图所示，在

48、的状态转换图如下图所示，在x,y上构造一个正则表达式上构造一个正则表达式e，使，使L(e)=L(M)。 3.6 3.6 有穷自动机有穷自动机123xyyx4x ,yyxn解：构造过程如下：解：构造过程如下：3.6 3.6 有穷自动机有穷自动机123xyyx4x ,yyxS T 1x,yS 4T xy*yyx*x3.6 3.6 有穷自动机有穷自动机1x,yS Txy*y|yx*xST(x|y)*(xy*y|yx*x)所求的正则表达式为：所求的正则表达式为：(x|y)*(xy*y|yx*x)3.6 3.6 有穷自动机有穷自动机n如果有两个确定的有穷自动机如果有两个确定的有穷自动机DFA A1和和D

49、FA A2所接所接受的语言完全一样，我们说这两个自动机是等价的。受的语言完全一样，我们说这两个自动机是等价的。n对于任何给定的对于任何给定的DFA，都有一个含有最少状态的等价，都有一个含有最少状态的等价的的DFA（称为（称为最小化的最小化的DFA），而且这个最小化的），而且这个最小化的DFA是唯一的。是唯一的。n等价状态与不等价状态等价状态与不等价状态(P49)： 在一个确定的有穷自动机里，在一个确定的有穷自动机里，如果从如果从S1状态出发接受的所有符状态出发接受的所有符号串集合与从号串集合与从S2状态出发接受的状态出发接受的所有符号串集合一样，那么称状所有符号串集合一样，那么称状态态S1和和

50、S2是等价的；否则是不等是等价的；否则是不等价的。价的。02134abaabn多余状态：多余状态：一是从初始状态到该状态之间没有通路；一是从初始状态到该状态之间没有通路；二是从该状态到终止状态之间没有通路。二是从该状态到终止状态之间没有通路。n例例3-15 (P49) 判断如下的状态图中，哪些状态是多余判断如下的状态图中，哪些状态是多余状态。状态。012345bba0234bb有多余状态的状态图有多余状态的状态图 删除多余状态的状态图删除多余状态的状态图 n多余状态是无用的，应该删除。删除多余状态的方法多余状态是无用的，应该删除。删除多余状态的方法是直接将多余状态结点以及相关的弧线删除，即可得

51、到是直接将多余状态结点以及相关的弧线删除，即可得到等价的自动机。等价的自动机。 aab3.6 3.6 有穷自动机有穷自动机3.6 3.6 有穷自动机有穷自动机n设设DFA M=(Q,q0,F)，最小化（或化简）最小化（或化简）DFA的算的算法法(P49) :1）先将自动机的状态划分成）先将自动机的状态划分成非结束状态集非结束状态集S1和和结束结束状态集状态集S2。2）对各状态集按下面方法划分，直到所有状态集不）对各状态集按下面方法划分，直到所有状态集不再产生新的划分为止。设第再产生新的划分为止。设第m次划分将次划分将Q分成分成n个状态个状态集，即集，即Q= S1S2Sn 。 对状态集合对状态集

52、合Si（i=1，2，n）中的各个状态逐一检查，设状态）中的各个状态逐一检查，设状态q1和和q2是状是状态集合态集合Si中的两个状态，对于输入符号中的两个状态，对于输入符号a（a），有），有(q1,a)= S、(q2,a)=S,若状态若状态S 和和S属于同一状态属于同一状态集合，则将状态集合，则将状态q1和和q2放在同一状态集合中；否则，将放在同一状态集合中；否则，将状态状态q1和和q2分为两个集合。分为两个集合。3.6 3.6 有穷自动机有穷自动机3）重复第）重复第2步，直到所有状态集合都不能划分。此时，步，直到所有状态集合都不能划分。此时，每个状态集合中的状态都是等价的。每个状态集合中的状态

53、都是等价的。4）将每个状态集合中的等价状态合并成一个等价代）将每个状态集合中的等价状态合并成一个等价代表状态。将状态函数中的所有状态用相应的等价代表表状态。将状态函数中的所有状态用相应的等价代表状态表示。从状态图上看，要将一个状态集合中的等状态表示。从状态图上看，要将一个状态集合中的等价状态结点合并成一个结点。价状态结点合并成一个结点。5）删除多余状态。）删除多余状态。 3.6 3.6 有穷自动机有穷自动机n例例 将将DFA（见右图）最小化。（见右图）最小化。解：将状态集分成非结束状态集解：将状态集分成非结束状态集S1=q0,q1,q2和结束状态集和结束状态集S2=q3 。在在S1中，由于状态

54、中，由于状态q0无输入无输入1，而，而状态状态q1和状态和状态q2有输入有输入1，所以将，所以将S1分割成分割成S11=q0和和S12=q1,q2。又因为又因为 (q1,0)=q2S12， (q2,0)=q2S12， (q1,1)=q3S2， (q2,1)=q3S2，所以状态，所以状态q1和状态和状态q2等价。等价。将原状态集合分割成以下子集：将原状态集合分割成以下子集：q0，q1,q2，q3q0q1011q20q30103.6 3.6 有穷自动机有穷自动机n例例3-16(P50) 对如图所示的有穷自动机化简。对如图所示的有穷自动机化简。01234bbbaaabaab待化简的有穷自动机待化简的

55、有穷自动机 解：将状态集分成非结束状态集解：将状态集分成非结束状态集S1=0,1,2和结束状态集和结束状态集S2 =3，4 。对对S1=0，1，2的划分的划分:(0,a)=1,(1,a) =3,(2,a) =1,(0,b)=2,(1,b) =2,(2,b) =4将将S1分成分成S4=0，S5=1, S6=2对对S2=3，4的化分的化分:(3,a)=3，(4,a) =3,(3,b)=4，(4,b) =4状态状态3和和4等价。等价。最终得到不能划分的状态集有最终得到不能划分的状态集有: S2=3,4, S4=1,S5=0,S6=2。0123bbbaaaab化简后的有穷自动机化简后的有穷自动机 3.

56、6 3.6 有穷自动机有穷自动机n练习练习 将将DFA（见下图）最小化。（见下图）最小化。01xy234576xxxxxxyyyyyy3.6 3.6 有穷自动机有穷自动机n练习练习 将将DFA（见下图）最小化。（见下图）最小化。01xy234576xxxxxxyy yyyy01xy235xxxyyy最小化最小化DFA待化简的待化简的DFA3.6 3.6 有穷自动机有穷自动机n根据根据DFA来构造词法分析程序的方法来构造词法分析程序的方法（P51）：）：直接编程的词法分析器直接编程的词法分析器 用程序来模拟用程序来模拟DFA的行为。在这种方法里，将的行为。在这种方法里，将DFA用状态图表示，按下列步骤根据状态图画出词法分析程用状态图表示，按下列步骤根据状态图画出词法分析程序流程图：序流程图：p1) 开始状态对应程序的开始；开始状态对应程序的开始；p2) 结束状态对应程序的结束；结束状态对应程序的结束；p3) 状态转移对应条件语句或多分支选择语句；状态转移对应条件语句或多分支选择语句；p4) 状态图的环对应程序中循环语句；状态图的环对应程序中循环语句；p5) 结束