第三章-词法分析

1、概述v 本章引入词法分析器（扫描器）的构造原理和实现技术v 扫描器的任务2022-6-201v 讨论扫描器的设计需求和实现机制v 介绍单词的内部表示，引入单词的描述工具正规式v 描述识别单词的转换图和有限自动机的概念和应用v 先讨论扫描器的手工构造，然后引入自动构造原理2022-6-202Contents词法分析器的手工构造1正规表达式2有限自动机3词法分析器的自动生成4编译阶段词法分析2022-6-203编译阶段词法分析v将源程序分解为单词符号串2022-6-205词法分析器v词法分析的任务 自左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中

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

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

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

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

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

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

8、缓冲区上直接进行v扫描缓冲区的结构 通常采用一个长度为 2N 的双半区（双缓冲区）设计扫描器需维护两个指示器一个指向正在扫描单词的首字符，一个向前搜索其终点若单词被半区边界截断，则再装入N个字符到另半区单词的长度 N，故语言通常限制标识符和常数的长度2022-6-2016扫描缓冲区的结构2022-6-2017词法分析器的结构2022-6-2018预处理子程序扫描缓冲区扫描器输入缓冲区输入列表单词符号2022-6-2019 3.2.2 单词符号的识别：超前搜索v识别单词通常需要超前搜索 为了识别当前单词，需要扫描后继的若干个字符v关键字的识别 如FORTRAN，关键字和用户字无区别；单词之间无界

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

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

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

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

13、etBC(), 若 ch = , 则反复调用GetChar()直至ch 5. Concat(), strToken := strToken | ch6. isletter/isDigit, 若 ch = letter/digit, 则返回 true, 否 false7. int Reserve(), 若strToken = 保留字, 则返回编码，否 08. Retract(),搜索指示器回调一个字符，ch := 9. int InsertId(), 将strToken插入符号表，返回符号表指针10.int InsertConst(),将strToken插入常数表，返回常数表指针Nextv手工构

14、造词法分析器 非形式的词法规则转换图扫描器v接下来讨论如何形式化上述过程 其目的在于能够自动化（机械化）该过程，即词法的形式规则 形式状态转换图 扫描器 其中：描述词法的形式规则是 正规式 正规文法 描述转换图的形式工具是 有限自动机 形式化也使得可以用数学方法保证结果的正确性自动自动2022-6-20363.3 正规表达式与有限自动机正规式与正规集1DFA和NFA2正规文法3等价性证明43.3.1 正规式与正规集v 正规集已知任何形式语言均为*的一个子集程序语言的单词一般均属于*的一个特殊子集 正规集已知正规集上的字符串（字）可以使用正规文法描述正规式是一种比文法更为简单、高效的方法2022

15、-6-20372022-6-2038正规式与正规集定义v设字母表，正规式与其所表示的正规集可递归定义为1.和都是上的正规式，它们所表示的正规集分别为和;2.任何a，a都是上的一个正规式，它所表示的正规集为a；3.假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么(U|V)、(UV)和(U)*也都是正规式，它们所表示的正规集分别是L(U)L(V)、 L(U)L(V)（连接积）和(L(U)*（闭包）。仅由有限次使用上述三个步骤而得到的表达式才是上的正规式仅由这些正规式所表示的字集才是上的正规集v正规式运算符（优先级从高到低）* （闭包） （连接） |（或）正规式与正规集例

16、v例 设字母表=a，b，部分上的正规式和正规集如下：正规式正规集aaa|ba，bab ab(a|b)(a|b)aa，ab，ba，bba*，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的字2022-6-2039正规式与正规集例v 例 令 = A, B, 0, 1(A|B)(A|B|0|1)* 上标识符的全体(0|1)(0|1)*上数的全体v 例 令r = letter( letter|digit )*，则其正规式表示的语言 L(r)

17、 = L(letter) ( L(letter)L(digit) )* =A，Z，a，z(A，Z，a，z，0，9)*v 例 令L(x)=a，b,L(y)=c，d且r1=x|y，r2=y|x，则L(r1)=a，b，c，dL(r2)=a，b，c，dL(r1)= L(r2)正规式与正规集等价性v 正规式的等价性若两个正规式所表示的正规集相同，则认为两者等价两个等价的正规式 u 和 v 记为 u = v如，b(ab)* = (ba)*b, (a|b)* = (a*b*)*v 等价性证明若要证明 u = v，1. 须证明L(u) = L(v)集合相等证明方法2. 使用正规式的代数性质2022-6-204

18、12022-6-2042正规式与正规集正规式的代数性质连接对 | 是可分配的 是连接的恒等元素性性 质质描描 述述A|B=B|A| 是可交换的A|(B|C)=(A|B)|C| 是可结合的A(BC)=(AB)C连接是可结合的A(B|C)=AB|AC(A|B)C=AC|BC连接对 | 是可分配的 A = AA = A 是连接的恒等元素 A* = (A | )*和之间的关系A*=A*幂的等价性正规式与正规集等价性证明v例，证明 b(ab)* = (ba)*b b(ab)*= b(ab)0 | (ab)1 | (ab)2 | )= b | b(ab)1 | b(ab)2 | /分配律= b | (ba

19、)1b | (ba)2b | /结合律= ( | (ba)1 | (ba)2 | ) b/分配律= (ba)*b2022-6-2043v例，证明 (A*)* = A*, 其中A为任意正规 需证明 L(A*)*) = L(A*) /注： L(A*)*) = (L(A*)* 首先证明 L(A*)*) L(A*) 显然有 L(A*)*) = L(A*)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)

20、*于是有 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*)2022-6-2045 3.3.2 确定有限自动机（DFA）v一个DFA M是一个五元式M = (S, ,s0,F)，其中1.S = S0, S1, , Sn为有限集，Si S 为状态2. 为有限字母表， a 为输入字符3.: S S 的单值（部分）映射（状态转换函数） (s, a) = s 意为：现行状

21、态为 s，输入字符为 a，则转换到后继状态s 从转换图来看，相当于4.S0 S 为唯一的初态5.F S 为终态集（可空）ssa2022-6-2046确定有限自动机DFA的表示v五元式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)=3(3,b)=32022-6-2047确定有限自动机DFA的表示v 状态转换矩阵 行：状态 列：输入字符 矩阵元素：(s,a)的值01a3b2aaa,bbbv 状态转换图DFA的表示DFA M = (0, 1, 2, 3, a, b, , 0, 3) 映射状态矩阵 状态转

22、换图2022-6-20482022-6-2049确定有限自动机DFA M识别的字v对于*上的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于，则称可为DFA M所识别（读出或接受）。v若M的初态结点同时又是终态结点，则空字可为M所识别。vDFA M所识别的字的全体记为L(M)。DFA示例v是DFA吗？接受什么样的字符串？2022-6-2050v是DFA吗？接受什么样的字符串？DFA示例v自然数v带符号的自然数DFA示例v带符号的实数v浮点数DFA示例vC语言注释非确定性vDFA的确定性 映射:SS是单值函数 任何状态sS和输入符号a, (s,a)唯一地

23、确定了下一个状态。v例，构造识别:=, =, =的DFA 构造识别三个运算符的DFA 只能用唯一的初始状态将它们连接在一起2022-6-2054非确定性2022-6-2055非确定性v如果有两个字符串以相同字符开始呢？ 下面的转换图是DFA吗？2022-6-2056非确定性v可以用增加新状态的方法解决相同符号的冲突 这个是DFA吗？与上图比较有什么优劣？2022-6-20572022-6-20583.3.3 非确定有限自动机（NFA）v非确定的有限自动机（NFA） 允许是一个多值函数 允许有标记的转换：表示没有输入字符直接转换状态2022-6-2059NFA定义v一个NFA M是一个五元式M

24、= (S,S0,F)，其中 S是一个有限状态集 是一个有穷字母表，是输入字符集合 是一个从S*到S的子集的映射，即:S*2S S0 S，是非空初态集 F S，是一个终态集（可空）NFA示例v : S * 2S的含义 其含义为 (s, ) = s | s S 注意： * (* = +a * 与 a 不加区分，有 | a | = 12S为S的幂集，即由S的所有子集构成的集合如，S = 0, 1, 2S = , 0, 1, 0, 1 例，NFA M = (0, 1, 2, a, b, , 0, 1, 2)2022-6-20602022-6-2061NFA和状态转换图v 含有m个状态和n个输入字符的N

25、FA可以表示为如下的状态转换图： 该图有m个状态结点，每个结点可以射出若干条箭弧与别的结点相接，每条弧用*中的一个字作标记（输入字，可以是），整张图至少含有一个初态结点以及若干个终态结点。aabbb3210NFA示例2022-6-20622022-6-2063NFA识别的字v对于*中的任何一个字，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于，则称可为NFA M所识别（读出或接受）。v若M的某些初态结点同时又是终态结点，或者存在一条从某个初态结点到某个终态结点的通路，则空字可为M所接受。DFA和NFA的编程实现v方法一：硬编码 类似于转换图的实现 可

26、以用固定代码模式2022-6-2064DFA和NFA的实现v方法二：状态转换表驱动的实现 将状态转移用表的方式表示，如下3表示该状态不读取输入字符空白表示错误状态接受状态用标记2022-6-2065DFA和NFA的实现v给定如上的转换表，对任意DFA我们可以编写下面的程序进行词法分析2022-6-2066DFA和NFA的实现例C注释2022-6-2067DFA和NFA的实现例C注释DFA和NFA的实现例C注释DFA和NFA的实现例C注释DFA和NFA的实现例C注释正规式NFADFA词法分析器v我们的思路1. 用正规式（RE）描述词法规则2. 将正规式转换为NFA3. 将NFA转换为DFA4.

27、根据DFA构造词法分析程序v要考虑的问题这些表示方式是否等价？这一系列转换是否能够自动进行（有算法）？v下一步：等价性证明和构造（转换）算法正规式转换为NFAv每条有向边上标记为或单个字符2022-6-2073NFA转换为正规式2022-6-2074NFA和正规式的等价性v上述方法说明NFA和正规式是等价的 每个NFA M所识别的字的全体 L(M) 是上的正规集 每个上的正规集L(R)均可被一个NFA M所识别 L(M) = L(R), 称为两者是等价的 原则上，若程序语言的词法用正规式描述，则可自动构造一个NFA M来识别该语言的单词 NFA的非确定性使之不容易用于实现词法分析器 若能消除N

28、FA的非确定性，将其转换为DFA，则容易实现2022-6-2075NFA和DFA的等价性v有限自动机的等价性 FA M，FA M，若L(M) = L(M)，则称两者是等价的 DFA与NFA的等价性是自动机理论的一个重要定理vDFA和NFA是等价的1.DFA是NFA的特例即：DFA M，NFA M，使L(M) = L(M)DFA : S SNFA : S * 2S2.需证明，NFA M存在一个DFA M使 L(M)=L(M)2022-6-2076* , 2S SNFA转换为DFAvNFA M，DFA M，使L(M) = L(M) 设 NFA M = (S, , , S0, F) 将 NFA M

29、改造为 NFA M引入唯一的新初态结点X和新终态结点YX 到 S0 中所有结点均用 边 连接 F 中所有结点到 Y 也均用 边 连接反复使用图示的替换直至每条有向边上标记为 或单个字符 显然，L(M) = L(M)2022-6-2077NFA转换为DFAv基本思想是采用一种“子集构造” 算法来确定化 构造一个DFA M，使其每个状态对应于NFA M的状态集 使得在DFA读入a1a2an时，所处的状态对应于NFA所能到达的状态集如NFA读入a1a2an到达状态 中的任意一个，则DFA到达状态集2,3,4，即状态 观察NFA M：可能有 边，也可能有相同标记的边要构造DFA M，必须合并这两种边到

30、达的状态2022-6-2078NFA转换为DFAv 子集构造方法设 I S，定义 _closure ( I )1. q I, q _closure ( I )2. q I, 从 q 出发经任意条 边可达的 q _closure ( I ) 即 _closure ( I ) = I q | q I 旨在合并与状态集 I 相关的 边可达状态设 I S，a , 定义 Ia = _closure ( J ) q I，从 q 出发经 a 边可达的q J2022-6-2079NFA转换为DFAv 确定化方法1. 假定 = a1,a2,ak, 我们构造一张表S，S有k+1列，依次标记为I,Ia1,Ia2,I

31、ak2. 置该表的首行首列为_closure ( X ), X为NFA M 的初态3. 如果确定了第m（m1,2,）行中第一列的I，则计算Iax （x1,2,k），并填入m行中对应的列即Sm， Iax中4. 检查m行上的每个状态子集Iax （x1,2,k），如果Iax ，并且它还没有在表S的第一列中出现，则将其填入到空行的第一列5.重复3、4，直至所有Iax （x1,2,k）都在第一列上出现该过程一定在有限步内终止，因为M的子集数 = 2|S| 2022-6-2080NFA转换为DFAv 确定化方法（示例）假设 = a, b, 则定义一张表 S(I, Ia, Ib) 其中，第i行的表元素分别为

32、Si, I, Si, Ia, Si, Ib1. 置S1, I = _closure ( X ), X为NFA M 的初态2. 若Si, I , 则计算 Ia, Ib，填入 Si, Ia, Si, Ib3. 检查第i行的元素，若 Si, Ia 或 Si, Ib 还没有在第一列出现过 则 将Si, Ia 或 Si, Ib 填入 Sk+, I, （k表示第一个空行）；i+；返回步骤2否则算法终止2022-6-2081v 例 (a|b)*(aa|bb)(a|b)*2022-6-2082ISIaaIbbX, 5, 105, 3, 11 5, 4, 125, 3, 115, 3, 1, 2, 6, Y3

33、5, 4, 125, 4, 125, 3, 11 5, 4, 1, 2, 6, Y55, 3, 1, 2, 6, Y35, 3, 1, 2, 6, Y3 5, 4, 1, 6, Y45, 4, 1, 6, Y45, 3, 1, 6, Y6 5, 4, 1, 2, 6, Y55, 4, 1, 2, 6, Y55, 3, 1, 6, Y6 5, 4, 1, 2, 6, Y55, 3, 1, 6, Y65, 3, 1, 2, 6, Y3 5, 4, 1, 6, Y4v构造 DFA M 所构造的S表指定了DFA M的状态转换矩阵S表中的每个状态子集为DFA M的一个状态S表中的首行首列为初态S表中含有

34、终态的状态子集为DFA M的终态2022-6-20843.3.5 正规式与有限自动机的等价性v 证明一FA M，正规式 r，使得 L(r) = L(M)正规式与有限自动机的等价性v证明二正规式 r, FA M，使得 L(M) = L(r) 用关于正规式 r中运算符个数归纳证明1. 归纳基础：r中运算符数目为0即 r = 或 r = 或 r = a (a )，则显然，三个NFA分别接受的正规集为, 和a2. 归纳假设：设r,如果r中的运算符数目为k，则存在一个FA M，使得 L(M)=L(r)3. 当r中有k+1个运算符时，r有三种可能：r = r1| r2, r = r1 r2 或 r = r

35、1*； r1和r2 中的运算符数目=k. 根据归纳假设，对r1和r2存在FAM1和M2使得 L(M1)=L(r1)L(M2)=L(r2)2022-6-2085则对于r = r1| r2, 构造 M 为其中，为M引入新的初态结点q0和终态结点f0，并从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*, 构

36、造 M 为显然，有L(M) = L(M1)* = L(r1)* = L(r)2022-6-2086正规式与有限自动机的等价性v 基本思想（Thompson 构造算法） 对正规式的各个部分构造NFA 用弧连接起各个NFA，构成完整的自动机2022-6-2087接受正规式a的NFA接受正规式的NFA假设接受正规式r的NFA如下接受正规式rs的NFA接受正规式r|s的NFA接受正规式r*的NFA正规式与有限自动机的等价性例子v 设正规式为 r1= 1*， r2 = 01*， r3 = 01* | 12022-6-2088Thompson构造算法例子v正规式ab|a的NFA2022-6-2089Tho

37、mpson构造算法例子v正规式letter(letter|digit)*的NFA正规文法与有限自动机的等价性v 正规文法与正规式 程序语言通常采用正规文法定义它的词法规则 正规式是自动构造词法分析器的有效工具v 正规（3型）文法 G = (VT, VN, S, P) P: A B, A , A, B VN, VT * （右线性文法） P: A B, A , A, B VN, VT * （左线性文法）v 可等价变换为 p： A aB， A a A, B VN, a VT （右线性文法） p： A Ba， A a A, B VN, a VT （左线性文法）v 方便起见，右和左线性文法为分别记为GR

38、和GL正规文法与有限自动机的等价性v 等价性对正规文法G和FA M，若L(G)=L(M), 则称为G和M等价1. GR或GL，FA M，L(GR) = L(M) 或 L(GL) = L(M) 2. FA M， GR或GL， L(M) = L(GR) = L(GL) v 等价性证明对右线性文法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)2022-6-2092正规文法与有限自动机的等价性v 等价性证明（从正规文法构造FA

39、）基本思想 设 w = a1a2ak, 分别考虑GR和GL的最左推导 GR : S a1B1 a1a2B2 a1a2ak-1Bk-1 a1a2ak GL : S Bk-1ak Bk-2ak-1ak B1a2ak a1a2ak 非终结符的作用是记住字符个数，将其作为状态2022-6-2093正规文法与有限自动机的等价性v 从右线性文法构造FA设 GR = (VT, VN, S, P), 其中p： A aB， A a 令 NFA M = (VN F, VT, , S, F)，其中，1. 若AVN, 且a VT, 有A a, 则令 (A, a) = F2. 若AVN, 且a VT, 有A aA1|a

40、A2|aAk,则令 (A, a) = A1,A2, Ak容易证明，该NFA M所识别的语言L(M) = L(GR)2022-6-2094正规文法与有限自动机的等价性v 从左线性文法构造FA设 GL = (VT, VN, S, P), 其中P: A Ba， A a 令 NFA M = (VN q0, VT, , q0, S)，其中，1. 若AVN, 且a VT, 使A a, 则令 (q0, a) = A2. 若AVN, 且a VT, 使A1 Aa, A2 Aa,Ak Aa则令 (A, a) = A1,A2, Ak2022-6-2095正规文法与有限自动机的等价性v 从DFA中构造GR 设DFA

41、M = (S, , , S0, F), 若S0 F，则令GR = (, S, S0, P), 其中 P为若 则 A aB 或 A a | aB 若S0 F, 则因(S0, ) = S0, 故 L(M), 但 L(GR)引入S0 代替 S0 作为新的开始符号，并增加P：S0 S0 | 容易证明，L(GR) = L(M)v 从DFA中构造GL 可用类似的方法，但需逆向构造； 若 B Aa 若 A a | S0a2022-6-2096v 例3.4 DFA M GR NFA M GL 1. 设 DFA M = (A, B, C, D, 0, 1, , A, B) 使用FA到正规式的算法可证明L(M)

42、= 0(10)* GR = (0,1, A, B, C, D, A, P, 其中 P 为A 0 | 0B | 1DB 0D | 1CC 0 | 0B | 1DD 0D | 1D (D为无用产生式）2. 从GR中构造NFA M M = (A, B, C, D, F, 0, 1, , A, F)2022-6-20973. 从NFA M构造 GL 将 F 作为开始符号，从终态 F 出发逆向构造F 0 | A0 | C0C B1B 0 | A0 | C0D 1 | A1 | C1| D0 | D1| B0 因没有有向边射入 A，所以没有有关 A 的产生式 删除无用候选式后GL = (0, 1, F,

43、B, C, D, F, P)F 0 | C0C B1B 0 | C0D 1 | C1| D0 | D1| B02022-6-2099等价性的结论v正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的能力上是互相等价的。RG2022-6-20100DFA的化简vDFA M的化简 化简：寻找DFA M，使L(M) = L(M), 且|SM| SM| 最小化：寻找具有最少状态数的M，使L(M) = L(M)v等价状态和可区别的状态 M中的不同状态s和t是等价的如果从状态s出发能读出某个字w而停于终态，那么同样从t出发也能读出同样的字w而停于终态；反之，若从t出发能读出某个字w而停于终态，则

44、从s出发也能读出同样的w而停于终态。2022-6-20101DFA的化简v 状态的等价关系() 设 s, t SM, s t, 定义s t, 若w = a1a2ak *, 有v 状态的可区分关系 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, 使得SiSj = , s, t Si, s