编译原理-刘善梅-第3章 词法分析4ppt课件

1、第三章第三章 词法分析词法分析n对于词法分析器的要求对于词法分析器的要求n词法分析器的设计词法分析器的设计n正规表达式与有穷自动机正规表达式与有穷自动机n词法分析器的自动产生词法分析器的自动产生-LEX-LEX词法分析词法分析n词法分析的任务：从左至右逐个字符地词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符对源程序进行扫描，产生一个个单词符号。号。n词法分析器词法分析器(Lexical Analyzer) (Lexical Analyzer) 又称扫又称扫描器描器(Scanner)(Scanner)：执行词法分析的程序：执行词法分析的程序3.13.1 对于词法分析器的要求

2、对于词法分析器的要求一、词法分析器的功能和输出形式一、词法分析器的功能和输出形式功能功能: :输入源程序、输出单词符号输入源程序、输出单词符号单词符号的种类：单词符号的种类：基本字：如基本字：如 begin begin，repeatrepeat，标识符标识符表示各种名字：如变量名、数表示各种名字：如变量名、数组名和过程名组名和过程名常数：各种类型的常数常数：各种类型的常数运算符：运算符：+ +，- -，* *，/ /，界符：逗号、分号、括号和空白界符：逗号、分号、括号和空白n输出的单词符号的表示形式输出的单词符号的表示形式: :n( (单词种别，单词自身的值单词种别，单词自身的值) )n单词种

3、别通常用整数编码表示。单词种别通常用整数编码表示。n若一个种别只有一个单词符号，则种别编若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算码就代表该单词符号。假定基本字、运算符和界符都是一符一种。符和界符都是一符一种。n若一个种别有多个单词符号，则对于每个若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。单词符号，给出种别编码和自身的值。n标识符单列一种；标识符自身的值表示成标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。按机器字节划分的内部码。n常数按类型分种；常数的值则表示成标准常数按类型分种；常数的值则表示成标准的二进制形式。的二进制

4、形式。例例 FORTRAN FORTRAN程序程序nIF (5.EQ.M) GOTO 100IF (5.EQ.M) GOTO 100n输出单词符号：输出单词符号：n逻辑逻辑IFIF(34(34，-)-)n左括号左括号(2(2，-)-)n整常数整常数(20(20， 5 5的二进制的二进制) )n等号等号(6(6，-)-)n标识符标识符(26(26， M) M)n右括号右括号(16(16，-)-)nGOTOGOTO(30(30，-)-)n标号标号(19(19， 100 100的二进制的二进制) )n助忆符：直接用编码表示不便于记忆，因此用助忆助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码

5、。符来表示编码。例：例：IFIF(34(34，-) (IF-) (IF，-) -) 左括号左括号(2(2，-) (-) (，-) -) 等号等号(6(6，-) (=-) (=，-) -) 例例 C C程序程序n while (i=j) i-;n输出单词符号：输出单词符号：nnnn=, - nnnnn二、词法分析器作为一个独立子程序二、词法分析器作为一个独立子程序n词法分析是作为一个独立的阶段，是否词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？应当将其处理为一遍呢？n作为独立阶段的优点：结构简洁、清晰作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一和条理化，有利于集

6、中考虑词法分析一些枝节问题。些枝节问题。n不作为一遍：将其处理为一个子程序。不作为一遍：将其处理为一个子程序。词法分析器词法分析器词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.词法分析器的结构词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入3.2 词法分析器的设计删除无用的空白、跳格、回删除无用的空白、跳格、回车和换行等编辑性字符车和换行等编辑性字符区分标号区、捻接续行和给区分标号区、捻接续行和给出句末符等出句末符等 WhatALongWord WhatALongWord

7、 WhatALongWord WhatALongWon扫描缓冲区扫描缓冲区 起点起点 搜索搜索指示器指示器 指示器指示器一、扫描缓冲区一、扫描缓冲区 二、单词符号的识别二、单词符号的识别: :超前搜索超前搜索以基本字的识别为例：以基本字的识别为例：例如例如:DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能确定哪些是基本字需要超前搜索才能确定哪些是基本字几点限制几点限制不必使用超前搜索不必使用超前搜索n所有基本字都是保留字；用户不能用它们作自己所有基本字都是保留字；用户

8、不能用它们作自己的标识符；的标识符；n 基本字作为特殊的标识符来处理基本字作为特殊的标识符来处理;不用特殊的状不用特殊的状态图来识别，只要查保留字表。态图来识别，只要查保留字表。n如果基本字、标识符和常数或标号之间没有如果基本字、标识符和常数或标号之间没有确定的运算符或界符作间隔，则必须使用一个空确定的运算符或界符作间隔，则必须使用一个空白符作间隔白符作间隔三、状态转换图三、状态转换图1 1 概念概念状态转换图是一张有限方向图。状态转换图是一张有限方向图。213a数字数字结点代表状态，用圆圈表示。结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧状态之间用箭弧连结，箭弧上的标记上的标记( (字

9、符字符) )代表射出结代表射出结状态下可能出现的输入字符状态下可能出现的输入字符或字符类。或字符类。一张转换图只包含有限个状态，其中一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。有一个为初态，至少要有一个终态。识别标识符的状态转换图识别标识符的状态转换图123字母字母其他其他字母或数字字母或数字*识别整常数的状态转换图识别整常数的状态转换图123数字数字其他其他数字数字*n一个状态转换图可用于识别一个状态转换图可用于识别( (或接受或接受) )一定一定的字符串。的字符串。词法分析器设计流程词法分析器设计流程 某程序设计语言的某程序设计语言的单词符号串集单词符号串集 分析词法规

10、则分析词法规则 画出识别单词的状态图画出识别单词的状态图 根据状态图写词法分析器程序根据状态图写词法分析器程序单单 词词 符符 号号 种种 别别 编编 码码 助助 忆忆 符符 内内 码码 值值 D DI IM M 1 1 $ $D DI IM M - - I IF F 2 2 $ $I IF F - - D DO O 3 3 $ $D DO O - - S ST TO OP P 4 4 $ $S ST TO OP P - - E EN ND D 5 5 $ $E EN ND D - - 标标 识识 符符 6 6 $ $I ID D 内内 部部 字字 符符 串串 常常 数数 ( (数数 ) )

11、7 7 $ $I IN NT T 标标 准准 二二 进进 制制 形形 式式 = = 8 8 $ $A AS SS SI IG GN N - - _ _ 9 9 $ $P PL LU US S - - * * 1 10 0 $ $S ST TA AR R - - * * * 1 11 1 $ $P PO OW WE ER R - - ， 1 12 2 $ $C CO OM MM MA A - - ( ( 1 13 3 $ $L LP PA AR R - - ) ) 1 14 4 $ $R RP PA AR R - - 1 12 23 34 45 56 67 78 89 9101011111212

12、13130 0空白空白字母字母字母或数字字母或数字非字母与数字非字母与数字数字数字非数字非数字数字数字= =+ +* *非非* *, ,( () )其它其它* * * * *3 状态转换图的实现状态转换图的实现思想：每个状态结对应一小段程序。思想：每个状态结对应一小段程序。做法做法:1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASE语句语句或一组或一组IF-THEN-ELSE语句实现语句实现GetChar( );if (IsLetter( ) 状态状态j的对应程序段的对应程序段;else if (IsDigit( ) 状态状态k的对应程序段的对应程序段;else if (ch

13、=/) 状态状态l的对应程序段的对应程序段;else 错误处理错误处理;ijkl字母字母数字数字/3 状态转换图的实现状态转换图的实现2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILE语句构成的程序语句构成的程序.i字母或数字字母或数字其它其它jGetChar( );while (IsLetter( ) or IsDigit( )GetChar( );状态状态j的对应程序段的对应程序段3 状态转换图的实现状态转换图的实现3)终态结表示识别出某种单词符号，因此，终态结表示识别出某种单词符号，因此，对应语句为对应语句为 RETURN (C，VAL) 其中，其中，C为单词种别

14、，为单词种别，VAL为单词自身值为单词自身值.n全局变量与过程全局变量与过程n1)ch 字符变量、存放最新读入的源程字符变量、存放最新读入的源程序字符序字符n2)strToken 字符数组，存放构成单词字符数组，存放构成单词符号的字符串符号的字符串n3)GetChar 子程序过程，把下一个字子程序过程，把下一个字符读入到符读入到 ch 中中n4)GetBC 子程序过程，跳过空白符，直子程序过程，跳过空白符，直至至 ch 中读入一非空白符中读入一非空白符n5)Concat 子程序，把子程序，把ch中的字符连接中的字符连接到到 strToken 6)IsLetter和和 IsDisgital 布尔

15、函数，布尔函数，判断判断ch中字符是否为字母和数字中字符是否为字母和数字7) Reserve 整型函数，对于整型函数，对于 strToken 中的字符串查找保留字表，若它是保留字中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送则给出它的编码，否则回送08) Retract 子程序，把搜索指针回调一子程序，把搜索指针回调一个字符位置个字符位置9)InsertId 整型函数，将整型函数，将strToken中中的标识符插入符号表，返回符号表指针的标识符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将整型函数过程，将strToken中的常数插入常数表，返回常中的常数

16、插入常数表，返回常数表指针。数表指针。 int code, value;strToken := “ ”; /*置置strToken为空串为空串*/GetChar(); GetBC();if (IsLetter()beginwhile (IsLetter() or IsDigit()beginConcat(); GetChar(); endRetract();/搜索指针回调搜索指针回调code := Reserve(); /判断是否为保留字判断是否为保留字if (code = 0) /标识符标识符beginvalue := InsertId(strToken);return ($ID, valu

17、e);endelsereturn (code, -); /保留字保留字endelse if (IsDigit()begin while (IsDigit() begin Concat( ); GetChar( ); endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) return ($PLUS, -);5=*6*+else if (ch =*)beginGetChar();if (ch =*) return ($

18、POWER, -);Retract(); return ($STAR, -);endelse if (ch =;) return ($SEMICOLON, -);else if (ch =() return ($LPAR, -);else if (ch =) return ($RPAR, -);else ProcError( );/* 错误处理错误处理*/将状态图的代码一般化将状态图的代码一般化n变量变量curState用于保存现有的状态用于保存现有的状态n用二维数组表示状态图：用二维数组表示状态图：n stateTransstatecharcurState=初态初态GetChar();Whi

19、le(stateTranscurStatech有定义有定义)/存在后继状态，读入，拼接存在后继状态，读入，拼接Contact();/转入下一状态，读入下一字符转入下一状态，读入下一字符curState=stateTranscurStatech；If curState是终态是终态 then 返回返回strToken中的单词中的单词GetChar(); FA正规集正规集正规式正规式DFANFA正规文法正规文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.63.3 3.3 正规表达式与有限自动机正规表达式与有限自动机3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机n几个

20、概念几个概念: :n考虑一个有穷考虑一个有穷 字母表字母表 字符集字符集n其中每一个元素称为一个字符其中每一个元素称为一个字符n上的字上的字( (也叫字符串也叫字符串) ) 是指由是指由中的字中的字符所构成的一个有穷序列符所构成的一个有穷序列n不包含任何字符的序列称为空字，记为不包含任何字符的序列称为空字，记为n用用* *表示表示上的所有字的全体上的所有字的全体, ,包含空字包含空字n例如例如: : 设设 =a =a， b b，那么，那么 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n*的子集的子集U和和V的连接积定义为的连接积定义为nUV

21、 | U & V nV自身的自身的 n次积记为次积记为nVn=VVVn规定规定V0=，令，令n V*=V0V1V2V3 n称称V*是是V的闭包的闭包;n记记 VVV* ，称，称V+是是V的正规闭包。的正规闭包。3.3.1 正规式和正规集正规式和正规集n正规集可以用正规表达式简称正规式正规集可以用正规表达式简称正规式表示。表示。n正规表达式是表示正规集一种方法。一正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规个字集合是正规集当且仅当它能用正规式表示。式表示。n正规式和正规集的递归定义：正规式和正规集的递归定义：n对给定的字母表对给定的字母表n1)1) 和和都是都是上

22、的正规式，它们所表上的正规式，它们所表示的正规集为示的正规集为 和和; ;n2) 2) 任何任何a a ，a a是是上的正规式，它上的正规式，它所表示的正规集为所表示的正规集为a ;a ;3) 假定假定e1和和e2都是都是 上的正规式，它们所表示上的正规式，它们所表示的正规集为的正规集为L(e1)和和L(e2)，那么，那么i) (e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，ii) (e1.e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)(连接积连接积)，iii) (e1)*为正规式，它所表示的正规集为为正规式，它所

23、表示的正规集为(L(e1)*（闭包，即任意有限次的自重复连（闭包，即任意有限次的自重复连接），接），仅由有限次使用上述三步骤而定义的表达式才仅由有限次使用上述三步骤而定义的表达式才是是 上的正规式，仅由这些正规式表示的字集上的正规式，仅由这些正规式表示的字集才是才是 上的正规集。上的正规集。n所有词法结构一般都可以用正规式描述。所有词法结构一般都可以用正规式描述。n若两个正规式所表示的正规集相同，则称若两个正规式所表示的正规集相同，则称这两个正规式等价。如这两个正规式等价。如nb(ab)b(ab)* *=(ba)=(ba)* *b b(a(a* *b b* *) )* *=(a|b)=(a|b

24、)* *n L( (ba)*b) = L(ba)*) L(b)= (L(ba)*L(b) = (L(b)L(a)* L(b) = ba* b = , ba, baba, bababa, b= b, bab, babab, bababab, L(b(ab)*) = L(b)L(ab)*) = L(b) (L(ab)*= L(b) (L(a)L(b)*=b ab* = b , ab, abab, ababab, = b, bab, babab, bababab, L(b(ab)*)= L( (ba)*b) b(ab)*=(ba)*bn对正规式，下列等价成立：对正规式，下列等价成立：ne1|e2 =

25、 e2|e1 交换律交换律ne1 |(e2|e3) = (e1|e2)|e3 结合律结合律ne1(e2e3) = (e1e2)e3 结合律结合律ne1(e2|e3) = e1e2|e1e3 分配律分配律n(e2|e3)e1 = e2e1|e3 e1分配律分配律ne = e = e e1e2 e2 e1 L(e1|e2) = L(e1 ) L(e2)= L(e2 ) L(e1)= L(e2|e1)FA正规集正规集正规式正规式DFANFA3.3.13.3.23.3.33.3.2 确定有限自动机确定有限自动机(DFA)n对状态图进行形式化，则可以下定义：对状态图进行形式化，则可以下定义：n自动机自动

26、机M M是一个五元式是一个五元式M=(S, M=(S, , f, S0, F), f, S0, F),其中：其中：n1. S: 1. S: 有穷状态集，有穷状态集，n2. 2. ：输入字母表：输入字母表( (有穷有穷) )，n3. f: 3. f: 状态转换函数，为状态转换函数，为S SS S的单值部的单值部分映射，分映射，f(sf(s，a)=sa)=s表示：当现行状态为表示：当现行状态为s s，输入字符为输入字符为a a时，将状态转换到下一状态时，将状态转换到下一状态s s。我们把我们把s s称为称为s s的一个后继状态。的一个后继状态。n4. S04. S0S S是唯一的一个初态；是唯一的

27、一个初态； n5 F5 FS S ：终态集：终态集( (可空可空) )。n例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定义如下：定义如下：nf(0，a)=1f(0，b)=2nf(1，a)=3 f(1，b)=2nf(2，a)=1f(2，b)=3nf(3，a)=3 f(3，b)=3ab012132213333状态转换矩阵状态转换矩阵0312aaaa状态转换图状态转换图bbbbn对于对于 * *中的任何字符串中的任何字符串，若存在一条从，若存在一条从初态到某一终态的道路，且这条路上所有初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字符串等于弧上的标记符连

28、接成的字符串等于，则，则称称为为DFA MDFA M所识别所识别( (接纳接纳) )。nDFA MDFA M所识别的字符串的全体记为所识别的字符串的全体记为L(M)L(M)。142300011011练习练习下图下图DFADFA识别的识别的L(M)L(M)是什么？是什么？A.L(M)=A.L(M)=以以aaaa或或bbbb开头的字符串开头的字符串B.L(M)=B.L(M)=含含aaaa或或bbbb的字符串的字符串C.L(M)=C.L(M)=以以aaaa或或bbbb结尾的字符串结尾的字符串答案：答案：B B0312aaaaDFADFAbbbb3.3.3 3.3.3 非确定有限自动机非确定有限自动机

29、(NFA) (NFA) 1976年图灵奖年图灵奖 For their joint paper“Finite automata and their decision problemswhich introduced the idea of nondeterministic machines，which has proved to be an enormously valuable concept. Their classic paper has been a continuous source of inspiration for subsequent work in this field.3.

30、3.3 3.3.3 非确定有限自动机非确定有限自动机(NFA) (NFA) n定义：一个非确定有限自动机定义：一个非确定有限自动机(NFA) M(NFA) M是是一个五元式一个五元式M=(S, M=(S, , f, S0, F), f, S0, F)，其中：，其中：n1 S: 1 S: 有穷状态集；有穷状态集；n2 2 ：输入字母表：输入字母表( (有穷有穷) )；n3 f: 3 f: 状态转换函数，为状态转换函数，为S S* *2S2S的的部分映射部分映射( (非单值非单值) )；n4 S04 S0S S是非空的初态集；是非空的初态集；n5 F 5 F S S ：终态集：终态集( (可空可空

31、) )。n从状态图可看出从状态图可看出NFA 和和DFA的区别：的区别：n 1 可有多个初态可有多个初态n 2 弧上的标记可以是弧上的标记可以是 *中的一个字甚至可中的一个字甚至可以是一个正规式），而不一定是单个字符；以是一个正规式），而不一定是单个字符；n 3 同一个字可能出现在同状态射出的多条弧同一个字可能出现在同状态射出的多条弧上。上。nDFA是是NFA的特例。的特例。021 aaa|bb*cabNFADFAn对于对于 * *中的任何字中的任何字，若存在一条从初态，若存在一条从初态到某一终态的道路，且这条路上所有弧上到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于的标记符连接成

32、的字等于（忽略那些标（忽略那些标记为记为的弧），则称的弧），则称为为NFA MNFA M所识别所识别( (接接纳纳) )nNFA MNFA M所识别的字符串的全体记为所识别的字符串的全体记为L(M)L(M)。021 a|baaa|bbba|b012abab识别所有含相继两个识别所有含相继两个a a或相继两个或相继两个b b的字的字ambn | m，n1NFA示例示例n定义：对于任何两个有限自动机定义：对于任何两个有限自动机M和和M，如果如果L(M)=L(M)，则称，则称M与与M等价。等价。n自动机理论中一个重要的结论：判定两自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。个自动

33、机等价性的算法是存在的。n对于每个对于每个NFA M存在一个存在一个DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA与与NFA描述能力描述能力相同。相同。NFA与与DFA1. 假定假定NFA M=，我们对，我们对NFA M的状态转换图进行以下改造：的状态转换图进行以下改造： 1) 引进新的初态结点引进新的初态结点X和终态结点和终态结点Y，X,YS， 从从X到到S0中任意状态结点连一条中任意状态结点连一条箭弧，箭弧， 从从F中任意状态结点连一条中任意状态结点连一条箭弧到箭弧到Y。 2) 按以下按以下3条规则对条规则对NFA M的状态转换图进一的状态转换图进一步施行替换，直到把这个图转

34、变为每条弧只步施行替换，直到把这个图转变为每条弧只标记为标记为 上的一个字符或上的一个字符或；其中；其中k是新引入是新引入的状态。的状态。NFA转换为等价的转换为等价的DFA代之为代之为ikABjijAB代之为代之为ijA|BijBA代之为代之为ijA*ik jA按下面的按下面的3条规则对箭弧进行分裂条规则对箭弧进行分裂:n例：识别所有含相继两个例：识别所有含相继两个a或相继两个或相继两个b的字的字XY 514236ab ababab5126ab abaabb2. 把上述把上述NFA确定化确定化采用子集法采用子集法.设设I是是NFA的状态集的一个子集，定义的状态集的一个子集，定义I的的-闭包闭

35、包-closure(I)为为: i) 若若sI，则，则s-closure(I)； ii) 若若sI，则从，则从s出发经过任意条出发经过任意条弧弧而能到达的任何状态而能到达的任何状态s都属于都属于-closure(I) 即即 -closure(I)=Is|从某个从某个sI出发经过任出发经过任意条意条弧能到达弧能到达sn设设a是是中的一个字符，定义中的一个字符，定义nIa= -closure(J)n 其中，其中，J为为I中的某个状态出发经过一条中的某个状态出发经过一条a弧而到达的状态集合。弧而到达的状态集合。IIaaIJaK n -closure(1)=1，2=I n J=5，4，3n Ia= -

36、closure(J)= -closure(5，4，3)n =5，4，3，6，2，7，861a 234578aa n设设a是是中的一中的一个字符，定义个字符，定义nIa= -closure(J)n 其中，其中，J为为I中的中的某个状态出发经某个状态出发经过一条过一条a弧而到弧而到达的状态集合。达的状态集合。Ia=？n确定化的过程确定化的过程: :n 不失一般性，设字母表只包含两个不失一般性，设字母表只包含两个a a和和b b，我们构造一张表，我们构造一张表: :IIaIb -C losure(X )u首先，置第首先，置第1行第行第1列为列为-closure(X)求出这一列的求出这一列的Ia，Ib

37、；u然后，检查这两个然后，检查这两个Ia，Ib，看，看它们是否已在表中的第一列中出它们是否已在表中的第一列中出现，把未曾出现的填入后面的空现，把未曾出现的填入后面的空行的第行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.u重复上述过程，知道所有第重复上述过程，知道所有第2，3列子集全部出现在第一列为止。列子集全部出现在第一列为止。IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,

38、2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab abababn现在把这张表看成一个状态转换矩阵，把其中的每个子现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。集看成一个状态。n这张表唯一刻划了一个确定的有限自动机这张表唯一刻划了一个确定的有限自动机M，它的初态，它的初态是是-closure(X) ，它的终态是含有原终态，它的终态是含有原终态Y的子集。的子集。n不难看出，这个不难看出，这个DFA M与与M等价。等价。IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5

39、,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YIIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,

40、3,6,1,Y5,2,3,1,6,Y5,4,6,1,YIab012132214334465565634Iab0121322143344655656340123546aabbbabaabababFA正规集正规集正规式正规式DFANFA3.3.13.3.23.3.33.3.53.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性n定理：定理：n 1. 对任何对任何FA M，都存在一个正规式，都存在一个正规式r，使得使得L(r)=L(M)。n 2. 对任何正规式对任何正规式r，都存在一个，都存在一个FA M，使得使得L(M)=L(r)。n对转换图概念拓广，令每条弧可用一个对转换图概念拓广，

41、令每条弧可用一个正规式作标记。正规式作标记。(对一类输入符号对一类输入符号)n证明：证明： n 1 1 对对 上任一上任一NFA MNFA M，构造一个，构造一个 上的正规上的正规式式r r，使得，使得L(r)=L(M)L(r)=L(M)。n首先，在首先，在M M的转换图上加进两个状态的转换图上加进两个状态X X和和Y Y，从从X X用用弧连接到弧连接到M M的所有初态结点，从的所有初态结点，从M M的所有终态结点用的所有终态结点用弧连接到弧连接到Y Y，从而形，从而形成一个新的成一个新的NFANFA，记为，记为M M，它只有一个初态，它只有一个初态X X和一个终态和一个终态Y Y，显然，显然

42、L(M)=L(ML(M)=L(M) )。n然后，反复使用下面的一条规则，逐步消然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下去的所有结点，直到只剩下X X和和Y Y为止；为止；代之为代之为ijr1r2kikr1r2代之为代之为ijr1|r2ijr2r1代之为代之为ikr1r2*r3ijr1r3kr212354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1q最后，最后，X到到Y的弧上标记的正规式即为的弧上标记的正规式即为所构造的正规式所构造的正规式rq显然显然L(r)=L(M)=L(M)XYrn定理：

43、定理：n 1. 对任何对任何FA M，都存在一个正规式，都存在一个正规式r，使得，使得L(r)=L(M)。n 2. 对任何正规式对任何正规式r，都存在一个，都存在一个FA M，使得，使得L(M)=L(r)。n证明证明2: 对于对于 上的正规式上的正规式r，构造一个，构造一个NFA M，使，使L(M)=L(r)，并且，并且M只有一个只有一个终态，而且没有从该终态出发的箭弧。终态，而且没有从该终态出发的箭弧。n 下面使用关于下面使用关于r中运算符数目的归纳法中运算符数目的归纳法证明上述结论。证明上述结论。n(1) 若若r具有零个运算符，则具有零个运算符，则r=或或r=或或r=a，其中，其中a。此时

44、下图所示的三个有。此时下图所示的三个有限自动机显然符合上述要求。限自动机显然符合上述要求。q0q0qfaq0qf(2) 假设结论对于少于假设结论对于少于k(k1)个运算符的正个运算符的正规式成立。规式成立。 当当r中含有中含有k个运算符时，个运算符时，r有三种情形：有三种情形：情形情形1：r=r1|r2，r1,r2中运算符个数少于中运算符个数少于k。从而，由归纳假设，对从而，由归纳假设，对ri存在存在Mi=，使得，使得L(Mi)=L(ri)，并且，并且Mi没没有从终态出发的箭弧有从终态出发的箭弧i=1,2）。不妨设）。不妨设S1S2=，在，在S1 S2中加入两个新状态中加入两个新状态q0，f0

45、。 令令M=，其中，其中定义如下：定义如下：(a) (q0, )=q1,q2(b) (q,a)= 1(q,a), 当当qS1-f1, a1(c) (q,a)= 2(q,a), 当当qS2-f2, a2(d) (f1,)=(f2,)=f0。 M的状态转换如右图所示。的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r) q0f0M1q1f1M2q2f2 l情形情形2：r=r1r2, 设设Mi同情形同情形1(i=1,2)。l 令令M=，其中其中定义如下：定义如下：l(a) (q,a)= 1(q,a), 当当qS1-f1, a1l(b) (q,a)= 2(q,a),

46、 当当qS2, a2l(c) (f1,)=q2l M的状态转换如右图所示。的状态转换如右图所示。l L(M)=L(M1)L(M2)l =L(r1)L(r2)=L(r)。 M1q1f1M2q2f2l情形情形3：r=r1*。设。设M1同情形同情形1。l令令M=，其，其中中q0, f0S1，定义如下：定义如下：l(a) (q0,)=(f1,)=q1, f0l(b) (q,a)= 1(q, a), 当当qS1-f1, a1。lM的状态转换如右图所示。的状态转换如右图所示。lL(M) = L(M1)* = L(r1)* = L(r)l至此，结论至此，结论2获证。获证。 M1q1f1q0f0 1) 1)

47、构造构造 上的上的NFA M NFA M 使得使得 L(V)=L(M) L(V)=L(M)首先，把首先，把V V表示成表示成XYV上述证明过程实质上是一个将正规表达式上述证明过程实质上是一个将正规表达式转换为有限自动机的算法。转换为有限自动机的算法。代之为代之为ijV1V2kikV1V2代之为代之为ijV1|V2ijV2V1代之为代之为ikV1*ij kV1然后，按下面的三条规则对然后，按下面的三条规则对V进行分裂进行分裂n逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的上的一个字符或一个字符或，最后得到一个，最后得到一个NFA M，显，显然然L(M)=L(V)n(a|b

48、)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY 514236ab abababIIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab abababIab0121322143344655656340123546aabbbabaabababF

49、A正规集正规集正规式正规式DFANFA3.3.13.3.23.3.33.3.5DFA3.3.63.3.6 确定有限自动机的化简确定有限自动机的化简n对对DFA M的化简的化简:寻找一个状态数比寻找一个状态数比M少少的的DFA M，使得，使得L(M)=L(M)n假设假设s和和t为为M的两个状态，称的两个状态，称s和和t等价等价:如果从状态如果从状态s出发能读出某个字出发能读出某个字而停止而停止于终态，那么同样，从于终态，那么同样，从t出发也能读出出发也能读出而停止于终态；反之亦然。而停止于终态；反之亦然。n两个状态不等价，则称它们是可区别的。两个状态不等价，则称它们是可区别的。n对一个对一个DF

50、A M最少化的基本思想最少化的基本思想:n 把把M的状态集划分为一些不相交的子集，的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，的。最后，让每个子集选出一个代表，同时消去其他状态。同时消去其他状态。n具体做法具体做法: 对对M的状态集进行划分的状态集进行划分n首先，把首先，把S划分为终态和非终态两个子集，划分为终态和非终态两个子集，形成基本划分形成基本划分。 n假定到某个时候，假定到某个时候，已含已含m个子集，记个子集，记为为=I(1)，I

51、(2)，I(m)，检查，检查中中的每个子集看是否能进一步划分的每个子集看是否能进一步划分:n对某个对某个I(i)，令，令I(i)=s1,s2, ,sk，若存，若存在一个输入字符在一个输入字符a使得使得Ia(i) 不会包含在现不会包含在现行行的某个子集的某个子集I(j)中即，中即， Ia(i)中的元中的元素分布在现行划分的多个子集中），则素分布在现行划分的多个子集中），则至少应把至少应把I(i)分为两个部分。分为两个部分。n例如，假定状态例如，假定状态s1和和s2经经a弧分别到达弧分别到达t1和和t2，而，而t1和和t2属于现行属于现行中的两个不同中的两个不同子集，说明有一个字子集，说明有一个字

52、， t1读出读出后到后到达终态，而达终态，而t2读出读出后不能到达终态，或后不能到达终态，或者反之，那么对于字者反之，那么对于字a ， s1读出读出a后后到达终态，而到达终态，而s2读出读出a不能到达终态，不能到达终态，或者反之，所以或者反之，所以s1和和s2不等价。不等价。s1t1as2t2a j in则将则将I(i)分成两半，使得一半含有分成两半，使得一半含有s1 :n I(i1)=s|sI(i)且且s经经a弧到达弧到达t, n 且且t与与t1属于现行属于现行中的同一子集中的同一子集n 另一半含有另一半含有s2 : I(i2)=I(i)-I(i1)s1t1as2t2a j in一般地，对某

53、个一般地，对某个a和和I(i)，若，若Ia(i) 落入现行落入现行中中 N个不同子集，则应把个不同子集，则应把I(i)划分成划分成N个不相个不相交的组，使得每个组交的组，使得每个组J的的Ja都落入的都落入的同一同一子集。这样构成新的划分。子集。这样构成新的划分。n重复上述过程，直到重复上述过程，直到所含子集数不再增长。所含子集数不再增长。n对于上述最后划分对于上述最后划分中的每个子集，我们选中的每个子集，我们选取每个子集取每个子集I中的一个状态代表其他状态，中的一个状态代表其他状态，则可得到化简后的则可得到化简后的DFA M。n若若I含有原来的初态，则其代表为新的初态，含有原来的初态，则其代表

54、为新的初态，若若I含有原来的终态，则其代表为新的终态。含有原来的终态，则其代表为新的终态。0123546aabbbabaabababI(1)=0, 1, 2 I(2)=3, 4, 5, 6 Ia(1) =1, 3 I(11) =0, 2 I(12) =1I(2)=3, 4, 5, 6 I(11) =0, 2Ia(11) =1 Ib(11) =2, 5 I(111) =0 I(112) =2 I(12) =1 I(2)=3, 4, 5, 6 Ia(2) =3, 6 Ib(2) =4, 5 0123546aabbbabaababab0123aabbbaabFA正规集正规集正规式正规式DFANFA3

55、.3.13.3.23.3.33.3.5DFA3.3.685一一. .原理原理 单词的词法规则用正规式描述单词的词法规则用正规式描述 正规式正规式 NFA NFA DFA DFA min DFAmin DFALEXLEX编译器编译器LEXLEX源程序源程序lex.1lex.1词法分析程序词法分析程序Lex.yy.c二二. .用用LEXLEX建立词法分析程序的过程建立词法分析程序的过程3.4 词法分析器的自动产生词法分析器的自动产生-LEXC编译器编译器词法分析程序词法分析程序Lex.yy.c词法分析程序词法分析程序Lex.out或或lex.exe 词法分析程序词法分析程序L L单词符号单词符号输

56、入串输入串状态转换矩阵状态转换矩阵控制执行程序控制执行程序3.4 词法分析器的自动产生词法分析器的自动产生-LEX3.4 词法分析器的自动产生词法分析器的自动产生-LEXlexlex源程序源程序 lex lex源程序由三部分组成源程序由三部分组成声明声明% % 识别规则识别规则( (翻译规则）翻译规则）%辅助过程辅助过程 声明包括变量，符号常量和正规定义式。声明包括变量，符号常量和正规定义式。正规定义式是形式如下的一系列定义：正规定义式是形式如下的一系列定义： d1 d1 r1 r1 d2 d2 r2 r2 dn dn rn rn其中，其中， di di 表示不同的名字，表示不同的名字， ri ri 是正规式是正规式识别规则翻译规则的形式为：识别规则翻译规则的形式为： p1 p1 动作动作1 1 p2 p2 动作动作22 p n p n 动作动作nn 每个每个pi是一个正规式，称为词形。是一个正规式，称为词形。 每个每个动作动