03第3章 词法分析1.ppt

3 5正则表达式 由于各种高级程序设计语言的单词形式基本上差不多 人们就希望能否构造一个自动生成系统 只要给出程序设计语言的各类单词描述以及识别出各类单词后应输出的结果 这种自动系统便能自动产生此程序设计语言的词法分析程序 词法分析程序自动生成系统的实现涉及正则表达式和有限自动机理论 假设有字母表 0 1 那么 字母表上的每个元素都是正则表达式 这样的正则表达式表示的语言只有一个句子 例如 0是一个正则表达式 表示的语言为 0 该语言只有一个句子0 如果想表示更加复杂的语言 就必须使用运算符组成复杂的正则表达式 这一点很像用加减乘除运算符构造算术表达式 在正则表达式中 可使用的运算符有连接 选择和重复 例3 4 有正则表达式R1 1 R2 1 R3 0 所描述的语言分别为L1 1 L2 1 L3 0 求正则表达式R1 R2 R3 R1 R3 R1 描述的语言 解 根据正则表达式运算符的操作定义 可得如下结果 R1 R2 R3是一个正则表达式 描述的语言为 110 该语言有一个句子110 R1 R3是一个正则表达式 描述的语言为 1 0 该语言有两个句子1和0 R1 是一个正则表达式 描述的语言为 1n n 0 1 2 该语言有无穷的句子 如1 11 11111等等 标识符的正则表达式为 标识符 字母 字母 数字 而带有符号的实数的正则表达式为 数 数字 数字 数字 3 5 1正则表达式定义 设有两个正则表达式R1和R2 它们分别产生语言L1和L2 则正则表达式运算符的操作定义如下 连接 R1 R2 xy x L1 y L2 选择 R1 R2 x x L1或x L2 重复 R1 x x L1 L1 L10 L11 L12 3 5 1正则表达式定义 定义了运算符后 下面我们给出正则表达式的形式定义 设 是有穷字母表 在 上的正则表达式及所描述的语言可递归定义如下 1 是一个表示空集的正则表达式 2 是一个正则表达式 它所表示的语言仅含一个空符号串 即 3 a是一个正则表达式 a 它所表示的语言由符号a所组成 a 4 如果R1和R2是正则表达式 其表示的语言分别为L1和L2 则1 R1 R2或R1 R2是一个表示语言L1 L2的正则表达式2 R1 R2或R1R2是一个表示语言L1L2的正则表达式3 R1 或R1 是一个表示语言L1 的正则表达式4 R 表示的语言仍是L1的正则表达式 但调整优先权 使括号内的运算符优先权高于括号外的 5 所有 上的正则表达式可由上述4条规则构造出来 注意 不要混淆 和 正则表达式 描述的语言只含一个空字符串 而 表示的语言不含有任何字符串 3 5 1正则表达式定义 在正则表达式的运算符中 重复优先级高于连接 而连接高于选择 因此 p p q 可写成p pq 但表达式 p q r中的括号则不能去掉 例3 5 设字母表 a b 则a b 和 都是 上的正则表达式 所描述的语言为 a b 求表达式 a b a b 和 aa ab ba bb 定义的语言 解 根据正则表达式的形式定义 可得如下结果 表达式 a b 定义的语言为 ambn m 0 n 0 表达式 a b 定义的语言为 x x a b 即字母a或b组成的任意长度字符串 而表达式 aa ab ba bb 表示的语言由字母a或b组成的所有偶长度字符串 3 5 1正则表达式定义 例3 6 设字母表 0 求表达式0 0 与00 0 0定义的语言 解 表达式0 0 定义的语言是 0i i 1 表达式00 0 0定义的语言是 0i i 1 例3 6给出了两个不同的正则表达式 但描述的语言却相同 这说明不同的正则表达式可描述相同的语言 如果两个正则表达式表示相同的语言 则称这两个表达式等价或相等 显然 例3 6的表达式0 0 和00 0 0是等价的 正则表达式的部分操作符满足结合律 交换律和分配律 即 ab c a bc a b c a b c a b b aa b c ab ac注意 连接不满足交换律 即ab ba 3 5 2正则文法与正则表达式的等价性 正则文法与正则表达式有等价性 即可以将正则文法转换成正则表达式 例如 用正则文法表示标识符的文法规则如下 标识符 a b z 标识符 a 标识符 b 标识符 z 标识符 0 标识符 1 标识符 9而采用正则表达式则为 标识符 a b c z a b z 0 1 9 或简写成 标识符 字母 字母 数字 由此可见 正则表达式在描述语言时比正则文法更为简洁 3 5 2正则文法与正则表达式的等价性 例3 7 有正则文法如下 将其换成等价的正则表达式 S aSS aBB bCC aCC a解 先用元符号 和 将文法改写成如下 S a aBB bCC a a 然后按解方程组的方法可得 C a aB b a aS a ab a a 最终转成正则表达式S a ab a a可以验证 它表示的语言与原来的正则文法描述的语言相同 3 6有穷自动机 FA 有穷自动机不是一台具体的机器 而是一种具有离散输入与输出系统的数学模型 在这种数学模型中有有限个状态 状态间存在着转换关系 系统可以处于有限个状态中的任意一个之中 系统的当前状态概括了有关过去输入的信息 这些信息对于确定系统在以后的输入上的行为是必需的 当系统处在某个状态之下读入一个字符时 会使系统所处的状态发生变化 从而形成状态转换 改变后的状态称为后继状态 在状态转换中 后继状态可能为一个 也可能为多个 有穷自动机分确定的和不确定的 所谓 确定的有穷自动机 是指在当前的状态下 输入一个符号 有穷自动机将转换到唯一的后继状态 而 不确定的有穷自动机 在当前状态下输入一个符号 可能有两种或两种以上可选择的后继状态 3 6 1确定的有穷自动机 状态图就是一个确定的有穷自动机 1 确定的有穷自动机定义一个确定的有穷自动机M 记作DFAM 是一个五元组 M Q q0 F 其中 是一个字母表 它的每个元素称为一个输入符号Q 是一个有穷的状态集合 q0 q0 Q 是唯一的初始状态 F F Q 称为终结状态集合 状态转换函数 是一个Q Q的单值映射 在确定的有穷自动机中 状态转换函数的具体形式如下 q a q 其中q Q q Q a 这是一个单值函数 表示在当前状态为q下 输入符号为a时 自动机将从状态q转换到下一个状态q q 称为q的后继状态 3 6 1确定的有穷自动机 2 确定的有穷自动机状态图 确定的有穷自动机M Q q0 F 可以用状态图来表示 状态图中的结点代表状态 用圆圈表示 它与自动机M中的状态集合Q相对应 其中包括初始状态q0和终结状态集合F 结束状态用双圈表示 状态间用有向弧线连接 连接弧上标记有符号 每条弧线对应一个状态转换函数 弧线上标记的符号集合就是字母表 例3 8设有穷自动机DFAM 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 3画出该自动机对应的状态图 解 该自动机对应的状态图如图3 9所示 a b 3 6 1确定的有穷自动机 3 确定的有穷自动机状态转换矩阵图3 10状态转换矩阵确定的有穷自动机M Q q0 F 还可以用关系矩阵即状态转换矩阵来表示 矩阵中的第一列元素与自动机M中的状态集合Q一一对应 且初始状态q0是第一列的第一个元素 右上角标记 的元素对应终结状态 状态转换矩阵的第一行元素与子目标中的每个符号相对应 矩阵中的元素对应每个状态转换函数 如果有状态转换函数 q a q 其中q Q q Q a 那么 就在矩阵中状态q对应的行和符号a对应的列单元中填入q 例3 5中的状态转换矩阵如图3 10所示 3 6 1确定的有穷自动机 4 确定的有穷自动机接受的语言 为了讲解确定的有穷自动机如何接受或识别字符串 首先 我们对状态转换函数作补充定义 q at q a t 其中a t 即t是 上的字符串例如 有 0 a 1且 1 b 2 则 0 ab 0 a b 1 b 2对一个确定的有穷自动机M Q q0 F 以及某个字符串x x 如果有 q0 x p 且p F 则字符串x就被该自动机M所接受 也就是从自动机开始状态开始 在读完全部输入串以后 自动机刚好到达终止状态 那么该输入串为该自动机所接受 从状态图上看 如果一个字符串能被自动机接受 那么从初始状态出发 则存在一条到达某一终结状态的路径 且组成这条路径的弧线上标记的符号连接起来正好就是字符串x 一个确定的有穷自动机M所接受的语言就是所能接受的输入串构成的集合 用L M 表示 可定义为 L M t q0 t F t 3 6 1确定的有穷自动机 例3 9 设计能接受偶数个0和偶数个1组成的串的有穷自动机 画出其状态图及状态转换矩阵并判别110101 11101能否被该自动机接受 解 首先设计能接受偶数个0和偶数个1组成的数字串的有穷自动机如下 M1 S A B C 0 1 S S S 0 B S 1 A A 0 C A 1 S B 0 S B 1 C C 0 A C 1 B其状态图及状态转换矩阵分别如图3 11 a b 所示 S A B C 1 1 0 1 0 0 1 0 图3 11 a 图3 11 a 下面判别110101 11101能否被该自动机接受 S 110101 A 10101 S 101 B 101 C 01 A 1 S 接受 S 11101 A 1101 S 101 A 01 C 1 B 拒绝 3 6 2不确定的有穷自动机 不确定的有穷自动机与确定的有穷自动机的区别主要有两点 一是状态转换函数 为多值函数 二是输入符号可允许为 1 不确定的有穷自动机定义一个不确定的有穷自动机NFAM 是一个五元式M Q q0 F 其中 Q 有穷状态集 输入字母表与空串组成的集合 输入可以是字母表中的字符 也可以是空串q0 开始状态q0 QF 终止状态集F Q 状态转换函数 为Q 到Q的子集的映射 不确定的有穷自动机同样可以用状态图和状态转换矩阵来表示 表示方法与确定的相同 3 6 2不确定的有穷自动机 2 不确定的有穷自动机接受的语言与确定的有穷自动机一样 为了判别一个字符串x能否被NFA接受 我们还需要对状态转换函数做补充定义 设 q a p1 p2 pn 其中a q p1 p2 pn Q1 q closure q 其中 closure q 表示从状态q出发 沿着 弧到达的后继状态集合以及再从这些后继状态沿着 弧所能到达的所有状态集合 2 q at p1 t p2 t pn t 其中a Vt t 3 q1 q2 qn x q1 x q2 x qi x 其中x 表示从不确定自动机的状态集出发 扫描字符串x后 所到达的状态集等于从当前状态集的每一个状态集出发 扫描字符串x后所到达的状态集之和 3 6 2不确定的有穷自动机 对某台不确定的有穷自动机NFAM Q q0 F 及某个字符串x x 若有 q x Q 且Q F 则x为M 所接受 也就是从自动机开始状态开始 在读完全部输入串以后 自动机能够到达某个终止状态 那么该输入串为该自动机所接受 从状态图上看 如果一个字符串能被自动机接受 那么从初始状态出发 则存在一条到达某一终结状态的路径 且组成这条路径的弧线上标记的符号连接起来正好就是字符串x 如果初始状态也是终结状态 或是存在一条从初始状态到达某个终结状态的路径 路径上的所有标记都是 则 可被NFA接受 M 所接受的语言为L M x x q0 x Q Q F 3 6 2不确定的有穷自动机 例3 10 有NFAM 0 1 2 a b 0 2 其中 0 a 2 0 1 1 b 1 2 2 a 2 2 b 2 画出其状态图及状态转换矩阵 确定该自动机接收的语言 解 不确定的有穷自动机用状态图和状态转换矩阵来表示 如图3 12 a 和3 12 b 所示 该自动机接受的语言为L M a bm a b n m 1 n 0 图3 12 a 图3 12 b 3 6 3NFA到DFA的转化 不确定的有穷自动机与确定的有穷自动机从功能上来说是等价的 它们所接受的语言类相同 给定任一不确定的有穷自动机NFAM 就能构造一个确定的有穷自动机DFAM 使得L M L M 为了实现NFA到DFA的转化 首先要介绍两个状态子集的计算方法 它们是从NFA到DFA的转化过程中需要计算的状态子集 1 状态集P的 闭包设p是一NFAM 的状态集Q的一个子集 则 closure p 称为状态集p的 闭包 闭包也是状态集Q的一个子集 其计算方法如下 1 若q p 则q closure p 即P的所有成员都是p的 闭包的成员2 若q p 那么从q出发经过任意条 弧而能到达的任何状态都属于 closure p 3 6 3NFA到DFA的转化 例3 11 对图3 13所示的NFAM 求P 1 P 2 P 1 2 的 闭包 解 当P 1 时 有 1 3 3 6 3 4 所以 closure 1 1 3 4 6 当P 2 有 2 6 所以 closure 2 2 6 当P 1 2 则 closure 1 2 closure 1 closure 2 1 3 4 6 2 6 1 2 3 4 6 3 6 3NFA到DFA的转化 2 状态集P的a弧转换集设p仍是一自动机M 的状态集的子集 p p1 p2 pn a 即a是字母表 的一个输入符号 则Pa弧转换集为 pa closure J 其中J p1 a p2 a pn a 即J是从状态子集p中的每一个状态出发 沿着标记为a的弧而到达的状态所组成的集合 从定义可知 状态集P的a弧转换集Pa也是状态子集 其集合元素为从P的每个状态出发 沿着标记为a的弧所到达的后继状态集合 再加上这些后继状态集合中的每个状态的 闭包 即从这些后继状态集合中的每个状态出发 沿着 弧所能到达的状态的集合 例3 12 对图3 13所示的NFAM 若p 1 求pa 解 因为 1 a 2 1 a 4所以pa closure J closure 1 a closure 2 4 2 4 6 3 6 3NFA到DFA的转化 3 根据NFAM 构造DFAM下面我们通过一个例子来介绍根据NFAM 构造DFAM的方法 假设有一个不确定的有穷自动机NFAM Q q0 F 其中Q 1 2 3 4 a b c q0 1 F 4 状态图如图3 14所示 接受的语言 L M amb m 1 acn n 1 构造一个DFAM Q q0 F 使L M L M 图3 14NFAM 的状态图 3 6 3NFA到DFA的转化 构造确定的有穷自动机过程如下 1 首先根据 闭包的计算方法求NFAM的开始状态q0 的 闭包 从而确定DNFAM的开始状态q0 q0 closure q0 closure 1 1 4 2 根据弧转换集的计算方法求开始状态q0对每个输入符号的弧转换集q0a q0b和q0c从而确定与开始状态q0有关的状态转换函数 q0 a q0a closure 1 a 4 a closure 2 3 2 3 将 2 3 作为新状态 并令q1 2 3 即得到 q0 a q1 q0 b q0b closure 1 b 4 b closure q0 c q0c closure 1 c 4 c closure 由于 q0 b q0 c 说明没有新状态产生 至此 我们得到有关开始状态q0的全部状态转换函数只有一个 即 q0 a q1 3 6 3NFA到DFA的转化 3 按步骤2的方法 对每个新状态计算相关的状态转换函数 计算状态q1的状态转换函数 q1 a q1a 2 将 2 作为新状态 并令q2 2 q1 b q1b 4 将 4 作为新状态 并令q3 4 q1 c q1cc 3 4 将 3 4 作为新状态 并令q4 3 4 至此 得到有关开始状态q1的全部状态转换函数 接下来 计算状态q2 q3 q4的有关状态转换函数如下 q2 a 2 q2 q2 b 4 q3 q2 c q3 a q3 b q3 c q4 a q4 b q4 c 3 4 q4计算到此 不再有新状态出现 3 6 3NFA到DFA的转化 4 根据上面求出的各个状态确定终结状态集F p p F 其中p为M的每个状态子集 因为q0 1 4 q1 2 3 q2 2 q3 4 q4 3 4 而F 4 q0 q3 q4与F 相交不为空 所以确定终结状态集F q0 q3 q4 最后 我们得到确定的有穷自动机如下 DFAM q0 q1 q2 q3 q4 a b c q0 q0 q3 q4 其中状态转换函数为 q0 a q1 q1 a q2 q1 b q3 q1 c q4 q2 a q2 q2 b q3 q4 c q4该转换后的动机的状态图及状态转换矩阵如图3 16 a b 所示 3 6 3NFA到DFA的转化 图3 15 a 转换后的DFAM的状态图 图3 15 b 转换后的DFAM的状态转换矩阵 得到的确定的自动机接收的语言为 L M amb m 1 acn n 1 与原来不确定的有穷自动机接收的语言L M 一样 3 6 4正则表达式与有穷自动机的等价性 正则表达式与有穷自动机等价性由以下两点说明 1 若给定一个正则表达式R 那么 就可构造一个DFAM 并有L M L R 2 若给定一个DFAM M接受的语言为L M 则必然存在一正则表达式R 且L R L M 1 根据正则表达式构造有穷自动机根据正则表达式的组成规则 可采用下列构造分解规则来构造NFAM 1 基本正则表达式 和a a 描述的语言为空集 和a所定义的语言分别为 和 a 可构造的NFA分别是 S0 S1 S0 S1 S0 S1 a 图3 16 和a的状态转换图 3 6 4正则表达式与有穷自动机的等价性 2 连接 设R1和R2都是基本正则表达式 则构造与正则表达式R1 R2等价的NFA如图3 17 图3 17R1 R2的状态转换图 3 选择 设R1和R2都是正则表达式 则构造与正则表达式R1 R2等价的NFA如图3 18 图3 18R1 R2的状态转换图 4 重复 设R是正则表达式 则构造与正则表达式 R 等价的NFA如图3 19 R 图3 19 R 的状态转换图 对于任何正则表达式 我们都可根据上述NFA构造规则构造出等价的NFA 3 6 4正则表达式与有穷自动机的等价性 例3 13有正则表达式R a b a b 构造出等价的NFA 然后转化成DFA 解 构造过程如下 设初始状态为0 目标状态为1 将整个正则表达式 a bb a b 看成一个整体 则状态转换图如图3 20所示 图3 20正则表达式到NFA转换图1 因 a bb a b 由 a bb 和 a b 连接而成 所以展开连接后如图3 21 图3 21正则表达式到NFA转换图2 将重复展开后如图3 22所示 图3 22正则表达式到NFA转换图3 3 6 4正则表达式与有穷自动机的等价性 将选择展开后 最终得到的NFA状态图如图3 23所示 图3 23正则表达式到NFA转换图4 3 6 4正则表达式与有穷自动机的等价性 构造出NFA后 接下来 我们可按3 6 3小节介绍的方法将其转化成DFA 其过程如下 设DFAM Q q0 F q0 closure 0 0 4 2 3 5 1 q0a closure 4 5 4 2 3 5 1 q1q0b closure 6 5 6 5 1 q2q1a closure 4 5 4 2 3 5 1 q1q1b closure 6 5 6 5 1 q2q2a closure 5 5 1 q3q2b closure 3 5 3 5 1 q4q3a closure 5 5 1 q3q3b closure 5 5 1 q3q4a closure 5 5 1 q3q4b closure 5 5 1 q3 至此 不在有新状态产生 由于q0 q1 q2 q3 q4都含有状态1 所以都是目标状态 转化后的DFA如图3 24所示 图3 24DFA状态图 3 6 4正则表达式与有穷自动机的等价性 2 将DFAM转换成正则表达式若给定一个DFAM 构造正则表达式R相比之下更加容易 处理方法与上面的由正则表达式构造NFAM的方法是互逆的 其具体方法如下 1 填加两个新的结点S和T 将结点S与DFAM上的初态结点连接 将每个终态结点与T结点用弧线连接 所有连接弧线上均标记为 从而 使NFAM只有一个初态S和一个终态T 2 逐步去掉NFAM中的结点 直到只剩下结点S和T 在去掉结点的过程中 逐步用正则表达式来标记弧线 去掉结点的规则如下 连接 设R1和R2都是基本正则表达式 去掉结点 用弧线直接连接结点1和3 弧线上标记R1 R2 如图3 25所示 3 6 4正则表达式与有穷自动机的等价性 选择 设R1和R2都是正则表达式 去掉标记为R1和R2弧线 用一根弧线直接连接结点1和2 弧线上标记R1 R2 重复 设R是正则表达式 则构造与正则表达式 R 等价的NFA如图3 27所示 1 2 R1 R2 图3 26由NFA构造正则表达式R1 R2 例如 从例3 13中得到的NFAM 图3 23 反向看 图3 23 图3 22 图3 21以及图3 20就是构造正则表达式的过程 3 6 5确定的有穷自动机的化简 如果有两个确定的有穷自动机DFAM1和DFAM2所接受的语言完全一样 我们说这两个自动机是等价的 但如果DFAM1的状态个数比DFAM2的状态个数少 那么 我们说DFAM1更加简洁 在设计词法分析程序时 效率是很重要的一个因数 如果可能的话 我们应该构造尽可能小的DFA 上一小节我们介绍了将正则表达式分解派生出DFA的方法 但这一方法有个缺点 就是生成的DFA可能比较复杂 自动机理论中有一个很重要的结论 对于任何给定的DFA 都有一个含有最少状态的等价的DFA 而且这个最少状态的DFA是唯一的 从任何DFA中都可以得到这个最少状态的DFA 1 等价状态与不等价状态在一个确定的有穷自动机里 如果从S1状态出发接受的所有符号串集合与从S2状态出发接受的所有符号串集合一样 那么称状态S1和S2是等价的 否则是不等价的 例3 14 观察图3 27所示的状态图 判断状态1和状态2是否等价 解 因为有 1 a 3 2 a 3 因此 状态1和状态2是等价的 图3 28有等价状态的状态图 3 6 4正则表达式与有穷自动机的等价性 2 多余状态多余状态有两种 一是指从初始状态出发 输入任何输入串也无法到达的状态 即从初始状态到该状态之间没有通路 二是指从初始状态出发能够到达的状态 但从它出发却无法到达终止状态的状态 即从该状态到终止状态之间没有通路 多余状态是无用的 应该删除 删除多余状态的方法很简单 从状态图上看 就是直接将多余状态结点以及相关的弧线删除 即可得到等价的自动机 例3 15 在图3 28 a 所示的的状态图中 判断那些状态是多余状态 解 根据多余状态的定义 可发现 从初始状态0出发 无法到达状态1 所以状态1是多余状态 而从状态5无法到达终止状态4 所以 状态5也是多余状态 删除多余状态后的状态图入3 28 b 所示 图3 29 a 有多余状态的状态图 图3 29 b 删除多余状态的状态图 3 6 4正则表达式与有穷自动机的等价性 3 DFA化简算法设DFAM Q q0 F 化简算法如下 1 先将自动机的状态划分成终止状态集合S1和非终止状态集合S2 Q S1 S22 对各状态集合按下面方法划分 直到所有状态集合不再产生新的划分为止 设第m次划分将Q分成N个状态集合 即Q S1 S2 Sn 对状态集合Si i 1 2 n 中的各个状态逐一检查 设状态q1和q2是状态集合Si中的两个状态 对于输入符号a a 有 q1 a S q2 a S 若状态S 和S 属于同一状态集合 则将状态q1和q2放在同一状态集合中 否则 将状态q1和q2分为两个集合 3 重复第2步 直到所有状态集合都不能划分 此时 每个状态集合中的状态都是等价的 4 将每个状态集合中的等价状态合并成一个等价代表状态 将状态函数中的所有状态用相应的等价代表状态表示 从状态图上看 要将一个状态集合中的等价状态结点合并成一个结点 5 删除多余状态 3 6 4正则表达式与有穷自动机的等价性 例3 16对图3 30所示的有穷自动机化简 状态函数如下 a 0 a 1 1 a 3 2 a 1 3 a 3 4 a 3 0 b 2 1 b 2 2 b 4 3 b 4 4 b 4 解 首先将状态集合分成终止状态集合S1和非终止状态集合S2 S1 0 1 2 S2 3 4 对S1 0 1 2 化分 因为 0 a 1 1 a 3 2 a 11 3不属于同一状态集 所以将S1分成S3 0 2 S4 1 对S2 3 4 化分 3 a 3 4 a 3 3 b 4 4 b 4因为3 4属于同一状态集 所以S2不能划分 说明状态3和4等价 图3 30等待化简的有穷自动机 3 6 4正则表达式与有穷自动机的等价性 对S3 0 2 化分 因为 0 a 1 2 a 1 0 b 2 2 b 4所以将S3分成S5 0 S6 2 至此 不再能继续划分 最终得到不能划分的状态集有S2 3 4 S4 1 S5 0 S6 2 每个状态集留一个状态得 S2 3 S4 1 S5 0 S6 2 将原来的转换函数中的状态4改成状态3 得到 0 a 1 1 a 3 2 a 1 3 a 3 3 a 3 0 b 2 1 b 2 2 b 3 3 b 3 3 b 3去掉重复的 最终得到化简后的状态函数如下 对应的状态图如图3 31所示 0 a 1 1 a 3 2 a 1 3 a 3 0 b 2 1 b 2 2 b 3 3 b 3 3 6 6根据DFA构造词法分析程序 根据DFA来构造词法分析程序有两种方法 1 直接编程的词法分析器所谓直接编程的词法分析器 是将DFA识别过程转化为程序 即用程序来模拟DFA的行为 在这种方法里 首先将DFA用状态图表示 然后按下列步骤根据状态图画出词法分析程序流程图 1 初始状态对用程序的开始 2 终止状态对应程序的结束3 状态转移对应条件语句或多分支选择语句 4 状态图的环对应程序中循环语句 5 终态返回时 隐瞒组应满足最长匹配原则 其中最长匹配原则指识别出的单词有混淆时 按长度最长的来确定 例如符号串 认为是一个单词 而不是 和 这种设计方法适合手工实现 编写出的词法分析程序比较精简 分析速度快 前面3 4小节介绍的词法分析程序采用的就是这种方法 但这种词法分析程序与要识别的语言单词密切有关 通过程序的控制流转移来完成对输入字符的响应 程序中的每一条语句都与要识别的单词符号有关 一旦语言的单词符号集即词法规则发生变化 则要重新编写程序 一般来讲 这种方法适合编写词法比较简单的词法分析程序 3 6 6根据DFA构造词法分析程序 2 表驱动的词法分析程序表驱动的词法分析程序的模型如图3 32所示 它由输入字符序列 分析表和控制程序组成 分析表就是DFA的状态转换矩阵 如图3 33 控制程序有两个参数 一个参数接受扫描的字符a 另一个参数为DFA的状态i 其控制程序的算法是 1 在输入字符序列后面加一个字符 叫结束符 将扫描指针设在输入序列的最左端 状态参数i设为开始状态 2 扫描下一字符a 如果是结束符 则停止 否则 根据状态参数I和输入的字符a查分析表 将状态参数i设为查分析表 i a 后得到的状态 3 如果i是终态 则表示识别出一个单词转到4 否则 转到2 4 处理识别出的单词 输出单词符号 状态参数i设为开始状态 转到2 图3 33分析表 3 6 6根据DFA构造词法分析程序 表驱动的词法分析程序是根据分析表的内容进行操作 与要识别的单词符号无关 具体识别什么单词符号 由分析表的内容决定 是一种典型的数据与操作分离的工作模式 构造不同的词法分析程序实质上是构造不同的分析表 而控制程序是不变的 这就为词法分析程序的自动生成