编译原理与技术讲义-第2章.ppt

青岛大学信息工程学院 编译原理与技术 第 2章 词法分析 青岛大学信息工程学院 编译原理与技术 2 主要内容 词法分析器的设计 词法分析器的一种手工实现 正规表达式 有限自动机 词法分析的自动生成器 Lex 青岛大学信息工程学院 编译原理与技术 3 词法分析器在编译中的位置 词法分 析器 语法分 析器 符号表 源程序 单词 取下一个单词 单词记号 青岛大学信息工程学院 编译原理与技术 4 2.1 词法分析器的设计 词法分析器的基本功能 按照语言的定义规则，逐个地读入源程序的 符号，识别出对语言有意义的符号串，即单 词符号； 分析单词记号的属性，并把单词记号及其属 性填写在符号表中； 同时把源程序改造成等价的计算机内部表示 单词记号，以便编译的后续阶段使用。 还要对源程序进行预处理工作，包括：删除 源程序中的空格、制表符、换行、注释等不 影响程序语法、语义的结构。 青岛大学信息工程学院 编译原理与技术 5 2.1 词法分析器的设计 高级程序语言的五种单词记号： 保留字 是程序语言定义的具有固定意义的英文单词， 有时称为基本字或关键字。例如，在 C+中， char、 float、 extern、 friend、 switch、 new都是关键字。保 留字一般不能另作它用。 标识符 表示各种名字的字符串，如变量名、类型名、 函数名、对象名等。 运算符 如 +、 、 = =、 =等。 常量 常量的类型一般有整型、实型、布尔型、文字 型等。 分界符 如分号、括号、注释标记 /*、 */等。 青岛大学信息工程学院 编译原理与技术 6 2.1 词法分析器的设计 词法分析器的输出 单词记号一般采用形式为 的二元式。 单词的种别是语法分析需要的信息，通常用 整数表示； 单词的属性值则是编译的语义分析和代码生 成等阶段需要的信息。 青岛大学信息工程学院 编译原理与技术 7 2.1 词法分析器的设计 例 2.1： 假如保留字的编码是 1， 标识符的为 2，运算符为 3，分 界符为 4，整型常量为 10，实 型常量为 11。那么，对于源程 序代码： for (i = 1, sum = 9.8; i = 100; i+) sum += i3.14; 词法分析器产生的结果是单词 记号序列 3， 青岛大学信息工程学院 编译原理与技术 8 2.1 词法分析器的设计 词法扫描器与符号表 对符号表的操作主要是填表、查询和更新。 每当词法分析器识别了一个单词的时候，第一项工作 就是查询符号表。对于不同的单词种别，查询的方式 和随后的处理完全不同。例如，对于关键字、分界符 和运算符等，只需在各自的符号表中查询，获得并记 录其它属性值，生成相应的单词记号。 处理常量，特别是处理标识符要复杂的多，而且仅仅 在词法分析阶段是无法获得一个标识符的所有信息。 当词法扫描器识别了一个标识符的时候，首先查询关 键字表，看它是否是关键字；如果不是，还要在标识 符表中查询，看它是否已经存在，如果不存在就把它 填入标识符表，并填入种别、类型等信息。 青岛大学信息工程学院 编译原理与技术 9 2.1 词法分析器的设计 词法分析器的两种实现模式 完全独立模式和相对独立模式 在完全独立模式下，词法分析器作为编译的 子系统单独地运行一趟，扫描整个源程序， 把识别的单词序列以机器内码的形式输出在 一个中间文件上，供为语法分析使用。 青岛大学信息工程学院 编译原理与技术 10 2.1 词法分析器的设计 完全独立模式的好处 编译程序结构清晰、条理化而且便于高效地实现； 在设计高级语言时能独立地研究词法与语法两个方面 的特性； 增强编译程序的可移植性：可以就同一个语言为不同 的机器写不同的词法分析器，而只编写一个共同的语 法分析，使用这些词法分析器相同的单词机内表示； 把同一个词法由于单词记号的语法可以用较简单的文 法描述，把词法和语法分开，就能为这种文法建立有 效的特殊方法和自动构造技术。 青岛大学信息工程学院 编译原理与技术 11 2.1 词法分析器的设计 相对独立模式：词法分析器设计成一个子程 序，每当语法分析需要一个单词的时候，就 调用该子程序。 相对独立模式的好处：词法分析器和语法分 析器被设计在同一趟，省去了存放单词的终 结文件。 青岛大学信息工程学院 编译原理与技术 12 2.1 词法分析器的设计 词法错误的处理 在词法分析阶段发现的错误统称为词法错误， 它们大多是单词拼写错误，这或者是因为书 写错误、或者因为键入错误，例如把关键字 拼写错。 对词法错误校正的常用策略是修补尝试，一 般包括： 删除一个多余的字符； 插入一个遗漏的字符； 用一个正确的字符替换一个不正确的字符； 交换两个相邻的字符。 青岛大学信息工程学院 编译原理与技术 13 2.2 词法分析器的一种手工实现 输入的预处理 对于许多程序语言来说，空格、制表符、换 行符等编辑性字符除了出现在文字常量中， 在其它任何地方的出现都没有意义，而注释 作为程序的重要文档几乎可以出现在程序中 的任何地方。它们的存在可以改善程序的可 读性和易理解性，却不影响程序的语法结构 和执行语义。 通常在编译的词法分析阶段被预处理过程删 除掉。 青岛大学信息工程学院 编译原理与技术 14 2.2 词法分析器的一种手工实现 输入的预处理 扫描器对缓冲区进行扫描时一般使用两个指针： 一个指向当前正在识别的单词的起始位置，另一 个用于向前搜索以寻找该单词的终点，两个指针 之间的符号串就是要识别的单词符号。无论扫描 缓冲区设计的多大都不能保证单词符号不会超过 其边界。扫描缓冲区一分为二的两段置 . .f o r ( s u m = 0 , i = 1 . 搜索指针 起点指针 .C a r.e e l . 2 . 青岛大学信息工程学院 编译原理与技术 15 2.2 词法分析器的一种手工实现 超前搜索和最长匹配 为了识别一个更有意义的单词符号，在找到了可能是 单词符号的起点或者构成了单词部分时，扫描器并不 满足，还要继续读入输入串，看是否能找到由更多符 号所组成的单词（即最长匹配），有时可能要扫描到 一个可以“断句”的符号（超前搜索），才能决定最 后一个扫描的符号不属于之前的符号串所构成的单词。 超前搜索符号通常是最长匹配单词的结束标志，可以 是空格符、回车符、制表符等可以被预处理掉的符号； 也可能是下一个单词记号的起始符。 青岛大学信息工程学院 编译原理与技术 16 2.2 词法分析器的一种手工实现 超前搜索和最长匹配的例子 在识别“ for”的时候，要扫描到左括弧 (时 才知道，它不属于标识符的符号； 当读到了 ，以便构造出小于等于“ =”或 不等于“ ”的比较运算符，否则，就构造小 于运算符。 青岛大学信息工程学院 编译原理与技术 17 2.2 词法分析器的一种手工实现 状态转换图 状态转换图是构造词法分析器的一个良好工具，它描 绘了为得到一个单词记号，词法分析器应该执行的动 作。 状态转换图是一个有向图，结点代表状态，用圆圈表 示，内部用数字表示状态名称； 状态之间由箭弧连接，箭弧上有符号作为标记，称为 从箭弧尾的离开状态读入标记符号以后转换到箭弧头 的进入状态。 若离开状态 s的某个标记为 other，则表示离开 s的其它 箭弧标记以外的任意符号。 每个状态转换图中的状态数量有限，都有唯一的一个 起始状态（本书用一个进入的箭头表示）和至少一个 终结状态（用双圈表示）。 青岛大学信息工程学院 编译原理与技术 18 2.2 词法分析器的一种手工实现 状态转换图识别或接受一定的输入符号串 从起始状态开始，读进输入符号串的一个符 号 a，沿着状态转换标记为 a进入下一个状态， 重复执行直到进入终结状态。 即，如果存在一个从起始状态到终结状态的 路径，路径上的标记用连接运算连接在一起 形成一个符号串，它和输入符号串相同，则 称该输入符号串可以接受。如果不能进入任 何一个终结状态，则称该状态转换图不能识 别或接受这个输入符号串 青岛大学信息工程学院 编译原理与技术 19 2.2 词法分析器的一种手工实现 digit 0 1 letter letter 对于符号串 var1，有状态序列 11110 1 rav ， 例 2.2： 标识符一般定义为字母打头的字母数字序列 . 青岛大学信息工程学院 编译原理与技术 20 2.2 词法分析器的一种手工实现 5 other = 1 = 0 3 2 例 2.3： 类似语言中的关系符的 状态转换图 。 在终结状态加了星号 *，表示 在状态 1、 2和 3都还不能确定 它们是否是符合最长匹配准则 的单词记号，还需要在读入一 个字符才能确定。 而为实现最长匹配的一个超前 搜索符号“其它”则不属于这 个单词，应该推给扫描缓冲区。 青岛大学信息工程学院 编译原理与技术 21 2.2 词法分析器的一种手工实现 例 2.4： Pascal语言中数的状态转换图 。 在这个复杂的例子中，状态 3、 5和 8分别表示识别是整数、不带指数部分 的实数以及带有指数部分的实数，但是，只能在超前搜索一个其它符号以 后，才能在状态 9确定识别了一个 Pascal的数。读者可以自己验证例子数 2005， +1998， 81.07， 2.0036，看它们是否能被这个转换图所接受。 3 digit digit other digit digit digit 9 8 1 4 5 6 2 +, E 7 +, digit E digit other other * 青岛大学信息工程学院 编译原理与技术 22 2.2 词法分析器的一种手工实现 基于状态转换图的词法分析器的实现 code表示单词记号的种别； value存放标识符或数在符号表的入口地址； 过程 getghar(ch)从扫描缓冲区得到一个搜索符号， 存储在变量 ch中； 函数 isLetter(ch)和 isDigit(ch)分别检查 ch是否是字 母 /数字； 函数 lookup(token, table) 在符号表 table中查询是否 包含单词 token； insert (token, table)在则把单词 token插入符号表 table中并返回在符号表的地址； 函数 reporterror()报告并简单处理词法错误。 青岛大学信息工程学院 编译原理与技术 23 2.2 词法分析器的一种手工实现 根据状态栈图编写词法扫描器的方法一 让状态转移对应一个读入字符的语句或函数， 然后与转移上的标记比较，如果相等就进入 转移对应的程序段或子程序；否则，调用错 误处理程序。 多个转移就对应分支语句； 如果转移返回自身，形成一个圈，对应程序 段的就是循环语句。 青岛大学信息工程学院 编译原理与技术 24 2.2 词法分析器的一种手工实现 标识符状态转换图的一个实现 int code, value; char token =”; / 在开始状态 0 do token = token+ch; / 不断读入字母或数字 ， 合并成一个标识符 getchar(ch); / 保持在状态 1 while (!isLetter(ch) | !isDigit(ch)； / isLetter(ch)和 isDigit(ch)分别检查 ch是否是字母 / 数字 / 进入结束开始状态 2 code = lookup(token, keywordsTable); / 在关键字表中查询 token， 若它是关键字就返回 1 if (code= =1) return(1, token); / 返回关键字的单词记号 ， 假如关键字种别是 1 else value=insert(token, identifierTable); / 把 token插入标识符表 ， 返回入口地址 return (2, value) / 返回标识符的单词记号 ， 假如标识符种别是 2 青岛大学信息工程学院 编译原理与技术 25 2.2 词法分析器的一种手工实现 根据状态栈图编写词法扫描器的方法二 采用一个变量来记录当前的状态，把状态转 换嵌入到一个循环体内的分支语句中，其中 的第一个分支测试当前状态，而嵌入内层的 第一个分支语句则对给定的状态测试输入符 号，以决定转移进入的状态。 青岛大学信息工程学院 编译原理与技术 26 2.2 词法分析器的一种手工实现 例 2.5： 下图示意的是识别 C风格注释，即形式 /*.*/，的状态转换图。状态 2 中的标记 other是除 *之外的其它符号，而从状态 3到状态 2的标 记 other是除 *和 /之外的其它符号。 4 1 3 2 other * 0 / / other * * 青岛大学信息工程学院 编译原理与技术 27 2.2 词法分析器的一种手工实现 int state = 0; while (state = 0, 1, 2, 3 ) switch state case 0: getchar(ch); if (ch = = /) state = 1; getchar(ch) ; else reporterror(); case 1: getchar(ch); if (ch = = *) state = 2; getchar(ch) ; else reporterror(); case 2: getchar(ch); if (ch = = *) state = 3; getchar(ch) ; else getcharch(ch); / 还是在状态 2 case 3: getchar(ch); switch ch case /: state = 4; getchar(ch) ; case *: state =3; getchar(ch) ; default: state = 2 if (state = = 4 ) return; else reporterror(); 青岛大学信息工程学院 编译原理与技术 28 Id-keywords number other other other EA other other other digit other inID start LNE = * = = = = other * letter, digit letter 2 3 inNum * digit digit * comment GE = = * + * / = + * / digit 课本图 2.6: int code, value,; char state = “start”; char token =”; state_sets表示所有状态名的集合 青岛大学信息工程学院 编译原理与技术 29 2.2 词法分析器的一种手工实现 while (state属于 state_sets) switch state case “comment”: getchar(ch); if (ch = = ) state = “start”; getchar(ch) ; case “start”: getchar(ch); switch ch case isletter(ch): state = “inID”; token = ch; getchar(ch) ; case isdigit(ch): state = “inNum”; token = ch; getchar(ch) ; case ch = = : state = “comment”; getchar(ch) ; case ch = = : state = “GE”; token = ch; getchar(ch) ; case ch = =+ : state = “+” ; token = ch; case ch = = : state = “” ; token = ch; case ch = =* : state = “*” ; token = ch; case ch = =/ : state = “/” ; token = ch; default: getchar(ch); / 过滤掉无用的符号 青岛大学信息工程学院 编译原理与技术 30 2.2 词法分析器的一种手工实现 case “inNum”: while (state属于 inNumber, 2, 3) / 处理数 switch state case “inNum”: switch ch / 处理整数 case isdigit(ch): token = token+ch; getchar(ch) ; case ch = = . : state = “2”; token = token+ch; getchar(ch); default: state = “number”; code=10; / 处理实数 case “2”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else reporterror (); case “3”: if (isdigit(ch) state = “3”; token = token+ch; getchar(ch); else code = 11; state = “number”; case “number”: value = insert (token, identifierTable); return(code, value); 青岛大学信息工程学院 编译原理与技术 31 2.2 词法分析器的一种手工实现 case “inID”: while (isletter(ch) | isdigit(ch) token = token+ch; getchar(ch) ; code = lookup(token, keywordsTable); / 在关键字表中查询 token if (code= =1) return(1, token); / 返回关键字的单词记号 else value=insert(token, identifierTable); / 把 token插入标识符表 return (2, value); / 返回标识符的单词记号 case “LNE”: getchar(ch); if (ch = = ) getchar(ch); return(3, “”); if (ch = = =) getchar(ch); return(3, “=”); else return(3, “=”); else return(3, “”); case “+”: getchar(ch); return(3, “+”); case “”: getchar(ch); return(3, “”); case “”: getchar(ch); return(3, “”); case “/”: getchar(ch); return(3, “/”); 青岛大学信息工程学院 编译原理与技术 32 2.3 正规表达式 符号、符号串与符号集合 定义 2.1：字母表是有限的非空的符号集合， 字母表中的元素称作符号。 例如，二进制数语言的字母表是 0, 1； Java 语言的字母表可以说是一切可以打印字符组 成的集合。 青岛大学信息工程学院 编译原理与技术 33 2.3 正规表达式 定义 2.2：由字母表中的符号所组成的任何有 限序列称为符号串。一个符号串所包含符号 的个数称为该符号串的长度。 例如，对于字母表 a, b， a、 b、 aa、 ab、 ba 和 abba都是 上的符号串。符号串 b、 ab和 abba 的长度分别是 1、 2和 4。符号串中符号的排列顺序 十分重要，上面的 ab和 ba表示不同的符号串。通 常用小写的希腊字母 、 、 、 等表示符号串。 符号 的长度表示成 |，例如 |abba|=4。 允许空符号串，即不包含任何符号的符号串，用 希腊字母 表示， |=0。 青岛大学信息工程学院 编译原理与技术 34 2.3 正规表达式 如果 x=uv是一个符号串，则称 u是 x的头，称 v是 x 的尾。当我们堆一个符号串的某些部分感兴趣、 堆其它部分不感兴趣时，通常忽略调不感兴趣的 部分，而只保留感兴趣的部分。 例如，若我们只关心符号串 x=t中的符号 t，也 可以用 x=.t.表示；同样， x=t和 x=t.这两种表 示都只关注符号的头时符号 t。 青岛大学信息工程学院 编译原理与技术 35 2.3 正规表达式 定义 2.3：设 和 是同一字母表上的符号串，把 的各 个符号相继地写在 之后所的到的符号串称为 和 的 连接（并置）， 记做。显然， |=|+|。 例如，字母表 a, b, 0, 1上的符号串 =bb11、 =a00， 是 bb11a00，而 是 a00bb11，而且 | = | = 7 =| + | = | +| = 4+3 = 7。 显然，对于任何符号串 ，都有 。 定义 2.4：设 u是某一字母表上的符号串，把 u自身连 接 n次，即 =u.u(n个 u)，称作符号串 u的 n次方幂， 记做 =un。 例如， u1=u， u2=uu， u4=uuuu。特别地，当 n=0时， u0=。显然， uun-1 = un-1u= un。 青岛大学信息工程学院 编译原理与技术 36 2.3 正规表达式 定义 2.5：若集合 A中的所有元素都是某字母表上的符号串，则 称集合 A是该字母表上的符号集合。 字母表上的符号集合通常用大写字母 A、 B、 C等表示。例如， 字母表 a, b, 0, 1上长度为 2的符号串集合 A= | =xy，并且 x和 y是 中的一个符号 ；字母表 上单词 B= | 是 a, b中的符 号串 。 定义 2.6：两个符号串集合 A和 B的乘积 AB定义为： AB=uv | uA并且 vB。 例如，设 A=a, b， B=0, 1，那么 AB=a0, a1, b0, b1， BA=0a, 1a, 0b, 1b， AA=aa, ab, ba, bb。由于对于任何符号 串 x都有 x x x，所以 A=A=A，但是，对于空集 ，却 有等式 A=A=。 类似于符号串的方幂，可以定义符号串集合的方幂，特别地，定义字母表 A的方幂为 A0= ， A1=A， An= An-1 A ( n 0 )， 显然，若 u An，则 | u | = n。 青岛大学信息工程学院 编译原理与技术 37 2.3 正规表达式 定义 2.7：字母表 的闭包 * 0 1 . n.，正 闭包 + 1 2 . n. 。 例如，对于字母表 a, b， += a, b, aa, bb, ab, ba, aaa, bbb, aab, bba, aba, bab, abb, baa, .。 显然， * 0 +， += * = *。 *表示字母表 上所有长度的符号串的集合，包括空 符号串； +表示长度至少为 1的符号串的集合。 +实际上就表示了该字母表所构成的语言，句子就是 其中的符号串。 对于 C语言，可以说， C语言是其字母表，也即基本 符号正闭包的真子集。 青岛大学信息工程学院 编译原理与技术 38 2.3 正规表达式 例 2.6：令字母表 L=A, B, ., Z, a, b, ., z， D=0, 1, ., 9，那么 L D是字母和数字的集合； LD4表示以字母开头、跟随 4个数字的串的集 合； L(L D)15表示长度为 16的标识符，即以字母 开始的 16位的字母和数字串的集合； D*表示不含空的数字串的集合。 青岛大学信息工程学院 编译原理与技术 39 2.3 正规表达式 正规式与正规集 字母表 上的正规表达式用来描述一种称为正规集的语言。 定义 2.8：字母表 上的正规表达式（简称正规式）按照下列规 则递归地定义： （ 1） 是 上的正规式，它表示的正规集是 ； （ 2） 是 上的正规式，它表示的正规集是 ； （ 3） 中的任意符号 a都是 上的正规式，它表示的正规集是 a （ 4）若 r和 t都是正规式，它们所表示的正规集分别是 L(r)和 L(t)，那么 (r)、 r|t 、 rt和 r*都是正规式，表示的正规集分别是 L(r)、 L(r) L(t)、 L(r)L(t)、 ( L(r) *。 根据显然定义有下列等式： L(a)=a， L()=， L()=， L(r)= L(r)， L(rt)= L(r)L(t)， L(r|t)= L(r) L(t)， L(r*)= ( L(r) *。 青岛大学信息工程学院 编译原理与技术 40 2.3 正规表达式 例 2.7：令字母表 =a, b, c，那么 (a|b)(a|b) aa, ab, ba, bb； (a|c)*表示所有 a和 c组成的符号串，其中包含空串 ； (a|c)*b(a|c)*表示只包含一个 b的字母表 上的所有符 号串，例如 b， abc， baaac， caccb， ccbaaa。 最多包含一个 b的字母表 上的符号串的集合可以表 示成 (a|c)*| (a|c)*b(a|c)*)，或者 (a|c)*(b|)(a|c)*。 (a|c)*b(a|c)* b表示的集合是什么呢？它表示只含两个 b的符号串的集合。 青岛大学信息工程学院 编译原理与技术 41 2.3 正规表达式 定义 2.9：如果两个正 规式 r与 t表示的正规 集相同，则称它们的 等价的，记做 r=t。 正规式等价的例子如 a|(ba)*= (ba)*|a， (a|b)=(b|a)。 定理 解释 r|t = t|r | 的交换律 r|(s|t) = (r|s)|t r(st) = (rs)t 结合律 r(s|t) = rs | rt (r|s)t = rt | st 分配律 r = r = r r = r = r r | = r 吸收律 r* = (r | )* 闭包运算和 之间的关系 青岛大学信息工程学院 编译原理与技术 42 2.3 正规表达式 扩展的正规式 （ 1）一个或多次重复：一元后缀算符“ +”表示一个或多次重复， 即正规式 r+表示一个或多个 r的串的集合。这样， (0|1)+表示所 有二进制数字的集合，而 (0|1)*同时还包含了可串。 （ 2）字符集的范围：对于字母或数字的集合，可以使用 a|b|.|z或 0|1|.|9。更简洁的方式是用方括弧，用连接线表示范围，这样， 上面的字母或数字就可以分别表示成 a-z和 0-9。类似的， a|b|c|d可以写成 a-d或者 abcd。标识符是字母打头的字母数字 串，可以表示成 A-Za-z A-Za-z0-9*。 （ 3）零个或一个：一元后缀算符“ ?”表示零个或一个， r?是 r|的 缩写。带符号的整数可以写成 (+|)?1-90-9* 青岛大学信息工程学院 编译原理与技术 43 2.3 正规表达式 如果正规式很长，可以给它命名，使它们可 以像普通的符号一样，在随后的正规式中使 用这些名字来引用相应的正规式，以便得到 简洁的正规式。 如果 r如是字母表 上的正规式，那么正规定 义的形式是： name r 。这样，正规式 r的名 字 name就可以像 中的符号一样，在以后构 造 上正规式的时候使用。 青岛大学信息工程学院 编译原理与技术 44 2.3 正规表达式 例 2.8： Pascal语言的标识符集合是字母开头的 字母数字串，下面就是这个集合的正规定义： letter A -Za-z digit 0 -9 identifier letter( letter| digit )* 青岛大学信息工程学院 编译原理与技术 45 2.3 正规表达式 例 2.9： Pascal语言的数是 2005， +1998， 81.07， 2.0036这样的串，即由整数、小数和指数三个部分 组成。小数和指数部分是可选的，其中指数标记 E后 面可以有 +或 ，再跟上一个或多个数字，而小数点 之后必须至少有一个数字。下面就是 Pascal语言的数 的集合的正规定义： digit 0 -9 digits digit digit* signed + | fraction (.digits)? exponent (E(signed)?digits)? number signed? digits fraction exponent 青岛大学信息工程学院 编译原理与技术 46 2.3 正规表达式 正规表达式的实现和应用 正规表达式实际上是描述和识别一组字符串的模板 （模式），它包含字符、元符号（如表示重复的 * 和选择符 |）和一些具有特殊意义的符号。这个模板 决定什么样的字符串属于某一个集合。 正规表达式在处理文本方面具有强大的能力，它在 计算机领域的应用不仅仅局限于构造编译器的词法 扫描器，其它著名的应用还包括 UNIX操作系统的 命令工具如 grep，处理复杂文本分析与操作的脚本 语言 Perl， Tcl， Python， PHP和 awk以及通用程序 开发编辑器 emacs。 由于正规表达式的重要而广泛的应用， Java语言通 过包 java.util.regex还对正规表达式的处理提供了直 接支持。 青岛大学信息工程学院 编译原理与技术 47 2.4 有限自动机 为什么引入有限自动机 确定的有限自动机和不确定的有限自动机都 能识别正规集，即它们识别的语言正好就是 正规式所能表达的语言，而且在识别语言的 能力上，它们完全等价。 但是，实现这两类有限状态机的效率不同， 用它们构造的词法分析器在识别语言中单词 记号的效率方面也有显著的差别。 正规式 不确定的有限 自动机 确定的有限 自动机 词法分析器 青岛大学信息工程学院 编译原理与技术 48 2.4 有限自动机 确定的有限自动机 DFA 定义 2.10：一个确定的有限自动机 DFA M是五元组 ，其中： （ 1） S是非空的有限的状态集合； （ 2） 是非空的输入字母表； （ 3） T是部分单值映射 S S ，又称转移函数； T(s1, a)= s2表示输入符号 a时，把状态 s1转换到 s2，成 为当前状态； （ 4） s0S，是唯一的起始状态； （ 5） FS，是非空的终结状态。 被 M接受或识别的语言，记做 L(M)，定义为字符串 的集合，其中每个 ci，并且存在状态序列 s1=T(s0, c1), s2=T(s1, c2), . , sn=T(sn-1, cn)， sn F。 青岛大学信息工程学院 编译原理与技术 49 2.4 有限自动机 例 2.10：一个有限自动机 DFA N= ，其中 T的定义如下 : T(A, +)=B T(A, )=B T(A, )=C T(A, d)=D T(B, )=D T(B, d)=C T(C, ) E T(C, d)=C T(D, d) E T(E, d) E 状态 A是起始状态， E是终结状态。 青岛大学信息工程学院 编译原理与技术 50 2.4 有限自动机 转换函数可以用状态 转换矩阵或状态转换 表来表示，该表的行 表示状态，列对应输 入的符号，表元素表 示状态转移的状态， 空白元素对应的二元 组 没有 定义。 + d A B B C D B D C C E C D E E E 例 2.10有限自动机的状态转换矩阵 青岛大学信息工程学院 编译原理与技术 51 2.4 有限自动机 一个 DFA也可以表示成一个确定的状态转换 图，状态转换函数 T(s1, a)=s2对应了连接两个 结点 s1和 s2，标记为 a的有向弧。 +, C E d A D B d d d d 例 2.10有限自动机的状态转换图 从状态 A到 B的转换上的标记 “ +, ”表示两条从 A到 B的弧 的标记 +和 ， 这是常用的简 化方式。 青岛大学信息工程学院 编译原理与技术 52 2.4 有限自动机 定义 2.11：对于有限自动机 M的 *中的任何一 个符号串 ，若存在一条从起始状态到某一终 结状态的通路，且这条通路上所有弧的标记 符连成的串等于 ，则称 被 M识别（读出或 接受）。若起始状态也是一个终结状态，则 空串 可以为 M接受。 DFA M所能识别的所有 字的集合称为 M识别的语言，记做 L(M)。 青岛大学信息工程学院 编译原理与技术 53 2.4 有限自动机 例如，考虑上述的有限自动机，如果 d代表任意 一个数字 0， 1， .， 9，它能否接受符号串 30.、 +.28和 813.19？对于它们，可以分别给出从 状态 A到终结状态 E的路径： 因而它们都是这个 DFA N可以接受的数。 EEDBA 82. EEECCCBA 91.318 EEDA .03 青岛大学信息工程学院 编译原理与技术 54 2.4 有限自动机 定义 2.12(a)：两个有限自动机 M1和 M2是等价 的，当且仅当它们识别相同的语言，即 L(M1)=L(M2)。 定义 2.12(b)：两个有限自动机 M1和 M2是等 价的，当且仅当对于每个 M1接受的符号串 ， M2接受 。 青岛大学信息工程学院 编译原理与技术 55 2.4 有限自动机 不确定的有限自动机 NFA 定义：一个不确定的有限自动机 NFA M是五元组 ， 其中： （ 1） S是非空的有限的状态集合； （ 2） 是非空的输入字母表； （ 3） T是 S() 2S （ S的幂集），它可以把一个状态映射 到一组状态 ； T(s1, a)= s2表示输入符号 a时，把状态 s1转换到 s2，成为当前状 态； （ 4） s0S，是唯一的起始状态； （ 5） FS，是非空的终结状态。 被 M接受或识别的语言，记做 L(M)，定义为字符串 的集 合，其中每个 ci，并且存在状态序列 s1=T(s0, c1), s2=T(s1, c2), . , sn=T(sn-1, cn)， sn F。 青岛大学信息工程学院 编译原理与技术 56 2.4 有限自动机 例 2.11：识别语言 (a|b)nabb | n0的一 个 NFA M = ， a b 0 1,2 1 1 1,2 1 2 3 3 4 a a 2 4 a 0 3 1 b b b b a 这个 NFA识别 aabbabb，即存在一个状态序列，从状态 0到状态 4，路经上的标记连接 是 aabbabb： 43211110 bbabbaa 青岛大学信息工程学院 编译原理与技术 57 2.4 有限自动机 两个 NFA N1和 N2称为等价的，当且仅当它们 识别同一个语言，即 L(N1)=L(N2)。 为什么要引入 NFA？ 首先，需要有限自动机的主要目的是用来识别正 规式所描述语言的单词记号，直接从正规式构造 出 DFA的算法比较复杂，而从正规式构造 NFA的 算法则相对简单；然后，再从 NFA构造等价的 DFA作为记号的识别分析器。 其次，我们有时需要多值映射以及所谓的空转移， 即形式为 N 的产生式，以便简洁地表达多种可 能的选择。而且，使用空转移描述对空串的匹配， 更加直观和自然。 青岛大学信息工程学院 编译原理与技术 58 2.4 有限自动机 从 NFA到 DFA的等价变换 定理 2.1：对于任意一个 NFA N都存在一个 等价的 DFA M，即 L(N) = L(M)。 为了从 NFA构造出等价的 DFA，需要 消除 N 形式的产生式，即消除空转移； 确定化每个多重转移，即拆分多值函数为单值函 数。 一个常用的方法是子集法。 青岛大学信息工程学院 编译原理与技术 59 2.4 有限自动机 定义 2.13：设 I是 NFA N=中一 个状态子集，对 I的 闭包运算 -closure(I)的结 果是一个状态子集，定义为 -closure(I) = s | s I s | s -closure(I)并且存在 T(s, )=s。 直观地说，状态子集 I的 闭包就是从 I中的任 何一个状态经过任意个 连线所能达到的所有 状态。 青岛大学信息工程学院 编译原理与技术 60 2.4 有限自动机 例 2.12：下图是接受连续 a或 b的语言的一个 NFA， 尽管在每个状态，对应字母表上符号的转移是唯一 的，但是，由于增加了所谓的空转移 转移，所以， 它不是 DFA。 a b E 5 1 3 2 B 6 b a a a 4 b b 例如，一个子集 I=B，按照定义，计算 -closure(B)的序列如下： -closure(B) B B, 5 B, 5, 1 青岛大学信息工程学院 编译原理与技术 61 2.4 有限自动机 定义 2.14：设 I是 NFA N=中一 个状态子集， a，对 I移动的闭包运算 Ia的 结果是一个状态子集，定义为 Ia=-closure(J)， 其中 J = s | s I并且存在 T(s, a)=s。 直观上，状态子集 Ia是从 I中的任何一个状态 经过标记为 a的一次转移之后所能到达的所有 状态的 闭包。计算 Ia的两个步骤： （ 1）计算从 I读入符号 a所达到的状态集合 J； （ 2）求 J的 闭包，即 -closure(J)。 青岛大学信息工程学院 编译原理与技术 62 算法 2.1 从 NFA到 DFA的等价构造算法 输入： NFA N=) 输出： 等价的 DFA 假设 =a1,a2,., an （ 1）首先构造 DFA的状态转换表 MATRIX：这是一个 n+1列、行动态增长的表格； 第零列的每个元素对应 DFA的状态，随着算法的执行，递增地产生新的状态，即增加新行； 初始化： row = 1; / MATRIX的行 sn = row; / DFA的状态个数 MATRIXrow, 0 = -closure(q0)； S= MATRIXrow, 0 ； / 加入 DFA状态集合的第一个状态，它本身是一个集合 do / 逐行地填表 for i = 1 to n do MATRIXrow, i = Iai； / 在每行逐列地填表 if Iai S then S = S Iai； / 把 Iai加入 S sn = sn + 1; MATRIXsn, 0 = Iai； / 状态转换表增加一行，即增加一个新的状态 end if; end for； row = row + 1; / 计算下一个状态的 Iai while sn = = row / 直到没有新的状态为止 （ 2）矩阵中第一行第零列所表示的状态就是 DFA的起始状态； （ 3）包含了 NFA终结状态的新状态就是 DFA的终结状态。 （ 4）可选：重新命名 DFA的状态，相应地改变状态转换函数中状态名字。 青岛大学信息工程学院 编译原理与技术 63 2.4 有限自动机 例 2.13：对例 2.12表示的 NFA构造等价的 DFA。 首先，把 -closure(q0)=-closure(B)=B, 5, 1填入转 换矩阵表的第一行第一列。然后对每个 a计算 Ia并填入表 中，如果 Ia是新的状态集合，则在状态转换矩阵表中新增一 行，把它加入其中。对于 a，计算 Ia=-closure(B, 5, 1) =5, 1, 3，是个新的状态集合，加入表的第二行；对于对 于 b，计算 Ib=-closure(B, 5, 1) =5, 1, 4，也是个新的 状态集合，加入表的第三行。 然后，把 5, 1, 3看作 I，对每个 a计算 Ia并填入表中。 Ia= 5, 1, 3, 2, 6, E是个新的状态集合，加入表中的下一行，而 Ib= 5, 1, 4已经出现过，什么也不做。 青岛大学信息工程学院 编译原理与技术 64 2.4 有限自动机 这样继续下去，最后得到的状态转换矩阵如表 2.5(a)所示。 Ia Ib B, 5, 1 5, 1, 3 5, 1, 4 5, 1, 3 5, 1, 3, 2, 6, E 5, 1, 4 5, 1, 4 5, 1, 3 5, 1, 4, 2, 6, E 5, 1, 3, 2, 6, E 5, 1, 3, 2, 6, E 5, 1, 4, 6, E 5, 1, 4, 2, 6, E 5, 1, 3, 6, E 5, 1, 4, 2, 6, E 5, 1, 4, 6, E 5, 1, 3, 6, E 5, 1, 4, 2, 6, E 5, 1, 3, 6, E 5, 1, 3, 2, 6, E 5, 1, 4, 6, E 青岛大学信息工程学院 编译原理与技术 65 2.4 有限自动机 状态子集重新命名，并将 Ia和 Ib分 别视为 a与 b后得表 2.5(b)，对应的 状态转换图如图 2.13所示。 a b 0 1 2 1 3 2 2 1 4 3 5 6 4 6 4 3 5 a b 3 4 a 0 1 b b b a 2 5 6 b a a b b a a 青岛大学信息工程学院 编译原理与技术 66 2.4 有限自动机 例 2.14：对例子 2.11表示的 NFA（如下图）构造等价 的 DFA。 a b 4 3 a b 0 1 b b b a 2 b a a a Ia Ib 0 1, 2 1 1, 2 1, 2 1, 3 1 1, 2 1 1, 3 1, 2 1, 4 1, 4 1, 2 1 青岛大学信息工程学院 编译原理与技术 67 2.4 有限自动机 DFA的最小化 定理 2.2：对任意一个 DFA N都存在一个等价 的 DFA M，它包含最少的状态数，而且这个 最小状态的 DFA M是唯一的（状态名不同的 同构情况除外）。 关键在于把 DFA的状态划分成一些不相交的 等价子集，使得任何两个不同子集中的状态 都可以区别，而每个子集内的状态都是等价 的。这样，每个子集用一个状态代表，删除 子集中的其它状态，就得到了状态个数最少 的 DFA。 青岛大学信息工程学院 编译原理与技术 68 2.4 有限自动机 定义 2.15：设 q1和 q2是 DFA N中的两个不同的状态， 如果从状态 q1出发能扫描任意串 而停于终结状态， 当且仅当从 q2出发也能扫描任意串 而停于终结状态， 称状态 q1和 q2是等价的。 定义 2.16：若两个状态 q1和 q2不是等价的，则称这两 个状态是可区分的。 例如，例 2.14中状态 1和 3是可区别的，因为从状态 1读 入一个 b而停在终结状态 3 ，但是，从状态 3读入一个 b而没有达到终结状态 4。又如空串 把一切终结状态 与任何非终结状态区别开。 青岛大学信息工程学院 编译原理与技术 69 2.4 有限自动机 DFA最小化的方法 对一个 DFA M=的状态划分，不断地尝试对其中的状态 子集寻找可区别的状态，进行分裂，直到没有状态子集可以分裂为止， 直至每个子集内的状态是等价的，而每个状态子集是可区分的。 假如在某个时刻，划分 =I1,I2,.,Im，其中的任何一个都是状态子集。 对于任意一个状态子集 Ij q1,q2,.,qk，若存在一个输入符号 a， 对于任意两个不等的 qi和 qj使得 （ 1） T(qi ,a)=s和 T(qj ,a)=t不在当前划分 的任何一个状态子集中， （ 2）或者其中 T(qi ,a)和 T(qj ,a)的任何一个没有定义 则可以据此把 Ij一分为二：其中的一部分 Ij1是从 Ij的状态读入 a之后进 入包含 s状态子集的状态， Ij2=Ij Ij1。这样，在划分 中用 Ij1和 Ij2取 代 Ij，就形成一个新的划分。 青岛大学信息工程学院 编译原理与技术 70 2.4 有限自动机 可以根据 Ij中每个 qi的 T(qi ,a)来执行 K分裂：若 T(qi ,a)落在划分 的 K个不同的状态子集中，则可以把 Ij划分成 K个不相交的组， 使得每组的状态都落入 的同一子集中。 重复这个划分，直到没有可以分裂的状态子集为止，得到最终 的划分 。 选择每组中的一个状态作为代表，删除其它一切等价的状态， 所有这些状态代表就构成了化简了的 DFA状态集合。 每个状态组之间的连线转移就是每个状态代表之间的转移，同 时去掉不可达状态和无用状态。 含有原来初态的等价状态组就是化简了的 DFA的起始状态。 包含了原来终结状态的等价状态组就是化简了的 DFA的终结状 态。 青岛大学信息工程学院 编译原理与技术 71 2.4 有限自动机 算法 2.2 DFA最小化算法 输入： DFA N= 输出： 等价的具有最少状态的 DFA M 假设 =a1,a2,., an 初始化： = F, SF; 标记 F和 SF没有访问过 finished = false; 青岛大学信息工程学院 编译原理与技术 72 2.4 有限自动机 （ 1）完成划分； while not finished do if 中不存在未访问的子集 J then finished = true else 把 J标记“访问过”； / Ij q1,q2,.,qk distinguished = false; i = 1; while i n AND not distinguished do if J使得 Jai J 可区分的 then distinguished = true; 把 J 从 中删除； 设 T(qi ,a)落在划分 的 K个不同 Ji