【编译原理】词法分析 1. 词法分析的简介 2. 词法分析器 3. 词法分析 ——手工构造法 比较符 标识符 关键字 4、词法分析——正则表达式 5、词法分析——有限状态自动机 确定状态有限自动机（DFA） 非确定的有限状态自动机（NFA） 转换过程 6、RE到NFA：Thompson算法 7、NFA到DFA：子集构造算法 算法思想 子集构造算法（工作表算法） ε-闭包的计算 8、DFA的最小化：Hopcroft算法 9、DFA的代码表示 转移表 跳转表 1. 词法分析的简介 编译器的阶段： graph LR A(源程序) --> B[front end] B --> C(IR) C --> D[back end] D --> E[target program] 前端 2. 词法分析器 词法分析器将字符流转化为记号流 字符流：和被编译的语言密切相关 (ASCII, Unicode, or …) 记号流：编译器内部定义的数据结构，编码所识别出的词法单元 例子： if (x > 5) y = "hello"; else z = 1; 词法分析后： IF LPAREN IDENT(x) GT INT(5) RPAREN IDENT(y) ASSIGN STRING(“hello”) SEMICOLON ELSE IDENT(z) ASSIGN INT(1) SEMICOLON EOF 记号的数据结构定义： enum kind{IF, LPAREN, ID, INTLIT, ...}; struct token{ enum kind k; // 关键词 char *lexeme; // 值 }; 词法分析器的实现方法 手工编码实现法 相对复杂、且容易出错 但是目前非常流行的实现方法：GCC, LLVM, … 词法分析器的生成器 可快速原型、代码量较少 但较难控制细节 3. 词法分析 ——手工构造法 比较符 状态转移图： token nextToken () c = getChar (); switch (c) case ‘<’: c = getChar (); switch (c) case ‘=’: return LE; case ‘>’: return NE; default: rollback(); return LT; case ‘=’: return EQ; case ‘>’: c = nextChar (); switch (c): // similar ... 标识符 状态转移图 token nextToken () c = getChar(); switch (c) // continued from above cases… case ‘a’, …, ‘z’, ‘A’, …, ‘Z’, ‘_’: c = getChar (); while (c==‘a’ || c==‘b’|| … || c==‘_’) c = getChar(); 标识符和关键字 很多语言中的标识符和关键字有交集 从词法分析的角度看，关键字是标识符的一 部分 以C语言为例： 标识符：以字母或下划线开头，后跟零个或 多个字母、下划线、或数字 关键字：if, while, else, … 关键字 两种方案 第一种：在状态转移图上扩展新的边 第二种：关键字表算法 对给定语言中所有的关键字，构造关键字构成的哈希表H 对所有的标识符和关键字，先统一按标识符的转移图进行识别 识别完成后，进一步查表H看是否是关键字 通过合理的构造哈希表H（完美哈希）， 可以 $O(1)$ 时间完成 4、词法分析——正则表达式 对于给定的字符集 $\sum=\left \{ c_{1}, c_{2}, …, c_{n} \right \}$，归纳定义： 空串 $\varepsilon$ 是正则表达式 对于任意的 $c \in \sum$，$c$ 是正则表达式 如果 $M$ 和 $N$ 是正则表达式，那么以下也是正则表达式 选择： $M|N=\left \{ M\cup N \right \}$ 连接：$MN = \left \{ mn | m\in M, n \in N \right \}$ 闭包：$M^*=\left \{ \varepsilon,M,MM,MMM,...\right \}$（Kleene闭包） 语法糖：可以引入更多的语法糖，来简化构造 语法糖 意义 $[c_{1}-c_{n}]$ $c_{1} $e+$ 一个或多个 $e$ $e?$ 零个或一个 $e$ $“a_{*}”$ $a*$ 自身, 不是 $a$ 的Kleen闭包 $e \left \{i, j\right \}$ $i$ 到 $j$ 个 $e$ 的连接 . 除‘\n’外的任意字符 5、词法分析——有限状态自动机 graph LR subgraph 有限状态自动机 A("输入的字符串") ==> B["FA"] B ==> C("{Yes, No}") end 自动机：$M = (\sum, S, q_{0}, F, \delta)$ $\sum$：字母表，不同的语言不一样 $S$：状态集，指的是有限自动机的状态 $q_{0}$：初始状态 $F$：终结状态集，注意为状态集 $\delta$：转移函数 确定状态有限自动机（DFA） 对任意的字符，最多有一个状态可以转移 串读完的时候为最终状态即为可接受 graph LR O( ) --> A A((0)) --a--> B((1)) B --a--> C[2] A --b--> A B --b--> B C --a,b--> C $\sum = \left \{a, b \right \}$ $S = \left \{0,1,2 \right \}$ $q_{0} = \left \{ 0 \right \}$ $F = \left \{ 2 \right \}$ $\delta =$ $ \left \{ (q0,a) \to q1, (q0, b) \to q0,\right \}$ $\left \{(q1,a) \to q2,(q1,b) \to q1, \right \}$ $\left \{ (q2,a) \to q2, (q2, b) \to q2\right \}$ 非确定的有限状态自动机（NFA） 对任意的字符，有多于一个状态可以转移 graph LR O( ) --> A A((0)) --a,b--> B[1] A --a--> A B --b--> B B --b--> A $\sum = \left \{a, b \right \}$ $S = \left \{0,1 \right \}$ $q_{0} = \left \{ 0 \right \}$ $F = \left \{ 1 \right \}$ $\delta =$ $ \left \{ (q0,a) \to \left \{ q0, q1 \right \} \right \}$ $\left \{(q1,a) \to q1 \right \}$ $\left \{ (q2,a) \to \left \{ q0,q1\right \} \right \}$ 转换过程 graph LR A(RE) --Thompson<br>算法--> B(NFA) B --子集构造算法--> C(DFA) C --Hopcroft<br>最小化算法--> D>词法分析器代码] 6、RE到NFA：Thompson算法 正则表达式到非确定有限状态自动机: Thompson算法 基于对RE的结构做归纳（数学归纳法） 对基本的RE直接构造（2种） 对复合的RE递归构造（3种） 递归算法，容易实现 在我们的实现里，不到100行的C代码 【例】$a(b|c)*$ graph LR Begin( ) --> A A(0) --a--> B((1)) B --ε--> C((2)) C --ε--> D((3)) D --ε--> E((4)) E --b--> G((5)) D --ε--> F((6)) F --c--> H((7)) G --ε--> Y((8)) H --ε--> Y Y --ε--> D Y --ε--> Z(9) C --ε--> Z 7、NFA到DFA：子集构造算法 NFA->DFA：子集构造算法 算法思想 【例】$a(b|c)*$ 使用Thompson算法构造的NFA： graph LR Begin( ) --> A A(n0) --a--> B((n1)) B --ε--> C((n2)) C --ε--> D((n3)) D --ε--> E((n4)) E --b--> G((n5)) D --ε--> F((n6)) F --c--> H((n7)) G --ε--> Y((n8)) H --ε--> Y Y --ε--> D Y --ε--> Z(n9) C --ε--> Z 此时边上转移包含 $\varepsilon$（代价为0），即转移是不确定的，现在要转换成等价的DFA： $n0\overset{a}{\rightarrow} n1$ $n1 \to n2$代价为0，以此推算 $n0$ 可以无代价走到 $n1,n2,n3,n4,n6,n9$； 此时令集合 $q1 = \left \{n1,n2,n3,n4,n6,n9\right \}$，即 $n0\overset{a}{\rightarrow} q1$； 下面再从 $q1$ 出发： $q1\overset{b}{\rightarrow} \left \{ n5,n8,n9,n3,n4,n6 \right \}:q2$ $q1\overset{c}{\rightarrow} \left \{ n7,n8,n9,n3,n4,n6 \right \}:q3$ 从 $q2$ 出发：$q2\overset{...}{\rightarrow} \left \{ ... \right \}$ 依次类推求出所有子集，构造出 $n0 \overset{a}{\rightarrow} q1 \overset{b}{\rightarrow} q2 ......$，实现从NFA转化为DFA 在新的DFA里面，$q1,q2$ 其实都是接收状态 两个重要操作，称为ε-闭包 状态转换 对每个集合求边界 子集构造算法（工作表算法） q0 <- eps_closure(n0) // 计算n0能到达的地方 Q <- {q0} // 构造状态集 workList <- q0 // 队列 while (workList != []) // BFS remove q from workList foreach (character c) t <- eps_closure(delta(q, c)) D[q, c] <- t if (t \not\in Q) add t to Q and workList 对于上述例子来说： $q0= \left \{ n0 \right \}$； $q1 =t= \left \{ n1,n2,n3,n4,n6,n9\right \}$； $q2 = \left \{ n5.n8,n9,n3,n4,n6 \right \}$； $q3 = \left \{ n7,n8,n9,n3,n4,n6 \right \}$； $Q = \left \{ q0,q1,q2,q3 \right \}$ graph LR A((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C 接受状态为：$q1,q2,q3$。 不动点算法 算法为什么能够运行终止 时间复杂度 最坏情况$O(2^n)$ 但在实际中不常发生 因为并不是每个子集都会出现 ε-闭包的计算 深度优先方法 set closure = {}; void eps_closure (x) closure += {x} foreach (y: x--ε--> y) if (!visited(y)) eps_closure (y) 广度优先方法 set closure = {}; Q = []; // queue void eps_closure (x) = Q = [x]; while (Q not empty) q <- deQueue (Q) closure += q foreach (y: q----> y) if (!visited(y)) enQueue (Q, y) 8、DFA的最小化：Hopcroft算法 【例】DFA的$a(b|c)*$ graph LR A((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C 现在考虑合并：同样为接受状态/非接受状态 合并$q2,q3$： graph LR A((q0)) --a--> B(q1) B --b--> C(q4) B --c--> C C --b,c--> C 合并$q1,q4$，此时结构图正好诠释了$a(b|c)*$： graph LR A((q0)) --a--> B(q5) B --b,c--> B 这样的话可以占用更少的计算机资源 Hopcroft算法：基于等价类的思想 split(S) foreach (character c) if (c can split S) split S into T1, …, Tk hopcroft () split all nodes into N, A // 两个等价类：接受状态和非接受状态 while (set is still changes) split(S) 如图，split 相当于将 $s1$ 切分成 $s2$ 和 $s3$ graph LR subgraph s1 A B C end subgraph s2 D E end subgraph s3 F end A --a--> D B --a--> E C --a--> F 【例1】对于DFA的$a(b|c)*$，根据Hopcroft的思想： 首先我们分出两个集合：$N $ 和 $A$ graph LR subgraph N Aa end subgraph A B C D end Aa((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C 对于集合 $N$，不可再分；对于集合 $A$：可以接受 $b, c$ 两种不同字符，但总的来看不管怎么转换都是 $A$，即无法再分 graph LR A((q0)) --a--> B(q4) B --b,c--> B 【例2】如图 graph LR q0((q0)) --f--> q1((q1)) q1 --e--> q2((q2)) q1 --i--> q4((q4)) q2 --e--> q3(q3) q4 --e--> q5(q5) 则其对应的正则表达式为：$fee|fie = f(ee|ie)$ 首先切分成两个集合： graph LR subgraph N q0 q1 q2 q4 end subgraph A q3 q5 end q0((q0)) --f--> q1((q1)) q1 --e--> q2((q2)) q1 --i--> q4((q4)) q2 --e--> q3(q3) q4 --e--> q5(q5) 对于集合$A$，$q3,q5$ 无法区分，此集合不可分裂 对于集合$N$，到第三个字符 $e$ 时，$q2,q4$到$A$，但$q0, q1$还在内部，划分集合： $S1=\left \{ q0,q1 \right \},S2=\left \{ q2,q4 \right \},A=\left \{ q3,q5 \right \}$ 对于$S1$：都能接受$e$，且都可转换到$A$，不可再分 再看$S2$：$q0$不接受$e$，$q1$接受$e$后会转换到$S2$，拆分 最后得： graph LR q0((q0)) --f--> q1((q1)) q1 --e--> S((q2,q4)) q1 --i--> S S --e--> A(q3,q5) 9、DFA的代码表示 概念上讲，DFA是一个有向图 实际上，有不同的DFA的代码表示 转移表 (类似于邻接矩阵) 哈希表 跳转表 ...... 取决于在实际实现中，对时间空间的权衡 转移表 对于$a(b|c)*$ graph LR A((q0)) --a--> B(q1) B --b,c--> B 状态/字符 a b c 0 1 1 1 1 int table[M][N]; table[0]['a'] = 1; table[1]['b'] = 1; table[1]['c'] = 1; // other table entries are ERROR graph LR A[转移表] <--> B[词法分析驱动代码] 驱动代码： nextToken() state = 0 // 自动机目前走到的状态 stack = [] // 用于实现最长匹配 while (state != ERROR) c = getChar() if (state is ACCEPT) clear(stack) push(state) state = table[state][c] while(state is not ACCEPT) state = pop(); rollback(); 跳转表 nextToken() state = 0 stack = [] goto q0 q0: c = getChar() if (state is ACCEPT) clear (stack) push (state) if (c==‘a’) goto q1: q1: c = getChar() if (state is ACCEPT) clear (stack) push (state) if (c==‘b’||c==‘c’) goto q1