第三章 词法分析及有穷自动机

1、编 译 原 理 第三章 词法分析及有穷自动机 主主 要要 内内 容容 词法分析程序的设计过程。词法分析程序的设计过程。 描述单词的文法：正规文法和描述单词的文法：正规文法和 正规式及它们之正规式及它们之 间的转换。间的转换。 单词识别机制（有穷自动机）。单词识别机制（有穷自动机）。 正规式，正规文法和有穷自动机三者之间相互转正规式，正规文法和有穷自动机三者之间相互转 换。换。 1. 词法分析程序的任务词法分析程序的任务 一、词法分析程序的任务及处理方式一、词法分析程序的任务及处理方式 1. 词法分析程序的任务词法分析程序的任务 主要任务：从左至右逐个字符地对源程序进行扫 描，产生一个个单词序列

2、，用以语法分析。 词法分析程序（扫描程序）：执行词法分析的程 序。 2. 词法分析程序的处理方式词法分析程序的处理方式 词法分析程序与语法分析程序接口方式有两种： v第一种方式： 字 符 串 表 示 的 源程序 词 法 分 析程序 单 词 串 表 示 的 源程序 语 法 分 析程序 字符 单词 图 2.1 将词法分析作为单独一遍扫描，即在语法分析之前， 实现源程序的词法分析工作。其输出（单词串）形成一个 中间文件（内部形式的源程序表），然后移交给语法分析 程序。 v第二种方式： 将词法分析程序编写成一个子程序，每当语法分 析程序需要读一个新单词时，便去调用它。 注：后一种方式比较好。因为不需要

3、在内存中构 造和保存中间文件。 字 符 串 表 示 的 源程序 词 法 分 析程序 语 法 分 析程序 字符 回送单词 图 2.2 取单词 二、词法分析程序的二、词法分析程序的I/O 1. 输入输入 字符串表示的源程序 2.输出输出 单词符号序列或单词符号。 1) 程序语言的单词符号程序语言的单词符号 单词：指语言中具有独立意义的最小语法单位。 语言中的单词符号： 一般可归结为五种： v保留字（基本字）：如if, for, and 等个数确定 v标识符：表示常量、变量、类型、过程等名称个数不确定 v常数：如34，-0.37等个数不确定 v运算符：如+，-，*，/， 等个数确定 v界线符：如逗号

4、，分号，括号等个数确定 注：保留字，运算符，界线符可列表，供词法分析程序查询；保留字，运算符，界线符可列表，供词法分析程序查询； 标识符和常数可用正规文法或正规式描述，供词法分析标识符和常数可用正规文法或正规式描述，供词法分析 程序识别。程序识别。 2) 输出的单词形式输出的单词形式 v二元组：（单词的种别码，单词自身值） 1o 单词的种别码：表示单词的种类单词的种别码：表示单词的种类 v分类的原则：处理简单 v分类的方法：使每一个单词对应一个整数码 v分类的目的：最大限度地区别各个单词 单词地分类法有多种： v一种一类 v一字一类或一符一类 具体：具体： 保留字：一字一种。如： if 1 t

5、hen 2 。 标识符：统归一种。 常数：整数，实数，布尔 v统为一种 v或按类型分 整数11 实数12 布尔13 或全体一种 +29:= 17=21 -14 18= 22 *15 23 /16，1 then b:=10表示为一种一类的单词输出形式。 if a1 then b:=10 词法分析 器= (1, if ) (字符串表示 的源程序) (2, a ) , (4, ) (3,1 的二进 制数) (1, then ) (2, b ) (4, := ) (3, 10 的二 进制数) v例：采用一字一类或一符一类地分类技术，则保留 字单词自身值可无，但事先构造一个保留字单词对 照表，其值可在词

6、表中查到。 if a1 then b:=10 词法分析器=(1, ) 字符串表示的 源程序 (10, a ) (23, ) (3,1的二进制数) (2, ) (10,b) (17, ) (11,10 的二进制数) 上面符号表示要查保留词表 表2.1 保留字单词表 单词类别码单词类别码 . If1+29 Then2 - 14 else3*15 . / 16 . 23 for19 := 17 . 2. 词法分析程序的设计过程词法分析程序的设计过程 一、词法分析程序的设计过程一、词法分析程序的设计过程 v设计过程： v词法分析程序设计过程：词法分析程序设计过程： 把有的单词（如：标识符和常数标识符和

7、常数）用正规文法或正规式描述； 将正规文法或正规式转换成等价的状态转换图（最小化的 DFA图）； 根据状态转换图设计词法分析程序（状态转换图可视为词 法分析程序的框图）。 正规文法 NFA 转 换 正规式 DFA 化简 最少化 的 DFA 词 法 分 析 程序 转换规则转换规则 分裂法分裂法 子集法子集法 状态转换图（DFA图） 二、用状态转换图设计词法分析程序二、用状态转换图设计词法分析程序 1. 词法分析程序的预处理 词法分析程序在识别单词前，需要对输入到缓 冲区的源程序进行预处理。 预处理： 删去无用的空格，跳格，回车和换行等编辑性字符； 删去注释部分 每次对一串定长（如120个字符）的

8、输入字符进 行预处理，并装入一个指定的扫描缓冲区中。 v扫描缓冲区是一个一分为二的区域，每一个区域可 容纳120个字符，且相互交替使用。 v搜索指针从单词起点开始搜索，如果遇到半区的边 界但尚未达到单词的终点时，则可将后续的120个输 入字符装进缓冲区的另一半中。 搜 索 指 针 图 2.3 单 词 起 点 120 120 2. 状态转换图状态转换图 v状态转换图是为了识别正规文法或正规式而专门设计的有 向图。他是有穷自动机的非形式化表示。 v状态转换图的组成状态转换图的组成： 1o 有限个状态结点有限个状态结点 状态结点代表正规文法的非终结符（用单圈表示）； 开始状态结点：用双箭头指示； 终

9、止状态结点：用双圈表示。 2o 弧线弧线弧上的标记弧上的标记x指明在射出弧的结点状态下指明在射出弧的结点状态下 可能出现的输入字符或字符类可能出现的输入字符或字符类,即终结符。即终结符。(表示表示 机器的识别方向机器的识别方向). 大多数单词结构是用正规文法描述的大多数单词结构是用正规文法描述的 x 例： =| =| =+|-|*|/|. =；|，| ( | ) |. 。 3.由正规文法构造状态转换图由正规文法构造状态转换图 1) 左线性正规文法构造状态转换图 左线性正规文法的一般形式：U = a|wa 左线性正规文法构造状态转换图的步骤如下： 增加一个开始状态结点s（假定文法的词汇表中不含

10、s）； 以每个非终结符为状态作结点； 对于形如U =a的每一个规则，引一条从开始状态s到 状态U的弧，弧上标记为a； 对于形如U =wa的每一个规则，引一条从状态w 到状态U的弧，弧上标记为a； 以识别符号为终止状态。 S U a W U a 例：设有正规文法GZ： Z = U0|V1 U =Z1|1 V =Z0|0 （描述的语言为L(G)=01,10 ） 则状态转换图如下： S U V 0 1 0 1 0 1 Z 以开始符号以开始符号Z 作终态作终态 新增加开新增加开 始状态始状态S 0 1 字母 2 非字母和非数字 字母或数字 例：标识符的转换图： 从开始状态出发到某一终止状态结点为止，所

11、经过的路径 上的符号串，称能为该状态转换图所接收（识别）的符号 串。 如：标识符x26为上述转换图识别，识别路径为 x 0 1 2 非字母和非数字 2 1 6 1 2)右线性正规文法构造状态转换图 v右线性正规文法U = a|aV构造状态转换图的步骤： v增加一个终止状态结点z（假定文法的词汇表中不含 z）； v以每个非终结符为状态作结点； v对于形如U =a的每一个规则，引一条从开始状态U 到终止状态z的弧，弧上标记为a； v对于形如U =aV的每一个规则，引一条从状态U到 状态V的弧，弧上标记为a； 以识别符号为开始状态。 U a Z U V a 根据状态转换图设计词法分析程序根据状态转换

12、图设计词法分析程序 状态转换图实际上是编写词法分析程序的框图 根据状态转换图写出相应的词法分析程序的方 法： 1o对于每个状态构造一小段程序。对于每个状态构造一小段程序。 功能： 从输入串中读一个字符； 判明读入字符与由此状态出发的哪条弧上的标 记匹配，便转至相匹配的那条弧所指的状态； 均不匹配时便失败（不能达到正常出口） 2o 再根据图形决定小段程序之间的调用。再根据图形决定小段程序之间的调用。 注：词法分析程序除了识别单词外，还可为语法程 序提供更多的信息。因此，可在这些小段程序中加 上一些语义处理（如对数值进行10=2 等） 例：设有关于单词的文法G=(VN,VT,P,N1) 其中，VN

13、=N1,N2,N3,N4,N5,N6,N7 VT=d, , e , f, P：N1 =dN2|N3|eN5 N2 =dN2|N3|eN5| N3 =dN4 这里d表示数字（09）；e10；f ；表示空 字符；N1表示无符号数，其一般形式为： dddd e f dd N4 =dN4|eN5| N5 =dN7|fN6 N6 =dN7 N7 =dN7| v试构造识别此单词的词法分析程序 1 根据右线性正规文法，画出状态转换图根据右线性正规文法，画出状态转换图 N1=3N2=34N2=34N3=345N4 =3456N4=3456(达到出口),自上而下的推导过程。自上而下的推导过程。 N1 e N5

14、N2 N3 N7 N6 N4 d 出口 d f e d e d 出口 d 出口 d d 2根据状态转换图写词法分析程序 为每一个状态结点写一个过程或函数： 对N1结点： Procedure PN1 Begin Ch:=getchar( ); If ch=”e” then PN5 Else if ch=”d” then PN2 Else if ch=” ” then PN3 Else error End; 对N2结点： Procedure PN2 Begin Ch:=getchar( ); If ch=”e” then PN5 Else if ch=”d” then PN2 Else if ch

15、=” ” then PN3 Else return; End; 对N3,N4,N5,N6,N7结点分别写出程序段： 3 正规式与有穷自动机正规式与有穷自动机 v为了进一步讨论词法分析程序的自动生成， 需要将状态转换图的概念加以形式化；同时 将由正规文法描述的单词由正规式描述，可 利用有穷自动机生成词法分析程序。 一、正规式与正规集一、正规式与正规集 语言的单词结构不仅由正规文法描述，还可 以由正规式描述。 例： =| 此正规文法描述了一个语言的集合。定义在字母， 数字上的以字母开头的符号串的集合。这个集合还 可以用正规式描述：字母(字母|数字)*。 v正规式描述的字符串的集合称为正规集 1正规

16、式（也称正则式，正则表达式）和正规集的正规式（也称正则式，正则表达式）和正规集的 递归定义递归定义 设有字母表=a1,a2,an,那么 (1) , ,ai 都是上的正规式，它们所描述的正规 集分别为，ai； (2) 若e1和e2都是上的正规式，它们所描述的正规集 L(e1)、L(e2)，则： 1o正规式的“或”（|）运算： e1|e2也是正规式，相 应正规集为L(e1|e2)=L(e1) L(e2)； 2o正规式的“连接”（.）运算：e1e2也是正规式，相 应正规集为 L(e1e2)=L(e1) L(e2)； 3o正规式的“闭包”（*）运算:(e1)*也是正规式，相 应正规集为 L(e1)*)

17、= (L(e1)*； (3) 仅由有限次使用(1),(2)定义的表达式才是上的正 规式，由这些正规式所表示的字符集才是上的正 规集。 例：设=a,b，则上的正规式和正规集有 正规式正规集 1o a和b a L(a)=a和L(b)=b L(a) =L(a) L(a) L(a) =a=a,aa,. 基 本 3 oa|bL(a|b)=L(a)L(b)=a,b 4 oabL(ab)=L(a)L(b)=ab 5 oa*L(a*)=(L(a)*=L(a) L(a) L(a) . =a*=,a,aa,aaa,. 复 合 6 oba*L(ba*)=L(b) L(a*) =b,ba,baa,baaa, 7 oa

18、| ba*L(a| ba*)=L(a)L(ba*)=a,b,ba,baa, 8 o(a|b)*L(a|b)*)= (L(a|b)*=a,b*=,a,b,aa,ab, 所有ab组成的串 9 oa(a|b)*L(a(a|b)*)=L(a)( L(a)L(b)*=aa,b* 10 o(a|b)*(aa|bb) (a|b)*L(a|b)*(aa|bb) (a|b)*)=a,b*aa,bba,b* 012 + 1 23 + 2o 注：注：.正规式仅由字母正规式仅由字母中的终结符号，通过或，连接中的终结符号，通过或，连接 和闭包三种运算组成的式子。和闭包三种运算组成的式子。 例：有字母表例：有字母表=a，

19、b，下面正规式，求正规集。，下面正规式，求正规集。 ba* 正规集：正规集：b开头后面跟开头后面跟0个或若干个个或若干个a。 a(a|b)* 正规集：正规集：a开头后面跟开头后面跟0个或个或a、b任意排列。任意排列。 例：有字母表例：有字母表=a，b，下面用自然语言描述的正规，下面用自然语言描述的正规 集，求正规式集，求正规式(可能不唯一可能不唯一)。 以以ab结尾的所有字符串。结尾的所有字符串。 (a|b)*ab 包含偶数个包含偶数个b的所有字符串。的所有字符串。 (bb)* 只包含一个只包含一个a的所有字符串。的所有字符串。 b*ab* 不包含不包含ab子串的所有字符串。子串的所有字符串。

20、 b*a* 以以a开头开头b结尾的所有字符串。结尾的所有字符串。 a(a|b)*b 正规式的性质 （1）正规式的等价性 定义： 若正规式e1与e2描述的正规集相同，即L(e1)= L(e2)， 则e1与e2等价，记做e1=e2。 （2）正规式的代数性质 设r,s,t为正规式，正规式服从的代数规律有： 1or|s=s|r“或”满足交换律 2 or|(s|t)=(r|s)|t“或”满足结合律 3 o(rs)t=r(st)“连接”满足结合律。 “连接”不满足交换律 4 or(s|t)= r s| r t (s|t)r= s r| t r “连接”满足分配律 5or=r r=r 是“连接”的恒等元素

21、(3) 正规式的恒等式 设A和B式正规式，有 例：证明：A*= |AA*成立。 证明: 利用对应的正规集来证明： L(AA*| )=L(A)L(A*) UL()=L(A)L(A)*UL() = L(A)(L(A) UL(A) U(L(A) .)UL() = L() U(L(A) U(L(A) U(L(A) .) =(L(A)*)=L(A*) A*=AA*| 例：设=d, , e, +, - 则上的正规式： d*(dd*|)(e(+|-|)dd*|)表示无符号数：2.12,3.6e-2等。 表示无符号数的正规式，比表示无符号数的正规文法显得直观，简洁。表示无符号数的正规式，比表示无符号数的正规文

22、法显得直观，简洁。 1o（A*）*= A* 2 oA|BA=(|B)A 3 oA A*= A*A ；A =AA* 4 oA*=|A A*; A*=(A| )* 012 312 + 3正规文法与正规式的转换正规文法与正规式的转换 关系：对任意一个正规文法存在定义同一语言的正规式 反之：对于每一个正规式，存在一个生成同一语言的正 规文法。 两者之间具有等价的转换关系。 有的语言容易用正规文法定义，有的语言则更 容易用正规式定义 转换： 1o 正规式正规式-正规文法正规文法 将上的一个正规式转换成正规文法G=(VN,VT,S,P)： v首先：令VT= v再确定产生式P和VN，其方法： 对任何正规式r

23、，选择非终结符S生成产生式S =r， 并将S定义为G的识别符号。 若r含有正规式x,y,对形如A =xy（连接的变换） 产生式，用A =xB,B =y两个产生式替换。其中B 是新选择的非终结符。 对已经转换成文法中的形如：A =x*y （闭包和 连接的变换）的产生式，则重写为： A =xA 注：若y是则， AxA A =y A 对形如：A =x|y （或的变换）的产生式，重写为 A =x, A =y 不断利用上述规则作变换，直到每个产生式右部 最多含有一个终结符为止。 例：将正规式R=a(a|d)*转换成相应的正规文法。 解：令S是文法的识别符号，则首先形成： S =a(a|d)* 然后形成：

24、 S =aA, A = (a|d)* (其中AVN) 对于 A = (a|d)*重写为： A = (a|d)A A = 对于A = (a|d)A重写成：A =aA, A =dA 最后转换的等价正规文法G=(VN,VT,S,P) VT=a,d VN=S,A P: S =aA A =aA|dA| 2o正规文法正规文法正规式正规式 基本是上述的逆过程。最后只剩下一个识别符 号定义的产生式，且产生式的右部不含非终结符。 其转换规则如下表： 规则文法产生式正规式 1A =xB, B =yA=xy 2A =xA|yA=x*y 3A =x, A =yA=x|y 注：注：正规文法与正规式互相转换，关键式：正规

25、文法与正规式互相转换，关键式：AxA|y A= x*y 例：正规文法Gs： S =aA S =a A =aA A =dA A =a A =d 求正规式 解：先有：SaA|a 规则3 A=(aA|dA)|(a|d) 规则3 再将A的正则式变成：A=(a|d)A|(a|d) “或”分配律 根据规则2变成： A=(a|d)*(a|d) 再代入S的右部得： S=a(a|d)*(a|d)|a 再利用正则式代数变换： S=a(a|d)*(a|d)| ) S=a(a|d)* 即：a(a|d)*为所求的正则式 简便转换方法是: (1)将正规文法中的每一个非终结符表示成关于它的一个正规方程,获 得一个联立方程组

26、. (2)依据求解规则: v若x =x|,写成方程x= x+(“|”用“+”表示);则解为x= *. v若x =x|,写成方程x=x+(“|”用“+”表示);则解为x=*. 以及正规式的分配律,交换律和结合律求关于文法识别符号的正规式 方程组的解.此解就是关于文法识别符号S的一个正规式. 例如,上例:先写出正规式方程组(方程组中用“+”代替“|”): S =aA|a写成:S=aA+a（1） A =aA|dA|a|d写成:A=aA+dA+a+d（2） 将（2）式简化为：A=(a+d)A+(a+d) 使用求解规则：A=(a|d)*(a|d) （3） 将（3)的A代入（1)式：S=a(a|d)*(a

27、|d)|a =a(a|d)*(a|d) |) a(a|d)*(a|d)| )= a(a|d)*即为所求的正规式。 例：设有正规文法例：设有正规文法G: Z = 0A A = 0A|0B B = 1A| 试给出该文法的正规式。试给出该文法的正规式。 解：给出相应的正规式方程组：解：给出相应的正规式方程组： Z=0A（1） A=0A+0B（2） B=1A+ （3） （3）代入（）代入（2）中的）中的B得：得：A=0A+01A+0=(0+01)A+0 使用求解规则：使用求解规则：A=(0|01)*0（4） （4）代入（）代入（1）式中的）式中的A得：得：Z=0(0|01)*0 所以，所以， 0(0|

28、01)* 0 即为所求的正规式。即为所求的正规式。 例：设有正规文法例：设有正规文法G: P: A:= aB|bB , B:=aC|a|b , C:=aB 相应的正规式方程：相应的正规式方程：A=aB+bB （1） B=aC+a+b (2) C=aB .(3) (3)代入代入(2)中的中的C: B=aaB+a+b .(4) 对(4)式使用求解规则： B=(aa)*(a|b) .(5) 将（5）代入(1)式中的B： A=(a|b)(aa)*(a|b) (a|b)(aa)*(a|b) 即为所求。 二、有穷自动机二、有穷自动机(FA) 自动机：是一种能进行运算，并能实现自我控制的装 置。 装有程序的

29、计算机也具有运算和自我控制能力，因此 计算机是一部自动机 所谓有穷自动机：自动机受囿于它能存储的信息量， 因此是有限的（有穷的） 自动机是识别符号串处理的强有力的工具，因而它成 为研究词法分析器的重要基础。 有穷自动机分为： 确定的有穷自动机（DFA） 非确定的有穷自动机（NFA） 确定的有穷自动机（确定的有穷自动机（DFA） (1) DFA的形式定义：的形式定义：一个DFA M 是一个五元组： M=(S, ,f,S0,F) 其中：S：非空有穷的状态集：每个元素是一个状态。 ：有穷输入字母表；每个元素是输入的一个字符。 f：状态转换函数：是从SS的单值映射函数： f(S1,a)=S2 S0S是

30、唯一的开始状态 F S是终止状态集，可空（识别不出的字符串） 例：设有DFA M=(0,1,2,3,a,b,f,0,3) 其中：f： f(0,a)=1 f(0,b)=2 DFA的函数式表示的函数式表示 f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3 (2) DFA的状态图表示： 开始状态为0，终止状态为3，状态集为0,1,2,3，字 母表为：a,b 一般：假定DFA M含有m个状态，n个输入字符，则状 态图含有m个结点，每个结点最多有n条弧射出。 0 1 2 b b a a a b 3 a,b (3) DFA的矩阵表示： 矩阵的行表示

31、状态，列表示输入字符，矩阵中的元素表 示相应状态行和输入字符列下的新状态。即 K行a 列为 f(K,a)的值。 DFA的功能：的功能： 对于*中的任何字符串,若存在一条从开始结点到某一 终态结点的道路，其路上所有弧的标记符连成的字符串 等于，则称能为DFA所识别（接受）。 特别：若DFA的开始态结点同时又是终态结点，则空串 可为DFA所识别。 状态字符ab 012 132 213 333 注： DFA有3种表示法：函数表示，状态图表示，状态矩阵表 示。 DFA的确定性表现在转换函数f: SS是一个单值函 数。即：对于任何状态sS，和输入符号a,f(s,a)能唯 一确定下一个状态。 可以证明：若

32、存在一个正规文法G，G产生的语言L（G）, 当且仅当存在一个上的确定有穷自动机M，使得L（G） L（M）。 即：正规文法G在上描述的语言，一定存在DFA能够识别 这个语言。反之：若存在一个被DFA识别的语言，一定由 存在的正规文法所描述。 由于DFA能识别正规文法描述的单词，因此要想构造识别 单词的词法分析程序，也就成为怎样构造DFA的问题了。 2. 非确定的有穷自动机（非确定的有穷自动机（NFA） 定义：一个NFA也是一个五元组： M（S，f，S0，F） 其中：S，F同DFA S0 S是一个非空开始状态集 f：是一个多值的转换函数：SS的子集映射 NFA与DFA的区别： vNFA有一个开始状

33、态集，而DFA只有一个开始状态； (1)NFA转换函数是多值函数，DFA的转换函数是单值函 数。 例：设有NFA M（S, ,f,S0,F） 其中，S=q0, q1, q2, q3,=x,y,S0= q0,F= q1 f: f(q0,x)= q1, q2 f(q0,y)= q0 f(q1,x)= q0 f(q1,y)= q1, q2 f(q2,x)= q3 f(q2,y)= q3 f(q3,x)= q1, q3 f(q3,y)= q3 q0 q1 q2 q3 x x y x,y x,y x y x y NFA M的状态图表示： 状态字 符 xy q0 q1, q2 q0 q1 q0 q1 ,q

34、2 q2 q3 q3 q3 q1, q3 q3 NFA M的矩阵表示： v注： DFA是NFA的特例； 对于每个NFA M，存在一个DFA M,使得L(M)=L(M) 对于任何两个有穷自动机M和M，若L(M)=L(M)，则称 M与M等价。 三、由正规式构造三、由正规式构造NFA或将或将NFA转换成正规式转换成正规式 理论依据理论依据 定理：正规式与有穷自动机是等价的。 o 上的NFA M，可以构造上的正规式R，使： L(M)=L(R) o 在上的每个正规式R，可以构造上的NFA M使： L(R)=L(M) 注：由正规式（或正规文法）构造有穷自动机的意义 在于：将单词的描述结构转换为对单词的识别

35、结 构。 由正规式构造NFA 方法：分裂法分裂法 输入：输入：上的正规式R 输出：输出：识别R的NFA 步骤： 1o 引进一个开始状态结点x和终止状态结点y： x R y 2o 若R为复合公式，分裂R直到每条边上只留下一 个符号（可以为）为止； A B 替换成 A C B e2 A B 替换成 A A B 替换成 A e1|e2 e1* B C B e1 e2 e1 e1e2 e1 3o分裂的结果：保证一个唯一的开始状态结点和终止状态结点。 例：设=x,y上的正规式e=xy*(xy|yx)x*,构造一个NFA M，使得L(M)=L(e) 解: x S 分裂 Z xy *(xy|yx)x* S

36、1 y * 3 xy|yx 6 x * Z x S 1 3 Z 2 y 6 xy yx 7 x x S 1 3 Z 2 y 67 x 4 5 x x y y 例：已知正则式e=0(1*)*|01 ，求：NFA (A*)*=A*(A| A*= A*) e=0(1*)*|01 （利用恒式化简，然后构造NFA） =01*|01 = 0(1*|1)= 01* 构造NFA： x y a b 0 1 将NFA转换成正规式 方法：合并法合并法 （与分裂法相反） 输入：NFA M 输出：一个正规式e 步骤： 1o 对于NFA M中的开始状态和终止状态分别新设置一个唯 一的开始状态和终止状态，使所设的开始状态到

37、原开始状 态连接弧；原终止状态到所设的终止状态连接弧。 x y e Z x 1 替换成 S y e s为新增的开始为新增的开始 状态状态 Z为新增的终止为新增的终止 状态状态 2o 利用下列规则进行合并，直到图中只剩下新设置的 开始态和终止态为止。那么在开始态和终止态弧上 的正规式便是所求的结果。 替换成 A B C e2 合并成 A 合并成 A B B C e3 e1 e1 e2 e2 e1 e1e2 A C A B A C e1|e2 e1e2* e3 1 4 2 3 x y y x y x,y x 例：已知NFA如下，求正规式e 1 4 2 3 x y y x y x,y x S Z 1

38、o新设置一个唯一的开始状态和终止状态： 2o按照合并规则进行合并 e=(x|y)*(xy*y| yx*x) 1 4 yx*x x,y S Z xy*y 1 4 x,y S Z xy*y| yx*x S Z (x|y)*(xy*y| yx*x) 四、四、NFA到到DFA的转换（的转换（NFA的确定化）的确定化） 1. 理论依据和目的理论依据和目的 定理：定理：若L为一个能被NFA接受的语言，则存在一 个能接受L的DFA： 即：L(NFA M)=L(DFA M) 目的：目的： 消除消除NFA中中弧弧。 弧会使自动机做无用功。 合并合并NFA中不确定的状态中不确定的状态。不确定状态不 仅给自动机识别

39、字符串带来困难，而且使得编制 相应的词法分析程序变得更为复杂。 NFA到DFA的转换的基本思想基本思想： DFA的每一个状态对应于的每一个状态对应于NFA的一组状态（状态集合）。的一组状态（状态集合）。 方法方法：子集法子集法 2. 子集法子集法 分两种情况介绍分两种情况介绍NFA的确定化： 不含弧的NFA的确定化。 含弧的NFA的确定化 由NFA A=（S, ,f,S0,F）构造DFA A=（S, ,f,q0,F）方法： 1o DFA A的输入字母表与NFA A的完全相同 2o 把NFA A的每一个状态子集作为DFA A的一个状态， 因此该构造方法称为子集法。 3o 设NFA A的任一状态子

40、集r1，r2，, rn, riS(i=1,2,n),令r= r1，r2，, rn,rS。取 a,DFA A的映射函数定义为： f(r,a)=qS 其中，q= q1，q2，, qm,而 q1，q2，, qm =f(r1,a) f(r2,a) f(rm,a)。 4o DFA A的开始状态 q0= S1，S2，, SK ，其中， SiS0(i=1,2,K) 5o DFA A的终止状态F=e|e= e1，e2，, ep, e1， e2，, ep F 具体操作方法： 1o 依据NFA,构造确定化矩阵： 步骤：步骤： 设状态S0是NFA的开始状态，以S0作为DFA的 开始状态，S0 S. 再由f(S0,a

41、)= S1, S2 （a） 若：f(S0,b)= S0 （b） 则：S0状态对于输入字符a,b的映射分别是状态 S1, S2 与 S0。 其中： S1, S2 S是DFA的新状态。 再求新状态 S1, S2对于a,b的映射，设： f ( S1, S2,a)= S0, S3 S f ( S1, S2,b)= S1, S2,S3 S， 即： S0, S3和 S1, S2,S3均为DFA的新状态。 每得到一个新状态，就继续求新状态对a,b的映射， 直到再没有新状态为止。 2o 依据1o求出的确定化矩阵，代换出确定化的 状态转换矩阵。 3o 依据确定化的状态转换矩阵画出状态转换图。 （1）不含弧的NF

42、A的确定化 例:设有NFA 的N=(q0,q1,q2,q3,x,y,f,q0,q1)的状态 转换图如下： 求等价的DFA（见前例） q0 q1 q2 q3 y x x x,y y x x x,y y 解：1o 依据NFA，构造确定化矩阵： 状态输入xy q0q1, q2q0 q1, q2q0, q3q1, q2, q3 q0, q3q1, q2, q3q0, q3 q1, q2, q3q0, q1, q3q1, q2, q3 q0, q1, q3q0, q1, q2, q3q0, q1, q2, q3 q0, q1, q2, q3q0, q1, q2, q3q0, q1, q2, q3 2o

43、依据构造的确定化矩阵，代换成确定化的状态转换 矩阵(用符号重写确定化矩阵) 将确定化矩阵中的q0，q1, q2，q0, q3分别 用符号标记：A1, A2,，A6即可。 状态输入xy A1A2A1 A2A3A4 A3A4A3 A4A5A4 A5A6A6 A6A6A6 3o 依据确定化的转换矩阵画出状态转换图 确定开始状态为：A1(代替q0) 终止状态为：A2，A4，A5，A6（A2，A4，A5，A6 分别代替q1, q2，q1, q2, q3，q0, q1,q3，q0, q1, q2, q3,其中包含NFA中的终止态q1） s y x A5 y x y x A1 A6 x,y y A3 A4

44、A2 x x,y （2）NFA的确定化的确定化（带有空移或空环路的 NFA） 设NFA M=(Q, ,f,Q0,F)，有： 1o状态子集状态子集I的的闭包闭包（记为-closure(I)） vI蕴涵于Q,状态子集I的-closure(I)定义如下： 若状态qI，则q-closure(I); 若状态q-closure(I),q是由q出发经多条弧到 达的状态，则q-closure(I)，显然， -closure(I)蕴涵于Q 例：设有状态转换图如下： 显然，状态集Q=1,2,3,4,5,6,7,8 若子集I=1，则：-closure(I)=1,2 (状态1I, 1-closure(I)； 又从状态

45、1出发经弧可到达状态2 2-closure(I) 若子集I=4，5，则：-closure(I)=2,4,5,6,7,8 1 a 5 2 4 a 6 3 7 8 a 2o状态集合状态集合I的的a弧转换表示为弧转换表示为 f(I,a)=q| f(q,a)=q,qI =J（其中J蕴涵Q） 即：J是由子集I中的状态出发，经过一条a弧 （跳过a弧前的任意条弧）可到达的状态的 集合。 令：Ia=-closure(J) 表示：子集Ia是从子集I中任意状态出发，经a弧（前后可跳过 弧）而到达的状态的集合。 例：上例，若子集I=1,根据定义：子集J=f(1,a)=5,3,4 于是：子集Ia=closure(J)

46、=closure(5,3,4=5,3,4,6,2,8,7 1 ,2 的定义是为了消除空弧或空环。 例：已知NFA M如下图。下面以此为例介绍NFA确 定化过程。 解： 依据NFA的开始状态集S,求-closure(S)=S（汇集S 射出弧的结点集合）作为DFA的开始状态。 不断地按新的非空子集求对输入符号x,y的Ix和Iy，并将新 的Ix或Iy作为DFA的状态。这一过程一直重复到不再出现 新的Ix或Iy为止。 x 3 6 4 5 y x y x S Z 7 2 y 1 x 如：Ix=-closure(1)=1,2,3Iy=-closure()= Ix为非空新子集，作为DFA的状态，且继续以1,

47、2,3求Ix和Iy。 Ix=-closure(1,2,3)=4Iy=-closure(1,2,3)=2,3,5 其中，4和2,3,5作为DFA的结点，且又是新的Ix, Iy, 继续求Ix，ly，过程如下矩阵： IxIy S1,2,3 1,2,342,3,5 46,7,Z 2,3,54,6,7,Z2,3,5 6,7,Z7,Z 4,6,7,Z7,Z6,7,Z 7,Z7,Z v分别：将七种状态集：S，1,2,3,4,2,3,5, 6,7,Z,4,6,7,Z,7,Z用符号q0q6命名得DFA七 种状态矩阵：DFA图如下： 即为所求的DFA。 IxIy q0q1 q1q2q3 q2q4 q3q5q3 q

48、4q6 q5q6q4 q6q6 a 2 3 y b b x 0 1 b a 例：已知NFA（如图），求与之等价的DFA。 解： v求DFA的开始状态（与上例不同） -closure(x)=x,0,1，作为DFA的开始态。 构造确定化矩阵： IaIb x,0,10,2,10,1 0,2,10,2,10,1,3 0,10,2,10,1 0,1,30,2,10,y,1 0,y,10,2,10,1 IaIb ABC BBD CBC DBE EBC v画DFA的图形表示 A E B C b b a a b D b a b a a 五、五、DFA的化简（的化简（DFA的最小化）的最小化） 1. 化简化简D

49、FA的目的的目的 寻找一个状态数比M少的DFA M，使得 L(M)=L(M) DFA的状态少，则依据它编写的词法分析程序 就简单。 2. 化简化简 化简问题： 使化简后的DFA中，没有多余的状态没有多余的状态。 使化简后的DFA中，没有两个是相互等价的没有两个是相互等价的 状态状态。采用分割法。采用分割法。 所谓多余状态：从自动机的开始状态出发，输入 任何的字符串也不能到达的那个状态。 从自动机的开始状态到某个结点 有弧，但该结点无弧通向终止状态。 不可到达的状态对于生成自动机的语言毫无意义。 因此，应该从自动机中删去。 q0 q1 q2 不可到达状态 x y x q y q q x A C

50、D y B 是不可达的状态 B y x v两个状态s和t等价的条件是： 一致性条件：状态s和t必须同时为可接受状态 （终止状态）或不可接受状态（非终止状 态）。 漫延条件：对于所有输入符号，状态s和t必须 转换到等价的状态集里。 如果两个状态不等价，则称这两个状态是可区别的。 自动机中的非终止状态与终止状态是可区别 的（不满足一致性条件） v非终止状态0，2，1，3与终止状态4可区别。不满足 一致性条件。 v状态2与状态3可区别（状态2读入b后到达2;状态3读入b 后到达4，而2和4不等价：即2，3不满足漫延条件）。 注：分割法分割法就是使状态满足漫延条件和一致性条件。关 键：满足漫延条件的分

51、割方法。 0 2 1 b a 3 4 b b b a a DFA a a b 3. 用分割法化简用分割法化简DFA 基本思想：基本思想：将DFA的状态集分成若干个互不相交的子集， 使每个子集中的状态都是等价的，而不同状态子集中的状 态则是不等价的。即是可区分的。 1o 首先，将DFA的状态分成两个子集：终止状态子集和非 终止状态子集。（因为终止状态与非终止状态是可区别 的）。（使状态满足一致性条件） 2o 然后对每个子集进行再分解。分解后的两个状态属于同一 个子集，当且仅当对于任何一个输入字符，它们的映射 属于同一个子集，此过程一直执行到不能再分解为止。 （使状态满足漫延条件） 3o 将分解的

52、每个子集作为化简后的DFA的每一个状态。且 含有原来开始状态的子集和含有原来终止状态的子集分 别作为开始状态和终止状态。 具体DFA的化简过程。 例：已知有DFA图如下，化简DFA： 解： 1o将所有终止状态归为一个子集S1=q1, q3, q4, q5; 其余非终止状态归为另一个子集：S2= q0, q2 x q4 y y x y x q0 q5 x,y y q3 q1 x x,y q2 2o 按可区别性分解子集S1和S2 v 分解S1：f(q1,x)= q2S2 f(q3,x)= q4S1 f(q4,x)= q5S1 f(q5,x)= q5S1 (也可对y字符进行) 将S1分解成两个子集S

53、1= q1, S2= q3, q4, q5 v 分解S2： f(q0,x)= q1S1 f(q2,x)= q3S2 将S2分解成两个子集 q0, q2 最后分解成4个子集： q1, q3, q4, q5, q0,q2分别 用q1, q3, q0, q2来替换成4个子集的状态名。 DFA的化简：的化简： x q4 y y x y x q0 q5 x,y y q3 q1 x x,y q2 a y q2 q3 x q0 y y x q1 x,y 用状态矩阵形式辅助完成化简用状态矩阵形式辅助完成化简 x q0q1 q1q2 q2q3 q3q4 q4q5 q5q5 分解：分解：S1=q0, q2,S2=

54、q1,q3,q4,q5 对对x，S2分解：分解：S21=q1,S22=q3,q4,q5 对对x， s1分解：分解：S12=q0,s12=q2 , S22对对x或或y不能分解。不能分解。 最后得到分解：最后得到分解：q0,q1,q2,q3,q4,q5 例：将DFA（如下图）最小化。 解： 1o 将终止态与非终止态的结点分为2个子 集： =(A,B,C,D,E)(其中S0= A,B,C,D ,S1= E ) A E B C b b a a b D b a b a a 0 20 分解子集： S0 A,B,C,D 对a： 对b： f(A ,a)=B S0写成A,B,C,Da=B B包含在A,B,C,D

55、中, A,B,C,D对a不被分 裂 f(B, a)=B S0 f(C, a)=B S0 f(D, a)=B S0 f(A ,b)=C S0 写成A,B,C,Db=C,D,E C,D,E既不包含在A,B,C,D 中，又 不包含在E中， A,B,C,D对b要被分裂。 f(B, b)=DS0 f(C, b)=CS0 f(D, b)=ES1 =(A,B,C,D,E)(若令S2= A,B,C，S3=D ,S4= E ) 再分解：A,B,C 对a： 对b： f(A ,a)=B S2写成A,B,Ca=B B包含在A,B,C中, A,B,C对a不被分裂f(B, a)=B S2 f(C, a)=B S2 f(A

56、 ,b)=C S2 写成A,B,Cb=C,D C,D既不包含在A,B,C 中，又不包含在D中， A,B,C对b要被分裂。 f(B, b)=DS3 f(C, b)=CS2 1 A E B a D b a b a b a b （A,C,B,D,E） 再分解： A,C A,C a=B (B包含在B中,对a,A,C 不被分裂) A,C b=C (C包含在A,C中，对b, A,C不被分裂) 结论：A,C状态等价。整个分解终止。 =（A,C,B,D,E） DFA最小化为：最小化为： 2 3 IaIb ABC BBD CBC DBE EBC 注：注：可通过DFA确定化矩阵，应用 状态满足漫延条件和一致性条件

57、， 直接得出等价的状态。 如：上面的确定化矩阵，Bb=D, Db=E,而E,D不等价，导致B,D 不等价，所以，D和B要分裂。 例：已知正规式R=l(l|d)*,求最小DFA 解：步骤： 1o 求求DFA R = NFA = DFA =DFA 分裂法子集法分割法 最小 x y 1 2 l d 分裂： x y l(l|d) * l 2o 求求DFA 子集法：构造确定化的矩阵 IlId x1,2,y 1,2,y 2,y2,y 2,y2,y2,y IlId AB BCC CCC d A C B l l d l 3o 最小化最小化DFA 分割法：首先将DFA分解成两个子集： =(A,B,C) B,C不

58、能分解： 对l： 对d： B,C等价：去掉C 最小化DFA： 注：实现时，扩充为： 且规定：字符串的长度为n, f(B ,l)=C写成B,C l=C f(C, l)=C f(B ,d)=C写成 B,Cd=C f(C, d)=C d A B l l 0 六、由最小化的六、由最小化的DFA到词法分析程序的构造到词法分析程序的构造 若指明DFA的每一个状态要完成的任务 再把从状态0出发的弧上所标记的输入字符视为控制条件 则：DFA实际上就是一个程序流程图。 例：上例最小化DFA： 要识别一个标识符是否结束，必须读到该标识符后继 字符是分界符（或非l,d）因此，实现时，将标识符DFA 作适当修改： A

59、 Z 非l,d l B l，d v如果赋予状态A,B,Z一定的操作，则DFA变为 识别标识符程序的框图。 Char ch,nameK Name= Read(ch) A Name=name+ch Read(ch) 用name查符号表， 若没有，则填表， 否则返回地址 若ch=l 非l,d 若ch=l or d B Z 4.正规文法与有穷自动机之间的转换正规文法与有穷自动机之间的转换 一、正规文法到有穷自动机的转换 分别就左,右线性文法到有穷自动机的转换 1.右线性文法到有穷自动机的转换 设给定右线性文法G=(VN, VT,P,S),则相应的有穷 自动机M=(Q, ,f,q0,Z). 转换方法：

60、(1)将VN中每一个非终结符视作M1中的一个状态，并 增加一个终结状态D, D VN ,令Q=VND,Z=D, =VT, q0=S,f函数构造如下： (2)对G中每一形如:A = aB的产生式(A,B VN,a VT ),令f(A,a)=B; (3)对G中每一形如:A = a的产生式(A VN, a VT), 令f(A,a)=D; (注意：D是终结状态) (4)对G中每一形如:A =的产生式(AVN),令 f(A,)=D; 显然，这样构造的M是具有一个开始状态的NFA。 例：构造下列右线性文法GZ的有穷自动机。 Z = 0A A = 0A|0B B = 1A|1 则构造等价自动机M=(Z,A,