词法分析及词法分析程序

1、12词法分析程序设计的流程1、各类单词表示成不同的正规文法Gi2、求正规文法Gi对应的正规表达式3、由各个正规表达式构造对应的-NFA4、由各个-NFA组合成一个大的-NFA5、大的-NFA确定化、最小化得到DFA M6、DFA M就是构造词法分析程序的流程图7、按照DFA M编写词法分析程序3主要内容3.1 3.2 3.3 3.4 3.5 4词法分析的任务词法分析的任务 扫描输入串中的字符，从中识别出具有独立意义的基本扫描输入串中的字符，从中识别出具有独立意义的基本语法单位：单词，生成单词序列。语法单位：单词，生成单词序列。 剥去源程序中的注释（块、行）和剥去源程序中的注释（块、行）和“空白

2、空白”符符 预处理预处理宏处理与文件包含宏处理与文件包含词法分析程序亦称为扫描器设计和实现扫描器的相关问题： 描述语言中各种单词的结构：描述语言中各种单词的结构：3型文法及其正规式型文法及其正规式 识别源程序中的各个单词：状态转换图或有限自动机识别源程序中的各个单词：状态转换图或有限自动机5扫描器的功能词法分析器语法分析器get_next_token编译器其它阶段符号表高级语言源程序字符流token单词（流）6程序语言的单词（1）单词词文模式关键字WHILEwhilewhileFORforfor标识符IDtemp, i,max字母开头的字母数字串常数NUM3.14100数字串.数字串单词：同类

3、词文的总称词文：源程序中能匹配某一记号的字符串模式：描述用字符串构成单词的规则7程序语言的单词（2）单词词文模式运算符MUL*GT界符,串常量STRING“hello”there双（单）引号中间的字符串（不包括引号本身）83.1 3.1.1 词法分析的两种处理方式n将词法分析纳入到语法分析中进行将词法分析纳入到语法分析中进行n词法分析与语法分析分开来进行词法分析与语法分析分开来进行描述单词结构比描述语法结构简单，仅用描述单词结构比描述语法结构简单，仅用3 3型文法就够了；型文法就够了；将单词识别从语法分析中分离出来，可采用更有效的工将单词识别从语法分析中分离出来，可采用更有效的工具（状态转移图

4、、有限自动机等）实现；具（状态转移图、有限自动机等）实现；有些语言（如有些语言（如FORTRANFORTRAN）的单词识别与前后文相关，将词）的单词识别与前后文相关，将词法分析独立出来，有利于实现统一的语法分析；法分析独立出来，有利于实现统一的语法分析；使编译程序各部分独立出来，有利于设计、调试和维护使编译程序各部分独立出来，有利于设计、调试和维护n逻辑上的划分，不是指编译程序的执行流程逻辑上的划分，不是指编译程序的执行流程9n词法分析作为单独的一遍（词法分析作为单独的一遍（多遍扫描多遍扫描） 大部分编译时间花在扫描字符上，独立出来便于集大部分编译时间花在扫描字符上，独立出来便于集中处理中处理

5、. . 单词的词法规则简单，可建立特别适用于这种文法单词的词法规则简单，可建立特别适用于这种文法的有效技术，实现词法分析的自动生成的有效技术，实现词法分析的自动生成. . 整个编译程序结构简单，清晰，产生中间文件，占整个编译程序结构简单，清晰，产生中间文件，占内存内存. .n词法分析作为一个独立的子程序，供语法分析程序调词法分析作为一个独立的子程序，供语法分析程序调用用 （单遍扫描单遍扫描） 语法分析调用时，返回一个单词符号语法分析调用时，返回一个单词符号. . 无中间文件，省内存，编译效率高无中间文件，省内存，编译效率高. . 两种具体的实现方式两种具体的实现方式103.1.2 3.1.2

6、单词符号的内部表示单词符号的内部表示 词法分析器的输出形式词法分析器的输出形式(1) (1) 单词符号的种类单词符号的种类 保留字保留字：如：如beginbegin，end,doend,do等用户不能使用等用户不能使用 标识符标识符：由用户定义：由用户定义 无符号整数无符号整数：如：如124124 单字符分界符单字符分界符：+ +，* *，/ / ，；， （ ，），： 双字符分界符双字符分界符：/，/ /* *，* */ /，: := =等等11 (2)(2)单词符号的表示形式单词符号的表示形式二元组二元组 二元组：（单词类别，单词自身值）二元组：（单词类别，单词自身值） 单词类别单词类别：说

7、明单词属于哪一类，常用助记符或：说明单词属于哪一类，常用助记符或 整数编码表示整数编码表示. . 例：标识符用例：标识符用4 4 表示表示 + + 用用8 8表示表示 * * 用用1010表示表示单词自身值单词自身值 一种类只有一个单词，不必给出单词自身值一种类只有一个单词，不必给出单词自身值. .因为因为 根据类别编码能完全确定根据类别编码能完全确定. . 一种类含有多个单词，必须给出单词自身值予以一种类含有多个单词，必须给出单词自身值予以 区别。区别。12 一般：一般： 保留字、运算符和分界符都是一个符号一保留字、运算符和分界符都是一个符号一种类别，不需单词自身值种类别，不需单词自身值.

8、. 如如 + + 类别类别8, 8, + + 的二元组的二元组 （8 8，- -） 标识符整体作为一个类别,其单词自身值采用自身的字符串编码表示. 如标识符类别为如标识符类别为5 5，ABAB的二元组的二元组(5(5，ABAB） 常数按类型分类别：单词自身值采用自身常数按类型分类别：单词自身值采用自身 的的二进制二进制形式形式. . 如整数类别为如整数类别为2020，整数，整数4 4的二元组的二元组(20(20，100100）133.1.3 3.1.3 识别标识符的若干约定和策略识别标识符的若干约定和策略n约定：约定：(1)(1)标识符中的字符个数超过最大允许长度，截去尾部标识符中的字符个数超

9、过最大允许长度，截去尾部. .(2)(2)不超过最大长度的标识符，则按不超过最大长度的标识符，则按“尽可能长尽可能长”的原的原则匹配则匹配. .如：如果标识符最大长度为如：如果标识符最大长度为6,6,则则identifieridentifier识别为识别为identiidenti，而不是，而不是identifier;identifier; 而而NO23ANO23A可识别出可识别出NO23ANO23A标识符标识符, ,而不是而不是NONO、2323和和A A14n禁止关键字作为标识符的前缀的语言系统（如禁止关键字作为标识符的前缀的语言系统（如标准标准FORTRANFORTRAN和和PASCALP

10、ASCAL） DO10I会识别为DO 10 I，而不是将之识别为一个标识符。n若允许关键字作为标识符的前缀（非标准若允许关键字作为标识符的前缀（非标准FORTRANFORTRAN） DO99K=1DO99K=1, ,10 DO10 DO循环语句循环语句 DO99K=1DO99K=1. .10 10 变量赋值变量赋值 IF(5IF(5.EQ.EQ.M)X=5 IFM)X=5 IF语句语句 IF(5)IF(5)= =55 55 函数赋值函数赋值15单词符号的识别单词符号的识别超前扫描技术超前扫描技术n超前扫描技术：在无法判别和识别当前单词时，先向超前扫描技术：在无法判别和识别当前单词时，先向前扫描

11、若干个字符，直到可以进行判断和识别为止。前扫描若干个字符，直到可以进行判断和识别为止。n嵌套括号的分层 由外向内编号：第一层，第二层，n语句内容的分层 按包含它的括号层次确定 不被括号包含的语句内容称为属于第零层 不被括号包含的等号和逗号分别称为零层等号和零层逗号n利用超前扫描到的零层等号和零层逗号来识别单词符号16超前扫描技术示例超前扫描技术示例 DO99K=1DO99K=1, ,10 DO10 DO循环语句循环语句 DO99K=1DO99K=1. .10 10 变量赋值变量赋值 IF(5IF(5.EQ.EQ.M)X=5 IFM)X=5 IF语句语句 IF(5)IF(5)= =55 55 函

12、数赋值函数赋值n包含零层等号的语句：赋值语句、包含零层等号的语句：赋值语句、DODO语句、函数定语句、函数定义语句以及某些逻辑义语句以及某些逻辑IFIF语句语句n既包含零层等号，也包含零层逗号的语句：既包含零层等号，也包含零层逗号的语句：DODO语句语句n如，函数或数组赋值语句如，函数或数组赋值语句 f(a1,a2,an)=ef(a1,a2,an)=e函数语句：函数语句： f f不出现在数组说明符中不出现在数组说明符中数组赋值语句：数组赋值语句： f f出现在数组说明符中出现在数组说明符中n再如，扫描到字符再如，扫描到字符,还需继续向前扫描还需继续向前扫描,（左移）（左移）,=,=,=,=（复

13、合赋值）（复合赋值）17回退字符n在超前扫描结束后，还要“回退”字符，即将超前扫描的字符退回输入缓冲区。n实现回退的数据结构：堆栈 回退：将要回退的字符依次压入堆栈。 扫描：检查堆栈是否为空，如果不为空，则从栈顶读取后续字符，否则从输入字符串读取。n书中 程序给出了使用堆栈实现多字符回退的算法。183.1.4 3.1.4 源程序的输入及预处理源程序的输入及预处理 n缓冲输入：将磁盘上的源程序分批送入缓冲缓冲输入：将磁盘上的源程序分批送入缓冲区，等待扫描器处理。可以提高读盘效率和区，等待扫描器处理。可以提高读盘效率和方便扫描器工作。方便扫描器工作。n输入系统：一组完成源程序输入的函数或者输入系统

14、：一组完成源程序输入的函数或者子程序，支持读盘、超前搜索、多字符回退子程序，支持读盘、超前搜索、多字符回退等操作等操作nLexLex中的扫描缓冲区实例：中的扫描缓冲区实例：P46,P46,图图3-23-2n预处理预处理: :消除无用空白、回车、换行、制表、消除无用空白、回车、换行、制表、注释、区分标号区、续行号（注释、区分标号区、续行号（FORTRANFORTRAN）等）等. .1920n程序设计语言的单词都能用正规文法描述，例如，标识符可定义为：n若把字母、数字视为终结符，则上述产生式为左线性文法，是正规文法。n若我们用d表示0-9间的数字，则C语言的的文法是右线性文法，也是正规文法（见P4

15、8）21由一组矢线连接的有限个结点所组成的有向图。每个结点代表在识别分析过程中扫描器所处的状态，其中含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。状态之间可用有向边连接，其上标记一字符a，表示从有向边的射出状态出发，识别一字符a后，将进入箭头所指状态（结点）n凡能用正规文法描述的语言，均可由某种有限状态算法进行分析。22设设G=(VN,VT,P,S)是一右线性文法，并设是一右线性文法，并设|VN|=k,则所要构造的状态转换图共有则所要构造的状态转换图共有k+1个状态个状态(结结点点)。用。用VN中的每个符号分别标记其中的中的每个符号分别标记其中的k个个结点，且令结点

16、，且令G的开始符的开始符S为初态结点；余下为初态结点；余下的一个结点作为终态结点，用的一个结点作为终态结点，用F( VN)标记。标记。23A状态转换图的构造原则状态转换图的构造原则G G的每一个非终结符号代表一结点的每一个非终结符号代表一结点( (状态状态) ) 开始符号开始符号S S作为初始状态作为初始状态 设一符号设一符号F F不属于不属于V V作为终止状态作为终止状态 形如形如AaBAaB的规则的规则 a a 形如形如AaAa的规则的规则 a a 特别特别:A :A 未曾在未曾在A A的射出弧中的射出弧中 出现过的终结符号出现过的终结符号 某些情况下也可考虑直接将某些情况下也可考虑直接将

17、A A作为终态作为终态BSFBAAFAFA24例例:GZ:GZ:Z0UZ0U 1V1VU 1ZU 1Z 1 1V 0ZV 0Z 0 0 25例例:GZ: :GZ: 状态转换图状态转换图:Z0UZ0U 1V1VU 1ZU 1Z 1 1 1 V 0ZV 0Z 0 0 0 1 初态初态 1 0 0 ZUVF26无符号数文法举例0. d | | d1. d | | E | | d2. E | d | d 3. d | d 4. d | + | - | d 5. d | d6. d | d d表示09之间的数字27无符号数文法对应的状态转换图无符号数文法对应的状态转换图n例如,P48中定义的无符号数的文

18、法对应的状态转换图为(化简后):n可识别的无符号数形式：0453126d.dddd.E+|-Edd28对于已给的字符串对于已给的字符串w=a1a2an,ai VT,利用状态转换图利用状态转换图对对w 识别的步骤如下识别的步骤如下:(1)从初始状态从初始状态S出发出发,自左至右逐个扫描自左至右逐个扫描w的各个字符的各个字符(当前为当前为a1),此时在结点此时在结点S所射出的诸矢线中所射出的诸矢线中,寻找标寻找标记为记为a1的矢线的矢线(若不存在若不存在,则表明则表明w有语法错误有语法错误),读入读入a1并沿矢线所指方向前进并沿矢线所指方向前进,过渡到下一状态过渡到下一状态(设为设为A1).(2)

19、设当前处在设当前处在Ai状态状态,所扫描的字符为所扫描的字符为ai+1,在结点在结点Ai所所射出的诸矢线中射出的诸矢线中,寻找标记为寻找标记为ai+1的矢线的矢线(若不存在若不存在,则则表明表明w有语法错误有语法错误),读入读入ai+1,并进入状态并进入状态Ai+1;(3)重复重复(2),直到直到w中所有字符被读完且恰好进入终态中所有字符被读完且恰好进入终态F时时,宣告整个识别结束宣告整个识别结束,w可被接受可被接受.29例例:GZ: :GZ: 状态转换图状态转换图:Z0UZ0U 1V1VU 1ZU 1Z 1 1 1 V 0ZV 0Z 0 0 0 1 初态初态 1 0 0 1 1=011001

20、=0110012 2=111001=111001ZUVF30n显然显然, ,若从若从初态初态出发出发, ,分别沿分别沿一切可能一切可能的的路径路径到达到达终态终态结点结点, ,并将路径中并将路径中矢线上所标记的字符矢线上所标记的字符依次连接起来依次连接起来, ,便得到便得到状态转换图状态转换图所能识别的所能识别的全部符号串全部符号串, ,这些符号串这些符号串组成的集合构成了该组成的集合构成了该识别的语言。识别的语言。31状态转换图与文法推导状态转换图与文法推导n用状态转换图识别符号串w w的过程，就是为w w建立一个推导S S* * w w的过程。n在第一步（在初始状态S S下，扫描到a a1

21、 1而过渡到下一状态A A1 1），由状态转换图的构造规则可知，GG中必有产生式S Sa a1 1A A1 1;n对于识别过程的后续步骤，由状态A Ai i 识别a ai+1i+1后过渡到A Ai+1i+1恰好对应了使用产生式A Ai i a ai+1i+1A Ai+1 i+1 。n最后在状态A An-1n-1识别a an n后到达终态F F，对应了使用产生式A A a an n。n整个推导过程：S S a a1 1A A1 1 a a1 1a a2 2A A2 2 a a1 1a a2 2aan-1n-1A An-1n-1 a a1 1a a2 2aan n32例例:GZ: :GZ: 状态转

22、换图状态转换图:Z0UZ0U 1V1VU 1ZU 1Z 1 1 1 V 0ZV 0Z 0 0 0 1 初态初态 1 0 0 例例: =011001: =011001通过状态图可以确定通过状态图可以确定是文法的句子是文法的句子. .此过程是一种推导过程此过程是一种推导过程. .Z=0U=01Z=011V=0110Z=01100U=011001Z=0U=01Z=011V=0110Z=01100U=011001ZUVF33 设设 是一是一,是相应的是相应的,则从前面的讨则从前面的讨论可以看出如下事实：论可以看出如下事实：(1)在利用在利用对符号串对符号串 进行识别时进行识别时,中每次状态的转换都模拟

23、了一中每次状态的转换都模拟了一步直接推导步直接推导,即识别方法即识别方法(或称分析方法或称分析方法) 是是“ ”的的;(2)因因右线性文法右线性文法只有形如只有形如的产生式，所以推导的每一的产生式，所以推导的每一步所得句型只含一个非终结符，且必出现在句型的最右端，所以步所得句型只含一个非终结符，且必出现在句型的最右端，所以推导是推导是规范推导规范推导，每步所得的句型也必为，每步所得的句型也必为规范句型规范句型；(3)对于对于所识别的任一符号串所识别的任一符号串 ,必存在必存在G中的一个推导中的一个推导 (即有即有反之反之,对于对于中任一句子中任一句子 ,必存在一条从初态必存在一条从初态 到终态

24、到终态的路径的路径,此路径上各矢线的标记依次拼接起来所组成的符号串恰为此路径上各矢线的标记依次拼接起来所组成的符号串恰为34n设是一左线性文法,构造相应的状态转换图的方法是: 首先用中的非终结符标记M的结点，其中，开始符对应的结点为终态结点。引入一个新结点标记初态。矢线的连接规则为:(1)对于 中形如 的产生式，引矢线且标记为 ；(2)对于G中形如 的产生式，引矢，且标记为 。35已给文法已给文法G=(S,U,0,1,SS1 |U1, UU0 | 0,S)36例例:GZ:GZ:ZU0ZU0 V1V1U Z1U Z1 1 1V Z0V Z0 0 0状态转换图状态转换图: 0初态初态 1 1 0

25、0 1RUVZ(2)(2)状态转换图的使用状态转换图的使用 识别句子识别句子( (单词符号单词符号) )例例:100110:100110通过状态图可通过状态图可以确定是文法的句子以确定是文法的句子. . 识别过程对应着归约识别过程对应着归约过程过程 1 10011000110 U0U001100110 Z0Z0110110 V1V11010 Z1Z10 0 U0U0 Z Z37n由构造状态转换图的方法可知,从初态从初态到下一状态到下一状态A A的转换的转换, ,对应了形如对应了形如 的产生式的产生式,即将终结符 归约成非终结符A A;n从状态B B转换到状态 ,对应了形如对应了形如的产生式的产

26、生式,即将归约为 ;n如此下去,直到从某状态 转换到状态(终态),对应了形如对应了形如的产生式的产生式,即将归约为开始符 .此时归约成功,也恰好进入了终态,即状态转换图识别了(或接受)该符号串.n前面识别的例子对应的归约过程见右图38n状态转换图状态转换图可方便地用于识别单词.但是,如何让计算机利用状态转换图来进行词法分析呢?n一个简单实用的方法就是将图以矩阵的形式保存在内存中.这就是所谓的状态矩阵法状态矩阵法.n状态矩阵状态矩阵 以图中各个状态为行,以各个输入符号为列,组成一个矩阵 ,其元素指明扫描器此时应完成的语义动作和要转换到的下一状态.其含义是,在状态下,扫描到 符时,按序偶查矩阵 ,

27、扫描器根据的指示,先执行相应的语义动作,再转换到下个状态.n若为“”,则说明输入符号串有误,拒绝接受.扫描器将调用出错处理程序进行处理39 CurStat=0;FlagOfFS=NoneSeen; if(CurChar=EOF) return 0;while (CurChar != EOF) if(Stat=TransMatCurStatCurChar!=NULL) CurStat=Stat; advance( ); if( CurStat 是终态是终态) FlagOfFS=HasSeen; / 记下输入串中当前位置及该状态相关联的动作记下输入串中当前位置及该状态相关联的动作; 40 else

28、 if(FlagOfFS=NoneSeen) 报告词法错误报告词法错误; 略过当前词文及输入字符略过当前词文及输入字符; CurStat=0; else 回退到最近经历的那个终态的输入字符位置回退到最近经历的那个终态的输入字符位置; 执行所记录的该终态的相关动作执行所记录的该终态的相关动作; / 41贪心策略n目的是获得最长匹配单词（1）若当前状态对输入符号有后继动作，则继续进行状态转移；（2）若当前状态为终态，记下该状态和当前输入字符的位置，并继续向前扫描；（3）若当前状态已无后继状态，并且此前经历过终态，则执行曾经历的最近的终态所对应的语义动作；（4）若当前状态已无后继状态，并且此前没有经

29、历过终态，则表明输入字符串有词法错误，报错，并略过余下的部分词文，从状态0开始继续下一单词的识别。n状态矩阵是稀疏的，应该采用紧凑的数据结构42识别无符号数识别无符号数n功能：把识别出的无符号数转换成整数（n无符号数的输入形式：可改写为可改写为n用分别计录尾数、指数、小数位及指数的符号。因此数值为： n语义加工过程：初值为0， 初值为1； 处理整数部分时，对于每个 处理小数部分时，对于每个 处理指数时， 后若有 号，令；计算指数值 在出口处，令43无符号数无符号数当 前 状态扫 描 字 符语 义 处 理 操 作 或 接 受 动 作后 继 状态dw =0;n=0;p=0;e=1;w =w *10

30、+d1.w =0;n=0;p=0;e=1;30thererrordw =w *10+d;1.2E41otherreturn ( IC O N = w );enddn+; w =w *10+d;2E42otherreturn (FC O N =w *pow (10,e*p-n) ) ;enddn+;w =w *10+d;23othererrordp=p*10+d;6+5-e=-1;54othererrordp=p*10+d;65othererrordp=p*10+d;66otherreturn (FC O N =w *pow (10,e*p-n) );end44状态转换图实际上是有限自动机的图形

31、表示453.3.1 确定的有限自动机DFAn抽象地看抽象地看, ,状态转换图状态转换图由五个部分组成由五个部分组成: :(1)(1)有限个状态之集有限个状态之集, ,记作记作K K; ;(2)(2)有限个输入符号组成的字母表有限个输入符号组成的字母表, ,记作记作 ; ;(3)(3)从从K K到到K K的的转换函数转换函数 f: Kf: KK. f(p,a)=qK. f(p,a)=q表示若表示若当前状态为当前状态为p p, ,且输入符号为且输入符号为a a, ,则进入下一个状态为则进入下一个状态为q q; ;(4)(4)S S0 0 K K, ,初始初始( (开始开始) )状态状态; ;(5)

32、(5)若干个终态之集若干个终态之集: : Z(Z( K)K)由上述五个要素组成的五元式由上述五个要素组成的五元式 M=(K, M=(K, , f,S, f,S0 0,Z ),Z )称为称为一个一个确定的有限自动机确定的有限自动机 ( (DFADFA: : D Deterministic eterministic F Finite inite A Automatautomata) )由此可见由此可见, ,DFADFA实际上是状态转换图的形式描述实际上是状态转换图的形式描述( (数学定数学定义义),),状态转换图是状态转换图是DFADFA的几何的几何( (图形图形) )表示表示. .46ZUVF2

33、=1001已知已知DFA M=(K, , f,S0,Z )，其中：，其中：K=Z，U，V，F， =0，1，S0=Z，Z=Ff(Z,0)=U,f(Z,1)=V,f(U,0)=Z,f(U,1)=F,f(V,0)=Zf(V,1)=F状态转换图状态转换图: :1=0010010初态初态011103=11100147nDFA M的接受集 我们把一DFA M所接受的符号串的全体称为M的接受集或M接受的语言，记为L(M),即 L(M)= x | f(S0,x) Z,x* nM接受(或识别)某符号串x*：从初态S0出发,经一恰好标有x 的路径后可达到某终态S Z 。用f描述就是: S Z, f(S0,x)=S

34、 n将转换函数f 的定义域拓广到K* ，可以得到 f: (1) f (s, )=s, s K; (2) f (s,aw)=f ( f(s,a),w), s K,a,w*;n对于x* , f(s,x)=t 的含义是,当M从状态s出发,依次扫描完x的各个符号后将进入状态t.n只要f有定义, f与f的效果是一致的，以后不再区分。48转换函数转换函数 f: Kf: KK. K. f(p,a)=qf(p,a)=q表示若当前状态为表示若当前状态为p,p,且输入符号且输入符号为为a,a,则进入下一个状态为则进入下一个状态为q;q;把把f f拓广到拓广到f:f:f(p,f(p,x)=q)=q若若x=abcd=

35、abcdf(p,a)=p1,f(p1,b)=p2,f(p,a)=p1,f(p1,b)=p2,f(p,f(p,x)=f(f(p,a),bcd.)=f(f(p,a),bcd.)49n确定的FA：在状态转换的每一步，根据FA当前的状态及扫描的输入字符，便能唯一地唯一地确定FA的下一状态。在转换图上看，若|=n，则任何结点所引出的矢线至多有n条，且矢线上的标记均不同。n例如，P51图3-4所对应的DFA为 M=(R,U,S,0,1,f,R,S) 其中，f的定义如下：f(R,0)=Uf(U,0)=Uf(U,1)=Sf(S,1)=Sn由DFA与状态转换图的关系可知，构造状态转换图的算法，同样适用于构造DF

36、A。n可以证明， 正规文法G， DFA M，使L(M)=L(G)，反之亦然。50 在相应的状态转换图中，在相应的状态转换图中，就会出现这样的结点就会出现这样的结点U，它具有多条标记为同一它具有多条标记为同一输入符号输入符号a的矢线的矢线在在U状态下，输入符号为状态下，输入符号为a时，时，FA的下一状态不唯一，而的下一状态不唯一，而是在状态集是在状态集A,B,C,X中任选其一。具有这种性质的中任选其一。具有这种性质的FA称为非确定的称为非确定的FA（NFA: Nondeterministic FA）51nNFA M 也可用五元式定义：M=(K,f,S0,Z)，其中，K, ,S0,Z的含义同DFA

37、,转换函数f的定义为 f: K(K),即将(Si,aj)映射到K的一个子集Sk1,Skm n类似地，我们可把f的定义域拓广到K* ： (1) f(S,)=S; (2) f(S,aw)=f(f(S,a),w) a,w*.52n所有为所有为NFANFA M M所接受的符号串之集称为所接受的符号串之集称为NFA MNFA M的接受的接受集（或识别集），记作集（或识别集），记作 L(M).L(M).即即 L(M) L(M)=x x| |f f（S S0 0,x,x） Z Z , x, x* * nx x* * 为为M M所接受：集合所接受：集合f(Sf(S0 0,x),x)中含有中含有Z Z中的元素中

38、的元素（终态），即至少存在一条从初态（终态），即至少存在一条从初态S S0 0到某一终态的路到某一终态的路径，此路径上的符号之连接恰为径，此路径上的符号之连接恰为x x。例例3.13.1 给定给定M=(S,A,B,C, M=(S,A,B,C, a,b,f,S,C),a,b,f,S,C),其状态转其状态转换图见右。由图可知换图见右。由图可知M M是一是一NFANFA。53识别符号串识别符号串ababbababb的路径的路径 注意注意，NFANFA识别输入符号串时有一个试探过程，为了能识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（走到终态，往往要走许多弯路（带回溯带回溯），这影

39、响了），这影响了FAFA的效率。的效率。n符号串符号串ababbababb的识别路径的识别路径S(S(a a) )A(A(b b) )B(B(a a) )A(A(b b) )B(B(b b) )C C( (接受接受) )。 ( (参见书中参见书中P60P60) )543.3.3 n可将可将DFA看作看作NFA的特殊情况的特殊情况,即即DFA所接受所接受的语言类包含在的语言类包含在NFA所接受的语言类中。因所接受的语言类中。因此，要证明此，要证明NFA与与DFA的等价性，只需证明的等价性，只需证明每一个每一个NFA都可以确定化。都可以确定化。n确定化：对任意确定化：对任意NFA M，构造一个，构

40、造一个DFA M，使得使得L(M)=L(M)。n思路：令思路：令M的某个状态与的某个状态与M的某个状态子集的某个状态子集相对应，并使得在相对应，并使得在M扫描与扫描与M相同的输入符相同的输入符号时，保持对号时，保持对M的状态进行跟踪（能根据的状态进行跟踪（能根据M的状态确定的状态确定M的状态）。的状态）。55证明 对于字母表对于字母表 上的任一上的任一NFA M，必存，必存在与在与M等价的等价的DFA M 。 设设 M=(K,M=(K, ,f,S,f,S0 0,Z),Z) 是是 上的上的NFANFA，现构造，现构造 上上DFADFA M M=（K, , ,f,S0,Z).方法如下：方法如下：1

41、.1.K= (K).为表示方便为表示方便,如如K某子集为某子集为S1,S2,Si,记相应的状态为记相应的状态为S1,S2,Si.特别地特别地,令令S0=S0.2.映射映射f的定义的定义: f(S1,S2,Si,a)=R1,R2,Rj iff f(S1,S2,Si,a)=R1,R2,Rj3.M的终态集的终态集Z=Sp,Sq,Sr|Sp,Sq,Sr K并且并且Sp,Sq,Sr Z56现在现在,证明证明M与与M等价的等价性等价的等价性.为此为此,对输入符号串对输入符号串|x|=n的长度进行的长度进行归纳归纳,以证明如下论断以证明如下论断: f(S0,x)= S1,S2,Si f(S0,x)=S1,S

42、2,Si (S0=S0)当当|x|=0 (即即x= )时时,由于总有由于总有 f(S0, )=S0, f(S0, )=S0 ,即即f(S0, )=S0,故论断成立故论断成立.设对于长度小于或等于设对于长度小于或等于m的任何输入串的任何输入串x论断均成立论断均成立,即即f(S0,x)=S1,S2,Sif(S0,x)=S1,S2,Si现证明对于输入串现证明对于输入串xa,其中其中,|x|=m,a 论断也成立论断也成立,即即 f(S0,xa)=R1,R2,Rj f(S0,xa)=R1,R2,Rj57f(S0,xa)= f(f(S0,x),a)=f(S1,S2,Si,a) =R1,R2,Rjf(S0,

43、xa)=f(f(S0,x),a)=f(S1,Si,a) (归纳假设归纳假设) =R1,Rj (f的构造定义的构造定义) 最后最后,若若 f(S0,x) Z 及由及由Z的定义的定义,f(S0,x) Z.即即 x L(M) x L(M) 得证。由于得证。由于NFA与与DFA是等价的是等价的,今后统称今后统称FA. 还应指出，确定化时所得的还应指出，确定化时所得的DFA的状态数是很大的，的状态数是很大的，往往有许多无用状态（往往有许多无用状态（即那些从初态即那些从初态S0不可达的状态不可达的状态或那些从其出发不能到达终态的状态或那些从其出发不能到达终态的状态），这些状态可），这些状态可从从DFA中删

44、除。中删除。58例例3.23.2 M=(S0,S1,a,b,f,S0,S1)构造构造M的的DFA M=(K,a,b,f,S0,Z), 其中其中 K=S0,S1,S0,S1, f(S0,a)=S0,S1 f(S0,b)=S1f(S1,a)= f(S1,b)=S0,S1因为因为 f(S0,S1,a)= f(S0,a) f(S1,a)= S0,S1 f(S0,S1,b)= f(S0,b) f(S1,b)= S0,S1所以所以 f(S0,S1,a)= f(S0,S1,b)=S0,S1_f_|_a_ b_S0 |S0,S1 S1S1 | S0,S159f(,a)= f(,b)= f | a b | ne

45、w state | | S0 | S0,S1 S1 | 1S1 | S0,S1 | 2S0,S1| S0,S1 S0,S1 | 3Z= S1,S0,S1M=(K,a,b,f,S0, S1,S0,S1)603.3.4 n若在一若在一FAFA中中, ,允许对允许对 也作状也作状态转移态转移, ,则这样的则这样的FAFA称为具有称为具有 动作的动作的FA.n右图就是一个具有具有 动作的动作的FA。其中其中, ,有的矢线上标记有的矢线上标记为为（在此看作一个符号在此看作一个符号）。标记为 的矢线对识别符号串无影响,但却改变了当前的状态状态.例如,上图的FA中,从状态0到状态3存在路径: 0(a)0(a

46、)0()2(c)2(c)2()3,即M识别了aacc=aacc.61 定义为定义为 M=(K,f,S0,Z),其中,f定义为 f:K()(K).n在在中中, 视为一个视为一个输入符号输入符号, ,在矩阵表在矩阵表示中示中, ,也有相应的列也有相应的列。例如，对于前面例如，对于前面的的FAFA，相应的状态转换矩阵如，相应的状态转换矩阵如P63P63表表3-23-2所示。所示。n同理可以定义同理可以定义f:K*(K). f(S,x)是由这是由这样的状态样的状态q组成组成,存在从存在从S到到q的路径的路径,该路径上矢线该路径上矢线的标记组成的符号串恰好为的标记组成的符号串恰好为x, 标记中可以包含若

47、标记中可以包含若干个干个 。62状态S的-闭包：-CLOSURE(S)n状态S的 -闭包闭包：记为-CLOSURE(S),它是从S出发经过若干标记为的矢线所能达到的全部状态之集，其归纳定义如下： (1)S-CLOSURE(S); (2)设Sj-CLOSURE(S),且Sj Sk,则Sk-CLOSURE(S); (3)重复使用规则（2）所得的集合为-CLOSURE(S).n-CLOSURE还可定义在状态集上，设QK，则QSSCLOSUREQCLOSURE)()(63-CLOSURE示例n例如例如，对于右图的NFA， -CLOSURE(0)=0,1,2,3；-CLOSURE(1)=1；-CLOSU

48、RE(2)=2,3；-CLOSURE(3)=3.64转换函数f和f 的拓广n利用-CLOSURE(S)，可定义f如下： RqRqwSfqwqfwRfaqfaRfKRKRKKfKKfffaqfawSffPPCLOSUREwaSfSCLOSURESfwaKS),(),()4(),(),(3)(:)2(),(),(,);(),()2();(),()1 (,*),(*）（有：）（）。对（）（）和（）（）（定义分别拓广到的及将。其中65f与f的区别n由f的定义可知，f(S,a) 与f(S,a) 不同，f(S,a)是从S出发经过路径a所达的状态集（可走若干步）；而f(S,a)是从S出发经过矢线a所达的状态

49、集（只走一步）n显然，f(S,a) 只走一步只走一步a矢线矢线 -CLOSURE(f(S,a) 多步，第一步必须走多步，第一步必须走a矢线矢线 f(S,a) 路径路径a ：第一步可以是第一步可以是 矢线矢线n-NFA的接受集的接受集： L(M)=w|f(S0,w) Z66f与f的计算示例n例如，在右图的NFA中， f(0, )=1,2; f(0,a)=0 是输入符号是输入符号 f(0, )= -CLOSURE(0)=0,1,2,3; 是符号串是符号串 f(0,a)= -CLOSURE(f(f(0, ),a)= -CLOSURE(f(0,1,2,3,a) = -CLOSURE(f(0,a) f(

50、3,a)= -CLOSURE(0)=0,1,2,3 f(0,ac)= -CLOSURE(f(f(0,a),c)= -CLOSURE(f(0,1,2,3,c) = -CLOSURE(f(0,c) f(3,c)= -CLOSURE(2)=2,367 -NFA的用途：构造更复杂的的用途：构造更复杂的FAn有了-NFA，就可把识别各种不同单词的FA用矢线（并连）连接起来，组成一个单一的NFA，经确定化后可得识别所有单词的DFA，由此可设计编译程序的词法分析器。n例如，某语言的单词有： 1.BEGIN 2.END3.IF 4.THEN5.ELSE 6.标识符7.无符号整数 8. 9. = 10. =11

51、. 12. 13.= 可分别构造出识别各类单词的FA,然后将其合并为一个大FA,如书中P65图3-11所示。68n为具有为具有 动作的动作的NFA M=(K, ,f,S0,Z)构造相应的构造相应的DFA M=(K, ,f,q0,Z)n基本思路：从基本思路：从M的初始状态的初始状态S0出发，仅经过任意条出发，仅经过任意条矢线所能到达的状态集合作为矢线所能到达的状态集合作为M的初态的初态q0 ；然后从；然后从q0出发，将对输入符号出发，将对输入符号a进行状态转移所能到达进行状态转移所能到达的状态（包括转移后再经过的状态（包括转移后再经过 矢线所能到达的状态）矢线所能到达的状态）所组成的集合作为所组

52、成的集合作为M的状态，如此反复，直到无新的状态，如此反复，直到无新状态产生为止。状态产生为止。69构造构造K,f和和Z的递归过程的递归过程1. 令令 K= -CLOSURE(S0); f= ;2. 对对K中尚未被标记的状态中尚未被标记的状态qi=Si1,Si2,Sim:(1)标记标记qi;(2)对于每个对于每个a,令令Ta=f(Si1,Si2,Sim,a); 对对a转移转移 令令 qj= -CLOSURE(Ta); 进行进行 矢线转移矢线转移(3)若若qj K,则令则令K=K qj ;(4)令令f=f f(qi ,a)= qj ;3. 重复重复2.,直到直到K中无未标记的状态中无未标记的状态;

53、4. 令令Z=qj | qj Z (这里把这里把qj 视为集合视为集合)70确定化具有确定化具有 动作的动作的NFANFA的例子的例子例例3.4 考虑右图具有考虑右图具有 动作的动作的NFA1.q0 = -CLOSURE(0) =0,1,2,3=K;2.q0未标记未标记,故故 (1)标记标记q0; (2)f(q0,a)= -CLOSURE(f(0,1,2,3,a) = -CLOSURE(0) = q0; f(q0,b)= -CLOSURE(f(0,1,2,3,b) = -CLOSURE(1,3) = 1,3= q1 =K; f(q0,c)= -CLOSURE(f(0,1,2,3,c) = -C

54、LOSURE(2) = 2,3= q2 =K;71确定化具有确定化具有 动作的动作的NFANFA的例子的例子( (续续) )3. K=q0,q1, q2,q1,q2 没有标记，没有标记， (1) 标记标记q1; (2) f(q1,a)= -CLOSURE(f(1,3,a)= f(q1,b)=q1; f(q1,c)= ;4. q2 没标记没标记, (1) 标记标记q2; (2) f(q2,a)= -CLOSURE(f(2,3,a)=； f(q2,b)=;f(q2,c)=q2; K不再增大，且所有的状态都已被标记，不再增大，且所有的状态都已被标记，Z=q0,q1,q2，最后的最后的DFA M 如下

55、所示：如下所示：q1q0q2abbcc72n需要说明的是需要说明的是,上述算法也适合于不含上述算法也适合于不含 产生式的产生式的NFA的确定化的确定化. 对于书中图对于书中图3-11所示的所示的NFA利用上述算法所得利用上述算法所得的的DFA如如 P67图图3-13所示所示. 其中其中,圆圈中的数字是原圆圈中的数字是原NFA的状态编号的状态编号,在图在图3-13中中, q0=0,1,7,11,14,19,24,26,28,30,33,35,40. 标有标有“#”的状态为特殊状态的状态为特殊状态,在该状态下在该状态下,若遇非弧若遇非弧线上出现的字符线上出现的字符,则转到状态则转到状态25.733

56、.3.6 DFA状态数的最小化n对于一对于一DFA来说来说,其状态数可能并不是最小的其状态数可能并不是最小的.原因是原因是DFA中有些状态是中有些状态是“等价等价”的的.为得到高效率的为得到高效率的DFA,需需将这些将这些“等价等价”状态合并状态合并,这就是这就是DFA的最小化的最小化.nDFA M的最小化的最小化: 构造等价的构造等价的DFA MDFA M其状态数达到最其状态数达到最小小. .n可区分状态可区分状态: 设设s,t K, s,t由某由某w*所区分所区分 iff ( f(s,w) Z f(t,w) Z ) ( f(s,w) Z f(t,w) Z ) 若若 w*, f(s,w) Z

57、 f(t,w) Z,则则 s与与 t不可区分，称不可区分，称二者等价。二者等价。n确定了等价状态，就可以对其进行合并。确定了等价状态，就可以对其进行合并。74DFA最小化算法n基本思想: 将M的状态集K逐步地进行划分,以期将K划分为满足等价关系的等价类：使得在同一类中的状态不可区分;在不同类中的状态可区分.算法如下:1. 先将状态集K按终态和非终态划分为两个子集Z Z和K-K-Z Z,显然分属于这两个集合的状态是可(被 )区分的.记 =Z,K-Z.=Z,K-Z.2. 设当前的划分 中已含有mm个子集: =I=I1 1,I ,I2 2,I,Imm ,其中,属于不同子集I Ii i和I Ij j

58、(ij)的状态是可区分的,而属于同一子集I Ii i中的状态是待区分的.现对每个子集I Ii i=S=Si i1 1,S,Si i2 2,S,Si in n 中的各状态S Si ir r(S(Si ir r K,1K,1 r r n )n )进行考查,看其是否可区分.75DFA最小化算法(续) 对于S Si ip p, S, Si iq q I Ii i ,若存在a a,使得f(Sf(Si ip p,a)=S,a)=Su u I Ij j, f(S, f(Si iq q,a) ,a) =S=Sv v I Ik k（即经过a a转换后落在不同的等价类中），则根据 S Su u和S Sv v被某个

59、w w所区分可知,S Si ip p 和S Si iq q 可被awaw 区分: f(Sf(Si ip p,aw)=f(S,aw)=f(Su u ,w) ,w)，而f(Sf(Si iq q,aw)= f(S,aw)= f(Sv v ,w) ,w)，且且S Su u与S Sv v可区分.将I Ii i细分,使其落入不同的更小的子集中.得到新划分 new.new. （细分I Ii i的方法见下页）。3.若 newnew. 不等于,则令 = = new.new. 转2.4.对于最终的 ，从每个划分块I Ii i中任选一状态为代表，构成KK。若I Ii i中含有初态，则其代表也为初态；若I Ii i

60、Z Z，则I Ii i 的代表 ZZ。删除非代表状态，将引入非代表状态的矢线引向代表状态.76细分划分块的方法.),(,),(),(,21中同一子集落入使得个更小的子集分为则将个不同的子集中的状态分别落入若令对每个子集aIfIIIpIpIaSfaIfIaIjpiiiiiiaiISiaii.),(,),(,可区分有意义的状态它任何使与其则无意义使得若某状态iiIqaqfpapfIp77DFA最小化的例子1. =0,1,2,3,4 0,1,2,3a=1 未区分未区分; 0,1,2b=2,3, 3b=4, 所以所以3与与 0,1,2 可区分可区分; =0,1,2, 3,42. 0,1,2a=1, 未