编译原理与技术讲义-第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 i 3 14 词法分析器产生的结果是单词记号序列 编译原理与技术 8 2 1词法分析器的设计 词法扫描器与符号表对符号表的操作主要是填表 查询和更新 每当词法分析器识别了一个单词的时候 第一项工作就是查询符号表 对于不同的单词种别 查询的方式和随后的处理完全不同 例如 对于关键字 分界符和运算符等 只需在各自的符号表中查询 获得并记录其它属性值 生成相应的单词记号 处理常量 特别是处理标识符要复杂的多 而且仅仅在词法分析阶段是无法获得一个标识符的所有信息 当词法扫描器识别了一个标识符的时候 首先查询关键字表 看它是否是关键字 如果不是 还要在标识符表中查询 看它是否已经存在 如果不存在就把它填入标识符表 并填入种别 类型等信息 编译原理与技术 9 2 1词法分析器的设计 词法分析器的两种实现模式完全独立模式和相对独立模式在完全独立模式下 词法分析器作为编译的子系统单独地运行一趟 扫描整个源程序 把识别的单词序列以机器内码的形式输出在一个中间文件上 供为语法分析使用 编译原理与技术 10 2 1词法分析器的设计 完全独立模式的好处编译程序结构清晰 条理化而且便于高效地实现 在设计高级语言时能独立地研究词法与语法两个方面的特性 增强编译程序的可移植性 可以就同一个语言为不同的机器写不同的词法分析器 而只编写一个共同的语法分析 使用这些词法分析器相同的单词机内表示 把同一个词法由于单词记号的语法可以用较简单的文法描述 把词法和语法分开 就能为这种文法建立有效的特殊方法和自动构造技术 编译原理与技术 11 2 1词法分析器的设计 相对独立模式 词法分析器设计成一个子程序 每当语法分析需要一个单词的时候 就调用该子程序 相对独立模式的好处 词法分析器和语法分析器被设计在同一趟 省去了存放单词的终结文件 编译原理与技术 12 2 1词法分析器的设计 词法错误的处理在词法分析阶段发现的错误统称为词法错误 它们大多是单词拼写错误 这或者是因为书写错误 或者因为键入错误 例如把关键字拼写错 对词法错误校正的常用策略是修补尝试 一般包括 删除一个多余的字符 插入一个遗漏的字符 用一个正确的字符替换一个不正确的字符 交换两个相邻的字符 编译原理与技术 13 2 2词法分析器的一种手工实现 输入的预处理对于许多程序语言来说 空格 制表符 换行符等编辑性字符除了出现在文字常量中 在其它任何地方的出现都没有意义 而注释作为程序的重要文档几乎可以出现在程序中的任何地方 它们的存在可以改善程序的可读性和易理解性 却不影响程序的语法结构和执行语义 通常在编译的词法分析阶段被预处理过程删除掉 编译原理与技术 14 2 2词法分析器的一种手工实现 输入的预处理 扫描器对缓冲区进行扫描时一般使用两个指针 一个指向当前正在识别的单词的起始位置 另一个用于向前搜索以寻找该单词的终点 两个指针之间的符号串就是要识别的单词符号 无论扫描缓冲区设计的多大都不能保证单词符号不会超过其边界 扫描缓冲区一分为二的两段置 for sum 0 i 1 搜索指针 起点指针 Car eel 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 有状态序列 例2 2 标识符一般定义为字母打头的字母数字序列 编译原理与技术 20 2 2词法分析器的一种手工实现 例2 3 类似语言中的关系符的状态转换图 在终结状态加了星号 表示在状态1 2和3都还不能确定它们是否是符合最长匹配准则的单词记号 还需要在读入一个字符才能确定 而为实现最长匹配的一个超前搜索符号 其它 则不属于这个单词 应该推给扫描缓冲区 编译原理与技术 21 2 2词法分析器的一种手工实现 例2 4 Pascal语言中数的状态转换图 在这个复杂的例子中 状态3 5和8分别表示识别是整数 不带指数部分的实数以及带有指数部分的实数 但是 只能在超前搜索一个其它符号以后 才能在状态9确定识别了一个Pascal的数 读者可以自己验证例子数2005 1998 81 07 2 003 6 看它们是否能被这个转换图所接受 编译原理与技术 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词法分析器的一种手工实现 标识符状态转换图的一个实现 intcode value chartoken 在开始状态0do token token ch 不断读入字母或数字 合并成一个标识符getchar ch 保持在状态1 while isLetter ch isDigit ch isLetter ch 和isDigit ch 分别检查ch是否是字母 数字 进入结束开始状态2code lookup token keywordsTable 在关键字表中查询token 若它是关键字就返回1if code 1 return 1 token 返回关键字的单词记号 假如关键字种别是1else 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词法分析器的一种手工实现 intstate 0 while state 0 1 2 3 switchstate case0 getchar ch if ch state 1 getchar ch elsereporterror case1 getchar ch if ch state 2 getchar ch elsereporterror case2 getchar ch if ch state 3 getchar ch elsegetcharch ch 还是在状态2case3 getchar ch switchch case state 4 getchar ch case state 3 getchar ch default state 2 if state 4 return elsereporterror 编译原理与技术 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 intcode value charstate start chartoken state sets表示所有状态名的集合 编译原理与技术 29 2 2词法分析器的一种手工实现 while state属于state sets switchstate case comment getchar ch if ch state start getchar ch case start getchar ch switchch caseisletter ch state inID token ch getchar ch caseisdigit ch state inNum token ch getchar ch casech state comment getchar ch casech state GE token ch getchar ch casech state token ch casech state token ch casech state token ch casech state token ch default getchar ch 过滤掉无用的符号 编译原理与技术 30 2 2词法分析器的一种手工实现 case inNum while state属于 inNumber 2 3 处理数switchstate case inNum switchch 处理整数caseisdigit ch token token ch getchar ch casech state 2 token token ch getchar ch default state number code 10 处理实数case 2 if isdigit ch state 3 token token ch getchar ch elsereporterror 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 在关键字表中查询tokenif 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 elsereturn 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 u A并且v B 例如 设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 1A 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 编译原理与技术 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 9 0 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 003 6这样的串 即由整数 小数和指数三个部分组成 小数和指数部分是可选的 其中指数标记E后面可以有 或 再跟上一个或多个数字 而小数点之后必须至少有一个数字 下面就是Pascal语言的数的集合的正规定义 digit 0 9 digits digitdigit signed fraction digits exponent E signed digits number signed digitsfractionexponent 编译原理与技术 46 2 3正规表达式 正规表达式的实现和应用正规表达式实际上是描述和识别一组字符串的模板 模式 它包含字符 元符号 如表示重复的 和选择符 和一些具有特殊意义的符号 这个模板决定什么样的字符串属于某一个集合 正规表达式在处理文本方面具有强大的能力 它在计算机领域的应用不仅仅局限于构造编译器的词法扫描器 其它著名的应用还包括UNIX操作系统的命令工具如grep 处理复杂文本分析与操作的脚本语言Perl Tcl Python PHP和awk以及通用程序开发编辑器emacs 由于正规表达式的重要而广泛的应用 Java语言通过包java util regex还对正规表达式的处理提供了直接支持 编译原理与技术 47 2 4有限自动机 为什么引入有限自动机确定的有限自动机和不确定的有限自动机都能识别正规集 即它们识别的语言正好就是正规式所能表达的语言 而且在识别语言的能力上 它们完全等价 但是 实现这两类有限状态机的效率不同 用它们构造的词法分析器在识别语言中单词记号的效率方面也有显著的差别 正规式 不确定的有限自动机 确定的有限自动机 词法分析器 编译原理与技术 48 2 4有限自动机 确定的有限自动机DFA定义2 10 一个确定的有限自动机DFAM是五元组 其中 1 S是非空的有限的状态集合 2 是非空的输入字母表 3 T是部分单值映射S S 又称转移函数 T s1 a s2表示输入符号a时 把状态s1转换到s2 成为当前状态 4 s0 S 是唯一的起始状态 5 F S 是非空的终结状态 被M接受或识别的语言 记做L M 定义为字符串的集合 其中每个ci 并且存在状态序列s1 T s0 c1 s2 T s1 c2 sn T sn 1 cn sn F 编译原理与技术 49 2 4有限自动机 例2 10 一个有限自动机DFAN 其中T的定义如下 T A BT A BT A CT A d DT B DT B d CT C ET C d CT D d ET E d E状态A是起始状态 E是终结状态 编译原理与技术 50 2 4有限自动机 转换函数可以用状态转换矩阵或状态转换表来表示 该表的行表示状态 列对应输入的符号 表元素表示状态转移的状态 空白元素对应的二元组没有定义 例2 10有限自动机的状态转换矩阵 编译原理与技术 51 2 4有限自动机 一个DFA也可以表示成一个确定的状态转换图 状态转换函数T s1 a s2对应了连接两个结点s1和s2 标记为a的有向弧 例2 10有限自动机的状态转换图 从状态A到B的转换上的标记 表示两条从A到B的弧的标记 和 这是常用的简化方式 编译原理与技术 52 2 4有限自动机 定义2 11 对于有限自动机M的 中的任何一个符号串 若存在一条从起始状态到某一终结状态的通路 且这条通路上所有弧的标记符连成的串等于 则称 被M识别 读出或接受 若起始状态也是一个终结状态 则空串 可以为M接受 DFAM所能识别的所有字的集合称为M识别的语言 记做L M 编译原理与技术 53 2 4有限自动机 例如 考虑上述的有限自动机 如果d代表任意一个数字0 1 9 它能否接受符号串30 28和 813 19 对于它们 可以分别给出从状态A到终结状态E的路径 因而它们都是这个DFAN可以接受的数 编译原理与技术 54 2 4有限自动机 定义2 12 a 两个有限自动机M1和M2是等价的 当且仅当它们识别相同的语言 即L M1 L M2 定义2 12 b 两个有限自动机M1和M2是等价的 当且仅当对于每个M1接受的符号串 M2接受 编译原理与技术 55 2 4有限自动机 不确定的有限自动机NFA定义 一个不确定的有限自动机NFAM是五元组 其中 1 S是非空的有限的状态集合 2 是非空的输入字母表 3 T是S 2S S的幂集 它可以把一个状态映射到一组状态 T s1 a s2表示输入符号a时 把状态s1转换到s2 成为当前状态 4 s0 S 是唯一的起始状态 5 F S 是非空的终结状态 被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 n 0 的一个NFAM a a 2 4 a 0 3 1 b b b b a 这个NFA识别aabbabb 即存在一个状态序列 从状态0到状态4 路经上的标记连接是aabbabb 编译原理与技术 57 2 4有限自动机 两个NFAN1和N2称为等价的 当且仅当它们识别同一个语言 即L N1 L N2 为什么要引入NFA 首先 需要有限自动机的主要目的是用来识别正规式所描述语言的单词记号 直接从正规式构造出DFA的算法比较复杂 而从正规式构造NFA的算法则相对简单 然后 再从NFA构造等价的DFA作为记号的识别分析器 其次 我们有时需要多值映射以及所谓的空转移 即形式为N 的产生式 以便简洁地表达多种可能的选择 而且 使用空转移描述对空串的匹配 更加直观和自然 编译原理与技术 58 2 4有限自动机 从NFA到DFA的等价变换定理2 1 对于任意一个NFAN都存在一个等价的DFAM 即L N L M 为了从NFA构造出等价的DFA 需要消除N 形式的产生式 即消除空转移 确定化每个多重转移 即拆分多值函数为单值函数 一个常用的方法是子集法 编译原理与技术 59 2 4有限自动机 定义2 13 设I是NFAN 中一个状态子集 对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是NFAN 中一个状态子集 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的等价构造算法输入 NFAN 输出 等价的DFA假设 a1 a2 an 1 首先构造DFA的状态转换表MATRIX 这是一个n 1列 行动态增长的表格 第零列的每个元素对应DFA的状态 随着算法的执行 递增地产生新的状态 即增加新行 初始化 row 1 MATRIX的行sn row DFA的状态个数MATRIX row 0 closure q0 S MATRIX row 0 加入DFA状态集合的第一个状态 它本身是一个集合do 逐行地填表fori 1tondoMATRIX row i Iai 在每行逐列地填表ifIai SthenS S Iai 把Iai加入Ssn sn 1 MATRIX sn 0 Iai 状态转换表增加一行 即增加一个新的状态endif endfor row row 1 计算下一个状态的Iai whilesn 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 所示 编译原理与技术 65 2 4有限自动机 状态子集重新命名 并将Ia和Ib分别视为a与b后得表2 5 b 对应的状态转换图如图2 13所示 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 3a b 0 1 b b b a 2 b a a a 编译原理与技术 67 2 4有限自动机 DFA的最小化定理2 2 对任意一个DFAN都存在一个等价的DFAM 它包含最少的状态数 而且这个最小状态的DFAM是唯一的 状态名不同的同构情况除外 关键在于把DFA的状态划分成一些不相交的等价子集 使得任何两个不同子集中的状态都可以区别 而每个子集内的状态都是等价的 这样 每个子集用一个状态代表 删除子集中的其它状态 就得到了状态个数最少的DFA 编译原理与技术 68 2 4有限自动机 定义2 15 设q1和q2是DFAN中的两个不同的状态 如果从状态q1出发能扫描任意串 而停于终结状态 当且仅当从q2出发也能扫描任意串 而停于终结状态 称状态q1和q2是等价的 定义2 16 若两个状态q1和q2不是等价的 则称这两个状态是可区分的 例如 例2 14中状态1和3是可区别的 因为从状态1读入一个b而停在终结状态3 但是 从状态3读入一个b而没有达到终结状态4 又如空串 把一切终结状态与任何非终结状态区别开 编译原理与技术 69 2 4有限自动机 DFA最小化的方法对一个DFAM 的状态划分 不断地尝试对其中的状态子集寻找可区别的状态 进行分裂 直到没有状态子集可以分裂为止 直至每个子集内的状态是等价的 而每个状态子集是可区分的 假如在某个时刻 划分 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 2DFA最小化算法输入 DFAN 输出 等价的具有最少状态的DFAM假设 a1 a2 an 初始化 F S F 标记F和S F没有访问过finished false 编译原理与技术 72 2 4有限自动机 1 完成划分 whilenotfinisheddoif 中不存在未访问的子集Jthenfinished trueelse把J标记 访问过 Ij q1 q2 qk distinguished false i 1 whilei nANDnotdistinguisheddoif J 使得Jai J 可区分的thendistinguished true 把J从 中删除 设T qi a 落在划分 的K个不同Ji1 Jik 把J划分成K个不相交的组并加入到 中 elsei i 1 endif endwhile endif 试算 中的下一个状态子集endwhile 直到 的每个状态子集不可划分为止 编译原理与技术 73 2 4有限自动机 2 取 的每组中的一个状态作为代表 删除其它一切等价的状态 所有这些状态代表就构成了化简了的DFA状态集合 3 每个状态组之间的连线变成每个状态代表之间的连线 去掉不可达状态和无用状态 4 含有原来初态的等价状态组就是化简了的DFA的起始状态 5 包含了原来终结状态的等价状态组就是化简了的DFA的终结状态 编译原理与技术 74 2 4有限自动机 例2 15 图2 13所示的DFA的最小化过程如下 初始划分 0 1 2 3 4 5 6 计算 0 1 2 a 1 3 它不包含在 的任何一个子集当中 所以 可以把 0 1 2 分解 根据T 1 a 3 T 0 a T 2 a 1 把 0 1 2 分解成两个状态子集 1 和 0 2 这时的 1 0 2 3 4 5 6 继续划分 由于 0 2 b 2 5 未包含在当前划分的任何一个子集中 所以 0 2 一分为二 得到新的划分 0 1 2 3 4 5 6 由于 3 4 5 6 a 3 4 6 3 4 5 6 b 4 5 6 都包含在 3 4 5 6 内 不可再划分 至此 整个划分结束 令状态3代表 3 4 5 6 把原来进入状态4 5和6的弧都导入3 删除状态4 5和6 得到最小化的DFA如图2 15 编译原理与技术 75 2 4有限自动机 例2 15 a b 3 4 a 0 1 b b b a 2 5 6 b a a b b a a a b 3 b 0 1 b b a 2 b a a 最小化 图2 13所示的DFA 最小化的DFA 编译原理与技术 76 2 4有限自动机 例2 16 下图所示的DFA的最小化过程 a b 4 3 b 0 1 b b b a 2 b a a a 3 2 b 1 b b 0 b a a a a 1 因为状态仅状态4是终结状态 首先得划分 4 和 0 1 2 3 2 只需对 0 1 2 3 继续划分 0 1 2 3 在面临字符a时 每个状态都转换到状态1 无法区分 而在面临符号b时 状态3进入状态4 状态0 1和2都转换到 0 1 2 3 内得状态 所以 可以把 0 1 2 3 分解成 3 和 0 1 2 从而得到新的划分包括 4 3 和 0 1 2 3 可能再分解的是 0 1 2 在输入b时 T 0 b 2 T 1 b 3 T 2 b 2 据此可以把 0 1 2 分解成 1 和 0 2 4 继续尝试分解 0 2 这时的 0 2 a 1 0 2 b 2 无法区分 划分完毕 5 最小化的状态包括 0 2 1 3 和 4 重新命名 整理后得到右上图 编译原理与技术 77 2 4有限自动机 从正规式到有限自动机基于转换规则的算法 利用 转移把单个的正规式粘接起来 形成更复杂的 识别正规式表示语言的NFA 定理2 3 1 对字母表 上的任何一个正规表达式e都存在一个接受L e 的有限自动机M 即L e L M 2 对字母表 上的任何一个有限自动机M都存在一个接受L M 正规表达式e 即L M L e 编译原理与技术 78 2 4有限自动机 1 对应于基本正规式a 的NFA a 对应于基本正规式a的NFA是 对应于基本正规式 的NFA是 对应于基本正规式 的NFA是 编译原理与技术 79 2 4有限自动机 2 选择替换规则 e1 e2表示成 e2 e1 构造的有限自动机新增加了两个状态 分别表示开始状态和终结状态 然后把新增的起始状态与N e1 和N e2 的起始状态用 转移连接起来 把N e1 和N e2 的终结状态与新增的终结状态用 转移连接来 并且更改N e1 和N e2 起始状态和终结状态的性质 N e1 接受的任何串s 等价于 s 而它可以被N e1 e2 接受 即L e1 L e1 e2 同样 L e2 L e1 e2 反之 所有从N e1 e2 的开始状态 经过N e1 部分到达终结状态 所接受的语言是 L e1 L e1 或者经过N e2 部分到达终结状态 所接受的语言是 L e2 L e2 即L e1 e2 L e1 L e2 所以L e1 e2 L e1 L e2 编译原理与技术 80 2 4有限自动机 3 连接替换规则 e1e2表示成 e2 e1 e1和e2连接成e1e2时 把N e1 的终结状态改为非终结状态 然后通过 转移与N e2 的起始状态连接起来 N e1 的起始状态成为N e1e2 的起始状态 N e2 的终结状态成为N e1e2 的终结状态 如果N e1 接受s1 N e2 接受s2 那么 构成s1的路径必须经过标记为 的唯一的一条边后 才能与构成s2的路径连接起来到达结束状态 这样 合成的有限自动机接受的是e1 e2 即e1e2 编译原理与技术 81 2 4有限自动机 4 重复替换规则 e 表示成 e 对于e的闭包运算e 新增加了分别表示开始和结束的两个状态 并且更改N e 起始状态和终结状态的性质 然后新增四条 转移 连接新增的的起始状态与N e 的起始状态 连接新增的起始状态和终结状态 连接N e 的终结状态与新增的终结状态 连接N e 的终结状态与N e 的起始状态 新增的边 表示e的零次连接 等价于 L e 0 新增的边 和原来N e 构成了回路 这样 从N e 的开始状态到结束状态 可以经过N e 一次或多次 显然这个N e 识别语言 L e 编译原理与技术 82 2 4有限自动机 从正规式到有限自动机的例子例2 17 对正规式 dd 构造对应的NFA 把 dd 表示成e1e2 其中e1 e2 dd 这样 简化的构造有三步 过程如图 d d d d 编译原理与技术 83 2 4有限自动机 例2 18 对正规式ab ab ba a 构造等价的NFA 首先将其改造成形式为e1e2e3的三个子正规式的连接 其中e1 ab e2 e4 e5 e3 a 而e4 ab e5 ba b a b b a b a ab ba b a ab a b b a ab ba a a a b b a ab ab ba a b a 编译原理与技术 84 2 4有限自动机 有限自动机在计算机中的表示矩阵表示方法 表结构表示和程序表示法例2 19 设一个DFA的状态集合是 s0 s1 s2 s3 其中s0是起始状态 s3是接受状态 输入符号集合是 a b 映射t s0 a s1 t s0 b s2 t s1 a s1 t s2 b s2 t s1 b s3 t s2 a s3 t s3 a s3 我们可以定义一个矩阵M 4 2 使得M 0 0 1 M 0 1 2 M 1 0 1 M 2 1 2 M 1 1 3 M 2 0 3 M 3 0 3 其中状态就用状态的下表代替 字母a和b分别用0和1表示 编译原理与技术 85 2 4有限自动机 表结构表示 例2 20 例2 19中的DFA可以表示成如图2 19所示的表结构 比如给定一个状态s1和输入符号b 首先找到s1所在的表项 然后在这个表中找到输入符号b 按照b的指针就可以找到s3的表项 s