编者注：本文为历史博文归档；涉及 JDK、框架与工具链版本请以当前官方文档为准。引用外链图片可能失效，阅读时请注意时效性。词法分析 (1.html)：概念与转换图词法分析是编译过程的第一个阶段。正如前文简介所述，词法分析器的主要任务是将字符流转换为词法记号流（Token Stream）。在实际编译过程中，词法分析与语法分析通常是交错进行的。词法分析器不会一次性读取所有词法记号再交给语法分析器，而是每识别出一个词法记号，就立即送入语法分析器进行处理。流程图解如下：词法分析器是编译器中直接与源程序接触的部分，因此它可以承担以下任务：去掉注释：某些情况下可自动生成文档（如 C# 中的 /// 注释）。提供错误位置：通过记录行号来定位错误。一旦字符流变成词法记号流，行的概念就会消失。完成预处理：例如处理宏定义。1. 词法记号、词法单元与模式模式（Pattern）：一种规则，规定了什么样的字符串属于某个词法记号。词法单元（Lexeme）：源代码中匹配某个模式的具体字符串。词法记号（Token）：每个词法单元所属的类别。例如，对于代码 int a=3：int、a、=、3 都是词法单元。每个词法单元都属于某个词法记号。例如，3 是记号 num 的一个词法单元。模式规定了什么样的字符串对应什么样的记号。某一特定模式规定了某个词法记号下的一类词法单元。例如：模式：用字母开头的、包含字母和数字的串。词法记号：id（所有符合上述模式的字符串的记号都是 id）。词法单元：a123 或者 aabc 等。词法记号举例（简称记号）：每个关键字都有属于自己的记号。例如关键字 for 使用记号 for，关键字 int 使用记号 int。所有的关系运算符只有一个记号。例如 >=、<= 都用记号 relation。所有的标识符只有一个记号。例如 a123、aab 使用记号 id。所有的常数只有一个记号。例如 123、22、32.3、23E10 使用记号 num。所有的字符串只有一个记号。例如 "123"、"ab1" 使用记号 literal。在实际的编译器设计中，词法记号一般用一个整型数字表示。词法记号的属性：我们通常用 <词法记号，属性> 这个二元组来描述一个词法单元。对于源代码 position := initial + rate * 60 中的 +，可以使用 <add_op, '+'> 来表示。对于 position，表示为 <id, 指向符号表中 position 元素的指针>。具体来说，假定属性是一个字符串，那么 id 将指向字符串 "position\0"，存放这个字符串的地方叫做符号表。有些时候属性是不必要的。例如 := 表示赋值，我们可以使用 <assign_op, 257> 来表示。但这显得有些多余，因为 assign_op 和词法单元是一对一的，额外信息（属性）显得冗余。词法错误：词法分析器很难检测所有错误（有些错误还是可以检测的）。因为词法分析器的目的是产生词法记号流，它没有能力分析程序结构，因此无法检测到与程序结构有关的错误。例如：fi(a == b.html)。词法分析器不会发现这个错误，它认为 fi 是一个标识符而不是关键字 if。只有在后续阶段，这个错误才会被发现。词法分析器只能检测到词法单元上的问题。例如 12.ab 作为一个词法单元，没有对应的模式，就会产生错误。2. 正规式（Regular Expression）前面说过模式是一种规则，为了使用，我们需要一种规范的方式来表达模式，这就是正规式。1) 串和语言字符类（字母表）：关于字符的有限集合。串：字符类上字符的有穷序列。具体来说，是某个字符类上的串。串的长度：串中字符的个数。例如串 s = abc，长度为 3，用 |s| 表示。空串：用 ε 表示。语言：某字符类上的串的集合。属于语言的串，称为语言的句子或字。例如：{abc, a} 就是一个语言，abc 和 a 就是句子。另外空集也属于语言。连接：x 是串，y 是串，x 和 y 连接，结果就是 xy 这个串。假如 x 是串，x^3 为 xxx。对于 x^n (n>=0.html)，x^0 = ε。语言的运算（假定 L 和 M 是语言）：L U M = {s | s 属于 L 或者 M}。例如：L={1,2}, M={3,4}，那么 L U M = {1,2,3,4}。LM = {st | s 属于 L 且 t 属于 M}。例如：L={a,b}, M={1,2}，那么 LM = {a1,a2,b1,b2}，ML={1a,1b,2a,2b}。L^n = LLL...LLL（n 个 L）。例如：L={a,b}，那么 L^3 = {aaa,aab,aba,abb,baa,bab,bbb,bba}。注意 n 可以为 0，L^0 = {ε}。L* = L^0 U L^1 U L^2 U L^3 U ...L* 表示语言 L 中，所有的句子（串）以任意数目任意顺序组成的句子的集合，包括 ε。例如：{a,b}* = {ε,a,b,ab,ba,aab,aba,baa,bba,bab,abb,aaa,bbb...}。L* 叫做 L 的闭包。L+ = L^1 U L^2 U L^3 U...L+ 表示语言 L 中，所有的句子（串）以任意数目任意顺序组成的句子的集合，但是不包括 ε。L+ 中的句子和 L* 中的句子相比少一个 ε。通过上面的知识就可以表示一个标识符了。一般语言规定标识符是由字母开头，后接若干个字母或数字。我们可以这样表示：L={a-z A-Z}, N={0-9}，那么标识符就是 L(L U N.html)*。2) 正规式正规式又叫正规表达式，是模式的一种规范表达形式。正规式描述了一个集合，这个集合是由串组成的，其实这个集合就是我们前面说过的语言，不过这里大家喜欢使用正规集这个术语。正规式 r 表示正规集 L(r.html)。正规式的运算：闭包运算：运算优先级最高，(r.html)* 表示 (L(r.html))*。连接运算：运算优先级低于闭包，(r.html)(s.html) 表示 (L(r.html))(L(s.html))。或运算：运算优先级最低，(r.html) | (s.html) 表示 (L(r.html)) U (L(s.html))。例如：a | b 表示集合（语言/正规集）{a,b}。(a | b.html)(a | b.html) 表示集合 {aa,ab,ba,bb}。a* 表示由一切 a 字符组成的集合，包括 ε。(a | b.html)* 表示由 a,b 组成的集合，包括 ε。等价的正规式：(a | b.html) = (b | a.html)。正规式的代数性质：r|s = s|rr|(s|t.html) = (r|s.html)|t(rs.html)t = r(st.html)r(s|t.html) = rs|rtεr = rr** = r*r* = (r|ε.html)*注意，rs != sr，因为连接运算是有顺序的。记住并理解 2 个最基本的运算：a|b 表示 {a,b}，ab 表示 {ab}。3. 正规定义我们可以使用 名字 -> 正规式 这种表示，来说明一个等价的代替。例如：digit -> 0|1|2|3|4|5|6|7|8|9这里，我们就可以使用名字 digit 来代替后面的正规表达式。我们可以对某个串集进行正规定义，比如对标识符集合进行正规定义：letter -> A|B|...|Z|a|b|...|z digit -> 0|1|2|3|4|5|6|7|8|9 id -> letter(letter|digit.html)*请通过上面的例子理解正规定义。在表达正规表达式的时候，可以使用一些符号使得表达简化：+：表示一个或者多个实例。例如 a+ 表示 {a,aa,aaa,aaaa,...}。区别一下 *，他们的关系是 r+ = r r* 或 r+ = r* r（原文此处表述有误，通常 r+ 等价于 r r*，即至少一次，而 r* 包含零次。原文写 r+ = r* | ε 有误，应为 r* = r+ | ε。此处修正为通用定义：r+ 表示至少一次重复）。字符组：[abc] 表示 a|b|c，还可以这样表示 [a-zA-Z] 表示字母表中的字符。4. 状态转换图状态转换图是对词法分析器进行分析过程的描述。我们看一个判断关系运算的状态转化图：图中圆圈表示状态。箭头叫做边。X 状态的边，一般指的是由 X 状态出发，指向其他状态的边。边上的符号叫做标记。如何使用这个图？假定输入字符串是 <=。识别开始时，发现 < 和状态 0 与状态 1 间的边上的标记一样，那么就进入状态 1。下一个输入字符为 =，将进入状态 2，识别结束，返回二元组 <relop, LE>。上图中 2、3、4、5、7、8 状态，它们表示识别了一个关系运算符，这个状态叫做接受状态。状态 4 上面有一个 *，表示说，输入指针需要回移。所谓的输入指针，就是指向输入字符串中现在被读入的字符的位置。状态 4 会多读取一个字符，所以需要回移。也就是要注意的是，识别完成之后，输入指针指向的是被识别对象的最后一个字符，而不是待识别对象的第一个字符。这样的规定在实现词法分析器时，是有一定的意义。举例说明：输入字符串为：a>b识别的时候，从 > 开始，读入下一个字符 b 时，进入状态 4。这个时候，输入指针指向 b，这时候需要回移。我们在需要回移的状态上加一个 *。每个状态后面有一个 return(relop, XX.html)，这个是状态的行为。这里具体来说就是返回一个二元组的行为。词法分析器分析的结果就是得到二元组（词法记号和属性的二元组），这个二元组可以表示一个特定的字符串。其实上面的 * 也是表示行为，也就是输入指针回移的行为。我们可以看见，只有在接受状态才会有行为出现。对一门典型的语言来说，状态可能有几百个。5. 如何编写一个词法分析器根据需要写出正规定义。根据正规定义画出转换图。根据转换图写出词法分析器。这里详细讨论面向过程的语言（比如 C 语言）来实现一个词法分析器，并且主要讨论的是第 3 步。我们需要一个 nextchar() 函数，取得缓存中下一个等待分析的字符。这个函数完成 2 个任务：让输入指针向前移动一位。返回输入指针指向的字符。定义一个变量 token_beginning，在每个状态转换图开始的时候，记录输入指针的位置。定义 forward 变量作为输入指针。状态转换图被实现成为代码之后，每个状态都有属于自己的一块代码，这些代码按顺序完成以下工作：读取一个字符，通过 nextchar() 函数。读取的字符（标记），如果它和当前状态的边上的标记相同，那么状态将转换到边所指向的状态。具体实现只需要一个语句就是 state = xxx（xxx 为目标状态）；如果当前状态的所有边的标记和这个读取字符不一样，那么表示没有找到 Token（词法记号），这时候需要调用 fail() 函数。fail() 函数完成这样的功能：a. 指针回移，完成 forward = token_beginning 的操作。b. 找到适当的开始状态（也就是寻找另外一个转换图的开始状态）。假定所有的转换图都被尝试过，并且无法匹配，这时候会调用一个发现错误的小程序，来报告错误。请不要随意添加行为到各个状态所持有的代码中，应该以转换图中表示的行为为准。定义一个全局变量 lexical_value，用于保存一个指针。这个指针由 install_id() 和 install_num() 两个函数中的一个返回。定义两个整型变量 start, state，分别表示一个转换图的开始状态和当前的状态。nexttoken()：这是词法分析器的主程序。可以说，我们通过调用 nexttoken() 就完成了词法分析。这个函数一定是这样的格式：while(1.html){ switch(state.html){ case xx: ... case yy: ... default: ... } }关于详细的设计这里就不说了，举例说明一个转换图如何转换成为程序：这是一个识别浮点数的例子，看下面的代码：#include <stdio.h> #include <ctype.h> #include <string.h> char *nexttoken(); char nextchar(); void next(); void back(); char* gettoken(); char cbuf[] = "12.3********klj12.2e2jj778"; int forward = -1; int main(){ while(1.html){ printf("%s\n", nexttoken(.html)); if(forward >= strlen(cbuf.html)-1){ getchar(); return 0; } } } int state; int start; char* nexttoken(){ char c; state = 12; while(1.html){ switch(state.html){ case 12: c = nextchar(); start = forward; if(isdigit(c.html)){ state = 13; } else { next(); } break; case 13: c = nextchar(); if(isdigit(c.html)) state = 13; else if(c == 'e' || c == 'E'.html) state = 16; else if(c == '.'.html) state = 14; else state = 19; break; case 14: c = nextchar(); if(isdigit(c.html)) state = 15; break; case 15: c = nextchar(); if(isdigit(c.html)) state = 15; else if(c == 'e' || c == 'E'.html) state = 16; else state = 19; break; case 16: c = nextchar(); if(isdigit(c.html)) state = 18; else if(c == '+' || c == '-'.html) state = 17; break; case 17: c = nextchar(); if(isdigit(c.html)) state = 18; break; case 18: c = nextchar(); if(isdigit(c.html)) state = 18; else state = 19; break; case 19: back(); return gettoken(); } } } char nextchar(){ forward ++; return cbuf[forward]; } void back(){ forward --; } void next(){ forward ++; } char token_buf[128]; char* gettoken(){ int i, j = 0; for(i = start; i <= forward; i ++.html){ token_buf[j++] = cbuf[i]; } token_buf[j] = '\0'; return token_buf; }词法分析 (2.html)：NFA假定一个输入符号（Symbol），可以得到 2 个或者 2 个以上的可能状态，那么这个 Finite Automaton（有限自动机） 就是不确定的，反之就是确定的。例如：这就是一个不确定的有限自动机。在 Symbol a 输入的时候，无法确定状态应该转向 0 还是 1。不论是确定的 Finite Automaton 还是非确定的 Finite Automaton，它们都可以精确地描述正规集（Regular Sets）。我们可以很方便地把正规表达式（Regular Expressions）转换成为不确定 Finite Automaton。1. NFA (Nondeterministic Finite Automaton.html)非确定的有限自动机，我们用 NFA 这个术语表示。它是一个数学模型（Model）：一个关于状态的集合 S。一个关于输入符号（Input Symbols）的集合 Σ。函数 move : (状态，符号.html) -> P(S.html)。一个开始状态 s0，是一个唯一的状态。一个结束（接受）状态集合 F。注意，P(S.html) 表示 S 的幂集。在 NFA 中，Input Symbol 可以为 ε。转换函数（Transition Function）的含义：一个确定的状态已经从这个状态出发的一条边的标签（符号 Symbol），可以确定它的下一个状态组成的集合。比如上图（这个转换图就是 NFA 的一种表示方式），0 状态，a 符号，确定了一个状态的集合 {0,1}。2. 转换图（Transition Graph）的表示我们知道，计算机是无法直接表示一个图，我们应该如何来表示一个转换图？使用表格就是一个最简单的方法。每行表示一个状态，每列表示一个 Input Symbol。这种表格被叫做 Transition Table（转换表）。可以说使用表格是最简单的表示方式。但是我们可以注意到，在这个图中状态 1 和 Input Symbol a 是没有下一个状态的（空集合）。也就是说，对于一个大的状态图，我们可能花费大量的空间，而其中空集合会消耗不少空间，但是这种消耗又不是必须的。所以，作为最简单的一种实现方式，却不是最优的。语言（Language）被 NFA 定义：成为一个 Input String 的集合，而这个集合中的元素则是被 NFA 所接受的所有字符串（那些可以从开始状态到某接受状态的 Input String）。至于存储的方式，可以试试邻接表。注意，使用什么样的数据结构来保存 NFA 按情况不同而不同。在一些特殊情况下，某些数据结构会变得很方便使用，而换入其他情况，则不可以使用了。词法分析 (3.html)：DFA1. DFA (Deterministic Finite Automaton.html)DFA 就是确定的有限自动机。因为 DFA 和 NFA 关系密切，我们经常需要把他们拿到一起来讲。NFA 可以转化成为一个 DFA。DFA 依然是一个数学 Model，它和 NFA 有以下区别：不存在 ε-transition。也就是说，不存在 ε 为 Input Symbol 的边。对于 move 函数，move : (state, symbol.html) -> S。具体来说就是，一个状态和一个特定的 Input Symbol，不会映射到 2 个不同的状态。这样的结果是，每个状态，关于每个特定的 Input Symbol，只有一条出边。下图就是一个 DFA：接受语言 (a|b.html)*ab。注意一下，接受语言 (a|b.html)*ab 的 DFA 我们前面见过，就是这张图：2. DFA 的行为我们用一个算法来模拟 DFA 的行为：s = s0; c = nextchar(); while(c != EOF.html){ s = move(s, c.html); c = nextchar(); } if(s 属于 F.html) return "yes" else return "no"词法分析 (4.html)：NFA 与 DFA 的转化1. 子集构造 (Subset Construction.html)这是一个转换 NFA 到 DFA 的算法。我们知道 NFA 和 DFA 的区别最主要的就是一个状态和一个 Input Symbol 是否能够确定一个状态的问题。对于 NFA，它将确定一组状态；而 DFA 将确定一个状态。因此，我们有一个很好的办法就是把 NFA 的状态集对应每个 DFA 的状态。这就是 Subset Construction 的思想。不过这只是大概泛泛而论，我们需要更加明确的认识：NFA 在任何一个 Input Symbol 下，映射的状态集（通过 move 函数，这个集合通常用 T 字母表示）应该被知道。必须保证 1) 中状态集都对应了 DFA 中的一个状态。具体算法：Input：一个 NFA NOutput：接受相同语言的 DFA DMethod：为 D 构架一个 Transition Table（转换表）Dtran。每个 DFA 的状态是一个 NFA 的状态集合（这里一定要注意前面说过的 1)、2) 两点）。我们定义一些操作：s 表示 NFA 的状态。T 表示 NFA 的状态集合。a 表示一个 Input Symbol。ε-transition（ε转换）就是说 Input Symbol 为 ε 时的 Transition（转换）。操作 (Operation.html)描述 (Description.html)ε-closure(s.html)从 NFA 的状态 s 出发，只通过 ε-transition 到达的 NFA 的状态集合ε-closure(T.html)NFA 的集合 T 中的状态 p，只通过 ε-transition 到达的 NFA 的状态集合，再求这些集合的并集。用数学表达就是 `{pp 属于 ε-closure(t.html), t 属于 T}`move(T, a.html)NFA 的集合。这个集合在 Input Symbol 为 a，状态为 T 中任意状态情况下，通过一个转换得到的集合注意一下，所有的操作都是针对 NFA 的状态或者状态集合，得到的是 NFA 的状态集合，或者说是 DFA 看为一个状态。Subset Construction 算法：初始 Dstates，它仅仅含有状态（D 的状态）ε-closure(s0.html)，并且状态未被标记。s0 表示开始状态。注意，Dstates 放的是 D 的状态。while ( Dstates 有未标记的状态 T .html) { // T 是 D 中的一个状态，也是 N 中一个状态集 标记 T; for ( input symbol a .html) { // 遍历所有的 input symbol U = ε-closure(move(T, a.html)); // move 为 NFA 的 move 函数 if ( U 不在 Dstates 中 .html) 把 U 作为尚未标记的状态加入 Dstates; Dtran[T, a] = U } }注意，状态 s，ε-closure(s.html) 一定包含 s。我们先来熟悉上面的操作 Operation，再来看上面的算法。ε-closure(0.html) = {0, 1, 2, 4, 7} // 从 0 状态出发的，Input Symbol 为 ε 的所有状态的集合ε-closure(3.html) = {1, 2, 3, 4, 6, 7}ε-closure(8.html) = {8}ε-closure( {3, 8} .html) = ε-closure(3.html) U ε-closure(8.html) = {1, 2, 3, 4, 6, 7, 8}move(0, a.html) = 空move(7, a.html) = {8}move(8, b.html) = {9}move( {0, 1, 2, 4, 7}, a.html) = move(0,a.html) U move(1,a.html) U move(2,a.html) U move(4,a.html) U move(7,a.html) = {3, 8}现在可以回去理解一下算法了。这里再说说求 ε-closure(T.html) 的算法：把 T 的所有状态压入 stack(栈.html); ε-closure(T.html) 的初始值为 T 中的所有元素; // 也就是一定包含他们本身 while( 栈非空 .html) { 弹出栈顶元素 t; for( 每个属于 move(t, ε.html) 的状态 u ) { if( u 不在 ε-closure(T.html) 中 ) { u 加入 ε-closure(T.html); 把 u 入栈; } } }下面对上图如何使用 Set Construction 算法来构建 DFA 做一个详细的描述：初始化 Dstates，把集合 ε-closure(s0.html) = {0, 1, 2, 4, 7} 作为第一个状态，设此状态为 A。现在转化，Input Symbol {a, b}，因此，求：ε-closure(move(A, a.html))ε-closure(move(A, b.html))这里会得到 2 个状态：ε-closure(move(A, a.html)) = {1, 2, 3, 4, 6, 7, 8}，设其为 Bε-closure(move(A, b.html)) = {1, 2, 4, 5, 6, 7}，设其为 CB, C 放入 Dstates。改写 Dtrans。最终得到的 Dtrans 为：A = {0, 1, 2, 4, 7}B = {1, 2, 3, 4, 6, 7, 8}C = {1, 2, 4, 5, 6, 7}D = {1, 2, 4, 5, 6, 7, 9}因此，NFA 转化成为 DFA：词法分析 (5.html)：从正规式到 NFA在说到这个问题前，先告诉大家，我们可以直接从 Regular Expression 到 DFA，不过这里我们先不讨论这个问题。关于 RE 到 DFA 的算法有很多，这里学习一个最简单的。Algorithm Thompson's Construction：Input：一个字母表（Σ）上的 Regular Expression r。Output：一个接受 L(r.html) 的 NFA N。Method：把 r 解析成为子表达式（Subexpressions），然后使用下面的 1)、2) 规则，为 r 中的基本符号（Basic Symbols，基本符号就是 ε 和 Σ 中的字符）构建 NFA。基本符号符合 1)、2) 关于正规式的定义。注意，假如 Symbol a 出现多次，那么它每次出现都要构建一个 NFA。之后，我们需要通过 r 的语法结构，通过规则 3) 组合前面构建的 NFA，直到得到整个 NFA 为止。对于中间产生的 NFA，它只有一个终态，没有进入开始状态的边，也没有离开接受状态的边。1) 对于 ε 构造如下 NFA：注意，每次构建时，i, f 的值都不一样。因此可见构造一个识别 ε 的 NFA，会产生 2 个新的状态。2) 对于 Σ 中的每个字符 a：同样，对于 aaa，第一个 a 构造的 NFA 中的 i, f 不会和第 2 个 a 构造的 i, f 一样。因此可见构造一个识别 Σ 中的每个字符 a 的 NFA，会产生 2 个新的状态。3) 先假定 N(t.html), N(s.html) 分别是 t, s 的 NFA，则：a) 对于表达式 s|t 构建 NFA N(s|t.html)这里一样会产生 2 个新的状态 i, j。我们看其中一个 N(s.html)，左边的圆圈表示 N(s.html) 的开始状态，右边的圆圈表示 N(s.html) 的接受状态，N(t.html) 同理。b) 对于表达式 st，构建 N(st.html)这个时候，不产生新的状态。N(s.html) 的开始状态变为 N(st.html) 的开始状态，N(t.html) 的接受状态变成 N(st.html) 的接受状态，N(s.html) 的接受状态和 N(t.html) 开始状态成为一个状态。这里提醒一下，写程序的时候，这里千万要注意，因为没有新的状态产生，必须考虑状态的部分复制，如果不小心就会出错。c) 对于正规式 s*，构造 N(s*.html)这里一样需要产生 2 个新的状态 i, f。注意，产生了一条 N(s.html) 接受状态到 N(s.html) 开始状态的边，边上的 Symbol 为 ε。d) 对于 (s.html)，使用 N(s.html) 本身作为它的 NFA，也就是不用构造新的 NFA。注意一下，以上产生的 NFA，有以下性质：只有一个接受状态和一个开始状态。每个状态最多含有 2 个指向其他状态的边。详细的来说，如果状态只有一条指向其他状态的边，那么边上的 Symbol 为 Σ 中的任意字符或者 ε；如果状态有两条指向其他状态的边，那么边上的 Symbol 一定为 2 个 ε。由以上性质，我们可以很好的选择数据结构来表示 NFA。词法分析 (6.html)：DFA 的化简通过 NFA 转化而成的 DFA 不一定是最简的。也就是说，有多余的状态可以被删除。对于每一个正规定义，我们一定可以得到一个唯一的最简的 DFA。我们回顾一下 Move 函数，DFA 的 Move 函数：move : (state, symbol.html) -> S注意，这里 (state, symbol.html) 表示的是一个集合。这里规范的数学表达应该是：move : { (state, symbol.html) | 所有属于 DFA 的 state 和 symbol } -> S或者move : S × Σ -> S假如一个 DFA 的 Move 函数不是全函数，那么必须引入死状态。假如某个 DFA 的 Move 函数是全函数，那么每个状态在所有 Input Symbol 下都有出边。比如：这个 DFA 每个状态都可以接受所有的 Input Symbol，这里是 a, b。而下面的 DFA：先不要看红色部分。那么这个 DFA 的状态 c, d，它们无法通过 Input Symbol b 进入下一个状态。我们可以加上红色的部分，把这个 Move 函数转化成为一个全函数。并且，经过转化操作之后，新的 DFA 与原 DFA 等价。这个红色部分标识的状态，被叫做死状态。死状态：假如出现 DFA 的 Move 函数不是全函数，我们可以引入一个死状态 S（仅仅引入一个方可）。这个状态包括所有 Input Symbol 对自身的转换。所有的其他状态假如不接受某个 Input Symbol a，那么，我们建立这个状态到 S 且 Input Symbol 为 a 的边。状态的区别：假如一个状态 s，通过 Input String w，可以转换到某个状态；而某个状态 t，通过 w，转化到了一个与 s 通过 w 转化到的状态不同的状态。那么我们就可以通过 w 来区别状态 s, t。如果这样的 w 不存在，那么 s, t 这 2 个状态是无法区别的。每个接受状态都可以通过 ε 和非接受状态进行区别。化简算法，极小化 DFA 的思想：极小化 DFA 算法，它把状态分成一些不相交的子集。每一个子集中的所有状态都是不可区别的，而不同子集中的每个状态两两都是可区别的。最后我们把每个子集中的所有状态合成一个状态。1) 划分状态集首先把所有状态划分成为 2 个集合：一个集合是接受状态的集合，一个集合是非接受状态的集合。他们通过 ε 来区别。然后看每个集合中的状态是否还可以区别。例如一个集合通过 Input Symbol a，转换后得到的状态落入当前划分的不同集合，那么说明通过 Input Symbol a，是可以区别这个集合中的状态的（这里要强调的是，对于一个而不是多个 Input Symbol，假如转换到的状态落入不同的划分中，那么这些状态就是可以区别的）。我们假定有一个状态集合 {s1, s2}，s1 通过 a 到达状态集合 t1，s2 通过 a 到达状态集合 t2，t1, t2 分别是当前划分的状态集合。那么，集合 {s1, s2} 就可以分成 2 个集合 {s1}, {s2}。2) 构造最简的 DFA我们可以重复 1) 的步骤，最后得到一些子集合。我们从每个子集合中取一个状态，通过它们可以得到最简的 DFA。但具体需要按一定规则去构建。极小化 DFA 状态数的算法：Input：一个 DFA M，它的状态集是 S，输入符号集合 Σ，move : S × Σ -> S，开始状态为 s0，接受状态的集合为 F。Output：一个 DFA N，它和 DFA M 等价，并为最简。Method：初始化：假如 Move 函数不是全函数，那么加入死状态。构造划分 X：把 S 分成 2 个子集合，包括接受状态集合 F 和非接受状态集合 S-F（F 集合的补集）。Xnew 是一个划分。for( X 中的每个集合 G .html) { G 中状态每次通过 Σ 中的 symbol 转化到的状态如果属于 X 的不同子集，那么把集合 G 分成子集。每个 symbol 都可能划分 G，划分之后，使用下一个 symbol 进行操作，一直到遍历完所有的 input symbol。 更新 Xnew，用 G 的划分代替 G。 }如果 Xnew == X，那么定义 Xfinal = X，执行 4)。否则进行赋值操作 X = Xnew，进行 2)。Xfinal 中每个子集合中选择一个状态来代表这个状态集合。包含 s0 的状态集合，就是表示开始状态的集合。通过 DFA M 来构造 DFA N，规则是这样的：假如某状态 p 通过某 Input Symbol a，通过 DFA M 的 Move 函数转到另外一个状态 q，我们就用 q 所在的集合的代表状态来表示 q，并把这个转换过程的边、Input Symbol、集合的代表状态，加入 DFA N 中。我们需要遍历 DFA M，然后按规则构建 DFA N。化简的 DFA 中，可能有多个接受状态。如果 N 中有死状态（终态不是死状态），去掉它。有开始状态无法到达的状态，也去掉它。注意，在 DFA N 中有可能出现死状态，也就是通过所有的 Input Symbol 都回到自己的状态。前面说过，添加一个死状态得到的新的 DFA 与原 DFA 等价，那么我们这里也自然可以删除它。在真正的实现上面算法的时候，是灵活的。因为出于时间复杂度的考虑，可能并不需要完全照搬上面的算法，把握主要的思想是很重要的。每个 Input Symbol 都可能划分一次集合。每个集合中的状态被看成是不可区别的，即使在计算过程中某些集合中的状态是可以区别的。一定要确保每个集合都无法再分。补充说明：文法与自动机的关系参考链接：关于正则表达式、正则文法、NFA、LR(1.html)昨天和 Sumtec 谈到自动机和语法分析，一下子脑子有点混乱，把一些概念搞混了。看了半天清华的编译书也没有整明白... 今天早上起来看了《离散数学及其应用》里的自动机一部分，才厘清了头绪。还是外国人的书讲得清楚一点。昨天主要是把 NFA 和语法分析中的 LL(1.html)、LR(1.html) 搞混了。事实上 LL(1.html) 分析也好 LR(1.html) 分析也好，使用的是一个基于下推自动机的计算模型，而不是有限自动机。下推自动机的计算能力要比有限自动机强。其次就是 NFA 和 DFA 的计算能力确实是等价的。也就是对于任意一个 NFA 都可以找到一个与之等价的 DFA（可以使用子集法来构造这样一个 DFA）。为了说明有限自动机与 LL(1.html)、LR(1.html) 等分析法的关系，先概述一下文法的分类。文法分为四类：短语文法（0 型文法）上下文相关文法（1 型文法）上下文无关文法（2 型文法）正规（则）文法（3 型文法）上面四种文法有包含的关系。1 型文法是 0 型文法的一个子集，2 型文法是 1 型文法的一个子集，3 型文法是 2 型文法的一个子集。我们主要研究 2 型和 3 型文法。3 型文法（正则文法）与正则表达式（Regular Expression）是等价的。任意一个正则文法总是可以转化成一个等价的正则表达式。同时正则表达式与有限自动机是等价的。一个能由有限自动机识别的语言，必然可以用正则表达式来表示；而一个用正则表达式表示的语言一定可以用一个有限自动机来识别。但是正则文法不足以描述程序设计语言（比如，不能用正则表达式定义带有括号的数学表达式）。现在流行的程序设计语言如 C#、Java 等都是用 2 型文法，也就是上下文无关文法来定义的。因此有限自动机没有能力来识别程序设计语言（最后我会举个例子）。因此提出来下推自动机的模型。下推自动机具有有限自动机的所有部件，如状态、状态转移表等，同时它比有限自动机多一个堆栈，常称为计算栈。下推自动机可以根据情况将终结符或者非终结符压入栈，或者弹出栈。而 LL(1.html)、LR(1.html) 等分析法就是用来分析上下文无关文法的，基于下推自动机的模型。这也是为什么介绍语法分析时，所有的书都会说一个基于 LR(1.html) 分析法的预测分析器，都会有三部分组成：状态转移表、控制器和计算栈。而所谓的移进与归约就是入栈与出栈的问题。最后，举一个例子：先给出一个文法：S -> 0S1 | 01其中 0、1 是终结符。这样一个文法描述的语言其实就是 n 个 0 加上相等数量的 n 个 1，这里 n 是某个整数。这个文法是一个上下文无关文法，但不是一个正则文法。所以说我们没办法写出一个正则表达式来描述这样一个语言。等于一个能识别这个文法中的任意句子的 NFA，我们总能找到这样一个句子，它不是由该文法所定义的，却能被这个 NFA 接受。换句话说，任意 NFA 都不能用来判断某个句子是不是由以上这个文法所定义。说得实际一点，如果要求写一个着色程序，输入的文件是一串 0、1 组成的序列，要求把其中 n 个 0 加 n 个 1 的序列用红色着色，而其它用黑色的话，我们就不能光用正则表达式匹配来完成这一任务了。如果上面这个例子还比较抽象的话，那么对于“带有括号的数学表达式”这样一个语言，也是没有办法用正则表达式来进行匹配的。因为描述“带有括号的数学表达式”的文法，也不是一个正则文法，因为其中带有类似：F -> (E.html)这样的部分。而正则文法要求所有的产生式都必须是 A -> aB 或者 A -> a 这样的形式的（其中 A、B 是非终结符，a 是终结符）。说明：本文内容基于编译原理经典理论整理，部分示例代码为 C 语言风格，链接资源可能因年代久远失效，请以最新官方文档及教材为准。
Lex 代表 Lexical Analyzer（词法分析器），Yacc 代表 Yet Another Compiler Compiler（另一个编译器编译器）。让我们从 Lex 开始吧。LexLex 是一种生成扫描器（Scanner）的工具。扫描器是一种识别文本中词汇模式的程序。这些词汇模式（或者常规表达式）在一种特殊的句子结构中定义，我们将在下文讨论。一种匹配的正常表达式可能会包含相关的动作。这一动作可能还包括返回一个标记（Token）。当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。Lex 和 C 是强耦合的。一个 .lex 文件（Lex 文件具有 .lex 的扩展名）通过 lex 公用程序来传递，并生成 C 的输出文件。这些文件被编译为词法分析器的可执行版本。Lex 的常规表达式常规表达式是一种使用元语言的模式描述。表达式由符号组成。符号一般是字符和数字，但是 Lex 中还有一些具有特殊含义的其他标记。下面两个表格定义了 Lex 中使用的一些标记并给出了几个典型的例子。用 Lex 定义常规表达式字符含义A-Z, 0-9, a-z构成了部分模式的字符和数字。.匹配任意字符，除了 \n。-用来指定范围。例如：A-Z 指从 A 到 Z 之间的所有字符。[ ]一个字符集合。匹配括号内的 任意 字符。如果第一个字符是 ^ 那么它表示否定模式。例如：[abC] 匹配 a, b, 和 C 中的任何一个。*匹配 0 个 或者多个上述的模式。+匹配 1 个 或者多个上述模式。?匹配 0 个或 1 个 上述模式。$作为模式的最后一个字符匹配一行的结尾。{ }指出一个模式可能出现的次数。例如：A{1,3} 表示 A 可能出现 1 次或 3 次。**用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。^否定。**\**表达式间的逻辑或。"<一些符号>"字符的字面含义。元字符具有。/向前匹配。如果在匹配的模版中的"/"后跟有后续表达式，只匹配模版中"/"前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。( .html)将一系列常规表达式分组。常规表达式举例常规表达式含义joke[rs]匹配 jokes 或 joker。A{1,2}shis+匹配 AAshis, Ashis, AAshi, Ashi。(A[b-e].html)+匹配在 A 出现位置后跟随的从 b 到 e 的所有字符中的 0 个或 1 个。Lex 中的标记声明类似 C 中的变量名。每个标记都有一个相关的表达式。（下表中给出了标记和表达式的例子。）使用这个表中的例子，我们就可以编一个字数统计的程序了。我们的第一个任务就是说明如何声明标记。标记声明举例标记相关表达式含义数字 (number.html)([0-9].html)+1 个或多个数字字符 (chars.html)[A-Za-z]任意字符空格 (blank.html)" "一个空格字 (word.html)(chars.html)+1 个或多个 chars变量 (variable.html)(字符.html)+(数字.html)*(字符.html)*(数字.html)* Lex 编程Lex 编程可以分为三步：以 Lex 可以理解的格式指定模式相关的动作。在这一文件上运行 Lex，生成扫描器的 C 代码。编译和链接 C 代码，生成可执行的扫描器。注意: 如果扫描器是用 Yacc 开发的解析器的一部分，只需要进行第一步和第二步。关于这一特殊问题的帮助请阅读 Yacc 和 将 Lex 和 Yacc 结合起来 部分。现在让我们来看一看 Lex 可以理解的程序格式。一个 Lex 程序分为三个段：第一段是 C 和 Lex 的全局声明，第二段包括模式（C 代码），第三段是补充的 C 函数。例如，第三段中一般都有 main() 函数。这些段以 %% 来分界。那么，回到字数统计的 Lex 程序，让我们看一下程序不同段的构成。C 和 Lex 的全局声明这一段中我们可以增加 C 变量声明。这里我们将为字数统计程序声明一个整型变量，来保存程序统计出来的字数。我们还将进行 Lex 的标记声明。字数统计程序的声明%{ int wordCount = 0; %} chars [A-Za-z_'\."] numbers ([0-9].html)+ delim [" "\n\t] whitespace {delim}+ words {chars}+ %%两个百分号标记指出了 Lex 程序中这一段的结束和三段中第二段的开始。Lex 的模式匹配规则让我们看一下 Lex 描述我们所要匹配的标记的规则。（我们将使用 C 来定义标记匹配后的动作。）继续看我们的字数统计程序，下面是标记匹配的规则。字数统计程序中的 Lex 规则{words} { wordCount++; /* increase the word count by one*/ } {whitespace} { /* do nothing*/ } {numbers} { /* one may want to add some processing here*/ } %%C 代码Lex 编程的第三段，也就是最后一段覆盖了 C 的函数声明（有时是主函数）。注意这一段必须包括 yywrap() 函数。Lex 有一套可供使用的函数和变量。其中之一就是 yywrap。一般来说，yywrap() 的定义如下例。我们将在 高级 Lex 中探讨这一问题。字数统计程序的 C 代码段void main() { yylex(); /* start the analysis*/ printf(" No of words: %d\n", wordCount.html); } int yywrap() { return 1; }上一节我们讨论了 Lex 编程的基本元素，它将帮助你编写简单的词法分析程序。在 高级 Lex 这一节中我们将讨论 Lex 提供的函数，这样你就能编写更加复杂的程序了。将它们全部结合起来.lex 文件是 Lex 的扫描器。它在 Lex 程序中如下表示：$ lex <file name.lex>这生成了 lex.yy.c 文件，它可以用 C 编译器来进行编译。它还可以用解析器来生成可执行程序，或者在链接步骤中通过选项 -ll 包含 Lex 库。这里是一些 Lex 的标志：-c 表示 C 动作，它是缺省的。-t 写入 lex.yy.c 程序来代替标准输出。-v 提供一个两行的统计汇总。-n 不打印 -v 的汇总。高级 LexLex 有几个函数和变量提供了不同的信息，可以用来编译实现复杂函数的程序。下表中列出了一些变量和函数，以及它们的使用。详尽的列表请参考 Lex 或 Flex 手册（见后文的 资源）。Lex 变量变量说明yyinFILE* 类型。它指向 lexer 正在解析的当前文件。yyoutFILE* 类型。它指向记录 lexer 输出的位置。缺省情况下，yyin 和 yyout 都指向标准输入和输出。yytext匹配模式的文本存储在这一变量中（char*）。yyleng给出匹配模式的长度。yylineno提供当前的行数信息。（lexer 不一定支持。）Lex 函数函数说明yylex()这一函数开始分析。它由 Lex 自动生成。yywrap()这一函数在文件（或输入）的末尾调用。如果函数的返回值是 1，就停止解析。因此它可以用来解析多个文件。代码可以写在第三段，这就能够解析多个文件。方法是使用 yyin 文件指针（见上表）指向不同的文件，直到所有的文件都被解析。最后，yywrap() 可以返回 1 来表示解析的结束。yyless(int n.html)这一函数可以用来送回除了前 n 个字符外的所有读出标记。yymore()这一函数告诉 Lexer 将下一个标记附加到当前标记后。对 Lex 的讨论就到这里。下面我们来讨论 Yacc...YaccYacc 代表 Yet Another Compiler Compiler。Yacc 的 GNU 版叫做 Bison。它是一种工具，将任何一种编程语言的所有语法翻译成针对此种语言的 Yacc 语法解析器。它用巴科斯范式 (BNF, Backus Naur Form.html) 来书写。按照惯例，Yacc 文件有 .y 后缀。编译行如下调用 Yacc 编译器：$ yacc <options> <filename ending with .y>在进一步阐述以前，让我们复习一下什么是语法。在上一节中，我们看到 Lex 从输入序列中识别标记。如果你在查看标记序列，你可能想在这一序列出现时执行某一动作。这种情况下有效序列的规范称为语法。Yacc 语法文件包括这一语法规范。它还包含了序列匹配时你想要做的事。为了更加说清这一概念，让我们以英语为例。这一套标记可能是：名词，动词，形容词等等。为了使用这些标记造一个语法正确的句子，你的结构必须符合一定的规则。一个简单的句子可能是名词 + 动词或者名词 + 动词 + 名词。(如 I care. See spot run..html)所以在我们这里，标记本身来自语言（Lex），并且标记序列允许用 Yacc 来指定这些标记 (标记序列也叫语法.html)。终端和非终端符号终端符号: 代表一类在语法结构上等效的标记。终端符号有三种类型：命名标记: 这些由 %token 标识符来定义。按照惯例，它们都是大写。字符标记: 字符常量的写法与 C 相同。例如，- 就是一个字符标记。字符串标记: 写法与 C 的字符串常量相同。例如，"<<" 就是一个字符串标记。lexer 返回命名标记。非终端符号: 是一组非终端符号和终端符号组成的符号。按照惯例，它们都是小写。在例子中，file 是一个非终端标记而 NAME 是一个终端标记。用 Yacc 来创建一个编译器包括四个步骤：通过在语法文件上运行 Yacc 生成一个解析器。说明语法：编写一个 .y 的语法文件（同时说明 C 在这里要进行的动作）。编写一个词法分析器来处理输入并将标记传递给解析器。这可以使用 Lex 来完成。编写一个函数，通过调用 yyparse() 来开始解析。编写错误处理例程（如 yyerror()）。编译 Yacc 生成的代码以及其他相关的源文件。将目标文件链接到适当的可执行解析器库。用 Yacc 编写语法如同 Lex 一样，一个 Yacc 程序也用双百分号分为三段。它们是：声明、语法规则和 C 代码。我们将解析一个格式为 姓名 = 年龄 的文件作为例子，来说明语法规则。我们假设文件有多个姓名和年龄，它们以空格分隔。在看 Yacc 程序的每一段时，我们将为我们的例子编写一个语法文件。C 与 Yacc 的声明C 声明可能会定义动作中使用的类型和变量，以及宏。还可以包含头文件。每个 Yacc 声明段声明了终端符号和非终端符号（标记）的名称，还可能描述操作符优先级和针对不同符号的数据类型。lexer (Lex.html) 一般返回这些标记。所有这些标记都必须在 Yacc 声明中进行说明。在文件解析的例子中我们感兴趣的是这些标记：name, equal sign, 和 age。Name 是一个完全由字符组成的值。Age 是数字。于是声明段就会像这样：文件解析例子的声明%{ typedef char* string; /* to specify token types as char* */ #define YYSTYPE string /* a Yacc variable which has the value of returned token */ %} %token NAME EQ AGE %%你可能会觉得 YYSTYPE 有点奇怪。但是类似 Lex, Yacc 也有一套变量和函数可供用户来进行功能扩展。YYSTYPE 定义了用来将值从 lexer 拷贝到解析器或者 Yacc 的 yylval（另一个 Yacc 变量）的类型。默认的类型是 int。由于字符串可以从 lexer 拷贝，类型被重定义为 char*。关于 Yacc 变量的详细讨论，请参考 Yacc 手册（见 资源）。Yacc 语法规则Yacc 语法规则具有以下一般格式：result: components { /* action to be taken in C */ } ;在这个例子中，result 是规则描述的非终端符号。Components 是根据规则放在一起的不同的终端和非终端符号。如果匹配特定序列的话 Components 后面可以跟随要执行的动作。考虑如下的例子：param : NAME EQ NAME { printf("\tName:%s\tValue(name.html):%s\n", $1,$3);} | NAME EQ VALUE{ printf("\tName:%s\tValue(value.html):%s\n",$1,$3);} ;如果上例中序列 NAME EQ NAME 被匹配，将执行相应的 { } 括号中的动作。这里另一个有用的就是 $1 和 $3 的使用，它们引用了标记 NAME 和 NAME（或者第二行的 VALUE）的值。lexer 通过 Yacc 的变量 yylval 返回这些值。标记 NAME 的 Lex 代码是这样的：char [A-Za-z] name {char}+ %% {name} { yylval = strdup(yytext.html); return NAME; }文件解析例子的规则段是这样的：文件解析的语法file : record file | record ; record: NAME EQ AGE { printf("%s is now %s years old!!!", $1, $3.html);} ; %%附加 C 代码现在让我们看一下语法文件的最后一段，附加 C 代码。（这一段是可选的，如果有人想要略过它的话：）一个函数如 main() 调用 yyparse() 函数（Yacc 中 Lex 的 yylex() 等效函数）。一般来说，Yacc 最好提供 yyerror(char msg.html) 函数的代码。当解析器遇到错误时调用 yyerror(char msg.html)。错误消息作为参数来传递。一个简单的 yyerror( char* .html) 可能是这样的：int yyerror(char* msg.html) { printf("Error: %s encountered at line number:%d\n", msg, yylineno.html); }yylineno 提供了行数信息。这一段还包括文件解析例子的主函数：附加 C 代码void main() { yyparse(); } int yyerror(char* msg.html) { printf("Error: %s encountered \n", msg.html); }要生成代码，可能用到以下命令：$ yacc -d <filename.y>这生成了输出文件 y.tab.h 和 y.tab.c，它们可以用 UNIX 上的任何标准 C 编译器来编译（如 gcc）。命令行的其他常用选项-d, --defines: 编写额外的输出文件，它们包含这些宏定义：语法中定义的标记类型名称，语义的取值类型 YYSTYPE, 以及一些外部变量声明。如果解析器输出文件名叫 name.c, 那么 -d 文件就叫做 name.h。如果你想将 yylex 定义放到独立的源文件中，你需要 name.h, 因为 yylex 必须能够引用标记类型代码和 yylval 变量。-b file-prefix, --file-prefix=prefix: 指定一个所有 Yacc 输出文件名都可以使用的前缀。选择一个名字，就如输入文件名叫 prefix.c.-o outfile, --output-file=outfile: 指定解析器文件的输出文件名。其他输出文件根据 -d 选项描述的输出文件来命名。Yacc 库通常在编译步骤中自动被包括。但是它也能被显式的包括，以便在编译步骤中指定 -ly 选项。这种情况下的编译命令行是：$ cc -ly将 Lex 与 Yacc 结合起来到目前为止我们已经分别讨论了 Lex 和 Yacc。现在让我们来看一下他们是怎样结合使用的。一个程序通常在每次返回一个标记时都要调用 yylex() 函数。只有在文件结束或者出现错误标记时才会终止。一个由 Yacc 生成的解析器调用 yylex() 函数来获得标记。yylex() 可以由 Lex 来生成或完全由自己来编写。对于由 Lex 生成的 lexer 来说，要和 Yacc 结合使用，每当 Lex 中匹配一个模式时都必须返回一个标记。因此 Lex 中匹配模式时的动作一般格式为：{pattern} { /* do smthg*/ return TOKEN_NAME; }于是 Yacc 就会获得返回的标记。当 Yacc 编译一个带有 -d 标记的 .y 文件时，会生成一个头文件，它对每个标记都有 #define 的定义。如果 Lex 和 Yacc 一起使用的话，头文件必须在相应的 Lex 文件 .lex 中的 C 声明段中包括。让我们回到名字和年龄的文件解析例子中，看一看 Lex 和 Yacc 文件的代码。Name.y - 语法文件%{ typedef char* string; #define YYSTYPE string %} %token NAME EQ AGE %% file : record file | record ; record : NAME EQ AGE { printf("%s is %s years old!!!\n", $1, $3.html); } ; %% int main() { yyparse(); return 0; } int yyerror(char *msg.html) { printf("Error encountered: %s \n", msg.html); }Name.lex - Lex 的解析器文件%{ #include "y.tab.h" #include <stdio.h> #include <string.h> extern char* yylval; %} char [A-Za-z] num [0-9] eq [=] name {char}+ age {num}+ %% {name} { yylval = strdup(yytext.html); return NAME; } {eq} { return EQ; } {age} { yylval = strdup(yytext.html); return AGE; } %% int yywrap() { return 1; }作为一个参考，我们列出了 y.tab.h, Yacc 生成的头文件。y.tab.h - Yacc 生成的头文件# define NAME 257 # define EQ 258 # define AGE 259我们对于 Lex 和 Yacc 的讨论到此为止。今天你想要编译什么语言呢？相关主题您可以参阅本文在 developerWorks 全球站点上的 英文原文.Lex and Yacc, Levine, Mason 和 Branson, O'Reilly 及其合作公司，2nd Ed。Program Development in UNIX, J. T. Shen, Prentice-Hall India。Compilers: Principles, Techniques and Tools, Ahoo, Sethi 和 Ullman, Addison-Wesley Pub. Co., 1985，11。Lex and Yacc and compiler writing 指导。Java 版的 Lex 指导，叫做 Jlex。使用 Lex 和 Yacc 的 formalizing a grammar 实例。说明：本文基于经典的 Lex 与 Yacc 工具编写。在现代 Unix/Linux 开发环境中，通常建议使用其 GNU 增强版本 Flex (Fast Lexical Analyzer.html) 和 Bison 替代，二者兼容大部分 Lex/Yacc 语法但提供了更多特性与更好的维护支持。文中部分正则表达式特性（如 {m,n} 区间表达式）可能在标准 Lex 中不被支持，而在 Flex 中可用。