编译原理 陈火旺.

1、复习：复习：程序语言的语法描述程序语言的语法描述 n几个概念几个概念: : 考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集 其中每一个元素称为一个其中每一个元素称为一个字符字符 上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所构中的字符所构 成的一个有穷序列成的一个有穷序列 不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为 用用* *表示表示上的所有字的全体上的所有字的全体, ,包含空字包含空字 复习：复习：程序语言的语法描述程序语言的语法描述 n*的子集的子集U和和V的的连接连接（积积）定义为）定义为 UV | U n记记 V VV* ，称，称V

2、+是是V的正规闭包。的正规闭包。 复习：复习：程序语言的语法描述程序语言的语法描述 n上下文无关文法的定义：上下文无关文法的定义： 一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中 V VT T：终结符集合：终结符集合( (非空非空) ) V VN N：非终结符集合：非终结符集合( (非空非空) )，且，且V VT T V VN N= = S S：文法的开始符号，：文法的开始符号，S S V VN N P P：产生式集合：产生式集合( (有限有限) )，每个产生式形式为，每个产生式形式为 P P， P P V

3、 VN N， ( (V VT T V VN N) )* * 开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。 复习：复习：程序语言的语法描述程序语言的语法描述 n定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式， 且且 ， (VT VN)* 。 n如果如果 1 2 n，则我们称这个序，则我们称这个序 列是从列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n 。 n通常，用通常，用 表示：从表示：从 1 1出发，经过出发，经过 一步或

4、若干步，可以推出一步或若干步，可以推出 n n。 n 1 n * 1 用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或 若干步，可以推出若干步，可以推出 n n。 * 所以所以 ： 即即 或或 * S ,|)( * T V SGL q定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。 如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符 号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全所产生的句子的全 体是一个体是一个语言语言，将它记为，将它记为 L(G)L(G)。 复习：复习：程序语言的语法描述程序

5、语言的语法描述 n最左推导最左推导：任何一步：任何一步 都是对都是对 中的最中的最 左非终结符进行替换。左非终结符进行替换。 最右推导最右推导：任何一步：任何一步 都是对都是对 中的最中的最 右非终结符进行替换。右非终结符进行替换。 复习：复习：程序语言的语法描述程序语言的语法描述 n用一张图表示一个句型的推导用一张图表示一个句型的推导,称为称为语法树语法树。 E i + * () E i i EE EE E (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形式语言鸟瞰形式语言鸟瞰 0型型(短语文法，图灵机短语文法，图灵机)： 产生式形如：产生式形如： 其中：其中： (VT VN)*且至少含有一个非终结符；且至少含有一个非终结符； (VT VN)* 1型型(上下文有关文法，线性界限自动机

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

8、析的任务：从左至右逐个字符地词法分析的任务：从左至右逐个字符地 对源程序进行扫描，产生一个个单词符对源程序进行扫描，产生一个个单词符 号。号。 n词法分析器词法分析器(Lexical Analyzer) 又称扫描又称扫描 器器(Scanner)：执行词法分析的程序：执行词法分析的程序 3.13.1 对于词法分析器的要求对于词法分析器的要求 一、词法分析器的功能和输出形式一、词法分析器的功能和输出形式 n功能功能: :输入源程序、输出单词符号输入源程序、输出单词符号 n单词符号的种类：单词符号的种类： 基本字基本字：如：如 beginbegin，repeatrepeat， 标识符标识符表示各种名

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

10、个单词符号，则对于每个若一个种别有多个单词符号，则对于每个 单词符号，给出种别编码和自身的值。单词符号，给出种别编码和自身的值。 n标识符单列一种；标识符自身的值表示成标识符单列一种；标识符自身的值表示成 按机器字节划分的内部码。按机器字节划分的内部码。 n常数按类型分种；常数的值则表示成标准常数按类型分种；常数的值则表示成标准 的二进制形式。的二进制形式。 例例 C程序程序 n while (i=j) i-; n输出单词符号：输出单词符号： =, - 例例 FORTRAN程序程序 nIF (5.EQ.M) GOTO 100IF (5.EQ.M) GOTO 100 n输出单词符号：输出单词符号

11、： 逻辑逻辑IFIF(34(34，-)-) 左括号左括号(2(2，-)-) 整常数整常数(20(20， 55的二进制的二进制) ) 等号等号(6(6，-)-) 标识符标识符(26(26， M)M) 右括号右括号(16(16，-)-) GOTOGOTO(30(30，-)-) 标号标号(19(19， 100100的二进制的二进制) ) 二、词法分析器作为一个独立子程序二、词法分析器作为一个独立子程序 n词法分析是作为一个独立的阶段，是否词法分析是作为一个独立的阶段，是否 应当将其处理为一遍呢？应当将其处理为一遍呢？ 作为独立阶段的优点：结构简洁、清晰和条作为独立阶段的优点：结构简洁、清晰和条 理化

12、，有利于集中考虑词法分析一些枝节问理化，有利于集中考虑词法分析一些枝节问 题。题。 不作为一遍：将其处理为一个子程序。不作为一遍：将其处理为一个子程序。 词法分析器词法分析器 词法分词法分 析器析器 语法分语法分 析器析器 符号表符号表 源程序源程序 单词符号单词符号 取下一单词取下一单词 . 词法分析器的结构词法分析器的结构 预处理预处理 子程序子程序 扫描器扫描器 输入缓冲区输入缓冲区 扫描缓冲区扫描缓冲区 单词符号单词符号 输入输入 列表列表 3.2 词法分析器的设计词法分析器的设计 n输入串放在输入缓冲区中。输入串放在输入缓冲区中。 n预处理子程序：剔除无用的空白、跳格、预处理子程序：

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

14、99K=1.10 IF(5)=55 n需要超前搜索才能确定哪些是基本字需要超前搜索才能确定哪些是基本字 2 标识符识别标识符识别: n字母开头的字母数字串，后跟界符或算符字母开头的字母数字串，后跟界符或算符 3 常数识别常数识别: n识别出算术常数并将其转变为二进制内码识别出算术常数并将其转变为二进制内码 表示。有些也要超前搜索。表示。有些也要超前搜索。 5.EQ.M 5.E08 4 算符和界符的识别算符和界符的识别 n把多个字符符合而成的算符和界符拼合成把多个字符符合而成的算符和界符拼合成 一个单一单词符号。一个单一单词符号。 :=， *， .EQ. ， +，-，= 三三、状态转换图状态转换

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

16、转换图 123 数字数字其他其他 数字数字 * n一个状态转换图可用于识别一个状态转换图可用于识别( (或接受或接受) )一定一定 的字符串。的字符串。 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

17、 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 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

18、3 $ $L LP PA AR R - - ) ) 1 14 4 $ $R RP PA AR R - - 1 12 2 3 34 4 5 5 6 6 7 78 8 9 9 1010 1111 1212 1313 0 0 空白空白 字母字母 字母或数字字母或数字 非字母与数字非字母与数字 数字数字 非数字非数字 数字数字 = = + + * * 非非* * , , ( ( ) ) 其它其它 * * * * * * * * n几点重要限制几点重要限制不必使用超前搜索不必使用超前搜索 所有基本字都是保留字所有基本字都是保留字;用户不能用它们作自用户不能用它们作自 己的标识符己的标识符 基本字作为特殊

19、的标识符来处理基本字作为特殊的标识符来处理;不用特殊的不用特殊的 状态图来识别，只要查保留字表。状态图来识别，只要查保留字表。 如果基本字、标识符和常数如果基本字、标识符和常数(或标号或标号)之间没之间没 有确定的运算符或界符作间隔，则必须使用一有确定的运算符或界符作间隔，则必须使用一 个空白符作间隔。个空白符作间隔。 DO99K=1，10 要写成要写成 DO 99 K=1，10 3 状态转换图的实现状态转换图的实现 n思想：每个状态结对应一小段程序。思想：每个状态结对应一小段程序。 n做法做法: : 1)1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASECASE语句或语句或

20、 一组一组IF-THEN-ELSEIF-THEN-ELSE语句实现语句实现 GetChar( ); if (IsLetter( ) 状态状态j的对应程序段的对应程序段; else if (IsDigit( ) 状态状态k的对应程序段的对应程序段; else if (ch=/) 状态状态l的对应程序段的对应程序段; else 错误处理错误处理; i j k l 字母字母 数字数字 3 状态转换图的实现状态转换图的实现 2)2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILEWHILE结构结构 和和IFIF语句构成的程序语句构成的程序. . i 字母或数字字母或数字 其它其它

21、 j GetChar( ); while (IsLetter( ) or IsDigit( ) GetChar( ); 状态状态j的对应程序段的对应程序段 3 状态转换图的实现状态转换图的实现 3)终态结表示识别出某种单词符号，因此，对应终态结表示识别出某种单词符号，因此，对应 语句为语句为 RETURN (C，VAL) 其中，其中，C为单词种别，为单词种别，VAL为单词自身值为单词自身值. n全局变量与过程全局变量与过程 1)ch 字符变量、存放最新读入的源程序字符变量、存放最新读入的源程序 字符字符 2)strToken 字符数组，存放构成单词符字符数组，存放构成单词符 号的字符串号的字符

22、串 3)GetChar 子程序过程，把下一个字符子程序过程，把下一个字符 读入到读入到 ch 中中 4)GetBC 子程序过程，跳过空白符，直子程序过程，跳过空白符，直 至至 ch 中读入一非空白符中读入一非空白符 5)Concat 子程序，把子程序，把ch中的字符连接到中的字符连接到 strToken 6)IsLetter和和 IsDisgital 布尔函数，布尔函数， 判断判断ch中字符是否为字母中字符是否为字母和数字和数字 7) Reserve 整型函数，对于整型函数，对于 strToken 中的字符串查找保留字表，若它实保留字中的字符串查找保留字表，若它实保留字 则给出它的编码，否则回

23、送则给出它的编码，否则回送0 8) Retract 子程序，把搜索指针回调一子程序，把搜索指针回调一 个字符位置个字符位置 9)InsertId 整型函数，将整型函数，将strToken中中 的标识符插入符号表，返回符号表指针的标识符插入符号表，返回符号表指针 10)InsertConst 整型函数过程，将整型函数过程，将 strToken中的常数插入常数表，返回常中的常数插入常数表，返回常 数表指针。数表指针。 int code, value; strToken := “ ”; /*置置strToken为空串为空串*/ GetChar(); GetBC(); if (IsLetter() b

24、egin while (IsLetter() or IsDigit() begin Concat(); GetChar(); end Retract(); code := Reserve(); if (code = 0) begin value := InsertId(strToken); return ($ID, value); end else return (code, -); end else if (IsDigit() begin while (IsDigit() begin Concat( ); GetChar( ); end Retract(); value := InsertC

25、onst(strToken); return($INT, value); end else if (ch =) return ($ASSIGN, -); else if (ch =+) return ($PLUS, -); else if (ch =*) begin GetChar(); if (ch =*) return ($POWER, -); Retract(); return ($STAR, -); end else if (ch =;) return ($SEMICOLON, -); else if (ch =() return ($LPAR, -); else if (ch =)

26、return ($RPAR, -); else ProcError( );/* 错误处理错误处理*/ 3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机 n几个概念几个概念: : 考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集 其中每一个元素称为一个其中每一个元素称为一个字符字符 上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所中的字符所 构成的一个有穷序列构成的一个有穷序列 不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为 用用* *表示表示上的所有字的全体上的所有字的全体, ,包含空字包含空字 例如例如: 设设 =a， b，则，则 *

27、=,a,b,aa,ab,ba,bb,aaa,. n*的子集的子集U和和V的的连接连接（积积）定义为）定义为 UV | U n记记 V VV* ，称，称V+是是V的正规闭包。的正规闭包。 3.3.1 正规式和正规集正规式和正规集 n正规集正规集可以用可以用正规表达式正规表达式（简称（简称正规式正规式） 表示。表示。 n正规表达式正规表达式是表示是表示正规集正规集一种方法。一一种方法。一 个字集合是个字集合是正规集正规集当且仅当它能用当且仅当它能用正规正规 式式表示。表示。 冯-诺伊曼构造自然数的方案 n 0 n1 n, 2 n, , , 3 n正规式和正规集的递归定义：正规式和正规集的递归定义：

28、 对给定的字母表对给定的字母表 1) 和和都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规 集为集为 和和; 2) 任何任何a ，a是是 上的正规式，它所表示的上的正规式，它所表示的 正规集为正规集为a ; 3) 假定假定e e1 1和和e2都是都是 上的正规式，它们所表示的上的正规式，它们所表示的 正规集为正规集为L(e1)和和L(e2)，则，则 i) (e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为 L(e1) L(e2)， ii) (e1.e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为 L(e1)L(e2)， iii) (e1)*为

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

30、 = (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 n对正规式，下列等价成立：对正规式，下列等价成立： e1|e2 = e2|e1 交换律交换律 e1 |(e2|e3) = (e1|e2)|e3 结

31、合律结合律 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) 正规集正规集 正规式正规式 3.3.1 3.3.2 确定有限自动机确定有限自动机(DFA) n对状态图进行形式化，则可以下定义：对状态图进行形式化，则可以下定义： 自动机自动机M是一个五元式是一个五元式M=(S, , f, S0, F),其中：其中： 1. S: 有穷状态集，

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

33、b)=2 f(2，a)=1f(2，b)=3 f(3，a)=3 f(3，b)=3 ab 012 132 213 333 状态转换矩阵状态转换矩阵 0 3 1 2 a a a a 状态转换图状态转换图 b bb b nDFA可以表示为状态转换图。假定可以表示为状态转换图。假定DFA M 含有含有m个状态和个状态和n个输入字符，那么，这个输入字符，那么，这 个图含有个图含有m个状态结点，每个结点顶多含个状态结点，每个结点顶多含 有有n条箭弧射出，且每条箭弧用条箭弧射出，且每条箭弧用上的不同上的不同 的输入字符来作标记。的输入字符来作标记。 n对于对于 * *中的任何字中的任何字 ，若存在一条从初态，

34、若存在一条从初态 到某一终态的道路，且这条路上所有弧上到某一终态的道路，且这条路上所有弧上 的标记符连接成的字等于的标记符连接成的字等于 ，则称，则称 为为DFA M所所识别识别(接收接收) nDFA M所识别的字的全体记为所识别的字的全体记为L(M)。 n可以证明：可以证明： 上的字集上的字集V V* *是正规集，当是正规集，当 且仅当存在上的且仅当存在上的DFA M，使得，使得VL(M)。 3.3.3 3.3.3 非确定有限自动机非确定有限自动机(NFA) n定义：一个非确定有限自动机定义：一个非确定有限自动机(NFA) M是是 一个五元式一个五元式M=(S, M=(S, , , f, S

35、, S0 0, F), F)，其中：，其中： 1 S: 有穷状态集；有穷状态集； 2 ：输入字母表：输入字母表(有穷有穷)； 3 f: 状态转换函数，为状态转换函数，为S* 2S的部分映 的部分映 射射(非单值非单值)； 4 S S0 0 S S是非空的初态集；是非空的初态集； 5 F S S ：终态集：终态集(可空可空)。 n从状态图中看从状态图中看NFA 和和DFA的区别：的区别： 1 弧上的标记可以是弧上的标记可以是 *中的一个字，而不中的一个字，而不 一定是单个字符；一定是单个字符； 2 同一个字可能出现在同状态射出的多条同一个字可能出现在同状态射出的多条 弧上。弧上。 nDFA是是N

36、FA的特例。的特例。 0 2 1 a，b aa a，b bb a，b 012 ab ab 识别所有含相继两个识别所有含相继两个a 或相继两个或相继两个b的字的字 ambn | m，n 1 n定义：对于任何两个有限自动机定义：对于任何两个有限自动机M和和M， 如果如果L(M)=L(M)，则称，则称M与与M等价。等价。 n自动机理论中一个重要的结论：判定两自动机理论中一个重要的结论：判定两 个自动机等价性的算法是存在的。个自动机等价性的算法是存在的。 n对于每个对于每个NFA M存在一个存在一个DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA与与NFA描述能力描述能力 相同。相同。 1

37、. 假定假定NFA M=，我们对，我们对M的的 状态转换图进行以下改造：状态转换图进行以下改造： 1) 引进新的初态结点引进新的初态结点X和终态结点和终态结点Y，X,Y S， 从从X到到S0中任意状态结点连一条中任意状态结点连一条 箭弧，箭弧， 从从F 中任意状态结点连一条中任意状态结点连一条 箭弧到箭弧到Y。 2) 对对M的状态转换图进一步施行替换，其中的状态转换图进一步施行替换，其中k是是 新引入的状态。新引入的状态。 证明证明: 代之为代之为 ik AB j ij AB 代之为代之为 ij A|B ij B A 代之为代之为 ij A* ik j A 按下面的三条规则对按下面的三条规则对

38、V进行分裂进行分裂: n逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的上的 一个字符或一个字符或 ，最后得到一个，最后得到一个NFA M，显然，显然 L(M)=L(M) n识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字 XY 51 4 2 3 6 a b a b a b a b 5126 a b a b aa bb 2. 把上述把上述NFA确定化确定化采用子集法采用子集法. 设设I是的状态集的一个子集，定义是的状态集的一个子集，定义I的的 -闭包闭包 -closure(I)为为: i) 若若s I，则，则s-closure(I)； ii) 若若s

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

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

41、表中的第一列中出现，把未曾出现的填入表中的第一列中出现，把未曾出现的填入 后面的空行的第后面的空行的第1列上，求出每行第列上，求出每行第2，3列列 上的集合上的集合. 重复上述过程，知道所有第重复上述过程，知道所有第2，3列子集全列子集全 部出现在第一列为止。部出现在第一列为止。 IIaIb X,5,15,3,15,4,1 5,3,15,2,3,1,6,Y5,4,1 5,4,15,3,15,2,4,1,6,Y 5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y 5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y 5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y

42、 5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,Y XY 51 4 2 3 6 a b a b a b a b n现在把这张表看成一个状态转换矩阵，把现在把这张表看成一个状态转换矩阵，把 其中的每个子集看成一个状态。其中的每个子集看成一个状态。 n这张表唯一刻划了一个确定的有限自动机这张表唯一刻划了一个确定的有限自动机 M，它的初态是，它的初态是 -closure(X) ，它的终，它的终 态是含有原终态态是含有原终态Y的子集。的子集。 n不难看出，这个不难看出，这个DFA M与与M等价。等价。 Iab 012 132 214 334 465 565 634 0 1 2 3 5 4 6

43、 a ab b b a b a a b a b a b FA 正规集正规集 正规式正规式 DFA NFA正规文法正规文法 3.3.1 3.3.2 3.3.3 3.3.4 3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性 n对于正规文法对于正规文法G和有限自动机和有限自动机M，如果，如果 L(G)L(M)，则称，则称G和和M是是等价等价的。关于的。关于 正规文法和有限自动机的等价性，有以正规文法和有限自动机的等价性，有以 下结论：下结论： 3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性 n定理：定理： 1.对每一个右线性正规文法对每一个右线性正规文法G或

44、左线性正或左线性正 规文法规文法G，都存在一个有限自动机，都存在一个有限自动机(FA) M，使得，使得L(M)L(G)。 2.对每一个对每一个FA M，都存在一个右线性正规，都存在一个右线性正规 文法文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M) L(GR)L(GL)。 n证明：证明： 1. 1. 对每一个右线性正规文法对每一个右线性正规文法G或左线性正或左线性正 规文法规文法G，都构造一个有限自动机（，都构造一个有限自动机（FA） M，使得，使得L(M)L(G)。 (1) 设右线性正规文法设右线性正规文法G=。将。将 VN中的每一非终结符号视为状态符号，中的每一非终结符号视

45、为状态符号， 并增加一个新的终结状态符号并增加一个新的终结状态符号f，f VN。 令令M=，其中状态，其中状态 转换函数转换函数 由以下规则定义：由以下规则定义： (a) 若对某个若对某个A VN及及a VT ，P中有中有 产生式产生式Aa，则令，则令 (A,a)=f (b) 对任意的对任意的A VN及及a VT ，设，设P中中 左端为左端为A，右端第一符号为，右端第一符号为a的所有产的所有产 生式为：生式为： AaA1|aAk （不包括（不包括Aa），）， 则令则令 (A,a)=A1,Ak。 显然，上述显然，上述M是一个是一个NFA。 对于右线性正规文法对于右线性正规文法G，在，在S w的最

46、左推的最左推 导过程中导过程中: 利用利用AaB一次就相当于在一次就相当于在M中从状态中从状态A经经 过标记为过标记为a的箭弧到达状态的箭弧到达状态B（包括（包括a= 的情的情 形）形）; 在推导的最后，利用在推导的最后，利用Aa一次则相当于在一次则相当于在M 中从状态中从状态A经过标记为经过标记为a的箭弧到达终结状态的箭弧到达终结状态 f（包括（包括a= 的情形）。的情形）。 综上，在正规文法综上，在正规文法G中，中，S w的充要条件的充要条件 是：在是：在M中，从状态中，从状态S到状态到状态f有一条通路，有一条通路， 其上所有箭弧的标记符号依次连接起来恰好其上所有箭弧的标记符号依次连接起来

47、恰好 等于等于w，这就是说，这就是说，w L(G)当且仅当当且仅当 w L(M)，故，故L(G)L(M)。 (2) 设左线性正规文法设左线性正规文法G=。将。将 VN中的每一符号视为状态符号，并增加一中的每一符号视为状态符号，并增加一 个初始状态符号个初始状态符号q0，q0 VN。 令令M=，其中状，其中状 态转换函数态转换函数 由以下规则定义：由以下规则定义： (a) 若对某个若对某个A VN及及a VT ，若，若P中有产中有产 生式生式Aa，则令，则令 (q0,a)=A (b) 对任意的对任意的A VN及及a VT ，若，若P中所有中所有 右端第一符号为右端第一符号为A，第二个符号为，第二

48、个符号为a的产的产 生式为：生式为： A1Aa, , AkAa， 则令则令 (A,a)=A1,Ak。 与与(1)类似，可以证明类似，可以证明L(G)L(M)。 nGR(A) ： A0 | 0B | 1D B0D | 1C C0 | 0B | 1D D0D | 1D n从从GR出发构造出发构造NFA M = ，M的状态转换图的状态转换图 如右图所示。如右图所示。 n显然显然 L(M) = L(GR)。 例例: A B C D 1 0 0,1 1 1 0 f 0 00 3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性 n定理：定理： 1.对每一个右线性正规文法对每一个右线性正规

49、文法G或左线性正或左线性正 规文法规文法G，都存在一个有限自动机，都存在一个有限自动机(FA) M，使得，使得L(M)L(G)。 2.对每一个对每一个FA M，都存在一个右线性正规，都存在一个右线性正规 文法文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M) L(GR)L(GL)。 证明证明2：对每一个：对每一个DFA M，都存在一个右线，都存在一个右线 性正规文法性正规文法GR和左线性正规文法和左线性正规文法GL，使得，使得 L(M)L(GR)L(GL)。 设设DFA M= (1) 若若s0 F，我们令，我们令GR=，其，其 中中P是由以下规则定义的产生式集合：是由以下规则定义

50、的产生式集合： 对任何对任何a及及A,B S，若有，若有 (A,a)=B，则：，则： (a) 当当B F时，令时，令AaB， (b) 当当B F时，令时，令Aa|aB。 对任何对任何w*，不妨设，不妨设w=a1ak，其中，其中ai (i=1,k)。若。若s0 w，则存在一个最左推导：，则存在一个最左推导： s0a1A1a1a2A2a1aiAi a1ai+1Ai+1a1ak 因而，在因而，在M中有一条从中有一条从s0出发依次经过出发依次经过A1， Ak-1到达终态的通路，该通路上所有箭弧的到达终态的通路，该通路上所有箭弧的 标记依次为标记依次为a1,ak。反之亦然。所以，。反之亦然。所以， w

51、L(GR)当且仅当当且仅当w L(M)。 q 现在考虑现在考虑s0 F的情形：的情形： 因为因为 (s0, )=s0，所以，所以L(M)。但。但 不属于上面构不属于上面构 造的造的GR所产生的语言所产生的语言L(GR)。不难发现，。不难发现， L(GR)=L(M)- 。 所以，我们在上述所以，我们在上述GR中添加新的非终结符号中添加新的非终结符号s0 ， (s0S)和产生式和产生式s0s0| ，并用，并用s0 代替代替s0作开始作开始 符号。这样修正符号。这样修正GR后得到的文法后得到的文法GR 仍是右线性正仍是右线性正 规文法，并且规文法，并且L(GR )=L(M)。 (2) 类似于类似于(

52、1)，从，从DFA M出发可构造左线性正规出发可构造左线性正规 文法文法GL，使得，使得L(GL)=L(M)。 最后，由最后，由DFA和和NFA之间的等价性，结论之间的等价性，结论2得证。得证。 若有若有 (A,a)=B： (a) 当当A= q0时，令时，令Ba， (b) 当当A q0时，令时，令BAa nL(M) = 0(10)* nGR = ，其中，其中P由下列产生由下列产生 式组成：式组成： A0 | 0B | 1D B0D | 1C C0 | 0B | 1D D0D | 1D L(GR) = L(M) = 0(10)* 例例3.4 设设DFA M = 。M的状态转换图如下图所示。的状态

53、转换图如下图所示。 A B C D 1 0 0,1 1 1 0 0 n从从NFA M出发构造左线性出发构造左线性 正规文法正规文法GL = ，其中，其中P 由由 下列产生式组成：下列产生式组成： f0 | C0 CB1 B0 | C0 D1 | C1 | D0 | D1 | B0 易证易证 L(GL) = L(M)。 例例3.4 设设DFA M = 。M的状态转换图如图的状态转换图如图3.9(a)所示。所示。 A B C D 1 0 0,1 1 1 0 f 0 00 FA 正规集正规集 正规式正规式 DFA NFA正规文法正规文法 3.3.1 3.3.2 3.3.3 3.3.43.3.5 3.

54、3.5 3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性 n定理：定理： 1. 对任何对任何FA M，都存在一个正规式，都存在一个正规式r，使，使 得得L(r)=L(M)。 2. 对任何正规式对任何正规式r，都存在一个，都存在一个FA M，使，使 得得L(M)=L(r)。 2对转换图概念拓广，令每条弧可用一个对转换图概念拓广，令每条弧可用一个 正规式作标记。正规式作标记。(对一类输入符号对一类输入符号) n证明：证明： 1 1 对对 上任一上任一NFA M，构造一个，构造一个 上的正规上的正规 式式r，使得，使得L(r)=L(M)。 首先，在首先，在M的转换图上加进两个状态的转

55、换图上加进两个状态X和和Y， 从从X用用 弧连接到弧连接到M的所有初态结点，从的所有初态结点，从M的所的所 有终态结点用有终态结点用 弧连接到弧连接到Y，从而形成一个新，从而形成一个新 的的NFA，记为，记为M，它只有一个初态，它只有一个初态X和一个终和一个终 态态Y，显然，显然L(M)=L(M)。 然后，反复使用下面的一条规则，逐步消去的然后，反复使用下面的一条规则，逐步消去的 所有结点，直到只剩下所有结点，直到只剩下X和和Y为止；为止； 代之为代之为 ij r1r2 k ik r1r2 代之为代之为 ij r1|r2 ij r2 r1 代之为代之为 ik r1r2*r2 ij r1r3 k

56、 r2 1 2 3 5 4 U1 V1 U2 V2W2 W1 1 25 4 V1(U1|U2)*W1 V1(U1|U2)*W2 V2(U1|U2)*W2 V2(U1|U2)*W1 q最后，最后，X到到Y的弧上标记的正规式即为的弧上标记的正规式即为 所构造的正规式所构造的正规式r q显然显然L(r)=L(M)=L(M) n证明证明2: 对于对于 上的正规式上的正规式r，构造一个，构造一个NFA M，使，使L(M)=L(r)，并且，并且M只有一个终态，只有一个终态， 而且没有从该终态出发的箭弧而且没有从该终态出发的箭弧。 下面使用关于下面使用关于r中运算符数目的归纳法证中运算符数目的归纳法证 明上

57、述结论。明上述结论。 (1) 若若r具有零个运算符，则具有零个运算符，则r= 或或r= 或或r=a，其，其 中中a。此时下图所示的三个有限自动机显然。此时下图所示的三个有限自动机显然 符合上述要求。符合上述要求。 q0q0qf a q0qf (2) 假设结论对于少于假设结论对于少于k(k 1)个运算符的正个运算符的正 规式成立。规式成立。 当当r中含有中含有k个运算符时，个运算符时，r有三种情形：有三种情形： l情形情形1：r=r1|r2，r1,r2中运算符个数少于中运算符个数少于k。 从而，由归纳假设，对从而，由归纳假设，对ri存在存在Mi=，使得，使得L(Mi)=L(ri)，并且，并且Mi

58、没有从终没有从终 态出发的箭弧（态出发的箭弧（i=1,2）。不妨设）。不妨设S1S2= ， 在在S1 S2中加入两个新状态中加入两个新状态q0，f0。 令令M=， 其中其中 定义如下：定义如下： (a) (q0, )=q1,q2 (b) (q,a)= 1(q,a), 当当q S1-f1, a1 (c) (q,a)= 2(q,a), 当当q S2-f2, a2 (d) (f1, )= (f2, )=f0。 M的状态转换如右图所示。的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r) q0 f0 M1q1f1 M2q2f2 l情形情形2：r=r1r2, 设设Mi

59、同情形同情形1(i=1,2)。 令令M=，其中，其中 定义如下：定义如下： (a) (q,a)= 1(q,a), 当当q S1-f1, a1 (b) (q,a)= 2(q,a), 当当q S2, a2 (c) (f1, )=q2 M的状态转换如右图所示。的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。 M1q1f1 M2q2f2 l情形情形3：r=r1*。设。设M1同情形同情形1。 令令M=，其中，其中q0, f0 S1， 定义如下：定义如下： (a) (q0, )= (f1, )=q1, f0 (b) (q,a)= 1(q, a), 当当q S1-f

60、1, a1 。 M的状态转换如右图所示。的状态转换如右图所示。 L(M) = L(M1)* = L(r1)* = L(r) 至此，结论至此，结论2获证。获证。 M1q1f1 q0f0 1) 1) 构造构造 上的上的NFA M 使得使得 L(V)=L(M) 首先，把首先，把V表示成表示成 XY V 上述证明过程实质上是一个将正规表达式上述证明过程实质上是一个将正规表达式 转换为有限自动机的算法。转换为有限自动机的算法。 代之为代之为 ij V1V2 k ik V1V2 代之为代之为 ij V1|V2 ij V2 V1 代之为代之为 ik V1* ij k V1 然后，按下面的三条规则对然后，按下