第三章_词法分析

1、第三章第三章 词法分析词法分析内容内容 词法分析器的要求 词法分析的设计 正规表达式 有限自动机 词法分析器的自动产生3.1 对于词法分析器的要求对于词法分析器的要求 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序。 任务:从左至右逐个字符地对源程序进行扫描，产生从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序造成为单词符号串的中间程序 词法分析是编译的基础本章重点本章重点1. 单词的描述描述工具工具2. 单词的识别识别系统系统 设计和实现词法分析

2、程序首先需要首先需要描述和刻画描述和刻画程序设计语言中的原子单位程序设计语言中的原子单位单词单词，其次需要识别单词和执行某些相关的，其次需要识别单词和执行某些相关的动作动作。描述程序设计语言的词法的机制是描述程序设计语言的词法的机制是正规表达式正规表达式，识，识别机制是别机制是有穷状态自动机有穷状态自动机。 本章将讨论本章将讨论词法分析程序词法分析程序的设计原则，单词的的设计原则，单词的描述技术描述技术，识识别机制别机制及词法分析程序的及词法分析程序的自动构造原理自动构造原理。5 词法分析器词法分析器又称扫描器，是执行词法分析的程序。任务有二：又称扫描器，是执行词法分析的程序。任务有二： (1

3、) (1) 识别单词 从用户的源程序中把单词分离出来; (2) 翻译单词 把单词转换成机内表示，便于后续处理。 词法分析程序：词法分析程序： 词法分析词法分析是编译过程中的一个阶段，在语法分析前进行，也可是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍。以和语法分析结合在一起作为一遍。 输入：源程序字符串输入：源程序字符串 输出：等价的属性字序列（内部表示形式）输出：等价的属性字序列（内部表示形式） 词法分析程序的功能：词法分析程序的功能： 读入源程序字符串，读入源程序字符串，识别识别开具有独立含义的最小语法单位开具有独立含义的最小语法单位单词单词（符号）；把（符号

4、）；把单词单词变换成变换成长度统一长度统一的且为定长的的且为定长的属性字属性字。 其他功能：其他功能：滤掉空格，跳过注释、换行符；某些预加工处理。滤掉空格，跳过注释、换行符；某些预加工处理。3.1.1 3.1.1 词法分析器的功能和输出形式词法分析器的功能和输出形式 功能:输入源程序、输出单词符号单词符号的种类：单词符号的种类：关键字：如 begin，if, while, 标识符：表示各种名字。如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，界符：逗号、分号、括号和空白3.1.1 3.1.1 词法分析器的功能和输出形式词法分析器的功能和输出形式 输出的单词符号的表示形式:(

5、单词种别，单词符号的属性值)单词种别通常用整数编码表示。单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定关键字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值（属性）。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的二进制形式。 例 FORTRAN程序 IF (5.EQ.M) GOTO 100输出单词符号：输出单词符号：逻辑逻辑IFIF(34(34，-)-)左括号左括号(2(2，-)-)整常数整常数(20(20， 5 5的二进制的二进制) )等号等号(6(6

6、，-)-)标识符标识符(26(26， M M) )右括号右括号(16(16，-)-)GOTOGOTO(30(30，-)-)标号标号(19(19， 100100的二进制的二进制) ) 例 FORTRAN程序DO 15 I=1DO 15 I=1，100100输出单词符号：输出单词符号：DODO(3(3，-)-)标号标号(19(19， 1515的二进制的二进制) )标识符标识符(26(26， I I) )赋值号赋值号(40(40，-)-)整常数整常数(7(7， 1 1的二进制的二进制) )逗号，逗号，(12(12，-)-)整常数整常数(7(7， 100100的二进制的二进制) )10C C程序段程序

7、段 if(a1)if(a1) b=10; b=10;假定基本字、运算符、假定基本字、运算符、界符都是一符一种。界符都是一符一种。l它所输出的单词符号是：它所输出的单词符号是：(2, - -) 基本字基本字if(29, - -) 左括号左括号(10,a) 标识符标识符a(23, - -) 大于号大于号(11,1的二进制的二进制) 常数常数1 (30, - -) 右括号右括号)(10,b) 标识符标识符b(17, - -) 赋值号赋值号=(11,10的二进制的二进制) 常数常数10(26,) 分号；分号；3.1.2词法分析是作为一个独立的阶段，词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢

8、？是否应当将其处理为一遍呢？词法分析程序作为单独一趟来实现。词法分析程序读入整词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。个源程序，它的输出作为语法分析程序的输入。优点：结构简洁、清晰和条理化，有利于集中考虑词法分优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。析一些枝节问题。不作为一遍：将其处理为一个子程序。不作为一遍：将其处理为一个子程序。语法分析程序需要语法分析程序需要新符号时调用这个子程序。新符号时调用这个子程序。3.1.2 词法分析器作为一个独立子程序词法分析器作为一个独立子程序 词法分析程序和语法分析程序的关系作为子

9、程序的词法分析器作为子程序的词法分析器3.2 词法分析器的设计词法分析器的设计 词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表3.2.1 输入、预处理输入、预处理 第一步：输入串放在输入缓冲区中。 预处理子程序目的：改善程序的可读性。预处理子程序目的：改善程序的可读性。 方法：方法：剔除无用地空白、跳格、回车和换行等编辑性字符；区分标号区、连接续行和给出句末符等。 设置（双）扫描缓冲区扫描缓冲区，解决末尾单词被打断的问题。单词不能超每个缓冲区的长度单词不能超每个缓冲区的长度！ 起点起点 搜索搜索指示器指示器 指示器指

10、示器3.2.2 单词符号的识别单词符号的识别: :超前搜索超前搜索 1 关键字识别:例如例如: :1 DO99K=1，102 IF(5.EQ.M)GOTO 553 DO99K=1.104 IF(5)=55一般需要超前搜索才能确定哪些是关键字一般需要超前搜索才能确定哪些是关键字3.2.2 单词符号的识别单词符号的识别: :超前搜索超前搜索 2 标识符识别:字母开头的字母数字串，后跟界符或算符字母开头的字母数字串，后跟界符或算符 3 常数识别:识别出算术常数并将其转变为二进制内码表示。识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。如：有些也要超前搜索。如：5.EQ.M 5.EQ.M

11、与与 5.E085.E08 4 算符和界符的识别把多个字符符合而成的算符和界符拼合成一个单把多个字符符合而成的算符和界符拼合成一个单一单词符号。：一单词符号。：= =， * * *， .EQ.EQ.这些字符串是不这些字符串是不可分的，需要超前扫描。可分的，需要超前扫描。状态转换图：一种有效的词法分析工具状态转换图：一种有效的词法分析工具 状态转换图是一张有限方向图。结点结点代表状态，用圆圈表示代表状态，用圆圈表示。状态之间用箭弧连结状态之间用箭弧连结，箭弧上的标记，箭弧上的标记(字符字符)代代表射出结表射出结点点状态下可能出现的输入字符或字符状态下可能出现的输入字符或字符类类。一张转换图只包含

12、有限个状态，其中一张转换图只包含有限个状态，其中有一个为有一个为初态，至少要有一个终态初态，至少要有一个终态。213XY3.2.3 状态转换图状态转换图 一个状态转换图可用于识别(或接受)一定的字符串。（阅读P41 图3.2 实数型转换图） 状态从0或者1开始。123字母字母其他其他字母或数字字母或数字识别标识符的状态转换图识别标识符的状态转换图*123数字数字其他其他数字数字识别识别整常数整常数的状态转换图的状态转换图*例：识别一个简单语言所有电磁符号的转换图 助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码单词符号 种别编码 助忆符内码值DIM1$DIM-IF2$IF-DO3$DO

13、-STOP4$STOP-END5$END-标识符6$ID内部字符串常数(数)7$INT标准二进制形式=8$ASSIGN-_9$PLUS-*10$STAR-*11$POWER-，12$COMMA-(13$LPAR-)14$RPAR- 几点重要限制为了不使用超前搜索所有关键字都是保留字；用户不能用它们作自所有关键字都是保留字；用户不能用它们作自己的标识符己的标识符关键字作为特殊的标识符来处理；不用特殊的关键字作为特殊的标识符来处理；不用特殊的状态图来识别，只要查保留字表。状态图来识别，只要查保留字表。如果关键字、标识符和常数如果关键字、标识符和常数( (或标号或标号) )之间没之间没有确定的运算符

14、或界符作间隔，则必须使用一有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。个空白符作间隔。DO99K=1，10 要写成 DO 99 K=1，10状态转换图示例123456789101112130空白字母字母或数字非字母与数字数字非数字数字=+*非*,()其它*出错情况出错情况 思想：每个状态结对应一小段程序。 做法:1)1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASECASE语语句或一组句或一组IF-THEN-ELSEIF-THEN-ELSE语句实现语句实现2)2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILEWHILE结构和结构和IFIF语

15、句构成的程序语句构成的程序3)3)终态结表示识别出某种单词符号，因此，终态结表示识别出某种单词符号，因此，对应语句为对应语句为 RETURN (CRETURN (C，VAL)VAL) 其中，其中，C C为为单词种别，单词种别，VALVAL为单词自身值为单词自身值3.2.4 状态转换图的实现状态转换图的实现 全局变量与过程1)1) CHAR CHAR 字符变量、存放最新读入的源程序字符变量、存放最新读入的源程序字符字符2)2) TOKEN TOKEN 字符数组，存放构成单词符号的字符数组，存放构成单词符号的字符串字符串3)3) GETCHAR GETCHAR 子程序过程，把下一个字符读子程序过程

16、，把下一个字符读入到入到CHARCHAR中中4)4) GETNBC GETNBC 子程序过程，跳过空白符，直至子程序过程，跳过空白符，直至CHARCHAR中读入一非空白符中读入一非空白符5)5) CONCAT CONCAT 子程序，把子程序，把CHARCHAR中的字符连接到中的字符连接到TOKENTOKEN状态转换图实现示例 全局变量与过程6)6) LETTER LETTER 布尔函数，判断布尔函数，判断CHARCHAR中字符是否为字中字符是否为字母母7)7) DIGIT DIGIT 布尔函数，判断布尔函数，判断CHARCHAR中字符是否为数字中字符是否为数字8)8) RESERVE RESE

17、RVE 整型函数，对于整型函数，对于TOKENTOKEN中的字符串查中的字符串查找保留字表，找保留字表，若它若它是是保留字则给出它的编码保留字则给出它的编码，否，否则回送则回送0 09)9) RETRACT RETRACT 子程序，把搜索指针回调一个字符位子程序，把搜索指针回调一个字符位置置10)10) DTB DTB 函数，把函数，把TOKENTOKEN中的字符串翻译中的字符串翻译成成二进制二进制码码状态转换图实现示例START: TOKEN:=; /*置TOKEN为空串*/ GETCHAR; GETNBC; CASE CHAR OF A.Z: BEGIN BEGIN WHILE LETTE

18、R OR DIGIT DO WHILE LETTER OR DIGIT DO BEGIN CONCAT;GETCHAR END; BEGIN CONCAT;GETCHAR END; RETRACT; RETRACT; C:=RESERVE; C:=RESERVE; IF C=0 THEN RETURN ($ID IF C=0 THEN RETURN ($ID, ,TOKEN)TOKEN) ELSE RETURN (C ELSE RETURN (C，-)-) END; END;状态转换图实现示例（P45页 阅读）0.9: BEGIN BEGIN WHILE DIGIT DO WHILE DIGI

19、T DO BEGIN CONCAT;GETCHAR END; BEGIN CONCAT;GETCHAR END; RETRACT; RETRACT; RETURN ($INT RETURN ($INT，DBT)DBT) END; END;=: RETURN ($ASSIGN，-);+: RETURN ($PLUS，-);状态转换图实现示例*:BEGINBEGIN GETCHAR; GETCHAR; IF CHAR= IF CHAR=* * THEN RETURN ($POWER THEN RETURN ($POWER，-);-); RETRACT; RETURN ($STAR RETRACT;

20、 RETURN ($STAR，-);-);END;END;，: RETURN ($COMMA，-);(:RETURN ($LPAR，-);):RETURN ($RPAR，-);END OF CASE;ERROR;GOTO START;状态转换图实现示例第5周 周2复习复习3.1.1 3.1.1 词法分析器的功能和输出形式词法分析器的功能和输出形式 输出的单词符号的表示形式:(单词种别，单词符号的属性值)单词种别通常用整数编码表示。单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定关键字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号

21、，给出种别编码和自身的值（属性）。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的二进制形式。3.1.2 词法分析器作为一个独立子程序词法分析器作为一个独立子程序 词法分析程序和语法分析程序的关系作为子程序的词法分析器作为子程序的词法分析器3.2 词法分析器的设计词法分析器的设计 词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表状态转换图：一种有效的词法分析工具状态转换图：一种有效的词法分析工具 状态转换图是一张有限方向图。结点结点代表状态，用圆圈表示代表状态，用圆圈表

22、示。状态之间用箭弧连结状态之间用箭弧连结，箭弧上的标记，箭弧上的标记(字符字符)代代表射出结表射出结点点状态下可能出现的输入字符或字符状态下可能出现的输入字符或字符类类。一张转换图只包含有限个状态，其中一张转换图只包含有限个状态，其中有一个为有一个为初态，至少要有一个终态初态，至少要有一个终态。213XY正规表达式与有限自正规表达式与有限自动机动机3.3 正规表达式与有限自动机正规表达式与有限自动机 几个概念:考虑一个考虑一个有穷有穷字母表字母表字符集字符集其中每一个元素称为一个字符上的字(也叫字符串)是指由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体

23、,包含空字例如例如: : 设设 =a=a， bb，则，则 ,.,*aaabbbaabaaba*的子集U和V的连接（积）定义为,|VUUVV自身的自身的 n次积记为次积记为VVVVn n n210*VVVV规定规定V0= ，令，令称称V*是是V的的闭包闭包; ;21*VVVVV记记 称称V+是是V的的正规闭包正规闭包。3.3.1 正规式与正规集正规式与正规集 正规式正规式也称正则表达式,正规表达式是说明单词的模式的一种重要的表示法（记号），是定义正规集的数学工具。 用以描述单词符号。 一个字集合是正规集正规集当且仅当它能用正规式表示。3.3.1 正规式与正规集正规式与正规集 下面（递归的）定义正

24、规式和它所表示的正规集： 设字母表为，辅助字母表=，。1 1、 和和 都是都是 上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和 ；2 2、任何、任何a a ，a a是是 上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为aa；3 3、假定、假定e e1 1和和e e2 2都是都是 上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为L(eL(e1 1) )和和L(eL(e2 2) )，那么，那么，(e (e1 1) )，e e1 1 e e2 2，e e1 1 e e2 2，e e1 1 也都是正规式，它们也都是正规式，它们

25、所表示的正规集分别为所表示的正规集分别为L(eL(e1 1) )，L(eL(e1 1) ) L(eL(e2 2) )，L(eL(e1 1)L(e)L(e2 2) )和和(L(e(L(e1 1) ) 。4 4、仅由、仅由有限次有限次使用上述三步骤而定义的表达式才是使用上述三步骤而定义的表达式才是 上的上的正规式正规式，仅由这些正规式所表示的集合才是仅由这些正规式所表示的集合才是 上的上的正规集正规集。3.3.1 正规式与正规集正规式与正规集 例1：令=a，b， 上的正规式和相应的正规集的例子有：正规式正规式 正规集正规集a aa b a,bab ab(a b)(a b) aa,ab,ba,bba

26、 ,a,a, 任意个任意个a的串的串(a b) ,a,b,aa,ab 所有由所有由a和和 b 组成的串组成的串(a b) (aa bb)(a b) 上所有含有两个相继的上所有含有两个相继的a或或 两个相继的两个相继的b组成组成 的串的串3.3.1 正规式与正规集正规式与正规集 例2：令=l，d，则上的正规式 r=l(l d) 定义的正规集是什么： l,ll,ld,ldd,如果其中如果其中l代表字母，代表字母，d代表数字，正规式即是字母代表数字，正规式即是字母(字母字母|数字数字) ，它表示的正规集中的每个元素的模式是，它表示的正规集中的每个元素的模式是“字字母打头的字母数字串母打头的字母数字串

27、”，就是多数程序设计语言允许的就是多数程序设计语言允许的的标识符的词法规则。的标识符的词法规则。 例3：=d，e，+，-，则上的正规式 d(dd )(e(+- )dd )表示的是什么意义： 程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义. .无符号数的集合。其中无符号数的集合。其中d为为09的数字。的数字。小数点小数点 若两个正规式所表示的正规集相同，则称这两个正规式等价两个正规式等价。如 b(ab)*=(ba)*b (a*b*)*=(a|b)* 对正规式，下列等价成立：e1|e2 = e2|e1 交换律交换律e1| (e2|e3) = (e1|e2)|e3 结合律

28、结合律e1(e2e3) = (e1e2)e3 结合律结合律e1(e2|e3) = e1e2|e1e3 分配律分配律(e2|e3)e1 = e2e1|e3 e1分配律分配律e = e = e 但但 e1e2 e2 e1 3.3.1 正规式与正规集正规式与正规集有限自动机有限自动机 有限自动机(Finite Automata)作为一种识别装置识别装置，它能准确地识别正规集准确地识别正规集，即识别正规文法所定识别正规文法所定义的语言和正规式所表示的集合义的语言和正规式所表示的集合。 引入有限自动机这个理论，正是为词法分析程引入有限自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具序的自

29、动构造寻找特殊的方法和工具。 有限自动机分为两类：确定的确定的有限自动机(Deterministic Finite Automata)和不确定不确定的有限自动机(Nondeterministic Finite Automata) 。有限自动机有限自动机 有限自动机所讨论的4个问题确定的有限自动机确定的有限自动机DFA不确定的有限自动机不确定的有限自动机NFANFA的确定化的确定化DFA的最小化的最小化3.3.2 确定有限自动机(DFA) 对状态图进行形式化对状态图进行形式化 确定的有限自动机确定的有限自动机M是五元式是五元式M=(S, , f, S0, Z),其中：其中：1. S: 有穷状态集

30、；有穷状态集；2. ：输入字母表：输入字母表(有穷有穷)；3. f: 状态转换函数，为状态转换函数，为SS的单值部分映射，的单值部分映射，f(s，a)=s表示：当现行状态为表示：当现行状态为s，输入字符为，输入字符为a时，将状态转换到下一时，将状态转换到下一状态状态s。我们把。我们把s称为称为s的一个后继状态；的一个后继状态；4. S0 S是是唯一的一个初态唯一的一个初态； 5. Z：终态集终态集(可空可空)，Z S。3.3.2 确定有限自动机确定有限自动机(DFA) 例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定义如下：定义如下： f(0，a)=1f(0，

31、b)=2 f(1，a)=3 f(1，b)=2 f(2，a)=1f(2，b)=3 f(3，a)=3 f(3，b)=33.3.2 确定有限自动机确定有限自动机(DFA) 一个DFA可以用一个矩阵表示矩阵表示（状态转换状态转换矩阵矩阵），该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行行a列为列为f(k,a)的值的值。 a b 0 1 2 1 3 2 2 1 3 3 3 3 状态转换矩阵状态转换矩阵字符字符状态状态3.3.2 确定有限自动机确定有限自动机(DFA) DFA也可以表示成一个状态图(或称状态转换图状态转换图)。 假定DFA M含有m个状态个状态，n

32、个输入字符个输入字符，那么这个状态图含有m个结点个结点，每个结点最多有每个结点最多有n个个弧射出弧射出，整个图含有唯一唯一一个初态结点和若干个终态结点。0312aaaa状态转换图状态转换图bbbb 对于对于 * *中的任何字中的任何字 ，若存在一条从初态若存在一条从初态到某一终态的道路到某一终态的道路，且这条路上所有弧上，且这条路上所有弧上的标记符连接成的字等于的标记符连接成的字等于 ，则称，则称 为为DFA M所识别所识别(接收接收) DFA M所识别的字的全体记为所识别的字的全体记为L(M)。3.3.2 确定有限自动机确定有限自动机(DFA) 例例：证明证明t=baab被下图的被下图的DF

33、A所接受。所接受。f（S，baab）=f（f（S，b），aab） =f（V，aab）= f（f（V，a），ab） =f（U，ab） =f（f（U，a），b） =f（Q，b） =QQ属于终态。得证。bSUVQabba, baa3.3.2 确定有限自动机确定有限自动机(DFA) 对于任何两个有限自动机对于任何两个有限自动机M M和和MM，如果，如果L(M)=L(M)L(M)=L(M)，则称则称M M与与MM是等价的。是等价的。 可以证明：可以证明： 上的字集上的字集V V* *是正规集，当是正规集，当且仅当存在且仅当存在 上的上的DFA M，使得，使得VL(M)。3.3.2 确定有限自动机确定有限

34、自动机(DFA) DFA的的确定性确定性表现在转换函数表现在转换函数f：KK是一个单值函数是一个单值函数，也就是说，对任何状态，也就是说，对任何状态kK，和输入符号，和输入符号a，f(k,a)唯一地确唯一地确定了下一个状态定了下一个状态。 从状态转换图来看，若字母表从状态转换图来看，若字母表含有含有n个输个输入字符，那末入字符，那末任何一个状态结点最多有任何一个状态结点最多有n条条弧射出，而且每条弧以一个不同的输入字弧射出，而且每条弧以一个不同的输入字符标记。符标记。3.3.2 确定有限自动机确定有限自动机(DFA) 用程序来模拟用程序来模拟DFA的行为的行为DFA M =（K，f，S，Z）的

35、行为的模拟程序的行为的模拟程序K := S；C := getchar;while ce of do K := f ( K, c ); c := getchar; ;if K is in Z then return (yes) else return (no)3.3.3 非确定非确定有限自动机有限自动机(NFA) 定义：一个定义：一个非确定有限自动机非确定有限自动机(NFA) M是是一个五元式一个五元式M=(S, M=(S, , , f, S, S0 0, Z), Z)，其中：，其中：1. S： 有穷状态集；2. ：输入字母表(有穷)；3. f：状态转换函数，为S*2S的部分映射(非单值非单值)

36、；4. S0S是非空的初态集初态集；5. Z：终态集(可空)，Z S 。 从状态图中看从状态图中看NFA 和和DFA的区别：的区别：1. 弧上的标记可以是弧上的标记可以是 *中的一个字，而不一定是单个中的一个字，而不一定是单个字符字符2. 同一个字可能出现在同状态射出的多条弧上。同一个字可能出现在同状态射出的多条弧上。 3.3.3 非确定有限自动机非确定有限自动机(NFA) NFA的特点是它的不确定性的特点是它的不确定性，即在，即在当前状态下，当前状态下，对同一个输入字符，可能有多于一个的下一状态对同一个输入字符，可能有多于一个的下一状态转移。转移。不确定性反映在不确定性反映在NFA的定义中，

37、就是的定义中，就是f函数函数是一对多是一对多的；的；反映在转换图中，就是反映在转换图中，就是从一个节点可通过多于一条标从一个节点可通过多于一条标记相同字符的边转移到不同的状态记相同字符的边转移到不同的状态；反映在转换矩阵中，就是反映在转换矩阵中，就是fsi, sj中不是一个单一状态，中不是一个单一状态，而是一个状态的集合。而是一个状态的集合。 例：例：识别由正规式(a|b)*abb说明的记号的NFA定义如下：S=0,1,2,3, =a,b，s0 = 0, F=3f = f(0,a)=0, f(0,a)=1, f(0,b)=0, f(1,b)=2, f(2,b)=3 它的转换图和转换矩阵表示如图

38、所示。在转换矩阵中，它的转换图和转换矩阵表示如图所示。在转换矩阵中，需指出需指出0是初态，是初态，3是终态。是终态。NFA如何识别串？如何识别串？ 对于对于中的任何串中的任何串t，若存在一条从，若存在一条从某一某一初态结初态结到到某一某一终态结的道路，且这条道路上所有弧的终态结的道路，且这条道路上所有弧的标记字依序连接成的串标记字依序连接成的串(不理采那些标记为不理采那些标记为的弧的弧)等于等于t，则称，则称t可为可为NFA M所识别所识别 若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路，其上所有弧的标记均为，那么空字可为空字可为M所接受。所接受。 NFA M所能

39、接受的符号串的全体记为L(M)。NFA与与DFA定义：对于任何两个有限自动机定义：对于任何两个有限自动机M和和M，如，如果果L(M)=L(M)，则称，则称M与与M等价等价。自动机理论中一个重要的结论：自动机理论中一个重要的结论：判定两个自动判定两个自动机等价性的算法是存在的。机等价性的算法是存在的。对于对于，使得，使得 L(M)=L(M)。亦即亦即DFA与与NFA描述能力相同。描述能力相同。DFA是是NFA的特例。的特例。021 a，baaa，bbba，b012abab识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的的字字ambn | m，n 1NFA等价判断等价判断3.3.3

40、非确定有限自动机非确定有限自动机(NFA) DFA是NFA的特例 对每个NFA N一定存在一个DFA ，使得 L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。 有一种算法可将NFA转换成接受同样语言的DFA。这种算法称为子集法子集法。 与某一与某一NFA等价的等价的DFA不唯一。不唯一。证明：每个证明：每个NFA一定存在一个一定存在一个DFA，使得，使得 L(M)=L(N)。 阅读：P49，图3.6以下证明NFA确定化算法确定化算法 算法思路：从从NFA的矩阵表示中可以看出，每个表项的矩阵表示中可以看出，每个表项可以可以是是一状态的集合，而在一状态的集合，而在DFA的矩阵表示中

41、，表项是的矩阵表示中，表项是一个状态。一个状态。NFA到相应的到相应的DFA的构造的基本思路是：的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。NFA确定化算法确定化算法 定义对状态集合定义对状态集合I的几个有关运算的几个有关运算1. 状态集合状态集合I I的的-闭包闭包，表示为表示为-closure(I)closure(I)，定义为一状态集，是状态集定义为一状态集，是状态集I I中的任何状态中的任何状态S S经任经任意条意条弧而能到达的状态的集合。弧而能到达的状态的集合。状态集合状态集合I I的任何状态的任何状

42、态S S都属于都属于-closure(I)closure(I)。2. 2. 状态集合状态集合I I的的a a弧转换弧转换，表示为表示为move(I,a)move(I,a)定义为定义为状态集合状态集合J J，其中，其中J J是所有那些可从是所有那些可从I I中的某一状态中的某一状态经过一条经过一条a a弧而到达的状态的全体。弧而到达的状态的全体。NFA确定化算法确定化算法 状态集合I的有关运算的示例I=1， -closure(I)=1,2；I=5， -closure(I)=5,6,2；move(2,a)=3 -closure( move(1,2, a)=?状态集状态集I I中的任何状态中的任何状

43、态S S经任意条经任意条弧而能到达的弧而能到达的状态的集合。状态的集合。所有那些可从所有那些可从I I中的某一状态经过一条中的某一状态经过一条a a弧而到达弧而到达的状态的全体。的状态的全体。12534687aaa2,3,4,5,6,7,8；NFA确定化算法确定化算法 假设NFA N=(K，f，K0，Kt)按如下办法构造一个DFA M=(S，d，S0，St)，使得L(M)=L(N)：1. M的状态集的状态集S由由K的一些子集组成。用组成。用S1 S2. Sj表示表示S的元素，其中的元素，其中S1, S2,. Sj是是K的状态。并的状态。并且约定，状态且约定，状态S1, S2,. Sj是按某种规

44、则排列的，是按某种规则排列的，即对于子集即对于子集S1, S2= S2, S1,来说，来说，S的状态就是的状态就是S1 S2；NFA确定化算法确定化算法2. M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是 ；3. 转换函数是这样定义的：转换函数是这样定义的：d(S1 S2,. Sj, a) = R1R2. Rt 其中 R1,R2,. , Rt = -closure( move(S1, S2,. Sj, a) ) 4. S0= -closure(K0)为为M的开始状态；的开始状态；5. St=Si Sk. Se，其中，其中Si Sk. Se S且且Si , Sk,. Se KtNF

45、A确定化算法确定化算法 构造NFA N的状态状态K K的子集的子集的算法：假定所构造的子集族为假定所构造的子集族为C，即，即C= (T1, T2,. TI),其中其中T1, T2,. TI为为状态状态K的子集。的子集。1 开始，令开始，令 -closure(K0)为为C中唯一成员，并且它是未被标记的。中唯一成员，并且它是未被标记的。2 while （C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标记T； for 每个输入字母每个输入字母a do U:= -closure(move(T,a) ； if U不在不在C中中 then 将将U作为未标记的子集加在作为未标记的子集加在C中中

46、 4f35621iaaaabbbb 等价的等价的DFAaCDBAEFSbaaaaabbbbbabF作业：作业：P64：7、8、123.3.4 正规式与有限自动机的等价性正规式与有限自动机的等价性 定理：定理： 1. 上的每个非确定非确定有限自动机M所能识别的字的全体L(M)是上的一个正规集。 2. 对于上的每个正规集S，存在一个上的确定有限有限自动机M，使得S=L(M)。 对转换图概念拓广，令每条弧可用一个正规对转换图概念拓广，令每条弧可用一个正规式作标记。式作标记。(对一类输入符号对一类输入符号)3.3.4 正规式与有限自动机的等价性正规式与有限自动机的等价性 证明：证明： 1 1 对对 上

47、任一上任一NFA M，构造一个，构造一个 上的正规上的正规式式V，使得，使得L(V)=L(M)。首先，在M的转换图上加进两个状态X和Y，从X用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y，从而形成一个新的NFA，记为M，它只有一个初态X和一个终态Y，显然L(M)=L(M)。然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；代之为代之为ijV1V2kikV1V2代之为代之为ijV1|V2ijV2V1代之为代之为ikV1V2*V2ijV1V3kV2最后，最后，X到到Y的弧上标记的正规式即为所构造的弧上标记的正规式即为所构造的正规式的正规式V，显然显然L(V)=L(

48、M)=L(M) 示例：12354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W13.3.4 正规式与有限自动机的等价性正规式与有限自动机的等价性 证明：证明： 2 对于对于 上的每个正规式上的每个正规式V存在一个存在一个 上的上的DFA M使得使得L(V)=L(M) 分两步证明分两步证明:1) 构造上的NFA M 使得 L(V)=L(M)2) 把M确定化为等价的DFA。NFANFA确定化确定化采用子集法采用子集法1) 构造上的NFA M 使得 L(V)=L(M)首先，把首先，把V表示成表示成XYV然后，按下面的三条

49、规则对然后，按下面的三条规则对V进行分裂：进行分裂：代之为代之为ijV1V2kikV1V2代之为代之为ijV1|V2ijV2V1代之为代之为ikV1*ij kV1最后，逐步把这个图转变为每条弧只标最后，逐步把这个图转变为每条弧只标记为记为 上的一个字符或上的一个字符或 ，最后得到一个，最后得到一个NFA M，显然，显然L(M)=L(V)示例：示例：(a|b)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY514236abababab3.3.5 正规文法与有限自动机的等价性正规文法与有限自动机的等价性 对于正规文法G和有限自动机M，如果L(G)=L(M)，则称G和M是等

50、价的。 结论：结论：（1）对于每一个右线性正规文法或左线性正规对于每一个右线性正规文法或左线性正规文法文法G，都存在一个，都存在一个FA M，使，使L(M)=L(G)。（2）对于每一个对于每一个DFA M，都存在一个右，都存在一个右线性正线性正规文法规文法G和和一个一个左线性正规文法左线性正规文法G， 使使 L(M)=L(G)=L(G)。3.3.5 正规文法与有限自动机的等价性正规文法与有限自动机的等价性 （1）对于每一个右线性正规文法或左线性正规文法G，都存在一个FA M，使L(M)=L(G)。证：证：一、一、给定给定右线性正规文法右线性正规文法G=（P28文法文法定义）定义）,设设f VN

51、 （新总结状态符号）（新总结状态符号），令，令M=, 其中，其中，F= f , 转移函数转移函数 定义如下：定义如下： (a) 如如Aa, 则则 (A, a)=f (b) 如如A aA1 aA2 . aAk 则则 (A, a)= A1, A2 , . , Ak 显然，上述显然，上述M是一个是一个NFA3.3.5 正规文法与有限自动机的等价性正规文法与有限自动机的等价性证：给定证：给定左线性正规文法左线性正规文法G=, 设设q0 VN （新添加初状态符）（新添加初状态符），令，令M=, 其中转移函数其中转移函数 定义如下：定义如下： (a) 如如Aa, 则则 (q0, a)=A (b) 如如A1

52、Aa, A2Aa, , AkAa 则则 (A, a)= A1, A2, . , Ak 显然，上述显然，上述M也是一个也是一个NFA3.3.5 正规文法与有限自动机的等价性正规文法与有限自动机的等价性 （2）对于每一个DFA M，都存在一个右线性正规文法G和一个左线性正规文法G，使L(M)=L(G)=L(G)。 有DFA转正规文法证：设证：设M=(S, , , s0, F), 右右线性正规文法线性正规文法G的构造方法如下：的构造方法如下：1、若、若s0 F, 令令G=( , S, s0, P), P的定义如下：的定义如下： 对任何对任何a 及及A, B S, 若有若有 (A, a)=B, 则则

53、(a) 当当B F, 令令 A aB (b) 当当B F 令令 A a aB2、若、若s0 F, 则则 L(M), 但但L(G)=L(M)- ，因此添加非终结符，因此添加非终结符s0和和s0s0，并用，并用s0代替代替s0作开始符号。作开始符号。 构造左线性正规文法，构造左线性正规文法， P的定义如下：的定义如下： 对任何对任何a 及及A1, A2 S, 有有 (A1, a)=A2, 则则 (a) A1是初态，是初态， A2 a (b) A1不是初态不是初态, A2 A1a3.3.5 正规文法与有限自动机的等价性正规文法与有限自动机的等价性 例3.4 DFA m 右线性正规文法GADCB0,1

54、111000A00B 1DB 0D 1CC 0 0B 1DD 0D 1Df0C0B 0C0C B 1D 1B0 C1 D0 D1ADCB0,1111000f00NFA m左线性正规文法 3.3.6 确定有限自动机的化简确定有限自动机的化简 一个有限自动机是化简的，即是：它没有多余状态并且它的状态中没有两个是互相等价的。一个有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。 所谓所谓有限自动机的多余状态有限自动机的多余状态，是指这样的，是指这样的状态：从自动机的开始状态出发，状态：从自动机的开始状态出发，任何输任何输入串也不能到达的那个状态；或者从这个入串也不能

55、到达的那个状态；或者从这个状态没有通路到达终态。状态没有通路到达终态。3.3.6 确定有限自动机的化简确定有限自动机的化简 对对DFA M的化简：的化简：寻找一个状态数比寻找一个状态数比M少的少的DFA M，使得，使得L(M)=L(M) 假设假设s和和t为为M的两个状态，的两个状态，s和和t等价，即等价，即为为:如果从状态如果从状态s出发能读出某个字出发能读出某个字 而停而停止于终态，那么同样，从止于终态，那么同样，从t出发也能读出出发也能读出 而停止于终态；反之亦然。而停止于终态；反之亦然。 两个状态不等价，则称它们是两个状态不等价，则称它们是可区别可区别的。的。3.3.6 确定有限自动机的化简确定有限自动机的化简 DFA的最小化就是寻求最小状态DFA 最小状态DFA的含义:没有多余状态没有多余状态(死状态死状态) )没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别） 两个状态s和t可区别：不满足兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从s出发读入某个出发读入某个a a和从和从t出发出发读读入某个入某个a到达的状态等价。到达的状态等价。C和和D同是终态同是终态,读入读入a到达到达C和和F, C和和F同是终态同是终态, C和和F读入读入a都到达都