精品课程《编译原理》Chapt3词法分析ppt课件

1、复习：程序文语的语法描画复习：程序文语的语法描画 n几个概念几个概念: :n思索一个有穷思索一个有穷 字母表字母表 字符集字符集n其中每一个元素称为一个字符其中每一个元素称为一个字符n上的字上的字( (也叫字符串也叫字符串) ) 是指由是指由中的字中的字符所构成的一个有穷序列符所构成的一个有穷序列n不包含任何字符的序列称为空字，记为不包含任何字符的序列称为空字，记为n用用* *表示表示上的一切字的全体上的一切字的全体, ,包含空字包含空字复习：程序文语的语法描画复习：程序文语的语法描画 n*的子集的子集U和和V的衔接积定义为的衔接积定义为nUV | U & V nV本身的本身的 n次积

2、记为次积记为nVn=VVVn规定规定V0=，令，令n V*=V0V1V2V3 n称称V*是是V的闭包的闭包;n记记 VVV* ，称，称V+是是V的正规闭包。的正规闭包。复习：程序文语的语法描画复习：程序文语的语法描画 n上下文无关文法的定义：上下文无关文法的定义： n一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式n G=(VTG=(VT，VNVN，S S，P)P)，其中，其中nVTVT：终结符集合：终结符集合( (非空非空) )nVNVN：非终结符集合：非终结符集合( (非空非空) )，且，且VT VT VN= VN=nS S：文法的开场符号，：文法的开场符号，S SVNV

3、NnP P：产生式集合：产生式集合( (有限有限) )，每个产生式方式为，每个产生式方式为nP P， P PVNVN， (VT (VT VN) VN)* *n开场符开场符S S至少必需在某个产生式的左部出现一次。至少必需在某个产生式的左部出现一次。复习：程序文语的语法描画复习：程序文语的语法描画 n定义：称定义：称A直接推出直接推出，即，即nAn 仅当仅当A 是一个产生式，是一个产生式，n 且且， (VT VN)* 。n假设假设1 2 n，那么我们称，那么我们称这个序列是从这个序列是从1到到n的一个推导。假设的一个推导。假设存在一个从存在一个从1到到n的推导，那么称的推导，那么称1可可以推导出

4、以推导出n 。n通常，用通常，用 表示：从表示：从1 1出发，经过出发，经过一步或假设干步，可以推出一步或假设干步，可以推出n n。n1n*1 用用 表示：从表示：从1 1出发，经过出发，经过0 0步步或假设干步，可以推出或假设干步，可以推出n n。* 所以所以 ： 即即 或或*S ,|)(*TV SGLq定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开场符号。是它的开场符号。假设假设 ，那么，那么称是一个句型。仅含终称是一个句型。仅含终结符号的句型是一个句子。文法结符号的句型是一个句子。文法G G所产生的句子所产生的句子的全体是一个言语，将它记为的全体是一个言语，将它记为

5、L(G)L(G)。复习：程序文语的语法描画复习：程序文语的语法描画 n最左推导：任何一步最左推导：任何一步 都是对都是对中的中的最左非终结符进展交换。最左非终结符进展交换。n 最右推导：任何一步最右推导：任何一步 都是对都是对中中的最右非终结符进展交换。的最右非终结符进展交换。复习：程序文语的语法描画复习：程序文语的语法描画 n用一张图表示一个句型的推导用一张图表示一个句型的推导,称为语法树。称为语法树。Ei+*()EiiEEEEE (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E (E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)复习：程序文语的语

6、法描画复习：程序文语的语法描画 n定义：假设一个文法存在某个句子对应两定义：假设一个文法存在某个句子对应两颗不同的语法树，那么说这个文法是二义颗不同的语法树，那么说这个文法是二义的。的。n言语的二义性：一个言语是二义性的，假言语的二义性：一个言语是二义性的，假设对它不存在无二义性的文法。设对它不存在无二义性的文法。复习：程序文语的语法描画复习：程序文语的语法描画 n方式言语鸟瞰方式言语鸟瞰n0型型(短语文法，图灵机短语文法，图灵机)：n 产生式形如：产生式形如： n 其中：其中： (VT VN)*且至少含有一个且至少含有一个非终结符；非终结符； (VT VN)*n1型型(上下文有关文法，线性界

7、限自动机上下文有关文法，线性界限自动机)：n 产生式形如：产生式形如： n 其中：其中：| |，仅，仅 S 例外。例外。复习：程序文语的语法描画复习：程序文语的语法描画 n方式言语鸟瞰方式言语鸟瞰n2型型(上下文无关文法，非确定下推自动机上下文无关文法，非确定下推自动机)：n 产生式形如：产生式形如： A n 其中：其中：A VN； (VT VN)*。n3型型(正规文法，有限自动机正规文法，有限自动机)：n 产生式形如：产生式形如： A B 或或 A n 其中：其中： VT*；A，BVNn 产生式形如：产生式形如： A B 或或 A n 其中：其中： VT*；A，BVN第三章第三章 词法分析词

8、法分析n词法分析的义务：从左至右逐个字符地词法分析的义务：从左至右逐个字符地对源程序进展扫描，产生一个个单词符对源程序进展扫描，产生一个个单词符号。号。n词法分析器词法分析器(Lexical Analyzer) (Lexical Analyzer) 又称扫又称扫描器描器(Scanner)(Scanner)：执行词法分析的程序：执行词法分析的程序3.13.1 对于词法分析器的要求对于词法分析器的要求一、词法分析器的功能和输出方式一、词法分析器的功能和输出方式功能功能: :输入源程序、输出单词符号输入源程序、输出单词符号单词符号的种类：单词符号的种类：根本字：如根本字：如 begin begin，

9、repeatrepeat，标识符标识符表示各种名字：如变量名、数表示各种名字：如变量名、数组名和过程名组名和过程名常数：各种类型的常数常数：各种类型的常数运算符：运算符：+ +，- -，* *，/ /，界符：逗号、分号、括号和空白界符：逗号、分号、括号和空白n输出的单词符号的表示方式输出的单词符号的表示方式: :n( (单词种别，单词本身的值单词种别，单词本身的值) )n单词种别通常用整数编码表示。单词种别通常用整数编码表示。n假设一个种别只需一个单词符号，那么种假设一个种别只需一个单词符号，那么种别编码就代表该单词符号。假定根本字、别编码就代表该单词符号。假定根本字、运算符和界符都是一符一种

10、。运算符和界符都是一符一种。n假设一个种别有多个单词符号，那么对于假设一个种别有多个单词符号，那么对于每个单词符号，给出种别编码和本身的值。每个单词符号，给出种别编码和本身的值。n标识符单列一种；标识符本身的值表示成标识符单列一种；标识符本身的值表示成按机器字节划分的内部码。按机器字节划分的内部码。n常数按类型分种；常数的值那么表示成规常数按类型分种；常数的值那么表示成规范的二进制方式。范的二进制方式。例例 C C程序程序n while (i=j) i-;n输出单词符号：输出单词符号：nnnn=, - nnnnn例例 FORTRANFORTRAN程序程序nIF (5.EQ.M) GOTO 10

11、0IF (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词法分析是作为一个独立的阶段，能否词法分析是作为一个独立的阶段，能否该当将其处置为一遍呢？该当将其处置为一遍呢？n作为独立阶段

12、的优点：构造简约、明晰作为独立阶段的优点：构造简约、明晰和条理化，有利于集中思索词法分析一和条理化，有利于集中思索词法分析一些枝节问题。些枝节问题。n不作为一遍：将其处置为一个子程序。不作为一遍：将其处置为一个子程序。词法分析器词法分析器词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.词法分析器的构造词法分析器的构造预处置预处置子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表3.2 词法分析器的设计n输入串放在输入缓冲区中。输入串放在输入缓冲区中。n预处置子程序：剔除无用的空白、跳格、预处置子

13、程序：剔除无用的空白、跳格、回车和换行等编辑性字符回车和换行等编辑性字符; ;区分标号区、区分标号区、捻接续行和给出句末符等捻接续行和给出句末符等n扫描缓冲区扫描缓冲区 起点起点 搜索搜索指示器指示器 指示器指示器一、输入、预处置一、输入、预处置 WhatALongWord WhatALongWo rdrd WhatALongWord WhatALongWo二、单词符号的识别二、单词符号的识别: :超前搜索超前搜索1 根本字识别根本字识别:例如例如:DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10I

14、F(5)=55需求超前搜索才干确定哪些是根本字需求超前搜索才干确定哪些是根本字2 标识符识别标识符识别:字母开头的字母数字串，后跟界符或算符字母开头的字母数字串，后跟界符或算符3 常数识别常数识别:识别出算术常数并将其转变为二进制内码识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。表示。有些也要超前搜索。 5.EQ.M 5.E084 算符和界符的识别算符和界符的识别把多个字符符合而成的算符和界符拼合成把多个字符符合而成的算符和界符拼合成一个单一单词符号。一个单一单词符号。:=， *， .EQ. ， +，-，=三、形状转换图三、形状转换图1 1 概念概念形状转换图是一张有限方向图。形

15、状转换图是一张有限方向图。213XY结点代表形状，用圆圈表示。结点代表形状，用圆圈表示。形状之间用箭弧连结，箭弧形状之间用箭弧连结，箭弧上的标志上的标志( (字符字符) )代表射出结代表射出结形状下能够出现的输入字符形状下能够出现的输入字符或字符类。或字符类。一张转换图只包含有限个形状，其中一张转换图只包含有限个形状，其中有一个为初态，至少要有一个终态。有一个为初态，至少要有一个终态。识别标识符的形状转换图识别标识符的形状转换图123字母字母其他其他字母或数字字母或数字*识别整常数的形状转换图识别整常数的形状转换图123数字数字其他其他数字数字*n一个形状转换图可用于识别一个形状转换图可用于识

16、别( (或接受或接受) )一定一定的字符串。的字符串。2 2 例子例子q助忆符：直接用编码表示不便于记忆，助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。因此用助忆符来表示编码。单单 词词 符符 号号 种种 别别 编编 码码 助助 忆忆 符符 内内 码码 值值 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 $

17、$I ID D 内内 部部 字字 符符 串串 常常 数数 ( (数数 ) ) 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 - -

18、1 12 23 34 45 56 67 78 89 910101111121213130 0空白空白字母字母字母或数字字母或数字非字母与数字非字母与数字数字数字非数字非数字数字数字= =+ +* *非非* *, ,( () )其它其它* * * * *n几点重要限制几点重要限制不用运用超前搜索不用运用超前搜索n一切根本字都是保管字一切根本字都是保管字;用户不能用它们用户不能用它们作本人的标识符作本人的标识符n根本字作为特殊的标识符来处置根本字作为特殊的标识符来处置;不用特不用特殊的形状图来识别，只需查保管字表。殊的形状图来识别，只需查保管字表。n假设根本字、标识符和常数假设根本字、标识符和常数

19、(或标号或标号)之间之间没有确定的运算符或界符作间隔，那么必没有确定的运算符或界符作间隔，那么必需运用一个空白符作间隔。需运用一个空白符作间隔。nDO99K=1，10 n要写成要写成 DO 99 K=1，103 形状转换图的实现形状转换图的实现思想：每个形状结对应一小段程序。思想：每个形状结对应一小段程序。做法做法:1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASE语句语句或一组或一组IF-THEN-ELSE语句实现语句实现GetChar( );if (IsLetter( ) 形状形状j的对应程序段的对应程序段;else if (IsDigit( ) 形状形状k的对应程序段的

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

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

22、IsLetter和和 IsDisgital 布尔函数，布尔函数，判别判别ch中字符能否为字母和数字中字符能否为字母和数字7) Reserve 整型函数，对于整型函数，对于 strToken 中的字符串查找保管字表，假设它实保管中的字符串查找保管字表，假设它实保管字那么给出它的编码，否那么回送字那么给出它的编码，否那么回送08) Retract 子程序，把搜索指针回调一子程序，把搜索指针回调一个字符位置个字符位置9)InsertId 整型函数，将整型函数，将strToken中中的标识符插入符号表，前往符号表指针的标识符插入符号表，前往符号表指针10)InsertConst 整型函数过程，将整型函

23、数过程，将strToken中的常数插入常数表，前往常中的常数插入常数表，前往常数表指针。数表指针。 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, value);endelser

24、eturn (code, -);endelse if (IsDigit()beginwhile (IsDigit()beginConcat( ); GetChar( );endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) return ($PLUS, -);else if (ch =*)beginGetChar();if (ch =*) return ($POWER, -);Retract(); return (

25、$STAR, -);endelse if (ch =;) return ($SEMICOLON, -);else if (ch =() return ($LPAR, -);else if (ch =) return ($RPAR, -);else ProcError( );/* 错误处置错误处置*/3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机n几个概念几个概念: :n思索一个有穷思索一个有穷 字母表字母表 字符集字符集n其中每一个元素称为一个字符其中每一个元素称为一个字符n上的字上的字( (也叫字符串也叫字符串) ) 是指由是指由中的字中的字符所构成的一个有穷序列符所构成的一个

26、有穷序列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 | U & V nV本身的本身的 n次积记为次积记为nVn=VVVn规定规定V0=，令，令n V*=V0V1V2V3 n称称V*是是V的闭包的闭包;n记记 VVV* ，称，称V+是是V的正规闭包。的正规闭包。3.3.1 正规

27、式和正规集正规式和正规集n正规集可以用正规表达式简称正规式正规集可以用正规表达式简称正规式表示。表示。n正规表达式是表示正规集一种方法。一正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规个字集合是正规集当且仅当它能用正规式表示。式表示。冯-诺伊曼构造自然数的方案n 0n1n, 2n, , , 3n正规式和正规集的递归定义：正规式和正规集的递归定义：n对给定的字母表对给定的字母表 n1)1) 和和都是都是 上的正规式，它们所表上的正规式，它们所表示的正规集为示的正规集为 和和; ;n2) 2) 任何任何a a ，a a是是 上的正规式，它所上的正规式，它所表示的正规集为表示的

28、正规集为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)*为正规式，它所表示的正规集为为正规式，它所表示的正规集为(L(e1)*，仅由有限次运用上述三步骤而定义的表达式才仅由有限次运用上述三步骤而定义的表达式才是是 上的正规式，仅由这些正规式表示的字集上的正规式，仅由这些正规式表示的

29、字集才是才是 上的正规集。上的正规集。n一切词法构造普通都可以用正规式描画。一切词法构造普通都可以用正规式描画。n假设两个正规式所表示的正规集一样，那假设两个正规式所表示的正规集一样，那么称这两个正规式等价。如么称这两个正规式等价。如nb(ab)b(ab)* *=(ba)=(ba)* *b b(a(a* *b b* *) )* *=(a|b)=(a|b)* *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

30、(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 = e2|e1 交换律交换律ne1 |(e2|e3) = (e1|e2)|e3 结合律结合律ne1(e2e3) = (e1e2)e3 结合律结合律ne1(e2|e3) = e1e2|e1e3 分配律分配律n(e2|e3)e1 = e2e1|e3 e

31、1分配律分配律ne = e = e e1e2 e2 e1 L(e1|e2) = L(e1 ) L(e2)= L(e2 ) L(e1)= L(e2|e1)正规集正规集正规式正规式3.3.13.3.2 确定有限自动机确定有限自动机(DFA)n对形状图进展方式化，那么可以下定义：对形状图进展方式化，那么可以下定义：n自动机自动机M M是一个五元式是一个五元式M=(S, M=(S, , f, S0, F), f, S0, F),其中：其中：n1. S: 1. S: 有穷形状集，有穷形状集，n2. 2. ：输入字母表：输入字母表( (有穷有穷) )，n3. f: 3. f: 形状转换函数，为形状转换函数

32、，为S SS S的单值部的单值部分映射，分映射，f(sf(s，a)=sa)=s表示：当现行形状为表示：当现行形状为s s，输入字符为，输入字符为a a时，将形状转换到下一形时，将形状转换到下一形状状ss。我们把。我们把ss称为称为s s的一个后继形状。的一个后继形状。n4. S04. S0S S是独一的一个初态；是独一的一个初态； 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)=3

33、nf(3，a)=3 f(3，b)=3ab012132213333形状转换矩阵形状转换矩阵0312aaaa形状转换图形状转换图bbbbnDFA可以表示为形状转换图。假定可以表示为形状转换图。假定DFA M含有含有m个形状和个形状和n个输入字符，那么，这个输入字符，那么，这个图含有个图含有m个形状结点，每个结点顶多含个形状结点，每个结点顶多含有有n条箭弧射出，且每条箭弧用条箭弧射出，且每条箭弧用上的不同上的不同的输入字符来作标志。的输入字符来作标志。n对于对于 * *中的任何字中的任何字，假设存在一条从初，假设存在一条从初态到某一终态的道路，且这条路上一切弧态到某一终态的道路，且这条路上一切弧上的

34、标志符衔接成的字等于上的标志符衔接成的字等于，那么称，那么称为为DFA MDFA M所识别所识别( (接纳接纳) )nDFA MDFA M所识别的字的全体记为所识别的字的全体记为L(M)L(M)。n可以证明：可以证明： 上的字集上的字集V V* *是正规集，当是正规集，当且仅当存在上的且仅当存在上的DFA MDFA M，使得，使得V VL(M)L(M)。3.3.3 3.3.3 非确定有限自动机非确定有限自动机(NFA) (NFA) n定义：一个非确定有限自动机定义：一个非确定有限自动机(NFA) M(NFA) M是是一个五元式一个五元式M=(S, M=(S, , f, S0, F), f, S

35、0, F)，其中：，其中：n1 S: 1 S: 有穷形状集；有穷形状集；n2 2 ：输入字母表：输入字母表( (有穷有穷) )；n3 f: 3 f: 形状转换函数，为形状转换函数，为S S* *2S2S的的部分映射部分映射( (非单值非单值) )；n4 S04 S0S S是非空的初态集；是非空的初态集；n5 F 5 F S S ：终态集：终态集( (可空可空) )。n从形状图中看从形状图中看NFA NFA 和和DFADFA的区别：的区别：n 1 1 弧上的标志可以是弧上的标志可以是 * *中的一个字，中的一个字，而不一定是单个字符；而不一定是单个字符；n 2 2 同一个字能够出如今同形状射出的

36、同一个字能够出如今同形状射出的多条弧上。多条弧上。nDFADFA是是NFANFA的特例。的特例。021 a，baaa，bbba，b012abab识别一切含相继两个识别一切含相继两个a a或相继两个或相继两个b b的字的字ambn | m，n1n定义：对于任何两个有限自动机定义：对于任何两个有限自动机M和和M，假设假设L(M)=L(M)，那么称，那么称M与与M等价。等价。n自动机实际中一个重要的结论：断定两自动机实际中一个重要的结论：断定两个自动机等价性的算法是存在的。个自动机等价性的算法是存在的。n对于每个对于每个NFA M存在一个存在一个DFA M，使，使得得 L(M)=L(M)。亦即。亦即

37、DFA与与NFA描画描画才干一样。才干一样。1. 假定假定NFA M=，我们对，我们对M的形状转换图进展以下改造：的形状转换图进展以下改造： 1) 引进新的初态结点引进新的初态结点X和终态结点和终态结点Y，X,YS， 从从X到到S0中恣意形状结点连一条中恣意形状结点连一条箭弧，箭弧， 从从F中恣意形状结点连一条中恣意形状结点连一条箭弧到箭弧到Y。 2) 对对M的形状转换图进一步施行交换，其中的形状转换图进一步施行交换，其中k是新引入的形状。是新引入的形状。证明证明:代之为代之为ikABjijAB代之为代之为ijA|BijBA代之为代之为ijA*ik jA按下面的三条规那么对按下面的三条规那么对

38、V进展分裂进展分裂:n逐渐把这个图转变为每条弧只标志为逐渐把这个图转变为每条弧只标志为 上的上的一个字符或一个字符或，最后得到一个，最后得到一个NFA M，显然显然L(M)=L(M)n识别一切含相继两个识别一切含相继两个a或相继两个或相继两个b的字的字XY 514236ab ababab5126ab abaabb2. 把上述把上述NFA确定化确定化采用子集法采用子集法.设设I是的形状集的一个子集，定义是的形状集的一个子集，定义I的的-闭包闭包-closure(I)为为: i) 假设假设sI，那么，那么s-closure(I)； ii) 假设假设sI，那么从，那么从s出发经过恣意条出发经过恣意条

39、弧弧而能到达的任何形状而能到达的任何形状s都属于都属于-closure(I) 即即 -closure(I)=Is|从某个从某个sI出发经过出发经过恣意条恣意条弧能到达弧能到达sn设设a是是 中的一个字符，定义中的一个字符，定义nIa= -closure(J)n 其中，其中，J为为I中的某个形状出发经过一条中的某个形状出发经过一条a弧而到达的形状集合。弧而到达的形状集合。n -closure(1)=1，2=I n J=5，4，3n Ia= -closure(J)= -closure(5，4，3)n =5，4，3，6，2，7，861a 234578aa n设设a是是中的一中的一个字符，定义个字符，

40、定义nIa= -closure(J)n 其中，其中，J为为I中的中的某个形状出发经某个形状出发经过一条过一条a弧而到弧而到达的形状集合。达的形状集合。n把确定化的过程把确定化的过程: :n 不失普通性，设字母表只包含两个不失普通性，设字母表只包含两个a a和和b b，我们构造一张表，我们构造一张表: :IIaIb -Closure(X)首先，置第首先，置第1行第行第1列为列为-closure(X)求出求出这一列的这一列的Ia，Ib；然后，检查这两个然后，检查这两个Ia，Ib，看它们能否已，看它们能否已在表中的第一列中出现，把未曾出现的填在表中的第一列中出现，把未曾出现的填入后面的空行的第入后面

41、的空行的第1列上，求出每行第列上，求出每行第2，3列上的集合列上的集合.反复上述过程，知道一切第反复上述过程，知道一切第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,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如今把这张表看成

42、一个形状转换矩阵，把如今把这张表看成一个形状转换矩阵，把其中的每个子集看成一个形状。其中的每个子集看成一个形状。n这张表独一刻划了一个确定的有限自动机这张表独一刻划了一个确定的有限自动机M，它的初态是，它的初态是-closure(X) ，它的终，它的终态是含有原终态态是含有原终态Y的子集。的子集。n不难看出，这个不难看出，这个DFA M与与M等价。等价。Iab0121322143344655656340123546aabbbabaabababFA正规集正规集正规式正规式DFANFA正规文法正规文法3.3.13.3.23.3.33.3.43.3.4 正规文法与有限自动机的等价性正规文法与有限自动

43、机的等价性n对于正规文法对于正规文法G和有限自动机和有限自动机M，假设，假设L(G)L(M)，那么称，那么称G和和M是等价的。关是等价的。关于正规文法和有限自动机的等价性，有于正规文法和有限自动机的等价性，有以下结论：以下结论：3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性n定理：定理：n 1.对每一个右线性正规文法对每一个右线性正规文法G或左线性或左线性正规文法正规文法G，都存在一个有限自动机，都存在一个有限自动机(FA) M，使得，使得L(M)L(G)。n 2.对每一个对每一个FA M，都存在一个右线性正，都存在一个右线性正规文法规文法GR和左线性正规文法和左线性正规

44、文法GL，使得，使得L(M)L(GR)L(GL)。n证明：证明： n 1. 1. 对每一个右线性正规文法对每一个右线性正规文法G G或左线性或左线性正规文法正规文法G G，都构造一个有限自动机，都构造一个有限自动机FAFA M M，使得，使得L(M)L(M)L(G)L(G)。n(1) (1) 设右线性正规文法设右线性正规文法G=VT, VN, S, P G= 。将。将VNVN中的每一非终结符号视为形状符中的每一非终结符号视为形状符号，并添加一个新的终结形状符号号，并添加一个新的终结形状符号f f，f fVNVN。n 令令M=VNf, VT, M=, S, f，其中形状转换函数其中形状转换函数由

45、以下规那么定义：由以下规那么定义：(a) 假设对某个假设对某个AVN及及aVT，P中有产生式中有产生式Aa，那么令，那么令(A,a)=f(b) 对恣意的对恣意的AVN及及aVT，设，设P中左端为中左端为A，右端第一符号为，右端第一符号为a的一切的一切产生式为：产生式为：AaA1|aAk 不包括不包括Aa， 那么令那么令(A,a)=A1,Ak。 显然，上述显然，上述M是一个是一个NFA。对于右线性正规文法对于右线性正规文法G，在，在S w的最左推的最左推导过程中导过程中:利用利用AaB一次就相当于在一次就相当于在M中从形状中从形状A经经过标志为过标志为a的箭弧到达形状的箭弧到达形状B包括包括a=

46、的的情形情形;在推导的最后，利用在推导的最后，利用Aa一次那么相当于在一次那么相当于在M中从形状中从形状A经过标志为经过标志为a的箭弧到达终结形的箭弧到达终结形状状f包括包括a=的情形。的情形。综上，在正规文法综上，在正规文法G中，中，S w的充要条件的充要条件是：在是：在M中，从形状中，从形状S到形状到形状f有一条通路，有一条通路，其上一切箭弧的标志符号依次衔接起来恰好其上一切箭弧的标志符号依次衔接起来恰好等于等于w，这就是说，这就是说，wL(G)当且仅当当且仅当wL(M)，故，故L(G)L(M)。(2) 设左线性正规文法设左线性正规文法G=。将。将VN中的每一符号视为形状符号，并添加一中的

47、每一符号视为形状符号，并添加一个初始形状符号个初始形状符号q0，q0VN。 令令M=，其中，其中形状转换函数形状转换函数由以下规那么定义：由以下规那么定义：(a) 假设对某个假设对某个AVN及及aVT，假设，假设P中有产生式中有产生式Aa，那么令，那么令(q0,a)=A(b) 对恣意的对恣意的AVN及及aVT，假设，假设P中一切右端第一符号为中一切右端第一符号为A，第二个符号为，第二个符号为a的产生式为：的产生式为：A1Aa, , AkAa， 那么令那么令(A,a)=A1,Ak。与与(1)类似，可以证明类似，可以证明L(G)L(M)。nGR(A) ：nA0 | 0B | 1DnB0D | 1C

48、nC0 | 0B | 1DnD0D | 1Dn从从GR出发构造出发构造NFA M = ，M的形状转的形状转换图如右图所示。换图如右图所示。n显然显然 L(M) = L(GR)。例例:ABCD100,1110f0003.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性n定理：定理：n 1.对每一个右线性正规文法对每一个右线性正规文法G或左线性或左线性正规文法正规文法G，都存在一个有限自动机，都存在一个有限自动机(FA) M，使得，使得L(M)L(G)。n 2.对每一个对每一个FA M，都存在一个右线性正，都存在一个右线性正规文法规文法GR和左线性正规文法和左线性正规文法GL，使得

49、，使得L(M)L(GR)L(GL)。证明证明2：对每一个：对每一个DFA M，都存在一个右线，都存在一个右线性正规文法性正规文法GR和左线性正规文法和左线性正规文法GL，使，使得得L(M)L(GR)L(GL)。 设设DFA M= (1) 假设假设s0F，我们令，我们令GR=，其中其中P是由以下规那么定义的产生式集合：是由以下规那么定义的产生式集合：对任何对任何a及及A,BS，假设有，假设有(A,a)=B，那么：那么： (a) 当当BF时，令时，令AaB， (b) 当当BF时，令时，令Aa|aB。对任何对任何w*，无妨设，无妨设w=a1ak，其中，其中ai (i=1,k)。假设。假设s0 w，那

50、么存在一，那么存在一个最左推导：个最左推导： s0a1A1a1a2A2a1aiAia1ai+1Ai+1a1ak因此，在因此，在M中有一条从中有一条从s0出发依次经过出发依次经过A1，Ak-1到达终态的通路，该通路上一到达终态的通路，该通路上一切箭弧的标志依次为切箭弧的标志依次为a1,ak。反之亦然。反之亦然。所以，所以，wL(GR)当且仅当当且仅当wL(M)。q 如今思索如今思索s0F的情形：的情形：q 由于由于(s0, )=s0，所以，所以L(M)。但。但不属不属于上面构造的于上面构造的GR所产生的言语所产生的言语L(GR)。不难发现，。不难发现，L(GR)=L(M)-。q 所以，我们在上述

51、所以，我们在上述GR中添加新的非终结符号中添加新的非终结符号s0，(s0S)和产生式和产生式s0s0|，并用，并用s0替代替代s0作开场符号。这样修正作开场符号。这样修正GR后得到的文法后得到的文法GR仍是右线性正规文法，并且仍是右线性正规文法，并且L(GR)=L(M)。q (2) 类似于类似于(1)，从，从DFA M出发可构造左线性正出发可构造左线性正规文法规文法GL，使得，使得L(GL)=L(M)。q 最后，由最后，由DFA和和NFA之间的等价性，结论之间的等价性，结论2得证。得证。假设有假设有(A,a)=B：(a) 当当A= q0时，令时，令Ba，(b) 当当A q0时，令时，令BAan

52、L(M) = 0(10)*nGR = ，其中，其中P由以下产生由以下产生式组成：式组成：nA0 | 0B | 1DnB0D | 1CnC0 | 0B | 1DnD0D | 1DnL(GR) = L(M) = 0(10)*例例3.4 设设DFA M = 。M的形状转换图如以下图所示。的形状转换图如以下图所示。ABCD100,11100n从从NFA M出发构造左线性出发构造左线性正规文法正规文法GL = ，其中，其中P由以下产生式组成：由以下产生式组成：nf0 | C0nCB1nB0 | C0nD1 | C1 | D0 | D1 | B0n易证易证 L(GL) = L(M)。例例3.4 设设DFA

53、 M = 。M的形状转换图如图的形状转换图如图3.9(a)所示。所示。ABCD100,1110f000FA正规集正规集正规式正规式DFANFA正规文法正规文法3.3.13.3.23.3.33.3.43.3.53.3.5 3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性n定理：定理：n 1. 对任何对任何FA M，都存在一个正规式，都存在一个正规式r，使得使得L(r)=L(M)。n 2. 对任何正规式对任何正规式r，都存在一个，都存在一个FA M，使得使得L(M)=L(r)。n对转换图概念拓广，令每条弧可用一个对转换图概念拓广，令每条弧可用一个正规式作标志。正规式作标志。(对一类

54、输入符号对一类输入符号)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，记为，记为MM，它只需一个初，它只需一个初态态X X和一个终态和一个终态Y Y，显然，显然L(M)=L(M)L(M)=L(M)。n然后，反复运用

55、下面的一条规那么，逐渐然后，反复运用下面的一条规那么，逐渐消去的一切结点，直到只剩下消去的一切结点，直到只剩下X X和和Y Y为止；为止；代之为代之为ijr1r2kikr1r2代之为代之为ijr1|r2ijr2r1代之为代之为ikr1r2*r2ijr1r3kr212354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1q最后，最后，X到到Y的弧上标志的正规式即为的弧上标志的正规式即为所构造的正规式所构造的正规式rq显然显然L(r)=L(M)=L(M)n证明证明2: 对于对于 上的正规式上的正规式r，构造一个，构造一

56、个NFA M，使，使L(M)=L(r)，并且，并且M只需一个只需一个终态，而且没有从该终态出发的箭弧。终态，而且没有从该终态出发的箭弧。n 下面运用关于下面运用关于r中运算符数目的归纳法中运算符数目的归纳法证明上述结论。证明上述结论。n(1) 假设假设r具有零个运算符，那么具有零个运算符，那么r=或或r=或或r=a，其中，其中a。此时以下图所示。此时以下图所示的三个有限自动机显然符合上述要求。的三个有限自动机显然符合上述要求。q0q0qfaq0qf(2) 假设结论对于少于假设结论对于少于k(k1)个运算符的正个运算符的正规式成立。规式成立。 当当r中含有中含有k个运算符时，个运算符时，r有三种

57、情形：有三种情形：情形情形1：r=r1|r2，r1,r2中运算符个数少于中运算符个数少于k。从而，由归纳假设，对从而，由归纳假设，对ri存在存在Mi=，使得，使得L(Mi)=L(ri)，并且，并且Mi没没有从终态出发的箭弧有从终态出发的箭弧i=1,2。无妨设。无妨设S1S2=，在，在S1 S2中参与两个新形状中参与两个新形状q0，f0。 令令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的形状转换如右图所示。

58、的形状转换如右图所示。 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), 当当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=，其，其

59、中中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) 构造构造 上的上的NFA M NFA M 使得使得 L(V)=L(M) L(V)=L(M)首先，把首先，把V V表示成表示成XYV上述证明过程本质上是一个将正规表达式上述证明过程本质上是一个将正规表达式转换为有限自动机的算法。转换为有限自动机的算法。代之为代之为i

60、jV1V2kikV1V2代之为代之为ijV1|V2ijV2V1代之为代之为ikV1*ij kV1然后，按下面的三条规那么对然后，按下面的三条规那么对V进展分裂进展分裂n逐渐把这个图转变为每条弧只标志为逐渐把这个图转变为每条弧只标志为 上的上的一个字符或一个字符或，最后得到一个，最后得到一个NFA M，显然显然L(M)=L(V)n(a|b)*(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