1、国防科技大学计算机系国防科技大学计算机系602教研室教研室复习：复习：程序语言的语法描述程序语言的语法描述 n几个概念几个概念:考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集其中每一个元素称为一个其中每一个元素称为一个字符字符上的上的字字(也叫也叫字符串字符串)是指由是指由中的字符所构中的字符所构成的一个有穷序列成的一个有穷序列不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为用用*表示表示上的所有字的全体上的所有字的全体,包含空字包含空字国防科技大学计算机系国防科技大学计算机系602教研室教研室复习：复习：程序语言的语法描述程序语言的语法描述 n*的子集的子集U和和V
2、的的连接连接（积积）定义为）定义为UV|U&V nV自身的自身的 n次积记为次积记为Vn=VVVn规定规定V0=，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包;n记记 VVV*，称，称V+是是V的正规闭包。的正规闭包。国防科技大学计算机系国防科技大学计算机系602教研室教研室复习：复习：程序语言的语法描述程序语言的语法描述 n上下文无关文法的定义：上下文无关文法的定义：一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中V VT T：终结符集合：终结符集合(非空非空)V VN N：非终结符集合：非终
3、结符集合(非空非空)，且，且V VT T V VN N=S S：文法的开始符号，：文法的开始符号，S S V VN NP P：产生式集合：产生式集合(有限有限)，每个产生式形式为，每个产生式形式为P P，P P V VN N，(V VT T V VN N)*开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。国防科技大学计算机系国防科技大学计算机系602教研室教研室复习：复习：程序语言的语法描述程序语言的语法描述 n定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式，且且，(VT VN)*。n如果如果 1 2 n，则
4、我们称这个序，则我们称这个序列是从列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n。国防科技大学计算机系国防科技大学计算机系602教研室教研室n通常，用通常，用 表示：从表示：从 1 1出发，经过出发，经过一步或若干步，可以推出一步或若干步，可以推出 n n。n1n*1 用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步，可以推出若干步，可以推出 n n。*所以所以 ：即即 或或*S,|)(*TV SGLq定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号
5、。如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全所产生的句子的全体是一个体是一个语言语言，将它记为，将它记为 L(G)L(G)。国防科技大学计算机系国防科技大学计算机系602教研室教研室复习：复习：程序语言的语法描述程序语言的语法描述 n最左推导最左推导：任何一步：任何一步 都是对都是对 中的最中的最左非终结符进行替换。左非终结符进行替换。最右推导最右推导：任何一步：任何一步 都是对都是对 中的最中的最右非终结符进行替换。右非终结符进行替换。国防科技大学计算机系国防科技大学计算机系602教研室教研室复习
6、：复习：程序语言的语法描述程序语言的语法描述 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)国防科技大学计算机系国防科技大学计算机系602教研室教研室复习：复习：程序语言的语法描述程序语言的语法描述 n定义定义：如果一个文法存在某个句子对应两如果一个文法存在某个句子对应两颗不同的语法树颗不同的语法树，则说这个则说这个文法是二义的文法是二义的。n语言的二义性：一个语言的二义性：一个语言是二义性的语
7、言是二义性的，如，如果对它不存在无二义性的文法。果对它不存在无二义性的文法。国防科技大学计算机系国防科技大学计算机系602教研室教研室复习：复习：程序语言的语法描述程序语言的语法描述 n形式语言鸟瞰形式语言鸟瞰0型型(短语文法，图灵机短语文法，图灵机)：产生式形如：产生式形如：其中：其中：(VT VN)*且至少含有一个非终结符；且至少含有一个非终结符；(VT VN)*1型型(上下文有关文法，线性界限自动机上下文有关文法，线性界限自动机)：产生式形如：产生式形如：其中：其中：|，仅，仅 S 例外。例外。国防科技大学计算机系国防科技大学计算机系602教研室教研室复习：复习：程序语言的语法描述程序语
8、言的语法描述 n形式语言鸟瞰形式语言鸟瞰 2型型(上下文无关文法，非确定下推自动机上下文无关文法，非确定下推自动机)：产生式形如：产生式形如：A 其中：其中：A VN；(VT VN)*。3型型(正规文法，有限自动机正规文法，有限自动机)：产生式形如：产生式形如：A B 或或 A 其中：其中：VT*；A，B VN 产生式形如：产生式形如：A B 或或 A 其中：其中：VT*；A，B VN国防科技大学计算机系国防科技大学计算机系602教研室教研室第三章第三章 词法分析词法分析n词法分析的任务：从左至右逐个字符地词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符对源程序进行扫描，产
9、生一个个单词符号。号。n词法分析器词法分析器(Lexical Analyzer)又称扫描又称扫描器器(Scanner)：执行词法分析的程序：执行词法分析的程序国防科技大学计算机系国防科技大学计算机系602教研室教研室3.13.1 对于词法分析器的要求对于词法分析器的要求一、词法分析器的功能和输出形式一、词法分析器的功能和输出形式n功能功能:输入源程序、输出单词符号输入源程序、输出单词符号n单词符号的种类：单词符号的种类：基本字基本字：如：如 beginbegin，repeatrepeat，标识符标识符表示各种名字：如变量名、数组表示各种名字：如变量名、数组名和过程名名和过程名常数常数：各种类型
10、的常数：各种类型的常数运算符运算符：+，-，*，/，界符界符：逗号、分号、括号和空白：逗号、分号、括号和空白国防科技大学计算机系国防科技大学计算机系602教研室教研室n输出的单词符号的表示形式输出的单词符号的表示形式:(单词种别单词种别，单词自身的值单词自身的值)n单词种别通常用整数编码表示。单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算码就代表该单词符号。假定基本字、运算符和界符都是一符一种。符和界符都是一符一种。若一个种别有多个单词符号，则对于每个若一个种别有多个单词符号，则对于每个单词符号，给出种别
11、编码和自身的值。单词符号，给出种别编码和自身的值。n标识符单列一种；标识符自身的值表示成标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。按机器字节划分的内部码。n常数按类型分种；常数的值则表示成标准常数按类型分种；常数的值则表示成标准的二进制形式。的二进制形式。国防科技大学计算机系国防科技大学计算机系602教研室教研室例例 C程序程序n while(i=j)i-;n输出单词符号：输出单词符号：=,-国防科技大学计算机系国防科技大学计算机系602教研室教研室例例 FORTRAN程序程序nIF(5.EQ.M)GOTO 100IF(5.EQ.M)GOTO 100n输出单词符号：输出单词符
12、号：逻辑逻辑IFIF(34(34，-)-)左括号左括号(2(2，-)-)整常数整常数(20(20，55的二进制的二进制)等号等号(6(6，-)-)标识符标识符(26(26，M)M)右括号右括号(16(16，-)-)GOTOGOTO(30(30，-)-)标号标号(19(19，100100的二进制的二进制)国防科技大学计算机系国防科技大学计算机系602教研室教研室二、词法分析器作为一个独立子程序二、词法分析器作为一个独立子程序n词法分析是作为一个独立的阶段，是否词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？应当将其处理为一遍呢？作为独立阶段的优点：结构简洁、清晰和条作为独立阶段的优点：结
13、构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问理化，有利于集中考虑词法分析一些枝节问题。题。不作为一遍：将其处理为一个子程序。不作为一遍：将其处理为一个子程序。国防科技大学计算机系国防科技大学计算机系602教研室教研室词法分析器词法分析器词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.国防科技大学计算机系国防科技大学计算机系602教研室教研室词法分析器的结构词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表3.2 词法分析器的设计词法分析器的设计国防科技大学计
14、算机系国防科技大学计算机系602教研室教研室n输入串放在输入缓冲区中。输入串放在输入缓冲区中。n预处理子程序：剔除无用的空白、跳格、预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符回车和换行等编辑性字符;区分标号区、区分标号区、捻接续行和给出句末符等捻接续行和给出句末符等n扫描缓冲区扫描缓冲区 起点起点 搜索搜索指示器指示器 指示器指示器一、输入、预处理一、输入、预处理国防科技大学计算机系国防科技大学计算机系602教研室教研室 WhatALongWord WhatALongWo rdrd WhatALongWord WhatALongWo国防科技大学计算机系国防科技大学计算机系602
15、教研室教研室二、单词符号的识别二、单词符号的识别:超前搜索超前搜索1 基本字识别基本字识别:例如例如:DO99K=1，10 DO 99 K=1，10 IF(5.EQ.M)GOTO55 IF(5.EQ.M)GOTO 55DO99K=1.10IF(5)=55n需要超前搜索才能确定哪些是基本字需要超前搜索才能确定哪些是基本字国防科技大学计算机系国防科技大学计算机系602教研室教研室2 标识符识别标识符识别:n字母开头的字母数字串，后跟界符或算符字母开头的字母数字串，后跟界符或算符3 常数识别常数识别:n识别出算术常数并将其转变为二进制内码识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。表
16、示。有些也要超前搜索。5.EQ.M 5.E084 算符和界符的识别算符和界符的识别n把多个字符符合而成的算符和界符拼合成把多个字符符合而成的算符和界符拼合成一个单一单词符号。一个单一单词符号。:=，*，.EQ.，+，-，=国防科技大学计算机系国防科技大学计算机系602教研室教研室三三、状态转换图状态转换图1 1 概念概念n状态转换图是一张有限方向图。状态转换图是一张有限方向图。213XY结点代表状态，用圆圈表示结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧状态之间用箭弧连结，箭弧上的标记上的标记(字符字符)代表射出结代表射出结状态下可能出现的输入字符状态下可能出现的输入字符或字符类。或字符
17、类。一张转换图只包含有限个状态，其中一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。有一个为初态，至少要有一个终态。国防科技大学计算机系国防科技大学计算机系602教研室教研室识别标识符的状态转换图识别标识符的状态转换图123字母字母其他其他字母或数字字母或数字*识别识别整常数整常数的状态转换图的状态转换图123数字数字其他其他数字数字*n一个状态转换图可用于识别一个状态转换图可用于识别(或接受或接受)一定一定的字符串。的字符串。国防科技大学计算机系国防科技大学计算机系602教研室教研室2 2 例子例子q助忆符助忆符：直接用编码表示不便于记忆，：直接用编码表示不便于记忆，因此用助
18、忆符来表示编码。因此用助忆符来表示编码。国防科技大学计算机系国防科技大学计算机系602教研室教研室单单 词词 符符 号号 种种 别别 编编 码码 助助 忆忆 符符 内内 码码 值值 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 内内 部部 字字 符符 串串 常常 数数(数数)7 7$I IN NT T 标标 准准 二二 进进 制制 形形 式式 =8 8$A AS S
19、S 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 -国防科技大学计算机系国防科技大学计算机系602教研室教研室1 12 23 34 45 56 67 78 89 910101111121213130 0空白空白字母字母字母或数字字母或数字非字母与数字非字母与数字数字数字非数字非数字数字数字=+*非非*,()其它其它*国防科技大学计算机系国防科技大
20、学计算机系602教研室教研室n几点重要限制几点重要限制不必使用超前搜索不必使用超前搜索所有基本字都是保留字所有基本字都是保留字;用户不能用它们作自用户不能用它们作自己的标识符己的标识符基本字作为特殊的标识符来处理基本字作为特殊的标识符来处理;不用特殊的不用特殊的状态图来识别，只要查保留字表。状态图来识别，只要查保留字表。如果基本字、标识符和常数如果基本字、标识符和常数(或标号或标号)之间没之间没有确定的运算符或界符作间隔，则必须使用一有确定的运算符或界符作间隔，则必须使用一个空白符作间隔。个空白符作间隔。DO99K=1，10 要写成要写成 DO 99 K=1，10国防科技大学计算机系国防科技大
21、学计算机系602教研室教研室3 状态转换图的实现状态转换图的实现n思想：每个状态结对应一小段程序。思想：每个状态结对应一小段程序。n做法做法:1)1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASECASE语句或语句或一组一组IF-THEN-ELSEIF-THEN-ELSE语句实现语句实现GetChar();if(IsLetter()状态状态j的对应程序段的对应程序段;else if(IsDigit()状态状态k的对应程序段的对应程序段;else if(ch=/)状态状态l的对应程序段的对应程序段;else 错误处理错误处理;ijkl字母字母数字数字国防科技大学计算机系国防科技
22、大学计算机系602教研室教研室3 状态转换图的实现状态转换图的实现2)2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILEWHILE结构结构和和IFIF语句构成的程序语句构成的程序.i字母或数字字母或数字其它其它jGetChar();while(IsLetter()or IsDigit()GetChar();状态状态j的对应程序段的对应程序段国防科技大学计算机系国防科技大学计算机系602教研室教研室3 状态转换图的实现状态转换图的实现3)终态结表示识别出某种单词符号，因此，对应终态结表示识别出某种单词符号，因此，对应语句为语句为 RETURN(C，VAL)其中，其中，C为
23、单词种别，为单词种别，VAL为单词自身值为单词自身值.国防科技大学计算机系国防科技大学计算机系602教研室教研室n全局变量与过程全局变量与过程1)ch 字符变量、存放最新读入的源程序字符变量、存放最新读入的源程序字符字符2)strToken 字符数组，存放构成单词符字符数组，存放构成单词符号的字符串号的字符串3)GetChar 子程序过程，把下一个字符子程序过程，把下一个字符读入到读入到 ch 中中4)GetBC 子程序过程，跳过空白符，直子程序过程，跳过空白符，直至至 ch 中读入一非空白符中读入一非空白符5)Concat 子程序，把子程序，把ch中的字符连接到中的字符连接到 strToke
24、n 国防科技大学计算机系国防科技大学计算机系602教研室教研室6)IsLetter和和 IsDisgital 布尔函数，布尔函数，判断判断ch中字符是否为字母中字符是否为字母和数字和数字7)Reserve 整型函数，对于整型函数，对于 strToken 中的字符串查找保留字表，若它实保留字中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送则给出它的编码，否则回送08)Retract 子程序，把搜索指针回调一子程序，把搜索指针回调一个字符位置个字符位置9)InsertId 整型函数，将整型函数，将strToken中中的标识符插入符号表，返回符号表指针的标识符插入符号表，返回符号表指针1
25、0)InsertConst 整型函数过程，将整型函数过程，将strToken中的常数插入常数表，返回常中的常数插入常数表，返回常数表指针。数表指针。国防科技大学计算机系国防科技大学计算机系602教研室教研室int code,value;strToken:=“”;/*置置strToken为空串为空串*/GetChar();GetBC();if(IsLetter()beginwhile(IsLetter()or IsDigit()beginConcat();GetChar();endRetract();code:=Reserve();if(code=0)beginvalue:=InsertId(s
26、trToken);return($ID,value);endelsereturn(code,-);end国防科技大学计算机系国防科技大学计算机系602教研室教研室else if(IsDigit()beginwhile(IsDigit()beginConcat();GetChar();endRetract();value:=InsertConst(strToken);return($INT,value);endelse if(ch=)return($ASSIGN,-);else if(ch=+)return($PLUS,-);国防科技大学计算机系国防科技大学计算机系602教研室教研室else i
27、f(ch=*)beginGetChar();if(ch=*)return($POWER,-);Retract();return($STAR,-);endelse if(ch=;)return($SEMICOLON,-);else if(ch=()return($LPAR,-);else if(ch=)return($RPAR,-);else ProcError();/*错误处理错误处理*/国防科技大学计算机系国防科技大学计算机系602教研室教研室3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机n几个概念几个概念:考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集其中每一个元素称为
28、一个其中每一个元素称为一个字符字符上的上的字字(也叫也叫字符串字符串)是指由是指由中的字符所中的字符所构成的一个有穷序列构成的一个有穷序列不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为用用*表示表示上的所有字的全体上的所有字的全体,包含空字包含空字例如例如:设设=a，b，则，则*=,a,b,aa,ab,ba,bb,aaa,.国防科技大学计算机系国防科技大学计算机系602教研室教研室n*的子集的子集U和和V的的连接连接（积积）定义为）定义为UV|U&V V自身的自身的 n次积记为次积记为Vn=VVVn规定规定V0=，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包
29、;n记记 VVV*，称，称V+是是V的正规闭包。的正规闭包。国防科技大学计算机系国防科技大学计算机系602教研室教研室3.3.1 正规式和正规集正规式和正规集n正规集正规集可以用可以用正规表达式正规表达式（简称（简称正规式正规式）表示。表示。n正规表达式正规表达式是表示是表示正规集正规集一种方法。一一种方法。一个字集合是个字集合是正规集正规集当且仅当它能用当且仅当它能用正规正规式式表示。表示。国防科技大学计算机系国防科技大学计算机系602教研室教研室冯-诺伊曼构造自然数的方案n 0n1n,2n,3国防科技大学计算机系国防科技大学计算机系602教研室教研室n正规式和正规集的递归定义：正规式和正规
30、集的递归定义：对给定的字母表对给定的字母表 1)和和都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规集为集为 和和;2)任何任何a ，a是是 上的正规式，它所表示的上的正规式，它所表示的正规集为正规集为a;国防科技大学计算机系国防科技大学计算机系602教研室教研室3)假定假定e e1 1和和e2都是都是 上的正规式，它们所表示的上的正规式，它们所表示的正规集为正规集为L(e1)和和L(e2)，则，则i)(e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1
31、)L(e2)，iii)(e1)*为正规式，它所表示的正规集为为正规式，它所表示的正规集为(L(e1)*，仅由仅由有限次有限次使用上述三步骤而定义的表达式才使用上述三步骤而定义的表达式才是是 上的正规式，仅由这些正规式表示的字集上的正规式，仅由这些正规式表示的字集才是才是 上的正规集。上的正规集。国防科技大学计算机系国防科技大学计算机系602教研室教研室n所有词法结构一般都可以用正规式描述。所有词法结构一般都可以用正规式描述。n若两个正规式所表示的正规集相同，则称若两个正规式所表示的正规集相同，则称这两个正规式等价。如这两个正规式等价。如b(ab)*=(ba)*b(a*b*)*=(a|b)*L(
32、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)*b国防科技大学计算机系国防科技大学计算机系602教研室教研室n对正规式，下列等价成立：对正规式，下列等价成立：e1|e2=e2|e1 交换律交换律e1|(e2|e3)=(e1
33、|e2)|e3 结合律结合律e1(e2e3)=(e1e2)e3 结合律结合律e1(e2|e3)=e1e2|e1e3 分配律分配律(e2|e3)e1=e2e1|e3 e1分配律分配律e =e=e e1e2 e2 e1 L(e1|e2)=L(e1)L(e2)=L(e2)L(e1)=L(e2|e1)国防科技大学计算机系国防科技大学计算机系602教研室教研室正规集正规集正规式正规式3.3.1国防科技大学计算机系国防科技大学计算机系602教研室教研室3.3.2 确定有限自动机确定有限自动机(DFA)n对状态图进行形式化，则可以下定义：对状态图进行形式化，则可以下定义：自动机自动机M是一个五元式是一个五元
34、式M=(S,f,S0,F),其中：其中：1.S:有穷状态集，有穷状态集，2.：输入字母表：输入字母表(有穷有穷)，3.f:状态转换函数，为状态转换函数，为SS的单值部分映射，的单值部分映射，f(s，a)=s表示：当现行状态为表示：当现行状态为s，输入字符为，输入字符为a时，将状态转换到下一状态时，将状态转换到下一状态s。我们把。我们把s称为称为s的一个后继状态。的一个后继状态。4.S0 S是唯一的一个初态；是唯一的一个初态；5 F S：终态集：终态集(可空可空)。国防科技大学计算机系国防科技大学计算机系602教研室教研室n例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)，其中：其
35、中：f定义如下：定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3ab012132213333状态转换矩阵状态转换矩阵0312aaaa状态转换图状态转换图bbbb国防科技大学计算机系国防科技大学计算机系602教研室教研室nDFA可以表示为状态转换图。假定可以表示为状态转换图。假定DFA M含有含有m个状态和个状态和n个输入字符，那么，这个输入字符，那么，这个图含有个图含有m个状态结点，每个结点顶多含个状态结点，每个结点顶多含有有n条箭弧射出，且每条箭弧用条箭弧射出，且每条箭弧用上的不同上的不同的输入字符
36、来作标记。的输入字符来作标记。国防科技大学计算机系国防科技大学计算机系602教研室教研室n对于对于*中的任何字中的任何字，若存在一条从初态，若存在一条从初态到某一终态的道路，且这条路上所有弧上到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于的标记符连接成的字等于，则称，则称 为为DFA M所所识别识别(接收接收)nDFA M所识别的字的全体记为所识别的字的全体记为L(M)。n可以证明：可以证明：上的字集上的字集V V*是正规集，当是正规集，当且仅当存在上的且仅当存在上的DFA M，使得，使得VL(M)。国防科技大学计算机系国防科技大学计算机系602教研室教研室3.3.3 3.3.3
37、非确定有限自动机非确定有限自动机(NFA)n定义：一个非确定有限自动机定义：一个非确定有限自动机(NFA)M是是一个五元式一个五元式M=(S,M=(S,f,S,S0 0,F),F)，其中：，其中：1 S:有穷状态集；有穷状态集；2 ：输入字母表：输入字母表(有穷有穷)；3 f:状态转换函数，为状态转换函数，为S*2S的部分映的部分映射射(非单值非单值)；4 S S0 0 S S是非空的初态集；是非空的初态集；5 F S S：终态集：终态集(可空可空)。国防科技大学计算机系国防科技大学计算机系602教研室教研室n从状态图中看从状态图中看NFA 和和DFA的区别：的区别：1 弧上的标记可以是弧上的
38、标记可以是*中的一个字，而不中的一个字，而不一定是单个字符；一定是单个字符；2 同一个字可能出现在同状态射出的多条同一个字可能出现在同状态射出的多条弧上。弧上。nDFA是是NFA的特例。的特例。国防科技大学计算机系国防科技大学计算机系602教研室教研室021 a，baaa，bbba，b012abab识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字ambn|m，n 1国防科技大学计算机系国防科技大学计算机系602教研室教研室n定义：对于任何两个有限自动机定义：对于任何两个有限自动机M和和M，如果如果L(M)=L(M)，则称，则称M与与M等价。等价。n自动机理论中一个重要的结论
39、：判定两自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。个自动机等价性的算法是存在的。n对于每个对于每个NFA M存在一个存在一个DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA与与NFA描述能力描述能力相同。相同。国防科技大学计算机系国防科技大学计算机系602教研室教研室1.假定假定NFA M=，我们对，我们对M的的状态转换图进行以下改造：状态转换图进行以下改造：1)引进新的初态结点引进新的初态结点X和终态结点和终态结点Y，X,Y S，从从X到到S0中任意状态结点连一条中任意状态结点连一条 箭弧，箭弧，从从F中任意状态结点连一条中任意状态结点连一条 箭弧到箭弧到Y
40、。2)对对M的状态转换图进一步施行替换，其中的状态转换图进一步施行替换，其中k是是新引入的状态。新引入的状态。证明证明:国防科技大学计算机系国防科技大学计算机系602教研室教研室代之为代之为ikABjijAB代之为代之为ijA|BijBA代之为代之为ijA*ik jA按下面的三条规则对按下面的三条规则对V进行分裂进行分裂:国防科技大学计算机系国防科技大学计算机系602教研室教研室n逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的上的一个字符或一个字符或，最后得到一个，最后得到一个NFA M，显然，显然L(M)=L(M)国防科技大学计算机系国防科技大学计算机系602教研室教
41、研室n识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字XY 514236ab ababab5126ab abaabb国防科技大学计算机系国防科技大学计算机系602教研室教研室2.把上述把上述NFA确定化确定化采用子集法采用子集法.设设I是的状态集的一个子集，定义是的状态集的一个子集，定义I的的-闭包闭包-closure(I)为为:i)若若s I，则，则s-closure(I)；ii)若若s I，则从则从s出发经过任意条出发经过任意条 弧而能到弧而能到达的任何状态达的任何状态s都属于都属于-closure(I)即即 -closure(I)=I s|从某个从某个s I出发经过任
42、意出发经过任意条条 弧能到达弧能到达s国防科技大学计算机系国防科技大学计算机系602教研室教研室n设设a是是 中的一个字符，定义中的一个字符，定义Ia=-closure(J)其中，其中，J为为I中的某个状态出发经过一条中的某个状态出发经过一条a弧而到达的状态集合。弧而到达的状态集合。国防科技大学计算机系国防科技大学计算机系602教研室教研室n-closure(1)=1，2=I J=5，4，3 Ia=-closure(J)=-closure(5，4，3)=5，4，3，6，2，7，861a 234578aa n设设a是是 中的一个中的一个字符，定义字符，定义Ia=-closure(J)其中，其中，
43、J为为I中的某中的某个状态出发经过个状态出发经过一条一条a弧而到达弧而到达的状态集合。的状态集合。国防科技大学计算机系国防科技大学计算机系602教研室教研室n把确定化的过程把确定化的过程:不失一般性，设字母表只包含两个不失一般性，设字母表只包含两个a a和和b b，我们构造一张表我们构造一张表:IIaIb-Closure(X)国防科技大学计算机系国防科技大学计算机系602教研室教研室首先，置第首先，置第1行第行第1列为列为-closure(X)求出求出这一列的这一列的Ia，Ib；然后，检查这两个然后，检查这两个Ia，Ib，看它们是否已在，看它们是否已在表中的第一列中出现，把未曾出现的填入表中的
44、第一列中出现，把未曾出现的填入后面的空行的第后面的空行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.重复上述过程，知道所有第重复上述过程，知道所有第2，3列子集全列子集全部出现在第一列为止。部出现在第一列为止。国防科技大学计算机系国防科技大学计算机系602教研室教研室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
45、,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab ababab国防科技大学计算机系国防科技大学计算机系602教研室教研室n现在把这张表看成一个状态转换矩阵，把现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。其中的每个子集看成一个状态。n这张表唯一刻划了一个确定的有限自动机这张表唯一刻划了一个确定的有限自动机M，它的初态是，它的初态是-closure(X)，它的终，它的终态是含有原终态态是含有原终态Y的子集。的子集。n不难看出，这个不难看出，这个DFA M与与M等价。等价。国防科技大学计算机系国防科技大学计算机系602教研室教研室Iab012132214
46、3344655656340123546aabbbabaababab国防科技大学计算机系国防科技大学计算机系602教研室教研室FA正规集正规集正规式正规式DFANFA正规文法正规文法3.3.13.3.23.3.33.3.4国防科技大学计算机系国防科技大学计算机系602教研室教研室3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性n对于正规文法对于正规文法G和有限自动机和有限自动机M，如果，如果L(G)L(M)，则称，则称G和和M是是等价等价的。关于的。关于正规文法和有限自动机的等价性，有以正规文法和有限自动机的等价性，有以下结论：下结论：国防科技大学计算机系国防科技大学计算机系
47、602教研室教研室3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性n定理：定理：1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正或左线性正规文法规文法G，都存在一个有限自动机，都存在一个有限自动机(FA)M，使得，使得L(M)L(G)。2.对每一个对每一个FA M，都存在一个右线性正规，都存在一个右线性正规文法文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。国防科技大学计算机系国防科技大学计算机系602教研室教研室n证明：证明：1.1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正或左线性正规文法规文法G，都构造一
48、个有限自动机（，都构造一个有限自动机（FA）M，使得，使得L(M)L(G)。(1)设右线性正规文法设右线性正规文法G=。将。将VN中的每一非终结符号视为状态符号，中的每一非终结符号视为状态符号，并增加一个新的终结状态符号并增加一个新的终结状态符号f，f VN。令令M=，其中状态，其中状态转换函数转换函数 由以下规则定义：由以下规则定义：国防科技大学计算机系国防科技大学计算机系602教研室教研室(a)若对某个若对某个A VN及及a VT，P中有中有产生式产生式Aa，则令，则令(A,a)=f(b)对任意的对任意的A VN及及a VT，设，设P中中左端为左端为A，右端第一符号为，右端第一符号为a的所
49、有产的所有产生式为：生式为：AaA1|aAk （不包括（不包括Aa），），则令则令(A,a)=A1,Ak。显然，上述显然，上述M是一个是一个NFA。国防科技大学计算机系国防科技大学计算机系602教研室教研室对于右线性正规文法对于右线性正规文法G，在，在S w的最左推的最左推导过程中导过程中:利用利用AaB一次就相当于在一次就相当于在M中从状态中从状态A经经过标记为过标记为a的箭弧到达状态的箭弧到达状态B（包括（包括a=的情的情形）形）;在推导的最后，利用在推导的最后，利用Aa一次则相当于在一次则相当于在M中从状态中从状态A经过标记为经过标记为a的箭弧到达终结状态的箭弧到达终结状态f（包括（包括
50、a=的情形）。的情形）。综上，在正规文法综上，在正规文法G中，中，S w的充要条件的充要条件是：在是：在M中，从状态中，从状态S到状态到状态f有一条通路，有一条通路，其上所有箭弧的标记符号依次连接起来恰好其上所有箭弧的标记符号依次连接起来恰好等于等于w，这就是说，这就是说，w L(G)当且仅当当且仅当w L(M)，故，故L(G)L(M)。国防科技大学计算机系国防科技大学计算机系602教研室教研室(2)设左线性正规文法设左线性正规文法G=。将。将VN中的每一符号视为状态符号，并增加一中的每一符号视为状态符号，并增加一个初始状态符号个初始状态符号q0，q0 VN。令令M=，其中状，其中状态转换函数
