本章概述
 
执行词法分析的程序称为词法分析器。本章中，了解词法分析器的功能和输出形式，熟练掌握词法分析器设计的原理和方法，能够以转换图为工具使用某种语言的编写并调试一个扫描器。在正确理解正规表达式与有限自动机的有关概念、理论的基础上，了解词法分析的自动产生原理。词法分析器的功能和设计方法，正规表达式与有限自动机的等价性，有限自动机的确定化和最小化。
 
对于词法分析器的要求
 
词法分析器的功能和输出形式
 
词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列五种： 
 1. 关键字 是由程序语言定义的具有固定意义的标识符。有时称这些标识符为保留字或基本字。例如，Pascal中的begin, end, if, while都是保留字。这些字通常不用作一般标识符。 
 2. 标识符 用来表示各种名字，如变量名、数组名、过程名等等。 
 3. 常数 常数的类型一般有整型、实型、布尔型、文字型等等，例如，100，3.14159，TRUE，‘Sample’。 
 4. 运算符 如＋、－、*、/等等。 
 5. 界符 如逗号、分号、括号、/，/等等。 
 一个程序语言的关键字、运算符和界符都是确定的，一般只有几十个或上百个。而对于标识符或常数的使用通常都不加什么限制。 
 词法分析器所输出的单词符号常常表示成如下的二元式： 
 （单词种别，单词符号的属性值） 
 单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。 
 如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。 
 单词符号的属性是指单词符号的特性或特征。属性值则是反应特性或特征的值。例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。 
 在本书中，我们假定关键字、运算符和界符都是一符一种。对于它们，词法分析器只给出其种别编码，不给出它自身的值。标识符单列一种。常数按类型分种。
 
词法分析器作为一个独立子程序
 
词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列五种： 
 1. 关键字 是由程序语言定义的具有固定意义的标识符。有时称这些标识符为保留字或基本字。例如，Pascal中的begin, end, if, while都是保留字。这些字通常不用作一般标识符。 
 2. 标识符 用来表示各种名字，如变量名、数组名、过程名等等。 
 3. 常数 常数的类型一般有整型、实型、布尔型、文字型等等，例如，100，3.14159，TRUE，‘Sample’。 
 4. 运算符 如＋、－、*、/等等。 
 5. 界符 如逗号、分号、括号、/，/等等。 
 一个程序语言的关键字、运算符和界符都是确定的，一般只有几十个或上百个。而对于标识符或常数的使用通常都不加什么限制。 
 词法分析器所输出的单词符号常常表示成如下的二元式： 
 （单词种别，单词符号的属性值） 
 单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。 
 如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。 
 单词符号的属性是指单词符号的特性或特征。属性值则是反应特性或特征的值。例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。 
 在本书中，我们假定关键字、运算符和界符都是一符一种。对于它们，词法分析器只给出其种别编码，不给出它自身的值。标识符单列一种。常数按类型分种。
 
词法分析器的设计
 
输入和预处理
 
词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。 
 对于许多程序语言来说，空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义，而注解部分几乎允许出现在程序中的任何地方。它们不是程序的必要组成部分；它们存在的意义仅仅在于改善程序的易读性和易理解性。对于它们，预处理时可以将其剔掉。 
 有些语言把空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。 
 我们可以设想构造一个预处理子程序，它能够完成上面所述的任务。每当词法分析器调用它时，它就处理出一串确定长度（如120个字符）的输入字符，并将其装进词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样，分析器就可以在此缓冲区中直接进行单词符号的识别，而不必照管其它繁琐事务。 
 分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。 
 假定每半区可容120个字符，而这两个半区又是互补使用的。如果搜索指示器从单词起点出发搜索到半区的边缘但尚未到达单词的终点，那么就应调用预处理程序，令其把后续的120个输入字符装进另半区。我们认定，在搜索指示器对另半区进行扫描的期间内，现行单词的终点必定能够到达。这意味着对标识符和常数的长度实际上必须加以限制（例如，不得多于120个字符），否则，即使缓冲区再大也无济于事。
 
单词符号的识别：超前搜索
 
下面我们来介绍单词符号识别的一个简单方法——超前搜索。 
 关键字的识别 
 象FORTRAN这样的语言，关键字不加特殊保护（只要不引起矛盾，用户可以用它们作为普通标识符），关键字和用户自定义的标识符或标号之间没有特殊的界符作间隔。这就使得关键字的识别甚为麻烦。请看下面的例子： 
 1 DO99K=1,10 
 2 IF(5.EQ.M) I=10 
 3 DO99K=1.10 
 4 IF(5)=55 
 这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以基本字开头的。语句3和4是赋值句，它们都是以用户自定义标识符开头的。 
 为了从1、2中识别出关键字DO和IF，我们必须要能够区别1、3和区别2、4。语句1、3的区别在于等号之后的第一个界符：一个为逗点，另一个为句末符。语句2、4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。这就是说，为了识别 1、2 中的关键字，我们必须超前扫描许多个字符，超前到能够肯定词性的地方为止。对于1、3来说，尽管都以‘D’和‘O’两字母开头，但不能一见‘DO’就认定是DO语句。我们必须超前扫描，跳过所有的字母和数字，看看是否有等号。如果有，再向前搜索。若下一个界符是逗号，则可以肯定DO应为关键字。否则，DO不构成关键字，它只是用户标识符的头两个字母。所以，为了区别1和3，我们必须超前扫描到等号后的第一个界符处。对于语句2、4来说，必须超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。若此字符是字母，则得逻辑IF。若此字符是数字，则得算术IF。否则，就应认为是用户自定义标识符IF。 
 标识符的识别 
 多数语言的标识符是字母开头的“字母/数字”串，而且在程序中标识符的出现都后跟着算符或界符。因此标识符的识别大多没有困难。 
 常数的识别 
 多数语言算术常数的表示大体相似，对它们的识别也是很直接的。但对于某些语言的常数的识别也需用超前搜索的方法。例如，对于上述FORTRAN片断的第2句中的5.EQ.M，只有当超前扫描到字母Q时才能断定5的词性。因为5.E08和5.EQ.M的头三个字符完全一样。 
 逻辑（或布尔）常数和用引号括起来的字符串常数都很容易识别。但对FORTRAN的文字常数（例如3HABC）的识别却有点麻烦。对3HABC的识别单单依靠形式规则是不够的，而且需要了解“3H”的含义。也就是说，对于这种单词的识别有赖于理解词头的词义。所以，FORTRAN文字常数的识别通常需要特殊处理：当分析器读到尾跟H的无符号整型常数时，必须首先将这个常数的值翻译出来，然后把后续的n个（n为该整型常数的值）字符取出来，作为“字符串常数”输出。 
 算符和界符的识别 
 词法分析器应将那些由多个字符复合成的算符和界符（如C＋＋和Java中的＋＋、－－、>=等）拼合成一个单词符号。因为这些字符串是不可分的整体，若分划开来，便失去了原来的意义。在这里同样需要超前搜索。
 
状态转换图
 
使用状态转换图是设计词法分析程序的一种好途径。转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。一个状态转换图可用于识别（或接受）一定的字符串。 
 一个非常重要的事实是，大多数程序语言的单词符号都可以用转换图予以识别。 
 注意，一个程序语言的所有单词符号的识别也可以用若干张状态转换图予以描述。虽然用一张图就可以了，但用若干张图有时会有助于概念的清晰化。
 
状态转换图的实现
 
转换图容易用程序实现。最简单的办法是让每个状态结点对应一小段程序。下面我们将引进一组全局变量和过程，将它们作为实现转换图的基本成分。这些变量和过程是： 
 1. ch 字符变量，存放最新读进的源程序字符。 
 2. strToken 字符数组，存放构成单词符号的字符串。 
 3. GetChar 子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。 
 4. GetBC 子程序过程，检查ch中的字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符。 
 5. Concat 子程序过程，将ch中的字符连接到strToken之后。例如，假定strToken原来的值为“AB”，而ch中存放着‘C’，经调用Concat后，strToken的值就变为“ABC”。 
 6. IsLetter和IsDigit 布尔函数过程，它们分别判断ch中的字符是否为字母和数字。 
 7. Reserve 整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）。 
 8. Retract 子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。 
 9. InsertId 整型函数过程，将strToken中的标识符插入符号表，返回符号表指针。 
 10. InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。 
 这些函数和子程序过程都不难编制。使用它们能够方便地构造状态转换图的对应程序。一般来说，可让每个状态结点对应一程序段。 
 对于不含回路的分叉结点来说，可让它对应一个switch语句或一组if…then…else语句。 
 当程序执行到达“错误处理”时，意味着现行状态i和当前所面临的输入串不匹配。如果后面还有状态图，出现在这个地方的代码应为：将搜索指示器回退一个位置，并令下一个状态图开始工作。如果后面没有其它状态图，则出现在上述位置的代码应进行真正的出错处理，报告源程序含有非法符号，并进行善后处理。 
 对于含回路的状态结点来说，可让它对应一个由while语句和if语句构成的程序段。 
 终态结点一般对应一个形如return (code, value)的语句。其中，code为单词种别编码；value或是单词符号的属性值，或无定义。这个return意味着从分析器返回到调用者，一般指返回到语法分析器。凡带星号*的终态结点意味着多读进了一个不属于现行单词符号的字符，这个字符应予退回，也就是说，必须把搜索指示器回调一字符位置。这项工作由Retract过程来完成。 
 对于某些状态，若需要将ch的内容送进strToken，则可以调用Concat。
 
正规表达式与有限自动机
 
正规式与正规集
 
对于字母表å，我们感兴趣的是它的一些特殊字集，即所谓正规集。我们将使用正规式这个概念来表示正规集。下面是正规式和正规集的递归定义： 
 1. e和f都是S上的正规式，它们所表示的正规集分别为{e}和f； 
 2. 任何aÎS，a是S上的一个正规式，它所表示的正规集为{a}； 
 3. 假定U和V都是S上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，（U|V）、（U·V）和（U）也都是正规式，它们所表示的正规集分别为L(U) ∪L(V)、L(U)L(V)（连接积）和(L(U))（闭包）。 
 仅由有限次使用上述三步骤而得到的表达式才是S上的正规式。仅由这些正规式所表示的字集才是S上的正规集。 
 正规式的运算符“|”读为“或”，“·”读为“连接”，“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可以省去，但规定算符的优先顺序为：先“”，次“·”，最后“|”。连接符“·”一般可省略不写。 
 若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U＝V。例如，b(ab)=(ba)*b, (a|b)=(a*b*)*。 
 令U、V和W均为正规式，显而易见，下列关系普遍成立： 
 1. U|V=V|U（交换律） 
 2. U|(V|W)=(U|V)|W（结合律） 
 3. U(VW)=(UV)W（结合律） 
 4. U(V|W)=UV|UW（分配律） 
 (V|W)U=VU|WU 
 5. eU=Ue=U
 
确定有限自动机（DFA）
 
一个确定的有限自动机（DFA） M是一个五元式 
 

 
 $M=(Q,\sum,f,S,Z)$
 

 其中
 
 
 
Q是一个有限集，它的每个元素称为一个状态；
$\sum$是一个有穷字母表，它的每个元素称为一个输入字符； 
 3. f是一个从Q×$\sum$至Q的单值部分映射。$f(q_i,a)=q_j,(q_i,q_j\in Q,a\in\sum$意味着：当现行状态为$q_i$、输入字符为a时，将转换到下一状态$q_j$。我们称$q_j$为$q_i$的一个后继状态；
$S\in Q$，是唯一的初态。
$Z\subseteq Q$，是一个终态集（可空）。
 
 
显然，一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示d(s, a)的值。这个矩阵称为状态转换矩阵。例如，有DFA 
 
 
 
 $M=(\{0,1,2,3\}, \{a,b\}, d, 0, \{3\})$
 

 其中d为： 

 f(0,a)=1 f(0,b)=2 

 f(1,a)=3 f(1,b)=2 

 f(2,a)=1 f(2,b)=3 

 f(3,a)=3 f(3,b)=3 

 它所对应的状态转换矩阵如表3.2所示。 

 

 表3.2 状态转换矩阵

 
状态
a
b
0
1
2
1
3
2
2
1
3
3
3
3
 
一个DFA也可表示成一张（确定的）状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用S中的一个不同输入字符作标记，整张图含有唯一的一个初态结点和若干个（可以是0个）终态结点。 
 对于$\sum$中的任何字a，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于a，则称a可为DFA M所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字e可为M所识别（或接受）。DFA M所能识别的字的全体记为L(M)。 
 如果一个DFA M的输入字母表为S，则我们也称M是S上的一个DFA。可以证明：S上的一个字集VÍS*是正规的，当且仅当存在S上的DFA M，使得V＝L(M)。 
 DFA的确定性表现在映射d: S×S→S是一个单值函数。也就是说，对任何状态sÎS和输入符号aÎS，d(s,a)唯一地确定了下一状态。从转换图的角度来看，假定字母表S含有n个输入字符，那么，任何一个状态结最多只有n条弧射出，而且每条弧以一个不同的输入字符标记。如果也允许d是一个多值函数，我们就得到非确定自动机的概念。
 
非确定有限自动机（NFA）
 
一个非确定有限自动机（NFA）M是一个五元式 
 

 
 $M=(Q,\sum,f,S,Z)$
 

 其中
 
 
 
$Q,\sum,Z$意义同DFA；
f是一个从S×$\sum$到S的子集的映照，即 f：$Q\times\sum \to 2^Q$
$S\subset Q$，是一个非空初态集；
$Z\subseteq Q$，是一个终态集（可空）。
 
 
显然，一个含有m个状态和n个输入字符的NFA可表示成如下的状态转换图：该图含有m个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条弧用S*中的一个字（不一定要不同的字而且可以是空字e）作标记（称为输入字），整张图至少含有一个初态结点以及若干个（可以是0个）终态结点。某些结点既可以是初态结点也可以是终态结点。 
 对于$\sum$中的任何一个字a，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为e的弧）等于a，则称a可为NFA M所识别（读出或接受）。若M的某些结点既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的e通路，那么，空字e可为M所接受。 
 显然，DFA是NFA的特例。但是，对于每个NFA M存在一个DFA M”，使L(M)＝L(M”)。把NFA确定化为DFA的方法称为子集法。
 
正规文法与有限自动机的等价性
 
对于正规文法G和有限自动机M，如果L(G)＝L(M)，则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论： 
 1. 对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机（FA） M，使得L(M)＝L(G)。 
 2. 对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。
 
正规式与有限自动机的等价性
 
下面我们将证明： 
 1. 对任何FA M，都存在一个正规式r，使得L(r)=L(M)。 
 2. 对任何正规式r，都存在一个FA M，使得L(M)=L(r)。 
 上述结论加上3.3.3和3.3.4所证明的结论，说明正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的能力上是互相等价的。
 
确定有限自动机的化简
 
一个确定有限自动机M的化简是指：寻找一个状态数比M少的DFA M¢，使得L(M)＝L(M¢)。 
 假定s和t是M的两个不同状态，我们称s和t是等价的：如果从状态s出发能读出某个字w而停于终态，那么同样，从t出发也能读出同样的字w而停于终态；反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出同样的w而停于终态。如果DFA M的两个状态s和t不等价，则称这两个状态是可区别的。例如，终态与非终态是可区别的。因为，终态能读出空字e，非终态则不能读出空字e。又例如，图3.8中的状态1与2是可区别的，因为，状态1读出a而停于终态，状态2读出a后不到达终态。 
 一个DFA M的状态最少化过程旨在将M的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。 
 对M的状态集S进行分划的步骤是：首先，把S的终态与非终态分开，分成两个子集，形成基本分划P。显然，属于这两个不同子集的状态是可区别的。假定到某个时候P已含m个子集，记P={I(1), I(2), …, I(m)}，并且属于不同子集的状态是可区别的。检查P中的每个I(i)看能否进一步分划。对于某个I(i)，令I(i)={q1, q2, …, qk}，若存在一个输入字符a使得（关于Ia的定义见3.3.3）不全包含在现行P的某一子集I(j)中，就将I(i)一分为二。例如，假定状态s1和s2经a弧分别达到状态t1和t2，而t1和t2属于现行P的两个不同子集，那就将I(i)分成两半，使得一半含有s1： 
 I(i1) = { s | s ÎI(i) 且s经a弧到达t1所在子集中的某状态} 
 另一半含有s2： 
 I(i2) = I(i) - I(i1) 
 由于t1和t2是可区别的，即存在一个字w，t1将读出w而停于终态，而t2或读不出w或虽然可读出w但不到达终态；或情形恰好相反。因而字aw将状态s1和s2区别开来。也就是说，I(i1)中的状态与I(i2)中的状态是可区别的。至此我们将I(i)分成两半，形成了新的分划。 
 一般地，若落入现行P中N个不同子集，则应将I(i)划分为N个不相交的组，使得每个组J的Ja都落入P的同一子集，这样形成新的分划。重复上述过程，直至分划中所含的子集数不再增长为止。至此，P中的每个子集已不可再分。也就是说，每个子集中的状态是互相等价的，而不同子集中的状态则是可互相区别的。 
 经上述过程之后，得到一个最后分划P。对于这个P中的每一个子集，我们选取子集中的一个状态代表其它状态。例如，假定I={q1, …, qk}是这样一个子集，我们即可挑选q1代表这个子集。在原来的自动机中，凡导入到q2, …, qk的弧都改成导入到q1。然后，将q2, …, qk从原来的状态集S中删除。若I中含有原来的初态，则q1是新初态；若I中含有原来的终态，则q1是新终态。可以证明，经如此化简之后得到的DFA M¢和原来的M是等价的，也就是L(M)＝L(M¢)。若从M¢中删除所有无用状态（即从初态结开始永远到达不了的那些状态），则M¢便是最简的（包含最少状态）。
 
词法分析器的自动产生
 
语言LEX的一般描述
 
一个LEX源程序主要包括两部分。一部分是正规定义式，另一部分是识别规则。 
 如果å是一个字母表，å上的正规定义式是下述形式的定义序列： 
 d1 → r1 
 d2 → r2 
 … 
 di → ri 
 其中di表示不同的名字，每个ri是å∪{d1,…, di-1}上的符号所构成的正规式。ri中不能含有di, di+1, …, dn，这样，对任何ri，可以构成一个S上的正规表达式，只要反复地将式中出现的名字代之以相应的正规式即可。注意，如果允许ri中出现某些dj, j³i，那么这种替代过程将有可能不终止。 
 LEX源程序中的识别规则是一串如下形式的LEX语句： 
 P1 {A1} 
 P2 {A2} 
 … … 
 Pm {Am} 
 其中，每个Pi是一个正规式，称为词形。Pi中除了出现S中的字符外，还可以出现正规定义式左部所定义的任何简名di。即，Pi是S∪{d1,…,dn}上的一个正规式。由于每个di最终都可化为纯粹S上的正规式，因此，每个Pi也同样如此。每个Ai是一小段程序代码，它指出了，在识别出词形为Pi的单词之后，词法分析器应采取的动作。这些识别规则完全决定了词法分析器L的功能。分析器L只能识别具有词形P1，…，Pm的单词符号。 
 关于描述动作Ai的LEX语言成分可以有种种不同的选择。下面，在讨论L的作用时，将对Ai的有关组成成分予以必要的说明和解释。 
 首先，我们考察由LEX所产生的目标程序L（词法分析器）是如何进行工作的：L逐一扫描输入串的每个字符，寻找一个最长的子串匹配某个Pi，将该子串截下来放在一个叫做TOKEN的缓冲区中（事实上，这个TOKEN也可以只包含一对指示器，它们分别指出这个子串在原输入缓冲区中的始末位置）。然后，L就调用动作子程序Ai，当Ai工作完后，L就把所得的单词符号（由种别编码和属性值两部分构成）交给语法分析程序。当L重新被调用时就从输入串中继上次截出的位置之后识别下一个单词符号。 
 可能存在这样的情形，对于现行输入串找不到任何词形Pi与之相匹配。在这种情形下，L应报告输入串含有错误（如非法字符），并进行善后处理。但也可能存在一个最长子串，可以匹配若干个不同的Pi。在这种二义的情形下，以LEX程序中出现在最前面的那个Pi为准。换句话说，愈处于前面的Pi，匹配优先权就愈高（在服从最长匹配的前提下）。 
 每个词形Pi相应的动作Ai的基本组成成分是“返回Pi的种别编码和属性值”。这可用一个LEX过程表示成return(code, value)。如果Pi是“标识符”，则value为符号表入口指针；若Pi是“整型常数”，则value为常数表入口指针；若Pi既不是标识符也不是某种常数，那么，value便无定义。
 
超前搜索
 
在某些语言中，要识别一个单词符号必须超前看若干字符。例如，在标准FORTRAN中，空白字符除了出现在文字常数中有意义之外，在别的任何地方出现都是没有意义的。一个众所周知的例子是： 
 DO 501 I＝1.25 
 在碰到小数点之前，我们弄不清楚这是DO语句还是一个对标识符DO501I进行赋值的赋值语句。为此，我们引进另一个正规式运算符‘/’，用它来指出一个单词符号的截取点。于是，关于基本字DO的识别规则就可写为： 
 DO/(letter|digit)= (letter|digit)，{动作} 
 这意味着要求词法分析器L向前扫描到逗点，识别出具有如下词形的输入子串： 
 DO/(letter|digit)= (letter|digit)， 
 在寻找到这种匹配之后，就按识别规则中斜线所指处将输入串截断，取出其前一部分子串（即DO）作为词法分析器L的输出，而将后一部分子串归还给输入串。斜线‘/’应被当成是正规式的一个“算符”，可称它为“截断”算符。因此，并不意味着要求在输入串中有相应的斜线。分析器L下次扫描将从DO后面的那个字符开始。 
 对于FORTRAN这种语言，对其基本字的识别往往都得超前多看若干个字符。另一例子是关于基本字逻辑IF的识别问题，在FORTRAN中，语句 
 IF(M)＝322 
 是完全正确的。因此，当我们看到IF时，不能立即断定它就是基本字逻辑IF。要判别它是否是基本字逻辑IF，就必须看右括号右边是否是一个语句。由于FORTRAN 的语句都是以字母开头的，因此，等于要看右括号右边的第一个字符是否为字母。于是，识别逻辑IF的规则可表示为： 
 IF/‘(’any*‘)’letter {动作} 
 其中辅助定义名any代表FORTRAN字母表中任一字符。同样，识别算术IF的规则应为： 
 IF/‘(’any*‘)’digit+ {动作}
 
LEX的实现
 
LEX的编译程序旨在将一个LEX源程序改造为一个词法分析器L，这个词法分析器L将象有限自动机那样工作。LEX程序的编译过程是直观的。首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi；然后，引进一个新初态X，通过e弧，将这些自动机连接成一个新的NFA；最后，将它改造成一个等价的DFA（必要时，还可以对这个DFA进行化简）。
 
但是，根据LEX程序的要求，在编译时还必须注意以下几点： 
 首先，在原来的每个NFA Mi中都有它自己的一个终态，它指明一个匹配于词形Pi的输入子串已被识别到。在等价的DFA中，一个状态子集可能包含若干个不同的终态。而且，这个DFA的终态（子集）和通常的意义也有所不同。因为，我们要求的是匹配最长的子串，因此，在到达某个终态之后，这个DFA应继续工作下去，以便寻找更长的匹配。直到无法继续前进为止（即，到达那样的一个状态，它对所面临的输入字符没有后继状态）。 
 当到达“无法继续前进”的情形时，就回头检查DFA所经历的每个状态子集，从后面逐个向前检查，直到发现某个含有原来的NFA终态的子集为止（如果不存在这种子集则认为输入串含有错误）。如果这个子集中含有若干个原来的NFA终态，那么，就以那个与最先出现的识别规则相对应的终态为准。 
 关于正规式中超前搜索‘/’的实现问题可作如下处理：当将一个词形Pi化成相应的NFA Mi时，我们将‘/’当作e，但将射出‘/’弧的结标记为“截断结”。这意味着，当最终的DFA用于识别输入串时，我们不要求有一个真正的‘/’与之对应。但当含有‘/’的词形获得匹配时，必须把截断结以后的字符退还给输入串，而只取截断点前的那部分字符作为单词。 
 至此，我们简要地描述了LEX编译程序如何将LEX源程序翻译成一张状态转换表和一个有关控制程序的基本过程。由于词法分析工作很费时间和空间，因此，对确定化的自动机应进行状态化简。还有，当对LEX源程序的识别规则中的词形Pi进行展开时，其中那些代表字符类的辅助定义名（如letter，digit）可以保留不动，就好象它们也是一个“字符”那样。这样，就可为后来的NFA或DFA的构造节省许多状态。这意味着，当从输入串读入一个字符时，首先要判别它是否属于诸如字母或数字这样的类。 
 如果大量的关键字都作为正规式列于LEX源程序的识别规则之中，那么，状态结点的数目就很大，而且有许多结点非常相似。因此，为了节省内存，对最终所得的状态转换矩阵表应使用一种紧凑的数据表示法。
 
小结
 
通过这一章的学习，我们了解了词法分析器的功能和输出形式，掌握了词法分析器设计的原理和方法，了解了正规表达式与有限自动机的有关概念、理论，了解了词法分析的自动产生原理。在下一章中，我们将讨论语法分析程序的构造。
 
典型题解
 
例题3.1 是非题 
 1．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（ ） 
 2．对任何正则表达式e，都存在一个NFA M，满足L(M)=L(e) （ ）[北京航天航空大学2000年研究生入学试题] 
 3．对任何正则表达式e，都存在一个DFA M，满足L(M)=L(e) （ )[北京航天航空大学2000年研究生入学试题]
 
 
 
分析 
 1．转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符或字符串）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符串。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。由上述转换图的定义知道，转换图只能有一个初态，但至少要有一个终态，这说明转换图可以有多个终态，因此本题错。 
 2．正规式和有限自动机的等价性：：⑴ 对任何FA M，都存在一个正规式r，使得L(r)=L(M)；⑵ 对任何正规式r，都存在一个FA M，使得L(M)=L(r)。 
 因此对任何正则表达式e，都存在一个NFA M，满足L(M)=L(e)。 
 所以本题正确。 
 3．根据上题以及确定有限自动机和非确定有限自动机之间的等价性，可以知道本题正确。
 
 
例题3.2 填空题 
 1．词法分析器输出的单词符号常常表示成如下二元式：（ ）。 
 2．一张转换图只包含有限个状态，其中有一个被认为是（ ）态，而且实际上至少要有一个（ ）态。 
 3．词法分析器的任务是（ ）。 
 
 
 
解答 
 1．词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值） 
 2．一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是（初）态，而且实际上至少要有一个（终）态（用双圈表示） 
 3．词法分析器的功能是（输入源程序，输出单词符号）。
 
 
例题3.3 简答题 
 1．何谓扫描器？扫描器的功能是什么？[国防科大研究生院2001年硕士生入学考试] 
 2．试简述有穷状态自动机与正则表达式的等价性概念。 
 （南京大学2000年硕士研究生入学考试） 
 3．给出有限状态自动机的严格定义。 
 （浙江大学1998年硕士研究生入学考试试题）
 
 
 
解答 
 1．扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号，供语法分析器使用。 
 一般把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。 
 词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字符，如：空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义，而注解部分几乎允许出现在程序中的任何地方。它们不是程序的必要组成部分，预处理时可以将其剔掉。词法分析器一般会构造一个预处理子程序来处理上述任务。 
 2．∑上的非确定有限自动机M所能识别字的全体L（M）是∑上的一个正规集；同时，对于∑上的每个正规集V，存在一个∑上的确定有限自动机M，使得V=L（M）。 
 3．有限状态自动机分为确定有限状态自动机和非确定有限状态自动机两类，确定有限自动机是非确定有限自动机的特例，但它们具有相同的表示能力。给出有限状态自动机的定义实际上只需要给出非确定有限状态自动机的定义就可以了： 
 一个有限状态自动机（NFA）M是一个五元式 
 M=(S, S, d, S0, F) 
 其中 
 1. S是一个有限集，它的每个元素称为一个状态； 
 2. S是一个有穷字母表，它的每个元素称为一个输入字符； 
 3. d是一个从S×S*到S的子集的映照，即 
 d：S×S*→2S 
 4. S0ÍS，是一个非空初态集； 
 5. FÍS，是一个终态集（可空）。
 
 
例题3.4 选择题 
 1．__不是NFA的成分。 
 A.有穷字母表 B.初始状态集合 
 C.终止状态集合 D.有限状态集合 
 （北京航天航空大学2000年研究生入学考试试题） 
 2．__不是编译程序的组成部分。 
 A.词法分析程序 B.代码生成程序 
 C.设备管理程序 D.语法分析程序 
 （北京航天航空大学2000年研究生入学考试试题） 
 分析 
 1．分析NFA的5个组成部分：S是一个有限状态集合，S是一个有穷字母表，d是一个从S×S*到S的子集的映照，即d：S×S*→2S，S0ÍS是一个非空初态集，FÍS是一个终态集（可空）。从字面上看，似乎A、B、C、D四个选项都是NFA的组成部分，但仔细分析，就会发现B：初始状态集合和NFA中定义的S0有区别，S0是非空初态集，而初始状态集合却只是一个集合，可以是一个可空的集合。另外三个选项都和NFA中的定义一致，因此本题的选择为B。 
 2．查看编译程序的结构图，编译程序由以下7个部分组成：词法分析器、语义分析器、语义分析及中间代码生成器、优化段、目标代码生成器以及表格管理模块和出错处理模块。由此可以看出A、B、D所描述的都是编译程序的一个部分，但C设备管理程序，它所描述的是操作系统的一部分，在操作系统中负责各种外设的管理，和编译程序没有关系，因此本题的答案是C。
 
本章练习
 
编写一个对于Pascal源程序的预处理程序。该程序的作用是，每次被调用时都将下一个完整的语句送进扫描缓冲区，去掉注解行，同时要对源程序列表打印。
请给出以下C++程序段中的单词符号及其属性值。 
 int CInt::nMulDiv(int n1, int n2) 
 { 
 if (n3 == 0) return 0; 
 else return (n1 * n2) / n3; 
 }
用类似C或Pascal的语言编写过程GetChar, GetBC 和 Concat。
用某种高级语言编写并调试一个完整的词法分析器。
证明3.3.1中关于正规式的交换律、结合律等五个关系。
令A、B和C是任意正规式，证明以下关系成立： 
 A|A=A 
 (A*)=A 
 A*=e | AA* 
 (AB)A=A(BA) 
 (A|B)=(A*B)=(A | B*)* 
 A=b | aA当且仅当A=a*b
构造下列正规式相应的DFA 
 1(0 | 1)*101 
 1(1010* | 1(010)*1)*0 
 0*10*10*10* 
 (00|11) * ((01|10) (00|11) * (01|10) (00|11) * ) *
给出下面正规表达式： 
 (1) 以01结尾的二进制数串； 
 (2) 能被5整除的十进制整数； 
 (3) 包含奇数个1或奇数个0的二进制数串； 
 (4) 英文字母组成的所有符号串，要求符号串中的字母依照字典序排列； 
 (5) 没有重复出现的数字的数字符号串的全体； 
 (6) 最多有一个重复出现的数字的数字符号串的全体； 
 (7) 不包含子串abb的由a和b组成的符号串的全体。
对下面情况给出DFA及正规表达式： 
 (1) {0,1}上的含有子串010的所有串； 
 (2) {0,1}上不含子串010的所有串。
一个人带着狼、山羊和白菜在一条河的左岸。有一条船，大小正好能装下这个人和其它三件东西中的一件。人和他的随行物都要过到河的右岸。人每次只能将一件东西摆渡过河。但若人将狼和羊留在同一岸而无人照顾的话，狼将把羊吃掉。类似地，若羊和白菜留下来无人照看，羊将会吃掉白菜。请问是否有可能渡过河去，使得羊和白菜都不被吃掉？如果可能，请用有限自动机写出渡河的方法。
用某种高级语言写出： 
 (1) 将正规式变成NFA的算法； 
 (2) 将NFA确定化的算法； 
 (3) DFA状态最少化的算法。
(1) 给出描述C浮点数的DFA。 
 (2) 给出描述Java表达式的DFA。
构造一个DFA，它接受S＝{0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。
给定右线性文法G： 
 S→0S | 1S | 1A | 0B 
 A→1C | 1 
 B→0C | 0 
 C→0C | 1C | 0 | 1 
 求出一个与G等价的左线性文法。 
 *15. 非形式地说明：任何正规集L都存在一个非负整数p，使得L中任何长度超过p的字都可表示成abg，其中0< | b | £ p（|b|指b的长度），而对任何i³0, abig属于L。 
 *16. 下面的字集是否为正规集？或写出其正规式，或给出否证。 
 (1) L1={anbn | n³0}; 
 (2) L2={x|x中含有相同个数的a和b}; 
 (3) L3={ap|p为素数}。
假定L和M都是正规集 
 (1) 证明L∪M、L∩M和~M（补集）也是正规的； 
 (2) L¢是L中每个字的逆转，证明L¢也是正规的。
写出描述ANSI C的单词符号的LEX程序。
 
19. 
 假定有正规定义式 
 A0→a|b 
 A1→A0A0 
 … 
 An→An-1An-1 
 考虑词形An 
 (1) 把An中所有简名都换掉，最终所得的正规式的长度是多少； 
 (2) 字集An的元素是什么？把它们非形式地表示成n的函数； 
 (3) 证明识别An的DFA只需用2n+1个状态就足够了。 
 20. 把LEX的“动作”成分加以充实使得可用它来编写语法制导编辑器。
 
本章扩展资源
 
[1]陈火旺，钱家骅，孙永强. 程序设计语言编译原理. 北京：国防工业出版社，1984.
[2]Alfred V.Aho, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Acldison-Wesley Publishing Company, 1986.
[3]A.V.Aho, J.D. Ullman. Principles of Compiler Descign, Addison=Wesley, 1977.
[4]M. Minsky. Computation: Finite and Infinite Machines.  Prentice-Hall, 1967.
[5]A. Salomaa. Formal Languages. Academic Press, 1975.
[6]W.L. Johnson, etc. Automatic generation of efficient lexical analyzers using finite techniques.  Comm. AGM. 11:12, 1968.
[7]M.E. Lesk. LEX—a lexical analyzer generator, CSTR 39, Bell Lab, 1975.
[8]王兵山，吴兵，形式语言. 国防科技大学出版社，1988.
[9]霍普克罗夫特，厄尔曼. 形式语言及其与自动机的关系. 科学出版社，1979.