第二章 词法分析

null第一章 总结 第一章 总结 语言与语言的翻译 编译器的基本组成 编译器的分析/综合模式(编译器基础架构) 扫描遍数 编译器的编写第二章 词法分析第二章 词法分析词法的双重含义 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 单词形成的规则，被称为构词规则或词法规则。相当于立法，规定语言所允许的合法单词。 根据构词规则识别输入序列，被称为词法分析。相当于执法，识别出合法的单词、指出非法的输入序列。 主要内容 词法分析中的若干问题 模式的形式化描述 记号的识别 从正规式到词法分析器 上机：函数绘图语言的词法分析器x := y + z * 60.0 ;id1 := id2 + id3 * 60.0 ;2.1 词法分析中的若干问题2.1 词法分析中的若干问题记号、模式与单词 单词的基本分类： 关键字 kw(key word, or reserved word) 标识符 id(identifier) 字面量 literal 特殊符号 ks(key symbol, or special symbol) [例2.1]语句 position := initial + rate * 60 记号 id ks id ks id ks number 注意：称识别出id而不是rate或initial 问题：根据什么识别这些词法的基本单位（词法元素）？2.1 词法分析中的若干问题2.1 词法分析中的若干问题三个术语： 模式(pattern)：产生和识别元素的规则 记号(token)： 按照某个模式(或规则)识别出的元素(一组) 单词(lexeme)：被识别出的元素自身的值(一个)，也称为词值 2.1 词法分析中的若干问题2.1 词法分析中的若干问题记号的属性 记号是按照某个模式识别出的元素。 赋值句position := initial + rate * 60 position、initial和rate均为标识符，种类均是id。 问题：当识别出一个id时，如何判定是哪个id ？ 当识别出一个relation时，究竟是 = 还是 < ？ 记号＝记号的类别＋记号的属性 [例2.2] 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式 mycount > 25 由三个记号组成 类别 82 81 83 属性 “mycount” 5 25 注意：5与25的区别 （根据记号的类别） 25与“25”的区别 （如何区别？）2.1 词法分析中的若干问题2.1 词法分析中的若干问题词法分析器的作用与工作方式 词法分析器是编译器中唯一与源程序打交道的部分。 滤掉源程序中的无用成分，如注释、空格、回车等； 处理与平台有关的输入，如文件结束符的不同表示等； 根据模式识别记号，并交给语法分析器； 调用符号表管理器或出错处理器，进行相关处理 。 工作方式：单独扫描，作为语法分析器的子程序，并行工作2.2 模式的形式化描述2.2 模式的形式化描述字符串与语言 从词法分析的角度看程序设计语言，它是由记号组成的集合。 定义2.1 语言L是有限字母表∑上有限长度字符串的集合 说明： 字母表是字符的集合，这些字符可以组成字符串。 两个有限（计算机的表达能力有限）： 字母表是有限的； 字符串的长度是有限的。 [例2.3]字母表∑={a, b, c}，则其上的语言L={ε, a, b, c, aa, ab, ac, ba, bb, bc, ...}2.2 模式的形式化描述2.2 模式的形式化描述字符串的基本概念 术语 示例 |S| |abc| = 3 ε |ε| = 0 S1S2 abc def = abcdef Sn (abc)3 = abcabcabc S的前缀X abc的前缀有：ε，a，ab, abc S的后缀X abc的后缀有：ε，c，bc, abc S的子串X abc的子串有： ε，a，b, c, … S的真前缀 abc的真前缀有：a，ab S的真后缀 ？ S的真子串 ？ S的子序列X abdf是abcdef的一个子序列2.2 模式的形式化描述2.2 模式的形式化描述若 L = {a, b}, M = {c, d}，则 LM = {ac, bc, ad, bd}，L∩M = Φ L* = {ε, a, b, aa, bb, ab, ba, aaa, ...} L+ = { a, b, aa, bb, ab, ba, aaa, ...}2.2 模式的形式化描述2.2 模式的形式化描述正规式与正规集 定义2.2 令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下: 1. ε是正规式，它表示集合L(ε)={ε} 2. 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a} 3. 若正规式r和s分别表示集合L(r)和L(s)，则 （a） r|s是正规式，表示集合L(r)∪L(s)， （b） rs是正规式，表示集合L(r)L(s)， （c） r*是正规式，表示集合(L(r))*， （d）(r)是正规式，表示的集合仍然是L(r) 可用正规式描述的语言称为正规语言或正规集。 2.2 模式的形式化描述2.2 模式的形式化描述定义2.2说明： 运算的优先级与结合性 三种运算均具有左结合性质； 优先级从高到低：闭包、连接、或。 正规式中不必要的括号可以被省略。 例如：( a ) | ( ( ( b )* ) ( c ) )可以简化成 a | b* c。 正规式的等价 不同算术表达式可以表示同一个数，如3+5、5+3、2+6等均表示8。不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。2.2 模式的形式化描述2.2 模式的形式化描述定义2.3 若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P = Q。 [例2.4] 设字母表∑ = {a，b，c}，则∑上有： 正规式 正规集 a，b，c {a}，{b}，{c} a|b，b|a {a}∪{b}={a，b} a(a|b)* {a，aa，ab，aba，abb，aab，...}，a为首的ab串 ∑* {ε，a，b，c，aa，ab，ac，ba，bb，bc，...} [例2.5] 令 L(x) = {a，b}，L(y) = {c，d}， 则 L( x | y )={a，b，c，d} L( y | x )={a，b，c，d} 2.2 模式的形式化描述2.2 模式的形式化描述利用正规式的等价性可以化简复杂的正规式。 正规式的等价性判定可以采用两种方法： 根据定义，证明不同的正规式表示同一集合（例2.5） 根据下述正规式的代数性质进行运算2.2 模式的形式化描述2.2 模式的形式化描述记号的说明 自然语言对模式的非形式化描述很不精确，而正规式可以严格地规定记号的模式，用正规式说明记号的公式为： 记号 = 正规式 读作 （左边）记号定义为（右边）正规式 或者 记号是正规式 例如，id=a ( a | b )* 可以读作为 id定义为a ( a | b )* 注：在不引起混淆的情况下，把说明记号的公式简称为正规式，或者规则。2.2 模式的形式化描述2.2 模式的形式化描述[例2.6] 记号relation、id和num分别是Pascal的关系运算符、标识符和无符号数，它们的正规式表示如下所示。 relation = < | <= | <> | > | >= | = id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z) (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z |0|1|2|3|4|5|6|7|8|9)* num = (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* (ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*) (ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*) 返回2.2 模式的形式化描述2.2 模式的形式化描述简化正规式描述 正闭包 若r是表示L(r)的正规式，则r+是表示( L( r ) )+的正规式： r+ = r r* = r* r，r* = r+ | ε 例如： (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 化简为：(0|1|2|3|4|5|6|7|8|9)+ 可缺省 若r是正规式，则r?是表示L(r)∪{ε}的正规式： r?=r|ε 例如： E( + | - | ε ) 可改写为：E( + | - )? 注：+、?、*具有相同的结合性和优先级 引入？的原因在于字符ε无法使用键盘输入。2.2 模式的形式化描述2.2 模式的形式化描述字符组 若r是仅由|运算构成的正规式，则可改写为[r']，其中r'可以有如下两种形式： 枚举：如[abc]，等价于 a | b | c 分段: 如[0-9a-z]，等价于[0123456789abcdefghijklmnopqrstuvwxyz] 非字符组 若[r]是一个字符组形式的正规式，则[^r]是表示∑ - L(r)的正规式。 例如：若 ∑={a, b, c, d, e, f, g}， 则 L([^abc]) = { d, e, f, g }2.2 模式的形式化描述2.2 模式的形式化描述辅助定义 通俗地讲，辅助定义的作用是为复杂的或重复出现的正规式命名，并在以后的使用中用名字代替该正规式。 辅助定义的形式与正规式一样： 辅助定义名字 = 正规式 注： 辅助定义不与任何模式匹配； 作为辅助定义的正规式仅供内部使用，而不用于说明记号。 辅助定义： 内部名 = 正规式 规则： 记号名= 正规式 2.2 模式的形式化描述2.2 模式的形式化描述[例2.6] 引入正规式的缩写形式和辅助定义式后，id和num的正规定义式可重写如下： char = [a-zA-Z] digit = [0-9] digits = digit+ optional_fraction = ( . digits )? optional_exponent = ( E (+|-)? digits )? id = char ( char|digit )* num = digits optional_fraction optional_exponent 对比原来上次课总结上次课总结词法的双重含义； 模式、记号与单词； 形式化描述：正规式与正规集； 正规式描述；正规式简化表示、辅助定义2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机模式的描述―正规式 记号的识别―有限自动机（不确定、确定） 不确定的有限自动机 （Nondeterministic Finite Automaton, NFA） 定义2.4 NFA是一个五元组（5-tuple）： M =（S，∑，move，s0，F），其中 （1） S是有限个状态（state）的集合； （2） ∑是有限个输入字符（包括ε）的集合； （3） move是一个状态转移函数，move(si，ch)=sj表示，当 前状态si下若遇到输入字符ch，则转移到状态sj； （4） s0是唯一的初态（也称开始状态）； （5） F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机NFA两种直观的表示方式 ① 状态转换图 NFA中的每个状态，对应转换图中的一个节点； NFA中的每个move(si, a)=sj，对应转换图中的一条有向边；表示从节点si出发进入节点sj ，字符a(或ε)是边上的标记。 ② 状态转换矩阵 每个矩阵元素M[si,a]中的内容，是从状态si出发，经字符a(或ε)所到达的下一状态sj； 在转换矩阵中，一般以矩阵第一行所对应的状态为初态，而终态需要特别指出。状态转换图中如何表示呢？2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机[例2.7] 识别正规式(a|b)*abb所描述正规集的NFA的三种表示形式分别如下。(其中转换矩阵表示中0为初态，3为终态) S = {0, 1, 2, 3}, Σ = {a, b} move = { move(0, a) = 0, move(0, a) = 1, move(0, b) = 0, move(1, b) = 2, move(2, b) = 3 } s0 = 0, F = {3}2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机NFA如何识别记号? 对字符串，从初态开始，经一系列状态转移到达终态。 例如：对于字符串abb，有 定义：move = { move(0, a) = 0, move(0, a) = 1, move(0, b) = 0, move(1, b) = 2, move(2, b) = 3 } move(0, a)=1, move(1, b)=2, move(2, b)=3 转换矩阵：m[0, a]={0, 1}, m[1, b]=2, m[2, b]=3 转换图：0a1b2b3，最直观开始识别能是0a0吗？2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机[例2.8] 识别表2.1中记号relation、id和num的转换图。 relation = < | <= | <> | > | >= | = id = char(char|digit)*<=能被识别为<和=吗？最长识别原则2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机optional_fraction = ( . digits )? optional_exponent = ( E (+ | -)? digits )? num = digits optional_fraction optional_exponent2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机NFA识别记号的最大特点是它的不确定性，即在当前状态下对同一字符有多于一个的下一状态转移。 定义：move函数是1对多的； move = { move(0, a) = 0, move(0, a) = 1, move(0, b) = 0,...} 状态转换图：同一状态有多于一条边标记相同字符转移到不同的状态； 状态转换矩阵：M[si,a]是一个状态的集合2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机NFA识别输入序列的一般方法：反复试探所有路径，直到到达终态，或者到达不了终态。 不确定性带来的问题：识别输入序列时，在当前状态下遇到同一字符，应转移到哪个下一状态？ [例2.9] 在正规式 (a|b)*abb的NFA上识别输入序列abb和abab。2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机NFA识别记号存在的问题 只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。 识别过程中需要进行大量回溯，时间复杂度升高且算法趋于复杂。 问题：是否可以构造这样的有限自动机，它识别正规式所描述的字符串，且在任何一个状态下遇到同一字符最多有一个状态转移？2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机确定的有限自动机 （Deterministic Finite Automaton, DFA） 定义2.5 DFA是NFA的一个特例，其中： （1）没有状态具有 ε 状态转移（ε-transition），即状态转 换图中没有标记 ε 的边； （2）对每个状态 s 和每个字符 a ，最多有一个下一状态。 与NFA相比，DFA的特征是其确定性 定义：move（si, a）函数是1对1的； 转换图： 从一个节点出发的边上标记均不相同； 转换矩阵：M [ si , a ] 是一个状态。 且字母表不包括 ε 。2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机DFA对NFA施加的两条限制： 限制1：没有ε状态转移 限制2：同一状态下没有重复字符的状态转移 [例2.10] 正规式(a|b)*abb的DFA，识别输入序列abb和abab： 识别abb：0a1b2b3，状态，接受 识别abab：0a1b2a1b2，？2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机DFA识别输入序列的算法被称为DFA模拟器或驱动器，它与DFA共同构成词法分析器的核心，特点是算法与模式无关。 算法2.1 模拟DFA 输入 DFA D和输入字符串x (eof)。D的初态为s0，终态集为F 输出 若 D 接受 x，回答“yes”，否则回答“no”。 方法 用下述过程识别x： s := s0; ch := nextchar; -- 初值 while ch≠eof -- x结束? loop s := move(s, ch); ch := nextchar; -- 循环转移 end loop; if s is in F -- 终态返回 then return “yes”; else return “no”; end if;2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机识别abb： 1. s = 0, ch = a 2. s = 1, ch = b 3. s = 2, ch = b 4. s = 3, ch = eof 5. yes识别abab： 1. s = 0, ch = a 2. s = 1, ch = b 3. s = 2, ch = a 4. s = 1, ch = b 5. s = 2, ch = eof 6. no(a|b)*abb的DFA2.3 记号的识别－有限自动机2.3 记号的识别－有限自动机有限自动机的等价 定义2.6 若有限自动机M和M’识别同一正规集，则称M和M’是等价的，记为M=M’。 提示：正规式与有限自动机从两个侧面表示正规集。正规式是描述，自动机是识别。因此，当它们表示相同集合时，均存在等价的问题。 有几种可能的等价？ 2.4 从正规式到词法分析器2.4 从正规式到词法分析器构造词法分析器的一般方法和步骤： 描述：用正规式对模式进行描述； 构造NFA：为每个正规式构造一个NFA； 确定化：将NFA转换成等价的DFA； 最小化：优化DFA，使其状态数最少； 构造词法分析器：由DFA构造词法分析器。 问题：为何不直接从正规式构造DFA？ 机器构造需要 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 的算法； 正规式→NFA：有规范的一对一的构造算法； DFA→分析器：有便于记号识别的算法。2.4 从正规式到词法分析器2.4 从正规式到词法分析器从正规式到NFA 算法2.2 Thompson 算法 输入 字母表∑上的正规式 r 输出 接受 L(r) 的NFA N 方法 首先分解 r，然后根据下述步骤构造NFA： 对ε，构造NFA N(ε) 接受{ε}； 对∑上的每个字符a，构造NFA N(a) 接受{a}； 若N(p)和N(q)是正规式p和q的NFA，则ε a r|s rs r* (r)2.4 从正规式到词法分析器2.4 从正规式到词法分析器 （a）对正规式p|q，构造NFA N(p|q) 接受L(p)∪L(q)； （b）对正规式pq，构造NFA N(pq) 接受L(p)L(q)； （c）对正规式p*，构造NFA N(p*) 接受L(p*)； （d）对于正规式(p)，使用p本身的NFA，不再构造。ε a r|s rs r* (r)2.4 从正规式到词法分析器2.4 从正规式到词法分析器[例2.11] 用Thompson算法构造正规式r = (a | b)* a b b的NFA N(r) 。 先分解正规式，再自下而上构造NFA 注意： 算法的构造与正规式一一对应 构造一个新的NFA最多增加两个状态上次课总结上次课总结NFA定义M =（S，∑，move，s0，F） NFA直观表示：状态转换图与状态转换矩阵 NFA识别记号 NFA的不确定性 DFA－NFA的特例 模拟DFA的算法 自动机的等价 构造词法分析器的步骤 Tompson算法2.4 从正规式到词法分析器2.4 从正规式到词法分析器从NFA到DFA NFA识别记号的“并行”方法 [例2.12] 从甲地到乙地，可以乘汽车也可以骑自行车，具体路线如右图。其中c表示乘车，b表示骑自行车。现在 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 从甲地到乙地，只许乘车而不许骑自行车，该如何走？ 抽象：识别是否有从甲到乙标记为全c的路径 串行（试探）： 甲 c 2 无路可走，退回 甲 c 1 c 3 无路可走，退回 甲 c 1 c 乙 到达乙地，成功 并行：有多辆汽车，每次到达汽车能到达的全体 甲 c {1, 2}c {3, 乙} 到达乙地，成功2.4 从正规式到词法分析器2.4 从正规式到词法分析器由于并行的方法在每试探一步时，考虑了所有的下一状态转移（所有下一状态作为一个状态集合），因此所走的每一步都是确定的。 用NFA识别记号，并不采用串行的方法（算法不易构造，复杂度高且回溯），而是采用并行的方法，核心思想是将不确定的下一状态确定化。 NFA上识别记号的确定化方法是在计算下一状态转移时，实施如下确定化的两个步骤： 消除ε 状态转移：ε-闭包(T) 消除多于一个的下一状态转移：smove(S, a) 2.4 从正规式到词法分析器2.4 从正规式到词法分析器ε-闭包(T)：从状态T出发，不经任何字符达到的状态全体。 smove(S, a)：从状态集S出发，标记为a的下一状态全体。与move(s, a)的唯一区别：用状态集取代状态。 定义2.6 状态集T的ε-闭包(T)是一个状态集，且满足： （1）T中所有状态属于ε-闭包(T)； （2）任何smove(ε-闭包(T)，ε)属于ε-闭包(T)； （3）再无其他状态属于ε-闭包(T)。 根据定义，ε-闭包({s2})应包括： 1. s2自身 {s2} （1） 2. s4 {s2, s4} （2） 3. s5 {s2, s4, s5} （2）2.4 从正规式到词法分析器2.4 从正规式到词法分析器算法2.4 求ε-闭包 输入 状态集T 输出 状态集T的ε-闭包 方法 for T中每个状态t loop 加入t到U; push(t); end loop; while 栈不空 loop pop(t); for 每个u = move(t, ε) loop if u不在U中 then 加入u到U; push(u); end if; end loop; end loop; return U;闭包U和模拟递归的stack问题：试将函数直接写为递归的ε-闭包({s2})2.4 从正规式到词法分析器2.4 从正规式到词法分析器算法2.3 模拟NFA 输入 NFA N，x(eof)，s0，F 输出 若N接受x，回答“yes”，否则“no” 方法 用下边的过程对x进行识别。S是一个状态的集合 S := ε-闭包({s0}); -- 所有可能初态的集合 a := nextchar; while a ≠ eof loop S := ε-闭包(smove(S，a)); -- 所有下一状态的集合 a := nextchar; end loop; if S∩F≠Φ then return “yes”; else return “no”; end if; 2.4 从正规式到词法分析器2.4 从正规式到词法分析器识别abb: 计算初态集： ε-闭包({0}) = {0,1,2,4,7} A 从A出发经a到达： ε-闭包(smove(A, a)) = {3,8,6,7,1,2,4} B 从B出发经b到达： ε-闭包(smove(B, b)) = {5,9,6,7,1,2,4} C 从C出发经b到达： ε-闭包(smove(C, b)) = {5,10,6,7,1,2,4} D 结束且D∩{10}={10}，接受。 识别的路径为：A a B b C b D[例2.13] 在NFA上识别输入序列abb和abab2.4 从正规式到词法分析器2.4 从正规式到词法分析器识别abab: 初态集：ε-闭包(s0)={0,1,2,4,7} A 从A出发经a到达：ε-闭包(smove(A, a)) = {3,8,6,7,1,2,4} B 从B出发经b到达：ε-闭包(smove(B, b)) = {5,9,6,7,1,2,4} C 从C出发经a到达：ε-闭包(smove(C, a)) = {3,8,6,7,1,2,4} B 从B出发经b到达：ε-闭包(smove(B, b)) = {5,9,6,7,1,2,4} C 识别路径为：A a B b C a B b C。由于C∩{10}=Φ，所以不接受[例2.13] 在NFA上识别输入序列abb和abab2.4 从正规式到词法分析器2.4 从正规式到词法分析器子集法构造DFA 并行模拟NFA的弱点：每次动态计算下一状态转移的集合，效率低。改进方法：将NFA上的全部路径均确定化并且记录下来，得到与NFA等价的DFA。 从甲地到乙地的路径是一个NFA ，可找到一个等价的DFA。[例2.14] 用DFA识别cc和cbc： 甲 c {1,2} c {3,乙}， 接受 甲 c {1,2} b {3} c ?，不接受 消除了不确定性 无需动态计算状态集合null算法2.5 从NFA构造DFA（子集法） 输入 NFA N 输出 等价的DFA D，其初态含有NFA初态，终态是含有NFA终态的状态集合。 方法 用下述过程构造DFA Dstates = { ε-闭包({s0}) }; --是唯一状态且未标记 while Dstates有未标记状态T loop 标记T; for 每一个字符a loop U := ε-闭包(smove(T，a)); if U非空 then Dtran[T，a] := U; if U不在Dstates中 then U作为未标记状态加入Dstates; end if; end if; end loop; end loop;状态集Dstates和转换矩阵Dtrannullε-闭包({0})={0,1,2,4,7}*A ε-闭包(smove(A, a))={3,8,6,7,1,2,4}*B ε-闭包(smove(A, b))={5,6,7,1,2,4}*C ε-闭包(smove(B, a))={3,8,6,7,1,2,4}B ε-闭包(smove(B, b))={5,9,6,7,1,2,4}*D ε-闭包(smove(C, a))={3,8,6,7,1,2,4}B ε-闭包(smove(C, b))={5,6,7,1,2,4}C ε-闭包(smove(D, a))={3,8,6,7,1,2,4}B ε-闭包(smove(D, b))={5,10,6,7,1,2,4}*E ε-闭包(smove(E, a))={3,8,6,7,1,2,4}B ε-闭包(smove(E, b))={5,6,7,1,2,4}C[例2.15] 用算法2.5构造(a|b)*abb的DFA 选择哪一个 DFA？2.4 从正规式到词法分析器2.4 从正规式到词法分析器最小化DFA 对于若干个等价的DFA，总是希望由状态数最小的DFA构造词法分析器。将一个DFA等价变换为另一个状态数最小的DFA的过程被称为最小化DFA。 定义2.7 对于任何两个状态t和s，若从一状态出发接受输入字符串ω，而从另一状态出发不接受ω，或者从t出发和从s出发到达不同的接受状态，则称ω对状态t和s是可区分的。 设想任何输入序列ω对s和t均是不可区分的，则说明从s出发和从t出发，分析任何输入序列ω均得到相同结果。因此，s和t可以合并成一个状态。 最小化DFA的实质：在状态集S上找到一个基于不可区分的等价关系R，S/R即是最小DFA的状态集。2.4 从正规式到词法分析器2.4 从正规式到词法分析器算法2.6 最小化DFA的状态数 输入 DFA D={S，∑，move，s0，F}。 输出 等价的D’={S’，∑，move’，s0’，F’}(D’状态数最少) 方法 执行如下步骤： 1. 初始划分Π={S-F，F1，F2，..}，其中，Fi是F的子集，接受不同记号； 2. 应用下述过程构造新的划分Πnew： for Π的每一个组G loop 划分G，G的两个状态s和t在同一组中的充要条件是: a.(move(s,a)∈Gi∧move(t,a)∈Gi)； 用新划分的组替代G，形成新的划分Πnew； end loop； 3.若 Πnew=Π 则 Πfinal:=Π 且转4； 否则 Π=:Πnew 且转2；2.4 从正规式到词法分析器2.4 从正规式到词法分析器4. 在Πfinal每个组Gi中选一个代表si’，使得D中从Gi所有状态出发的状态转移在D’中均从si’出发，D中所有转向Gi中的状态转移在D’中均转向si’。含有D中s0的状态组G0的代表s0'称为D'的初态，D中所有含F中状态的Gj的代表sj'构成D'的终态集F'； 5. 删除死状态，即不是终态且对所有输入字符均转向其自身，或从初态不可到达的状态。 最小化DFA算法的主要步骤 初始划分：终态与非终态； 利用可区分的概念，反复分裂划分中的组Gi，直到不可再分裂； 由最终划分构造D'，关键是选代表和修改状态转移； 消除可能的死状态和不可达状态。2.4 从正规式到词法分析器2.4 从正规式到词法分析器[例2.17] 用算法2.6化简DFA 1．初始化划分Π1={ABCD，E} 2．反复分裂划分中的组： ① ∵ m(D, b)=E ∴ Π2={ABC，D，E} ② ∵ m(B, b)=D ∴ Π3={AC，B，D，E} ③ Π3？ 于是：Πfinal={AC，B，D，E} 4．根据Πfinal构造D'： ①选代表，用A代表AC组； ②修改状态转移： 用0123代替ABDEm(A,a)=B, m(A,b)=C m(B,a)=B, m(B,b)=D m(C,a)=B, m(C,b)=C m(D,a)=B, m(D,b)=E m(E,a)=B, m(E,b)=C2.4 从正规式到词法分析器2.4 从正规式到词法分析器由DFA构造词法分析器 表驱动型的词法分析器 有数据结构存放DFA； 修改算法2.1： 识别文件(而非一个记号)； 满足最长匹配原则。 对于输入序列： result := a + b 正确的识别：id := id + id 错误的识别： 仅识别一个： id （result） 不满足最长匹配： id （r或re或res ... ）2.4 从正规式到词法分析器2.4 从正规式到词法分析器直接编码的词法分析器 将DFA和DFA识别输入序列的过程合并在一起，直接用程序代码模拟DFA识别输入序列。 问题：如何用程序模拟DFA的状态和它的状态转移？ 1. 状态和状态转移与语句的对应关系 ① 初态 → 程序的开始； ② 终态 → 程序的结束(不同终态return不同记号)； ③ 转移 → 分情况或者条件语句(case/if)； ④ 环 → 循环语句(loop)； ⑤ return满足最长匹配原则。nullvoid main(){ char buf[]="aba#", *ptr=buf; while (*ptr!='#' ) { l0: while (*ptr=='b') ptr++; // state 0 l1: while (*ptr=='a') ptr++; // state 1 switch (*ptr) { case 'a': goto l1; case 'b': ptr++; switch (*ptr) // state 2 { case 'a': goto l1; case 'b': ptr++; switch (*ptr) // state3 { case 'a': goto l1; case 'b': goto l0; case '#': cout<<"yes"<