1、编译原理,第三章 词法分析,1,词法分析器模型 图3.49,3.8词法分析器生成工具的设计,2,DFA模拟器 图3.27,NFA模拟器 图3.27,DFA转换表,NFA转换表,词法分析器工作方式,词法分析器生成工具工作方式实例 3.26 任务包括多个正则表达式，且分别对应不同的语义动作。a 模式P1的动作A1abb 模式P2的动作A2a*b+ 模式P3的动作A3,3.8词法分析器生成工具的设计,3,词法分析器生成工具工作方式NFA/DFA转换表的构造把每个正则表达式转换为一个NFA按照图3.50方式，把所有NFA合并为一个NFA。把这个NFA转换为一个DFA，使用这个DFA识别与所有正则表达式
2、相匹配的词素。,3.8词法分析器生成工具的设计,4,词法分析器生成工具的设计基于NFA的模式匹配 图3.53一直运行到达一个没有后续状态的输入点后，首先回头查找一个包含可接收状态的集合，即利用最长匹配确定可接受状态集合，然后根据重要性（例如根据正则表达式出现顺序）确定哪个正则表达式。最后进行forward指针修复，同时执行与此正则表达式相关的语义动作。,5,3.8词法分析器生成工具的设计,3.8词法分析器生成工具的设计,词法分析器生成工具的设计基于DFA的模式匹配 图3.54与NFA类似：DFA可接受状态包含一个或多个NFA可接受状态。,6,转换方式：不需构造中间的NFA动机：可能的状态转移只
3、与某些状态相关转移函数：move(s,a)/move(S,a)存在一个非标号(中字母) 离开该状态s，即存在某个 字母a, 转移函数move(s,a)非空。,3.9直接从正则式到DFA（3.9.1-3.9.5）,7,构造原理重要状态对应于正则式中字母的每次出现位置，即抽象语法树的非叶子节点。拓广正则表达式 （r）#加入右端结束标记#确保接受状态是重要状态！实例 (a|b)*abb# 图3-56,3.9直接从正则式到DFA,8,构造原理转换表：聚焦重要状态之间的转移开始状态：可能出现在给定正则表达式描述的语言中任何一个串第一个符号位置的所有重要状态。接受状态：和结尾#相关的位置,3.9直接从正则
4、式到DFA,9,构造算法定义四个函数：nullable、firstpos、lastpos、followpos,3.9直接从正则式到DFA,10,构造算法计算nullable、firstpos、lastpos：图3.58&3.59,3.9直接从正则式到DFA,11,构造算法计算followpos：图3.60&3.61,3.9直接从正则式到DFA,12,构造算法算法3.36 图3.62 vs 图3.32子集构造法初始状态：firstpos(n0) vs -closure(s0)后续状态：S中和a对应的所有位置p的followpos(p) vs -closure(move(T,a)S中有些p与a对应
5、，有些不对应。,3.9直接从正则式到DFA,13,构造算法实例 例3.37,3.9直接从正则式到DFA,14,得到的DFA状态比通过NFA得到的DFA状态少！,DFA最简化原理最简DFA唯一性：每一个正则式可以由一个状态数最少的DFA识别，且这个DFA唯一。可行性：DFA存在不可区别状态，可以合并。化简条件：确保DFA是全函数DFA可能是部分函数：存在状态s符号a，move(s,a)不存在！解决方式：DFA化简前引入死状态（化简后可以去掉死状态）,3.10 DFA最简化（3.9.6-3.9.7）,15,死状态在转换函数由部分函数改成全函数表示时引入。死状态对所有输入符号都转换到本身。左图需要引
6、入死状态E ；右图无须引入死状态。,3.10 DFA最简化,16,可区别状态状态s和t可区别：存在一个串x，分别从状态s和t出发，沿着标号为x的路径到达的两个状态中只有一个是接受状态。A和B是可区别的状态：从A出发，通过串b，到达非接受状态C，而从B出发，通过过串b，到达接受状态D。A和C是不可区别的状态（等价的状态）：无任何串可像上面这样区别它们。,3.10 DFA最简化,17,最简化DFA算法：算法3.39 图3.64构造状态集合的初始划分：两个子集接受状态子集F和非接受状态子集S F可以存在多个接受状态子集：每个对应不同词法单元的识别。应用下面的过程构造new对于 中的每个子集G把G划分
7、为若干子集，G的两个状态 s 和 t 在同一子集中，当且仅当对任意输入符号 a ，s 和 t 的 a 转换都到 的同一子集中。在new 中，用G的划分代替G如果new = ，则final = ；否则令 = new ，转上步在final的每个状态子集中选一个状态代表它（同一个状态子集中的各个状态等价，不可区别），即为最简DFA的状态。最简DFA的开始状态：包含了原始DFA开始状态的组的代表最简DFA的接受状态：包含了原始DFA接受状态的组的代表转换表：对于final 中状态子集G和H的代表s和r，如果存在move(s,a)=t且t属H，那么move(s,a)=r。,3.10 DFA最简化,18,
8、最简化DFA算法：实例S-F=A, B, C, F=D A, C, B, Dmove(A,a)=Bmove(B,a)=Bmove(C,a)=Bmove(A,b)=Cmove(B,b)=D move(C,a)=C,3.10 DFA最简化,19,叙述下面的正则式描述的语言，并画出接受该语言的最简DFA的状态转换图(1|01)* 0*描述的语言：所有不含子串001的0和1的串,例 题 1,20,bbabaabb,例 题 2,用状态转换图表示接受(a|b)a(a|b)(a|b)的DFA,21,第三章总结（3.10）,第三章：总结,第三章总结（3.10）,第三章：总结,第三章总结（3.10）,第三章：总结,
