第三章 词法分析.ppt

1、词法分析,西北大学软件工程研究所 龚晓庆,概述,本章引入词法分析器（扫描器）的构造原理和实现技术 扫描器的任务,2020/7/7,2,讨论扫描器的设计需求和实现机制 介绍单词的内部表示，引入单词的描述工具正规式 描述识别单词的转换图和有限自动机的概念和应用 先讨论扫描器的手工构造，然后引入自动构造原理,2020/7/7,3,Contents,编译阶段词法分析,2020/7/7,4,编译阶段词法分析,将源程序分解为单词符号串,2020/7/7,6,词法分析器,词法分析的任务 自左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。 词法分析器的

2、构造 手工构造 自动生成 Lex：词法规则（正规式）有限自动机,2020/7/7,7,3.1 对词法分析器的要求功能,词法分析器的功能 功能 从数据输入到输出的一个变换过程或函数 说明该过程（或函数）需要做什么，而非如何做 扫描器的输入是代表源程序的字符串 输出是单词符号（token）的内部中间表示 过程是扫描输入的字符流，按词法规则识别出单词,2020/7/7,8,对词法分析器的要求输出形式,单词符号的种类 关键字由语言定义、具有固定含义的标识符 如，main, if, while, for 等 通常不作为程序员自定义的名字使用（保留字，基本字） 标识符用于表示各种名字 如，变量名、数组名、

3、类名，函数名和过程名等 常数具有某种数据类型的不变量 常见的类型有整型、实型、布尔型、文字型等 如，100、3.14159、TRUE 、 example 运算符，用于表示操作 如，+、-、*、/ 等 界符，用于区分各种不同的语法单位 如，“,”、“;”、“(”、“)”、“/*”、“*/” 等,对词法分析器的要求输出形式,单词符号的输出形式 二元式 （单词种别，单词符号的属性值） 单词种别：通常用整数编码表示，不能唯一确定单词时，需用 属性值：通常是指向符号表的指针（入口地址） 实现上，如何划分单词种别和编码纯属技术性考虑 如关键字、运算符和界符通常作为一符一种处理 关键字、运算符和界符由语言定

4、义，个数是固定的 种别的整数编码可唯一确定该单词，无须属性值 标识符常作为一种来处理，常数则可按类型分种 需用属性值来区分不同单词的特征 这些特征信息存放于相关的符号表项或常数表项中单词种别：用整数编码,2020/7/7,9,词法分析器的输出示例,2020/7/7,10,例，C+代码段：while (i = j) i-; 将被转换为 =, ,2020/7/7,11,词法分析器的组织,将词法分析器作为一个独立阶段 任务相对独立、简单，有高效的工具进行处理 与编译过程的其它工作分开造就良设计的软件架构 结构简洁、清晰、条理化 是否将词法分析器作为独立的一遍？ 没有必要，而且低效 与语法分析器通信的

5、其他方式 最常用的：作为一个子程序，由语法分析器在需要单词符号时调用 词法分析器和语法分析器作为两个并发的过程通过pipe通信,词法分析器的组织示例,作为独立阶段（一遍） 作为独立的子程序,3.2 词法分析器的设计问题,语言对程序格式的要求 自由格式 大部分语言不规定某个单词必须出现在程序行中的什么位置 固定格式 如早期的FORTRAN语言规定输入行的前6个字符是标号，最后的字符（7280列）是注释，以C开头的是注释行，等等 空白（空格和tab） 大多数PL，空白是有意义的 FORTRAN和Algol60，空白可以加在任何地方提高可读性,2020/7/7,13,词法分析器的设计问题,缓冲区 是

6、编译器中唯一需要处理每个字符的阶段 设计不合理会成为最费时和低效的阶段 不能从输入文件中逐个字符读入，一次读入大块文本放入一个缓冲区，由缓冲区给词法分析器提供字符 词法分析器需要向前扫描时，缓冲区也有用处 关键字 保留字：用户不能使用关键字作为标识符 PL/l 的关键字不是保留字，词法分析器要区分,2020/7/7,14,词法分析器的设计错误处理,词法分析中遇到了错误怎么处理？ 应急式（panic）跳过字符，直到发现一个结构良好的单词符号 替换替换一个不正确的字符 删除删除一个不正确的字符 插入插入一个缺失的字符 调换调换两个字符的位置,2020/7/7,15,3.2.1 输入、预处理,输入缓

7、冲区 为了提高效率，扫描器并非直接逐个字符地读源文件 每次从源文件中读出一定长度的字符串 将输入的字符串放入一个输入缓冲区中 预处理 对多数PL，用于正文编辑的字符一般没有实际意义 如，空格、跳格、回车和换行符只是在文字常数中有意义 注解的出现对程序的功能也无任何意义 为了方便识别工作，编辑性字符和注解应事先删除 有些PL将一个或相继多个空格用作单词之间的界符 此时应事先将相继多个空格合并为一个空格 预处理即在识别开始前，删去输入缓冲区中的无用字符,2020/7/7,16,输入、预处理,预处理子程序 可设计一个由扫描器调用的子程序 当调用时，处理出长度为 N 的字符串，并装入扫描缓冲区 使识别

8、工作可在此缓冲区上直接进行 扫描缓冲区的结构 通常采用一个长度为 2N 的双半区（双缓冲区）设计 扫描器需维护两个指示器 一个指向正在扫描单词的首字符，一个向前搜索其终点 若单词被半区边界截断，则再装入N个字符到另半区 单词的长度 N，故语言通常限制标识符和常数的长度,2020/7/7,17,扫描缓冲区的结构,2020/7/7,18,词法分析器的结构,2020/7/7,19,2020/7/7,20,3.2.2 单词符号的识别：超前搜索,识别单词通常需要超前搜索 为了识别当前单词，需要扫描后继的若干个字符 关键字的识别 如FORTRAN，关键字和用户字无区别；单词之间无界符 1 DO99K =

9、1, 10 循环语句：DO 关键字 99 结束行标号 3 DO99K = 1. 10 赋值语句： DO99K 为用户定义的变量名 必须超前搜索至第一个界符,或.才能确定单词的种别,单词符号的识别：超前搜索,标识符的识别 一般为字母开头的字母/数字序列，读到其它符号时可识别 常数的识别 各种类型的常数一般容易识别，但有些语言需超前搜索 如FORTRAN，5 .EQ. M 和 5.E08的前缀相同 算符和界符的识别 有些语言需要超前搜索 如C+，Java中，+，+=，-，=等,2020/7/7,21,2020/7/7,22,3.2.3 状态转换图,如何利用转换图手工（非形式）实现扫描器 转换图的作

10、用：词法规则 转换图 扫描器 词法规则的一种图形描述工具 描述扫描器动作 如，标识符可非形式地描述为字母开头的字母/数字序列 其转换图为 （其中0表示初始状态，双圈表示终止状态）,状态转换图,转换图是一张有限方向图 结点：状态 箭弧 标记：射出结点状态下可能出现的输入字符或字符类 初态和终态,2020/7/7,23,转换,状态,初态,终态,输入字符,状态转换图,扫描器可利用转换图识别（接受）一定的字符串（单词） 状态 S0 对应于单词识别的开始位置 在 Si，若存在有向边 (Si，Sj), 其上标记与输入字符匹配 则状态转换到 Sj，并将搜索指示器+1，否则失败 在终止状态，表示识别出一个单词

11、 在终止状态, 若多读了一个字符，应退给输入串，标记为*,2020/7/7,24,状态转换图示例,2020/7/7,25,2020/7/7,26,状态转换图作用,一个状态转换图可以用于识别（或接受）一定的字符串 大多数程序设计语言的单词符号都可以用转换图予以识别 状态转换图是设计词法分析器的有效工具 给出识别单词符号的状态转换图 实现状态转换图 每个状态结点对应一段程序 不含回路的分叉结点对应switch或if-else语句 含回路的状态结点对应while和if构成的程序段,状态转换图实现示例,2020/7/7,27,状态转换图实现代码 1,状态转换图实现代码 2,状态转换图实现代码 3,状态

12、转换图综合应用,构造识别一个简单语言所有单词符号的转换图,2020/7/7,31,状态转换图综合应用,词法处理约定 除标识符，常数外，均为一符一种 关键字均为保留字，不可用作用户字 设保留字表，识别出标识符时，查表确定是否为关键字 相邻单词之间至少存在一个界符、算符或空格 按此约定，无须使用超前搜索，也无须设关键字转换图,状态转换图综合应用,设计思想,状态转换图综合应用,状态转换图综合应用,变量与过程 ch， 字符变量，存放最新读入的字符 strToken，字符数组，存放组成单词的字符串 GetChar(), 读入当前字符，搜索指示器指向下一输入字符 GetBC(), 若 ch = , 则反复

13、调用GetChar()直至ch Concat(), strToken := strToken | ch isletter/isDigit, 若 ch = letter/digit, 则返回 true, 否 false int Reserve(), 若strToken = 保留字, 则返回编码，否 0 Retract(),搜索指示器回调一个字符，ch := int InsertId(), 将strToken插入符号表，返回符号表指针 int InsertConst(),将strToken插入常数表，返回常数表指针,Next,手工构造词法分析器 非形式的词法规则转换图扫描器 接下来讨论如何形式化上

14、述过程 其目的在于能够自动化（机械化）该过程，即 词法的形式规则 形式状态转换图 扫描器 其中：描述词法的形式规则是 正规式 正规文法 描述转换图的形式工具是 有限自动机 形式化也使得可以用数学方法保证结果的正确性,自动,自动,2020/7/7,37,3.3 正规表达式与有限自动机,3.3.1 正规式与正规集,正规集 已知任何形式语言均为*的一个子集 程序语言的单词一般均属于*的一个特殊子集 正规集 已知正规集上的字符串（字）可以使用正规文法描述 正规式是一种比文法更为简单、高效的方法,2020/7/7,38,2020/7/7,39,正规式与正规集定义,设字母表，正规式与其所表示的正规集可递归

15、定义为 和都是上的正规式，它们所表示的正规集分别为和; 任何a，a都是上的一个正规式，它所表示的正规集为a； 假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么(U|V)、(UV)和(U)*也都是正规式，它们所表示的正规集分别是L(U)L(V)、 L(U)L(V)（连接积）和(L(U)*（闭包）。 仅由有限次使用上述三个步骤而得到的表达式才是上的正规式 仅由这些正规式所表示的字集才是上的正规集 正规式运算符（优先级从高到低） * （闭包） （连接） |（或）,正规式与正规集例,例 设字母表=a，b，部分上的正规式和正规集如下： 正规式正规集 aa a|ba，b aba

16、b (a|b)(a|b)aa，ab，ba，bb a*，a，aa， 任意个a的串 ba*b(a)* = b, ba, baa, a(a|b)*a(a, b)* = a*, 上所有以a开头的字 (a|b)*(aa|bb)(a|b)* *aa, bb*, 上所有包含aa或bb的字,2020/7/7,40,正规式与正规集例,例 令 = A, B, 0, 1 (A|B)(A|B|0|1)* 上标识符的全体 (0|1)(0|1)*上数的全体 例 令r = letter( letter|digit )*，则其正规式表示的语言 L(r) = L(letter) ( L(letter)L(digit) )* =

17、A，Z，a，z(A，Z，a，z，0，9)* 例 令L(x)=a，b,L(y)=c，d且r1=x|y，r2=y|x，则 L(r1)=a，b，c，d L(r2)=a，b，c，d L(r1)= L(r2),正规式与正规集等价性,正规式的等价性 若两个正规式所表示的正规集相同，则认为两者等价 两个等价的正规式 u 和 v 记为 u = v 如，b(ab)* = (ba)*b, (a|b)* = (a*b*)* 等价性证明 若要证明 u = v， 须证明L(u) = L(v) 集合相等证明方法 使用正规式的代数性质,2020/7/7,42,2020/7/7,43,正规式与正规集正规式的代数性质,连接对

18、| 是可分配的, 是连接的恒等元素,正规式与正规集等价性证明,例，证明 b(ab)* = (ba)*b b(ab)*= b(ab)0 | (ab)1 | (ab)2 | ) = b | b(ab)1 | b(ab)2 | /分配律 = b | (ba)1b | (ba)2b | /结合律 = ( | (ba)1 | (ba)2 | ) b/分配律 = (ba)*b,2020/7/7,44,例，证明 (A*)* = A*, 其中A为任意正规 需证明 L(A*)*) = L(A*) /注： L(A*)*) = (L(A*)* 首先证明 L(A*)*) L(A*) 显然有 L(A*)*) = L(A

19、*)0 L(A*)1 L(A*)2 L(A*) 其次证明 L(A*)*) L(A*) 设 x L(A*)*) = (L(A*)* 若 x = , 则 x L(A*) 若 x , 则 x (L(A*)k 令 x = x1x2xk 有 xi L(A*) = (L(A)* 于是有 xi (L(A)mi （mi 0, i =1, 2, k) 则 x = x1x2xk (L(A)m1 (L(A)m2 (L(A)mk = (L(A) m1+ m2 + + mk 令 m = m1 + m2 + mk , 有 x (L(A)m (L(A)* 故有 L(A*)*) L(A*),2020/7/7,46,3.3.2

20、 确定有限自动机（DFA）,一个DFA M是一个五元式 M = (S, ,s0,F)，其中 S = S0, S1, , Sn为有限集，Si S 为状态 为有限字母表， a 为输入字符 : S S 的单值（部分）映射（状态转换函数） (s, a) = s 意为：现行状态为 s，输入字符为 a，则转换到后继状态s 从转换图来看，相当于 S0 S 为唯一的初态 F S 为终态集（可空）,2020/7/7,47,确定有限自动机DFA的表示,五元式 M = (0,1,2,3,a,b,0,3)， 其中为 (0,a)=1(0,b)=2 (1,a)=3(1,b)=2 (2,a)=1(2,b)=3 (3,a)=

21、3(3,b)=3,2020/7/7,48,确定有限自动机DFA的表示,状态转换矩阵 行：状态 列：输入字符 矩阵元素：(s,a)的值,状态转换图,DFA的表示,DFA M = (0, 1, 2, 3, a, b, , 0, 3) 映射状态矩阵 状态转换图,2020/7/7,49,2020/7/7,50,确定有限自动机DFA M识别的字,对于*上的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于，则称可为DFA M所识别（读出或接受）。 若M的初态结点同时又是终态结点，则空字可为M所识别。 DFA M所识别的字的全体记为L(M)。,DFA示例,是DFA吗

22、？接受什么样的字符串？,2020/7/7,51,是DFA吗？接受什么样的字符串？,DFA示例,自然数,带符号的自然数,DFA示例,带符号的实数,浮点数,DFA示例,C语言注释,非确定性,DFA的确定性 映射:SS是单值函数 任何状态sS和输入符号a, (s,a)唯一地确定了下一个状态。 例，构造识别:=, =, =的DFA 构造识别三个运算符的DFA 只能用唯一的初始状态将它们连接在一起,2020/7/7,55,非确定性,2020/7/7,56,非确定性,如果有两个字符串以相同字符开始呢？ 下面的转换图是DFA吗？,2020/7/7,57,非确定性,可以用增加新状态的方法解决相同符号的冲突 这

23、个是DFA吗？与上图比较有什么优劣？,2020/7/7,58,2020/7/7,59,3.3.3 非确定有限自动机（NFA）,非确定的有限自动机（NFA） 允许是一个多值函数 允许有标记的转换：表示没有输入字符直接转换状态,2020/7/7,60,NFA定义,一个NFA M是一个五元式 M = (S,S0,F)，其中 S是一个有限状态集 是一个有穷字母表，是输入字符集合 是一个从S*到S的子集的映射，即:S*2S S0 S，是非空初态集 F S，是一个终态集（可空）,NFA示例,: S * 2S的含义 其含义为 (s, ) = s | s S 注意： * (* = + a * 与 a 不加区分

24、，有 | a | = 1 2S为S的幂集，即由S的所有子集构成的集合 如，S = 0, 1, 2S = , 0, 1, 0, 1 例，NFA M = (0, 1, 2, a, b, , 0, 1, 2),2020/7/7,61,2020/7/7,62,NFA和状态转换图,含有m个状态和n个输入字符的NFA可以表示为如下的状态转换图： 该图有m个状态结点，每个结点可以射出若干条箭弧与别的结点相接，每条弧用*中的一个字作标记（输入字，可以是），整张图至少含有一个初态结点以及若干个终态结点。,NFA示例,2020/7/7,63,2020/7/7,64,NFA识别的字,对于*中的任何一个字，若存在一条

25、从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于，则称可为NFA M所识别（读出或接受）。 若M的某些初态结点同时又是终态结点，或者存在一条从某个初态结点到某个终态结点的通路，则空字可为M所接受。,DFA和NFA的编程实现,方法一：硬编码 类似于转换图的实现 可以用固定代码模式,2020/7/7,65,DFA和NFA的实现,方法二：状态转换表驱动的实现 将状态转移用表的方式表示，如下 3表示该状态不读取输入字符 空白表示错误状态 接受状态用标记,2020/7/7,66,DFA和NFA的实现,给定如上的转换表，对任意DFA我们可以编写下面的程序进行词法分析,202

26、0/7/7,67,DFA和NFA的实现例C注释,2020/7/7,68,DFA和NFA的实现例C注释,DFA和NFA的实现例C注释,DFA和NFA的实现例C注释,DFA和NFA的实现例C注释,正规式NFADFA词法分析器,我们的思路 用正规式（RE）描述词法规则 将正规式转换为NFA 将NFA转换为DFA 根据DFA构造词法分析程序 要考虑的问题 这些表示方式是否等价？ 这一系列转换是否能够自动进行（有算法）？ 下一步：等价性证明和构造（转换）算法,正规式转换为NFA,每条有向边上标记为或单个字符,2020/7/7,74,NFA转换为正规式,2020/7/7,75,NFA和正规式的等价性,上述

27、方法说明NFA和正规式是等价的 每个NFA M所识别的字的全体 L(M) 是上的正规集 每个上的正规集L(R)均可被一个NFA M所识别 L(M) = L(R), 称为两者是等价的 原则上，若程序语言的词法用正规式描述，则可自动构造一个NFA M来识别该语言的单词 NFA的非确定性使之不容易用于实现词法分析器 若能消除NFA的非确定性，将其转换为DFA，则容易实现,2020/7/7,76,NFA和DFA的等价性,有限自动机的等价性 FA M，FA M，若L(M) = L(M)，则称两者是等价的 DFA与NFA的等价性是自动机理论的一个重要定理 DFA和NFA是等价的 DFA是NFA的特例 即：

28、DFA M，NFA M，使L(M) = L(M) DFA : S S NFA : S * 2S 需证明，NFA M存在一个DFA M使 L(M)=L(M),2020/7/7,77,* , 2S S,NFA转换为DFA,NFA M，DFA M，使L(M) = L(M) 设 NFA M = (S, , , S0, F) 将 NFA M 改造为 NFA M 引入唯一的新初态结点X和新终态结点Y X 到 S0 中所有结点均用 边 连接 F 中所有结点到 Y 也均用 边 连接 反复使用图示的替换 直至每条有向边上 标记为 或单个字符 显然，L(M) = L(M),2020/7/7,78,NFA转换为DF

29、A,基本思想是采用一种“子集构造” 算法来确定化 构造一个DFA M，使其每个状态对应于NFA M的状态集 使得在DFA读入a1a2an时，所处的状态对应于NFA所能到达的状态集 如NFA读入a1a2an到达状态 中的任意一个，则DFA到达状态集2,3,4，即状态 观察NFA M：可能有 边，也可能有相同标记的边 要构造DFA M，必须合并这两种边到达的状态,2020/7/7,79,NFA转换为DFA,子集构造方法 设 I S，定义 _closure ( I ) q I, q _closure ( I ) q I, 从 q 出发经任意条 边可达的 q _closure ( I ) 即 _clo

30、sure ( I ) = I q | q I 旨在合并与状态集 I 相关的 边可达状态 设 I S，a , 定义 Ia = _closure ( J ) q I，从 q 出发经 a 边可达的q J,2020/7/7,80,NFA转换为DFA,确定化方法 假定 = a1,a2,ak, 我们构造一张表S，S有k+1列，依次标记为I,Ia1,Ia2,Iak 置该表的首行首列为_closure ( X ), X为NFA M 的初态 如果确定了第m（m1,2,）行中第一列的I，则计算Iax （x1,2,k），并填入m行中对应的列即Sm， Iax中 检查m行上的每个状态子集Iax （x1,2,k），如果I

31、ax ，并且它还没有在表S的第一列中出现，则将其填入到空行的第一列 重复3、4，直至所有Iax （x1,2,k）都在第一列上出现 该过程一定在有限步内终止，因为M的子集数 = 2|S|,2020/7/7,81,NFA转换为DFA,确定化方法（示例） 假设 = a, b, 则定义一张表 S(I, Ia, Ib) 其中，第i行的表元素分别为Si, I, Si, Ia, Si, Ib 置S1, I = _closure ( X ), X为NFA M 的初态 若Si, I , 则计算 Ia, Ib，填入 Si, Ia, Si, Ib 检查第i行的元素，若 Si, Ia 或 Si, Ib 还没有在第一列

32、出现过 则 将Si, Ia 或 Si, Ib 填入 Sk+, I, （k表示第一个空行）；i+；返回步骤2 否则算法终止,2020/7/7,82,例 (a|b)*(aa|bb)(a|b)*,2020/7/7,83,构造 DFA M 所构造的S表指定了DFA M的状态转换矩阵 S表中的每个状态子集为DFA M的一个状态 S表中的首行首列为初态 S表中含有终态的状态子集为DFA M的终态,2020/7/7,85,3.3.5 正规式与有限自动机的等价性,证明一 FA M，正规式 r，使得 L(r) = L(M),正规式与有限自动机的等价性,证明二正规式 r, FA M，使得 L(M) = L(r)

33、用关于正规式 r中运算符个数归纳证明 归纳基础：r中运算符数目为0 即 r = 或 r = 或 r = a (a )，则 显然，三个NFA分别接受的正规集为, 和a 归纳假设：设r,如果r中的运算符数目为k，则存在一个FA M，使得 L(M)=L(r) 当r中有k+1个运算符时，r有三种可能：r = r1| r2, r = r1 r2 或 r = r1*； r1和r2 中的运算符数目=k. 根据归纳假设，对r1和r2存在FAM1和M2使得 L(M1)=L(r1)L(M2)=L(r2),2020/7/7,86,则对于r = r1| r2, 构造 M 为 其中，为M引入新的初态结点q0和终态结点f

34、0，并从q0引出转换至q1和q2，从 f1和 f2引出转换至f0 显然，有L(M) = L(M1) L(M2) = L(r1) L(r2) = L(r) 对于r = r1 r2, 构造 M 为 其中， q1为新的初态， f2为终态，并从f1引出转换至q2 显然，有L(M) = L(M1) L(M2) = L(r1) L(r2) = L(r) 对于r = r1*, 构造 M 为 显然，有L(M) = L(M1)* = L(r1)* = L(r),2020/7/7,87,正规式与有限自动机的等价性,基本思想（Thompson 构造算法） 对正规式的各个部分构造NFA 用弧连接起各个NFA，构成完整

35、的自动机,2020/7/7,88,接受正规式a的NFA,接受正规式的NFA,假设接受正规式r的NFA如下,接受正规式rs的NFA,接受正规式r|s的NFA,接受正规式r*的NFA,正规式与有限自动机的等价性例子,设正规式为 r1= 1*， r2 = 01*， r3 = 01* | 1,2020/7/7,89,Thompson构造算法例子,正规式ab|a的NFA,2020/7/7,90,Thompson构造算法例子,正规式letter(letter|digit)*的NFA,正规文法与有限自动机的等价性,正规文法与正规式 程序语言通常采用正规文法定义它的词法规则 正规式是自动构造词法分析器的有效工

36、具 正规（3型）文法 G = (VT, VN, S, P) P: A B, A , A, B VN, VT * （右线性文法） P: A B, A , A, B VN, VT * （左线性文法） 可等价变换为 p： A aB， A a A, B VN, a VT （右线性文法） p： A Ba， A a A, B VN, a VT （左线性文法） 方便起见，右和左线性文法为分别记为GR和GL,正规文法与有限自动机的等价性,等价性 对正规文法G和FA M，若L(G)=L(M), 则称为G和M等价 GR或GL，FA M，L(GR) = L(M) 或 L(GL) = L(M) FA M， GR或GL

37、， L(M) = L(GR) = L(GL) 等价性证明 对右线性文法GR构造NFA M，并证明L(M)=L(GR) 对左线性文法GL构造NFA M，并证明L(M)=L(GL) 对DFA M构造右线性文法GR，并证明L(GR) =L(M) 对DFA M构造左线性文法GL，并证明L(GL) =L(M),2020/7/7,93,正规文法与有限自动机的等价性,等价性证明（从正规文法构造FA） 基本思想 设 w = a1a2ak, 分别考虑GR和GL的最左推导 GR : S a1B1 a1a2B2 a1a2ak-1Bk-1 a1a2ak GL : S Bk-1ak Bk-2ak-1ak B1a2ak

38、a1a2ak 非终结符的作用是记住字符个数，将其作为状态,2020/7/7,94,正规文法与有限自动机的等价性,从右线性文法构造FA 设 GR = (VT, VN, S, P), 其中p： A aB， A a 令 NFA M = (VN F, VT, , S, F)，其中， 若AVN, 且a VT, 有A a, 则令 (A, a) = F 若AVN, 且a VT, 有A aA1|aA2|aAk, 则令 (A, a) = A1,A2, Ak 容易证明，该NFA M所识别的语言L(M) = L(GR),2020/7/7,95,正规文法与有限自动机的等价性,从左线性文法构造FA 设 GL = (VT

39、, VN, S, P), 其中P: A Ba， A a 令 NFA M = (VN q0, VT, , q0, S)，其中， 若AVN, 且a VT, 使A a, 则令 (q0, a) = A 若AVN, 且a VT, 使A1 Aa, A2 Aa,Ak Aa 则令 (A, a) = A1,A2, Ak,2020/7/7,96,正规文法与有限自动机的等价性,从DFA中构造GR 设DFA M = (S, , , S0, F), 若S0 F，则令GR = (, S, S0, P), 其中 P为 若 则 A aB 或 A a | aB 若S0 F, 则因(S0, ) = S0, 故 L(M), 但 L

40、(GR) 引入S0 代替 S0 作为新的开始符号，并增加P：S0 S0 | 容易证明，L(GR) = L(M) 从DFA中构造GL 可用类似的方法，但需逆向构造； 若 B Aa 若 A a | S0a,2020/7/7,97,例3.4 DFA M GR NFA M GL 设 DFA M = (A, B, C, D, 0, 1, , A, B) 使用FA到正规式的算法可证明L(M) = 0(10)* GR = (0,1, A, B, C, D, A, P, 其中 P 为 A 0 | 0B | 1DB 0D | 1C C 0 | 0B | 1DD 0D | 1D (D为无用产生式） 从GR中构造N

41、FA M M = (A, B, C, D, F, 0, 1, , A, F),2020/7/7,98,从NFA M构造 GL 将 F 作为开始符号，从终态 F 出发逆向构造 F 0 | A0 | C0C B1 B 0 | A0 | C0D 1 | A1 | C1| D0 | D1| B0 因没有有向边射入 A，所以没有有关 A 的产生式 删除无用候选式后 GL = (0, 1, F, B, C, D, F, P) F 0 | C0 C B1 B 0 | C0 D 1 | C1| D0 | D1| B0,2020/7/7,100,等价性的结论,正规文法、正规式、确定有限自动机和非确定有限自动机在

42、接收语言的能力上是互相等价的。,RG,2020/7/7,101,DFA的化简,DFA M的化简 化简：寻找DFA M，使L(M) = L(M), 且|SM| SM| 最小化：寻找具有最少状态数的M，使L(M) = L(M) 等价状态和可区别的状态 M中的不同状态s和t是等价的 如果从状态s出发能读出某个字w而停于终态，那么同样从t出发也能读出同样的字w而停于终态； 反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出同样的w而停于终态。,2020/7/7,102,DFA的化简,状态的等价关系() 设 s, t SM, s t, 定义s t, 若w = a1a2ak *, 有,状态的可区分关系 s, t SM, s t, 若s，t不等价，则s，t是可区分的 据 关系，对SM可进行等价划分 SM = S1S2 Sn, SiSj = , | Si | 1 容易看出, s, t Si, s t, 而 s Si, t Sj, s与 t 是可区分的 等价划分是最大划分，即这样划分 n 为最小 每个等价集中元素可读出相同的w而终止，故可合并为一个状态 最小化算法: 从 SM中寻找 S1, S2,Sn,