第2章 词 法 分 析第2章 词 法 分 析2.1 词法分析中的若干问题词法分析中的若干问题 2.2 模式的形式化描述模式的形式化描述 2.3 记号的识别记号的识别有限自动机有限自动机 2.4 从正规式到词法分析器从正规式到词法分析器 2.5 本章小结本章小结 第2章 词 法 分 析2.1 词法分析中的若干问题词法分析中的若干问题2.1.1 记号、模式与单词记号、模式与单词自然语言中的句子通常由一个个单词和标点符号组成，可以根据其在句子中的作用，将它们划分为动词、名词、形容词、标点符号等不同的种类。程序设计语言与此相类似，组成语句的基本单元也可根据其在句子中的作用分类。最基本分类有四类：(1)关键字(保留字)：这类单词在程序设计语言中有固定的意义，如begin、end、while等。若在程序设计语言中不允许用它们再表示其他的意思，则这类单词也被称为保留字。第2章 词 法 分 析(2)标识符：标识符是程序设计语言中最大的一个类别，它的作用是为某个实体起一个名字，以便于今后称呼(引用)，如draw_line、sort等。可以用标识符来命名的实体包括类型、变量、过程、常量、类、对象、程序包、标号等，即类型名、变量名、过程名、常量名等。第2章 词 法 分 析(3)字面量：字面量是指直接以其字面所表示的常量，如25、true、Thisisastring等。值得注意的是，字面量与常量是两个不同的概念，常量可以是一个字面量(直接表示)，也可以是一个常量名(命名表示)。例如可以在Pascal中声明：constmax_length=25，显然25是一个常量，max_length也是一个常量，我们称25为字面量，而不称max_length为字面量。根据字面量的内容，可以将它们再进行更细的划分，如常数字面量(包括整型字面量、实型字面量、枚举字面量等)、字符串字面量等。第2章 词 法 分 析(4)特殊符号：程序设计语言中的特殊符号，类似于自然语言中的标点符号，每个符号在程序设计语言中均有特殊用途。可以根据它们的用途，再细分为算符(如+、*、/等)、分隔符(如；、”、“等)。显然，一个单词究竟是标识符、关键字，还是特殊符号，需要根据一定的构词规则来产生和识别。我们将产生和识别单词的规则称为模式(patten)，按照某个模式(规则)识别出的元素称为记号(token)，而单词(lexeme)一词是指被识别出元素自身的值。第2章 词 法 分 析例例2.1对于语句：position:=initial+rate*60，可以识别出下述序列：标识符特殊符号标识符特殊符号标识符特殊符号数字字面量其中position、initial、rate均被识别为标识符，因为它们均符合同一条规则，即以字母打头的字母数字串。记号至少含有两个信息：一个是记号的类别，如“标识符”；另一个是记号的值，如“position”。显然，如果把记号看作是一个类型的话，则单词就是一个类型中的实例。由于我们总是说识别出一个标识符，而不说识别出一个position或rate，因而将词法分析器识别出的序列称为记号流。第2章 词 法 分 析记号的类别、模式以及单词三者之间的关系可以用表2.1加以说明。其中，const和if分别是被细分的关键字，它们的特点是一个记号类别仅对应一个单词；relation表示关系运算符；id表示标识符；num表示数字字面量；literal表示字符串字面量；comment表示注释，它们的特点是一个记号类别可以对应若干个单词。由于语法分析及其后的阶段并不对注释进行分析，因而可在词法分析阶段中滤掉注释，即词法分析器可以不向语法分析器返回comment。而其他的记号，均是源程序中的有效成分，需要返回给语法分析器。第2章 词 法 分 析表表2.1 记号、模式与单词记号、模式与单词第2章 词 法 分 析2.1.2 记号的属性记号的属性从例2.1中已经知道，记号至少包含两个部分：记号类别和记号的其他信息。可以看出，记号的类别唯一标识一类记号，例如所有的关系运算符均可以由relation来标识，而所有字符串字面量均可以由literal来标识。所以，记号的类别可以被认为是记号的名字或记号的代表，在不引起混淆的情况下，将记号的类别简称为记号。记号的其他信息被称为记号的属性。例如，num可以取值3.1416，则称3.1416是num的属性，而literal可以取值“coredumped”(不含引号)，则称“coredumped”是literal的属性。由此可见，记号的类别标识一类记号，而记号的类别加属性标识一个记号实例。第2章 词 法 分 析在计算机内部，可以有不同的方式来表示记号的类别和属性。一般情况下，记号的类别可以用整型编码或枚举类型表示，如表2.1中每个记号类别可以用括号中的整型编码表示，如01表示const，82表示id等。根据记号类别的不同，记号的属性的值可以有不同的表示方法。relation的属性值是一个有限可枚举集合，可以用每个属性值在集合中的位置来表示它，如1表示，2表示25由表2.2的三个记号组成。其中标识符的属性值也可以由mycount在符号表中的入口(下标)来表示。表表2.2 记号的表示记号的表示第2章 词 法 分 析2.1.3 词法分析器的作用与工作方式词法分析器的作用与工作方式词法分析器是编译器中唯一与源程序打交道的部分，从某种意义说，也可以被认为是整个编译器的预处理器。它的主要工作包括：(1)滤掉源程序中的无用成分，如注释、空格、回车等。例如，表2.1中记号的种类除了comment之外，均有一个编码，表示需要递交给语法分析器进行后继的处理，而comment没有对应编码，表示注释成分可以过滤掉，不需要递交，因为语法分析及其之后的各个阶段已经不再需要它们。第2章 词 法 分 析(2)处理与具体平台有关的输入。不同的操作系统或相关软件构成的平台，对某些特殊符号(如文件结束符等)可能有不同表示，因此需要在词法分析阶段分情况处理。(3)识别记号，并交给语法分析器。这是词法分析器的主要任务，本章将在各节中详细讨论。第2章 词 法 分 析(4)调用符号表管理器或出错处理器，进行相关处理。词法错误是源程序中常见的错误，如出现非法字符、拼错关键字、多或少字符等。值得注意的是，词法错误往往不是由词法分析器检查出来的，而是由语法分析器发现的。这是因为，源程序中除了非法字符之外的大部分字符或字符串，都可以被词法分析器的某个模式所匹配，从而被识别成一个记号。而这些记号的正确与否，在没有上下文对照的情况下，是很难判断的。例如，12x被认为是一个非法的Pascal的标识符，但是，由于12可以被识别整型数的模式匹配，而x可以被识别标识符的模式匹配，因而词法分析器会分别识别出一个整型数和一个标识符，而不是报告一个错误。第2章 词 法 分 析根据编译器的总体需求，词法分析器在整个编译器中可以有不同的工作方式。(1)词法分析器作为语法分析器的子程序。最常采用，也最容易实现的工作方式是将词法分析器作为语法分析器的子程序，每当语法分析器需要一个记号时，就调用词法分析器，并得到一个识别出的记号。其工作方式如图2.1所示。(2)词法分析器进行单独的一遍扫描。另一种常用的工作方式，是安排词法分析器进行单独的一遍扫描，它以源程序为输入，输出是以记号流形式表示的源程序。其工作方式如图2.2所示。第2章 词 法 分 析图2.1作为子程序的词法分析器图2.2词法分析器进行单独一遍扫描第2章 词 法 分 析(3)与语法分析器并行工作的模式。上述两种词法分析器的工作模式与语法分析器的关系均被认为是串行的。为了提高编译器的效率，可以通过一个队列，使词法分析器和语法分析器以生产/消费的形式并行工作。词法分析器将识别出的记号流输出到队列中，语法分析器从队列中取得记号，只要队列中有识别出的记号，则词法分析器和语法分析器就可以同时工作。其工作方式如图2.3所示。第2章 词 法 分 析图2.3并行工作模式第2章 词 法 分 析2.1.4 输入缓冲区输入缓冲区词法分析器是编译器中读入源程序字符序列的唯一阶段，而相当可观的编译时间又消耗在词法分析阶段，所以，加快词法分析是设计编译器时要考虑的重要问题之一。可以通过设立输入缓冲区来加快读入源程序字符序列的速度。如果使用词法分析器生成器编写词法分析器，则生成器会提供读入和缓冲输入序列的例程；如采用通用程序设计语言编写词法分析器，就需要显式地管理源程序的读取。第2章 词 法 分 析输入缓冲区一般被设计为一块与磁盘扇区大小成倍数关系的内存。若一个扇区为1024字节，则输入缓冲区可以取1024、4096或8192字节等。这样可以保证对缓冲区的一次输入所需的I/O操作次数尽可能少。输入缓冲区的安排一般采用单缓冲区或双缓冲区(缓冲区对)的方式。下边所介绍的是单缓冲区方式，它也是词法分析器生成器FLEX所采用的方式。第2章 词 法 分 析图2.4是一个单缓冲区的示意图。有效输入序列从缓冲区的起始位置开始存放，最后添加一个特殊标记(此处用#表示)：若缓冲区一次装不下整个源程序，它就表示缓冲区的结束，否则它紧跟在文件结束符(eof)之后，表示整个输入源程序的结束。用两个指针c_ptr和f_ptr分别指向当前被识别记号的第一个字符和向前扫描的字符。最初，两个指针同时指向下一个被识别记号的第一个字符，f_ptr向前扫描，直到某个模式匹配成功。一旦这个记号被确定，f_ptr指向被识别出记号的右端字符，在此记号被处理后，两个指针都移向该记号之后的下一个字符。在f_ptr向前扫描的过程中，如果遇到文件结束标志，则表示输入序列已被处理完。如果遇到特殊标记#，说明缓冲区中的内容需要更新。这时，首先将c_ptr到f_ptr所指的内容(不包括特殊标记)移到缓冲区的起始位置，然后将新的内容读进缓冲区，最后加上特殊标记。具体算法如下：第2章 词 法 分 析c_ptrf_ptr图2.4单缓冲区第2章 词 法 分 析procedureget_next_buffer(buffer，start，length)is-start和length是需仍保留在缓冲区中字符串的起始位置和长度beginiflength=buffer_size-buffer_size是缓冲区实际容量thenreturnerror；elseforiinlow.low+length1-low是缓冲区下界，假设从0开始loopbuffer(i):=buffer(start+ilow)； -把剩余的输入移到缓冲区头部endloop；第2章 词 法 分 析num_to_read:=buffer_sizelength；ifnumber_to_readblock_size-block_size应是磁盘扇区的整数倍thennumber_to_read:=block_size;endif;read_buffer(buffer，length+low，num_to_read)；endif；endget_next_buffer；第2章 词 法 分 析假设被扫描的输入序列的最大长度不超过max_length，则可以选择buffer_size=block_size+max_length，即缓冲区的大小是磁盘扇区大小的整数倍加上一个最长可能被扫描的输入序列。这种缓冲技术能胜任大多数情况，但在向前被扫描字符个数超过缓冲区长度的极端情况下会失效。早期的程序设计语言通常采用开括号与闭括号的方式标识注释，如表2.1中的comment，如果程序员不小心忘记书写闭括号，而词法分析器的设计又将comment作为一个完整的记号识别，就会出现被扫描字符个数超过缓冲区长度的情况。因此，后来设计的程序设计语言大多采用仅有开括号，而默认换行标志为闭括号的注释方式，如上述算法中的“-”(Ada的注释方式)或者C+中的“/”，从根本上杜绝了这种极端情况。第2章 词 法 分 析2.2 模式的形式化描述模式的形式化描述2.2.1 字符串与语言字符串与语言从词法分析的角度看，程序设计语言是由记号组成的集合，每个记号又是由若干字母按照一定规则组成的字符串。为了讨论的简单性和准确性，本章对常用的术语以定义的方式给出。有一点需要强调，编译领域的很多名词术语的使用并不统一，因此希望读者掌握“是什么”，而不是“叫什么”。在下述的讨论中，我们首先定义一个泛泛的“语言”，然后在此基础上规定一个正规集，而程序设计语言就是一个正规集。第2章 词 法 分 析定义2.1语言L是有限字母表上有限长度字符串的集合。定义2.1明确指出，语言是一个集合，集合中的元素是字符串，并且强调了两个有限:字母表是有限的，即字母表中元素是有限多个；字符串的长度是有限的，即字符串中字符个数是有限多个。这是由于计算机所能表示的字符个数和字符串的长度都是有限的。第2章 词 法 分 析由于字符串的有序性，使得以字符串作为元素的集合具有某些特性。字符串和集合的基本概念和特性，以表格的形式分别列在表2.3和表2.4中。其中，字符串的连接运算是一种新形式的运算，它表示两个字符串首尾相接，形成一个新的集合。例如，S1=pre，S2=fix，则S1S2=prefix。值得注意的是，集合中连接运算所形成的新集合与交运算形成的新集合完全不同。例如，若L=pre，M=fix，则LM=，而LM=prefix。第2章 词 法 分 析表表2.3 字符串的基本概念字符串的基本概念第2章 词 法 分 析表表2.4 字符串集合上的基本运算字符串集合上的基本运算第2章 词 法 分 析2.2.2 正规式与正规集正规式与正规集定义2.2令是一个有限字母表，则上的正规式及其表示的集合递归定义如下:是正规式，它表示集合L()=；若a是上的字符，则a是正规式，它表示集合L(a)=；若正规式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的给出了正规式上的三种运算:(a)或运算、(b)连接运算和(c)闭包运算。对于由多个操作数和多个操作符组成的正规式，可以利用(d)所给的括号规定运算的先后次序。如果对或、连接和闭包运算进行如下约定:三种运算均具有左结合性质；运算的优先级从高到低顺序排列为:闭包运算、连接运算、或运算。则正规式中不必要的括号可以被省略。例如，(a)|(b)*(c)可以简化成a|b*c。第2章 词 法 分 析 例例2.3设字母表=a，b，c，部分上的正规式和正规式所表示的正规集如表2.5所示。表表2.5 正规式与它表示的正规集正规式与它表示的正规集第2章 词 法 分 析正规集是一个集合，而正规式是表示正规集的一种方法。正如不同算术表达式可以表示同一个数(如3+5、5+3、2+6等均表示8)一样，不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。例2.4令L(x)=a，b，L(y)=c，d，则L(x|y)=a，b，c，dL(y|x)=a，b，c，dx|y和y|x表示同一个正规集。第2章 词 法 分 析定义2.3若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。正规式之间的一些恒等运算，被称为正规式的代数性质。表2.6给出了正规式的若干代数性质。利用这些性质，可以对复杂的正规式进行化简，使得可以用最简单形式的正规式表示一个集合。而简单的正规式意味着其所对应的识别器的构造也是简单的。第2章 词 法 分 析表表2.6 正规式的代数性质正规式的代数性质第2章 词 法 分 析2.2.3 记号的说明记号的说明表2.1中用自然语言对模式进行了非形式化的描述，例如标识符模式的非形式化描述是“以字母打头的字母数字串”。这一描述很不精确，存在一些问题，如哪些符号是字母，哪些符号是数字，字母数字串的长度可以是多少等等。由于正规式是严格的数学表达式，采用正规式来描述模式，解决了精确描述模式的问题。另外，从词法分析器的角度上看程序设计语言，用正规式说明的记号是一个正规集。用正规式说明记号的公式为：记号=正规式，可以读作为“(左边)记号定义为(右边)正规式”，或者“记号是正规式”。通常，在不引起混淆的情况下，也把说明记号的公式简称为正规式，或者规则。第2章 词 法 分 析例例2.5表2.1中的记号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)*第2章 词 法 分 析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)*)上述正规式给出了标识符的精确定义，用自然语言可以描述为“字母是英文26个字母大小写中任何一个，数字是十进制阿拉伯数字中的任何一个，标识符是以字母打头的、其后可跟随0个或若干个字母或数字的字符串”。第2章 词 法 分 析 1简化正规式描述简化正规式描述为了简化正规式的描述，通常可以采用如下的几种正规式的缩写形式。(1)正闭包。若r是表示L(r)的正规式，则r+是表示(L(r)+的正规式，且下述等式成立:r+=rr*=r*r，r*=r+|+与*具有相同的运算优先级和结合性。(2)可缺省。若r是正规式，则(r)?是表示L(r)的正规式，且下述等式成立:r?=r|第2章 词 法 分 析(3)字符组。字符组是或关系的缩写形式，它把所有存在或关系的字符集中在里面。其中的字符可以有如下两种书写方式:枚举方式:如abc，它等价于a|b|c分段方式:如0-9a-z，它等价于0123456789abcdefghijklmnopqrstuvwxyz第2章 词 法 分 析(4)非字符组。若r是一个字符组形式的正规式，则r是表示L(r)的正规式。例如，若=，则L(abc)=d,e,f,g。(5)串。若r是字符连接运算的正规式，则串r与r等价，即r=r。特别地，=,?a=a。引入串的表示可以避免与正规式中运算符的冲突。例如：a|b=a|ba|b。第2章 词 法 分 析2引入辅助定义式引入辅助定义式引入辅助定义式的主要目的是为较复杂、但需要重复书写的正规式命名，并在定义式之后的引用中，用名字代替相应的正规式。所以，辅助定义式实质上仍然是正规式，唯一的区别是正规式与外部模式匹配，而辅助定义式不与任何模式匹配。第2章 词 法 分 析例例2.6引入正规式的缩写形式和辅助定义式后，id和num的正规式可重写如下。char=a-zA-Zdigit=0-9digits =digit+optional_fraction=(.digits)?optional_exponent=(E(+|)?digits)?id=char(char|digit)*num =digitsoptional_fractionoptional_exponent第2章 词 法 分 析2.3 记号的识别记号的识别 有限自动机有限自动机2.3.1 不确定的有限自动机不确定的有限自动机(Nondeterministic Finite Automata，NFA)定义2.4NFA是一个五元组(5-tuple)M=(S，move，s0，F)其中：S是有限个状态(state)的集合；是有限个输入字符(包括)的集合；第2章 词 法 分 析move是一个状态转移函数，move(si，ch)=sj表示当前状态si下若遇到输入字符ch，则转移到状态sj；s0是唯一的初态(也称开始状态)；F是终态集(也称接受状态集)，它是S的子集，包含了所有的终态。第2章 词 法 分 析有限自动机是一个抽象的概念，可以用两种直观的方式状态转换图和状态转换矩阵来表示，这两种方式分别简称为转换图和转换矩阵。转换图是一个有向图，NFA中的每个状态对应转换图中的一个节点；NFA中的每个move函数对应转换图中的一条有向边，该有向边从si节点出发，进入sj节点，字符ch(或)是边上的标记。显然，NFA的初态是转换图中没有前驱的节点，而NFA的终态在转换图中用有别于其他节点的方法表示。例如，若节点用一个圆圈表示，则终态节点可以用一个加粗的圆圈或者双圈表示。转换矩阵是一个二维数组，其中每个元素Msi,sj中的内容是从状态si到状态sj的边上的标记ch(或)。在转换矩阵中，一般以矩阵第一行所对应的状态为初态，而终态需要特别指出。第2章 词 法 分 析例例2.7识别由正规式(a|b)*abb说明的记号的NFA定义如下：S=0,1,2,3,=a,b，s0=0,F=3move=move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,move(2,b)=3它的转换图和转换矩阵表示如图2.5所示。在转换矩阵中，需指出0是初态，3是终态。第2章 词 法 分 析图2.5识别(a|b)*abb的NFA(a)转换图表示的NFA；(b)转换矩阵表示的NFA第2章 词 法 分 析例例2.8识别表2.1中记号id、num和relation的转换图如图2.6所示。id和num依据的是例2.6中简化的正规式。不难看出，转换图识别的每一个记号实质上是从初态开始到某个终态的路径上的标记。例如，在识别relation的转换图中，从0开始到2的路径标记是“=”，表示在终态2处识别出一个关系运算符，语句return(relation,LE)表示此处可以返回记号的种类relation和关系运算符的值LE(小于等于号)。第2章 词 法 分 析图2.6状态转换图(a)relation的转换图；(b)id的转换图；(c)num的转换图第2章 词 法 分 析NFA的特点是它的不确定性，即在当前状态下，对同一个字符ch，可能有多于一个的下一状态转移。不确定性反映在NFA的定义中，就是move函数是一对多的；反映在转换图中，就是从一个节点可通过多于一条标记相同字符的边转移到不同的状态；反映在转换矩阵中，就是Msi,sj中不是一个单一状态，而是一个状态的集合。第2章 词 法 分 析用NFA识别输入序列的方法是：从NFA的初态开始，对于输入序列中的每一个字符，寻找它的下一状态转移，直到没有下一状态转移为止。若此时所处状态是终态，则从初态到终态路径上的所有标记，构成了一个识别出的记号。否则沿原路返回，并在返回的每一个节点试探可能的下一条路径，直到遇到第一个终态，或者一直返回到初态也没有遇到终态。对于输入序列，若试探了所有的路径也找不到下一状态转移或不能到达一个终态，则NFA不接受该序列，说明它不是语言中的合法记号。若到达一个终态，则NFA接受该序列，说明它是语言中的一个合法记号。第2章 词 法 分 析 例例2.9用例2.7中的NFA来识别输入序列abb和abab。识别过程如图2.7所示。对于abb的识别，有两条路径。第一条路径从状态0出发，经过字符a到达状态0，经过字符b到达状态0，再经过字符b到达状态0，此时输入序列已经结束，但是NFA没有到达终态，所以NFA不接受输入序列abb。但是，由于在状态0遇到字符a的下一状态还可以是1，因此沿原路回退到状态0。再试探另一路径：从状态0出发，经过字符a到达状态1，经过字符b到达状态2，最后经过字符b到达状态3。由于状态3是一个终态，所以，字符串abb被NFA接受，或者说被NFA识别。该过程被称为识别过程，其中的0123被称为识别路径，而标记该路径的字符串abb是NFA所识别的记号。再来看对abab的识别过程。从0状态出发遇到第一个字符a可以选择两条路径对abab进行识别，当选择了遇到第一个字符a沿路径000到达第二个字符a时，又可以选择两条路径。因此，NFA对abab的识别有图2.7(b)所示的三条路径可走。但是三条路径均不能到达终态，且再无路径可以试探,?所以NFA不接受输入序列abab,?也就是说，abab不是一个合法的记号。第2章 词 法 分 析图2.7NFA识别输入序列abb和abab(a)abb的识别过程；(b)abab的识别过程第2章 词 法 分 析从例2.9中可以看出，用NFA识别记号存在下述问题：(1)只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。(2)识别过程中需要进行大量的回溯，时间复杂度与输入序列成指数级增长，且算法复杂。造成这种情况的原因是NFA的不确定性，即在当前的状态下，遇到的下一个字符可能有多于一条的路径可走，而在当前状态下，这些路径中哪条路径可以到达终态或者全部路径均不能到达终态都是不可知的。第2章 词 法 分 析2.3.2 确定的有限自动机确定的有限自动机(Deterministic Finite Automata, DFA)定义2.5DFA是NFA的一个特例，其中：没有状态具有状态转移(-transition)，即状态转换图中没有标记的边；对每一个状态s和每一个字符a，最多有一个下一状态。第2章 词 法 分 析例例2.10识别由正规式(a|b)*abb说明的记号的DFA，其转换图和转换矩阵表示如图2.8所示。根据转换图，读者不难写出此DFA的定义。用它识别输入序列abb和abab的过程如图2.9所示。图2.8识别(a|b)*abb的DFA(a)转换图表示的DFA；(b)转换矩阵表示的DFA第2章 词 法 分 析图2.9DFA识别输入序列abb和abab第2章 词 法 分 析与NFA相比，DFA的特点就是它的确定性，即在当前状态下，对同一个字符ch，最多有一个下一状态转移。确定性反映在DFA的定义中，就是move函数是一对一的；反映在转换图中，就是从一个节点出发的任何不同的边上标记的字符均不同；反映在转换矩阵中，就是Msi,sj中是一个单一状态。由于在DFA上识别输入序列时，在任何一个当前状态下遇到任何输入字符，其下一状态转移均是唯一确定的，因此，无论是接受还是不接受，均经历一条确定的路径，而无其他任何路径可走。也就是说，在DFA上识别输入序列无需回溯，从而大大简化了记号的识别过程。第2章 词 法 分 析DFA识别输入序列的过程总结为算法2.1，被称为模拟器(模拟DFA的行为)，也被称为驱动器(用DFA的数据驱动分析动作)。模拟DFA算法的最大特点是方法与模式无关，它仅根据DFA的当前状态和状态转移进行一系列的动作，直到回答yes或者no。而所有与模式相关的信息均包含在DFA中。第2章 词 法 分 析算法算法2.1 模拟模拟DFA输入输入DFAD和输入字符串x。x由文件结束符eof终止，D的初态为s0，终态集为F。输出输出若D接受x，回答“yes”，否则回答“no”。方法方法用下述过程识别x：s:=s0；a:=nextchar；whileaeofloops:=move(s，a)；a:=nextchar;endloop；ifsisinFthenreturnyes；elsereturnno；endif；第2章 词 法 分 析2.3.3 有限自动机的等价有限自动机的等价NFA和DFA统称为有限自动机(FA)。所谓有限，是指自动机的状态数是有限的，因此，有些教材中也称为有限状态自动机。与正规式的等价相似，FA之间也存在等价问题。定义定义2.6若有限自动机M和M识别同一个正规集，则称M和M是等价的，记为M=M。第2章 词 法 分 析图2.5和图2.8所示的FA均识别以正规式(a|b)*abb所表示的正规集，两个FA是等价的。由于DFA上识别记号的确定性和简单性，往往希望用DFA而不是NFA来识别记号。很幸运，对于任何一个NFA，均可以找到一个与它等价的DFA。这一结果意味着，对任何正规集，均可以构造一个DFA去识别它。第2章 词 法 分 析2.4 从正规式到词法分析器从正规式到词法分析器DFA和模拟DFA的算法2.1，实际上已经构成了词法分析器的基础，从而得到构造词法分析器的一般方法与步骤:用正规式对模式进行描述；为每个正规式构造一个NFA，它识别正规式所表示的正规集；将构造出的NFA转换成等价的DFA，这一过程也被称为确定化；优化DFA，使其状态数最少，这一过程也被称为最小化；从优化后的DFA构造词法分析器。第2章 词 法 分 析2.4.1 从正规式到从正规式到NFA对任何的正规式，可以用下述的Thompson算法构造一个NFA，它识别正规式所表示的正规集。算法算法2.2 Thompson 算法算法 输入输入字母表上的正规式r。 输出输出接受L(r)的NFAN。第2章 词 法 分 析方法方法首先，将r分解成最基本的正规式。由于分解是构造的逆过程，因此分解从正规式的最右端开始。然后按如下规则进行构造。每次构造的新状态都需重新命名，以使得所有状态的名字均不同。对，构造NFA如图2.10(a)所示。其中，s0为初态，f为终态，该NFA接受；对上的每一个字符a，构造NFA如图2.10(b)所示。其中，s0为初态，f为终态，该NFA接受；第2章 词 法 分 析若N(p)和N(q)是正规式p和q的NFA，则：(a)对正规式p|q，构造NFA如图2.10(c)所示。其中，s0为初态，f为终态，该NFA接受L(p)L(q)；(b)对正规式pq，构造NFA如图2.10(d)所示。其中，s0为初态，f为终态，该NFA接受L(p)L(q)；(c)对正规式p*，构造NFA如图2.10(e)所示。其中，s0为初态，f为终态，该NFA接受L(p*)。对于正规式(p)，使用p本身的NFA，不再构造新的NFA第2章 词 法 分 析图2.10Thompson算法中NFA的构造第2章 词 法 分 析例2.11用Thompson算法构造正规式r=(a|b)*abb的N(r)。首先把正规式分解为如图2.11(a)所示的树结构，然后自下而上构造整个正规式的NFA，如图2.11(b)所示。具体步骤为：运用算法2.2方法中的分别为正规式r1=a、r2=b、r6=a、r8=b、r10=b构造NFAN(r1)、N(r2)、N(r6)、N(r8)、N(r10)，运用(a)为正规式r3=r1|r2构造N(r3)，运用得到N(r4)=N(r3)，运用(c)为正规式r5=r4*构造N(r5)，运用(b)分别为正规式r7=r5r6、r9=r7r8、r11=r9r10构造N(r7)、N(r9)、N(r11)。N(r11)是最终的NFA，其中0为初态，10为终态。第2章 词 法 分 析图2.11构造正规式(a|b)*abb的NFA(a)分解正规式；(b)构造NFA第2章 词 法 分 析2.4.2 从从NFA到到DFA 1NFA识别记号的识别记号的“并行并行”方法方法用NFA识别记号的过程，是在NFA上顺序地、一条路径一条路径试探的过程。由于需要进行回溯，所以算法构造复杂且工作效率低下。事实上，用NFA识别记号，并不采用这种“串行”的方法，而是采用一种“并行”的方法，从而可以消除识别时的不确定性，以避免回溯。第2章 词 法 分 析例2.12从甲地到乙地，可以乘小汽车也可以骑自行车，具体路线如图2.12所示，其中c表示乘车，b表示骑自行车。现在要求从甲地到乙地，只许乘车而不许骑自行车，该如何走？此问题抽象在图2.12上，就是如何找到一条从甲地到乙地的路径，上边的标记均由c组成。首先，按照常规一条路径一条路径地试探：甲c2无路可走，退回甲c1c3 无路可走，退回甲c1c乙到达乙地，成功第2章 词 法 分 析图2.12甲地到乙地的所有路径第2章 词 法 分 析为了避免回溯，设想有足够多的小汽车同时走若干条路。假设从甲地出发，第一站可以到达乘车所能到达地点的全体，再从第一站出发，第二站可以到达乘车所能到达地点的全体，依此类推，直到某一站中包含了乙地。按照这样的方法，从甲地到乙地的过程与路径如下所示：甲c1,2c3,乙到达乙地，成功第2章 词 法 分 析从识别由c组成的路径标记的角度看，两种方法的效果是一样的，但是第二种方法仅有一条确定的路径，所付出的代价是需要有足够的小汽车。第二种方法的基本思想是将不确定的下一状态确定化：如果从当前状态出发经c可能到达不止一个状态，则将所有这些状态组成一个集合，而虚拟地认为到达这一状态集。显然从当前状态出发经c到达这一状态集的路径是唯一确定的。第2章 词 法 分 析将这种确定化的思想应用于例2.12中特定交通工具的任何一种组合方式，从甲地出发的一条路径或者达到乙地，或者不能到达乙地，均是确定的，无需也再无其他路径可以试探。例如，若要求从甲地到乙地，先乘车，再骑自行车，然后再乘车，即在图2.12上找到一条标记为cbc的路径。则用这种确定化的方法可以找到这样一条路径：甲c1,2b3。由于在3处没有通过乘车可以到达乙地的路径，可以断定上述要求无法从甲地到达乙地。第2章 词 法 分 析将确定化的思想用于NFA上记号的识别，可得到下述与算法2.1相似的模拟NFA的算法2.3。该算法中利用了两个函数smove(S,a)和_闭包(T)来计算下一状态集。S和T分别表示状态的集合，a是一个非字符。与算法2.1中的状态转移函数move(s,a)比较，smove(S,a)将状态扩大到了状态集，它表示从当前状态集S中的任何状态s出发，经字符a可直接到达状态的全体。即move针对的是状态，而smove针对的是状态集。_闭包(T)表示从状态集T出发，经所能到达状态的全体，更精确的定义在算法2.3之后给出。第2章 词 法 分 析算法2.3模拟NFA输入NFAN和输入字符串x。x由文件结束符eof终止，N的初态为s0，终态集为F输出若N接受x，回答“yes”，否则回答“no”方法用下边的过程对x进行识别。S是一个状态的集合。S:=_闭包(s0);-所有可能初态的集合a:=nextchar;whileaeofloopS:=_闭包(smove(S，a)；-所有下一状态的集合a:=nextchar;endloop;ifSFthenreturnyes;elsereturnno;endif;第2章 词 法 分 析表表2.7 算法算法2.1与算法与算法2.3的区别的区别 DFA(算法2.1)NFA(算法2.3)区别初态初态集从初态s0出发改变为从初态集出发下一状态下一状态集当前状态对字符a的下一状态改变为下一状态集sisinFSF判断输入序列被接受的条件由最后一个状态是否是终态集中的一个状态，改变为最后一个状态集与终态集的交集是否为空集第2章 词 法 分 析定义2.7状态集T的_闭包(T)是一个状态集，且满足：T中所有状态属于_闭包(T)；任何smove(_闭包(T)，)属于_闭包(T)；再无其他状态属于_闭包(T)。第2章 词 法 分 析有关定义2.7中的三个条件的说明如下：状态集T自身在闭包中；若某状态已在闭包中，则从此状态出发的任何经状态转移所到达的下一状态也在闭包中。由此可知，_闭包(T)就是从状态集T出发，经所能达到的状态的全体。根据_闭包的定义，不难得到计算_闭包的算法。由于_闭包是递归定义的，而反映递归的最佳数据结构是栈，所以算法中用一个栈来存放所有可能需要计算状态转移的状态。第2章 词 法 分 析算法2.4求_闭包输入状态集T输出状态集T的_闭包方法用下面的函数计算_闭包function_闭包(T)isbeginforT中每个状态tloop加入t到U;push(t);endloop;while栈不空looppop(t);for每个u=move(t,)loopifu不在U中then加入u到U;push(u);endif;endloop;endloop;returnU;end_闭包;第2章 词 法 分 析例2.13用算法2.3在图2.11(b)所示的NFA上识别记号abb和abab的过程分别如下。识别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。第2章 词 法 分 析输入序列已经结束，且D10=10，abb被接受。故abb的识别路径为：AaBbCbD。识别abab:_闭包(s0)=0,1,2,4,7A_闭包(smove(0,1,2,4,7,a)=3,8,6,7,1,2,4B_闭包(smove(3,8,6,7,1,2,4,b)=5,9,6,7,1,2,4C_闭包(smove(5,9,6,7,1,2,4,a)=3,8,6,7,1,2,4B_闭包(smove(3,8,6,7,1,2,4,b)=5,9,6,7,1,2,4C故abab的识别路径为：AaBbCaBbC。由于C10=，所以序列abab不被接受。第2章 词 法 分 析 2“子集法子集法”构造构造DFA虽然用算法2.3在NFA上识别输入序列的过程也是确定的，无需回溯，但是，它付出的代价是每走一步就要计算一次下一状态转移的集合。该计算分两步走：首先计算当前状态集的smove函数，得到一个集合，然后计算此集合的_闭包。_闭包的计算是递归的，需耗费大量时间，使得用NFA识别输入序列的效率很低。事实上，算法2.3的每次识别都是将一条路径确定化。延伸这一观点，预先将NFA上的全部路径均确定化，并且把它们记录下来，形成一个与NFA等价的DFA。而对记号的识别在DFA上进行，从而省去计算状态集的时间，以提高识别效率。第2章 词 法 分 析例2.14将图2.12中的所有路径确定化得到图2.13。图2.13中从甲地到乙地允许的合法走法为cc，ccb和cbb三条路径，与图2.12中的合法路径完全相同，所以二者是等价的。用图2.13分别识别cc和cbc的过程为：甲c1,2c3,乙，接受甲c1,2b3c?，不接受与用图2.12识别的结果完全相同。第2章 词 法 分 析图2.13确定化后的甲地到乙地的所有路径第2章 词 法 分 析将所有路径确定化以构造DFA的算法被归纳在算法2.5中。由于新构造的DFA中的每个状态是原NFA所有状态的一个子集，所以也将此算法称为构造DFA的“子集法”。算法中用Dstates存放DFA的状态，Dstates中每个状态是NFA全体状态的一个子集；smove(T,a)与算法2.3中的smove(S,a)意义相同；Dtran是一个状态转换矩阵，用它存放DFA的状态转移，即若_闭包(smove(T,a)=U，则DtranT，a中存放U。值得注意的是，由于DFA的一个状态是NFA全体状态的一个子集，所以在最坏情况下，有n个状态的NFA，其等价DFA的状态数可能是O(2n)级的。当遇到这种特殊情况且n很大时，往往不将NFA确定化为DFA，而是直接利用NFA和算法2.3对输入序列进行分析，也就是每分析一次，仅确定一条路径，从而减少了对存储空间的需求。第2章 词 法 分 析算法2.5从NFA构造DFA(子集法)输入一个NFAN输出一个接受同一正规集的DFAD。其中，含有NFA初态的DFA状态为DFA的初态，所有含有NFA终态的DFA状态构成DFA的终态集。方法用下述过程构造DFA：_闭包(s0)是Dstates仅有的状态，且尚未标记;whileDstates有尚未标记的状态Tloop标记T;第2章 词 法 分 析for每一个输入字符aloopU:=_闭包(smove(T，a);ifU不在Dstates中thenU作为尚未标记的状态加入Dstates;endif;DtranT，a:=U;endloop;endloop;第2章 词 法 分 析例2.15将算法2.5应用于图2.11(b)所示的NFA上，计算步骤如下所示。其中标有*的集合是第一次出现，在算法中需要被标记并处理。所得的DFA如图2.14所示，其中A是初态，E是终态集中仅有的终态。图图2.14 识别识别(a|b)*abb的的DFA(a) 转换图表示的转换图表示的DFA；(b) 转换矩阵表示的转换矩阵表示的DFA 第2章 词 法 分 析_闭包(0)=0,1,2,4,7*A_闭包(smove(0,1,2,4,7, a)=3,8,6,7,1,2,4*B_闭包(smove(0,1,2,4,7,b)=5,6,7,1,2,4*C_闭包(smove(3,8,6,7,1,2,4,a)=3,8,6,7,1,2,4B_闭包(smove(3,8,6,7,1,2,4,b)=5,9,6,7,1,2,4*D_闭包(smove(5,6,7,1,2,4,a)=3,8,6,7,1,2,4B_闭包(smove(5,6,7,1,2,4,b)=5,6,7,1,2,4C_闭包(smove(5,9,6,7,1,2,4,a)=3,8,6,7,1,2,4 B_闭包(smove(5,9,6,7,1,2,4,b)=5,10,6,7,1,2,4*E_闭包(smove(5,10,6,7,1,2,4,a)=3,8,6,7,1,2,4B_闭包(smove(5,10,6,7,1,2,4,b)=5,6,7,1,2,4C第2章 词 法 分 析例2.16在图2.14的DFA上识别输入序列abb和abab，其结果与在NFA上识别的结果完全相同。步骤如下：识别abb:AaBbDbE接受识别abab:AaBbDaBbD不接受第2章 词 法 分 析2.4.3 最小化最小化DFA比较图2.8和图2.14所示的DFA，它们接受相同的正规集，说明两个DFA是等价的，但是它们的状态数不同。一般来说，对于若干个等价的DFA，总是希望由状态数最少的DFA构造词法分析器。将一个DFA等价变换为另一个状态数最少的DFA的过程被称为最小化DFA，相应DFA称为最小DFA。第2章 词 法 分 析定义2.8对于任何两个状态t和s，若从一状态出发接受输入字符串，而从另一状态出发不接受，或者从t出发和从s出发到达不同的接受状态，则称对状态t和s是可区分的。反方向思考定义2.8，设想任何输入序列对s和t均是不可区分的，则说明分别从s出发和从t出发来分析任何输入序列，均得到相同结果。因此，s和t可以合并成一个状态。算法2.6用来最小化DFA的状态数，它的基本思想就是反向利用可区分的概念。一开始，仅有非终态和各终态是可区分的，经过一系列划分，把可区分的状态分离出来，直到不可再分离为止。根据可区分的概念可知，所有不可区分的状态可以合并成一个状态。第2章 词 法 分 析算法2.6最小化DFA的状态数输入一个DFAD=S，move，s0，F输出一个DFAD=S，move，s0，F，它和D接受同样的正规集，但是状态数最少方法构造状态集的初始划分=S-F，F1，F2，.，其中F1，F2，均是F的子集，它们接受不同的记号；第2章 词 法 分 析应用下述过程构造新的划分new：for的每一个组Gloop对G进行划分，G中的两个状态s和t被划分在同一个组中的充要条件是:任何输入字符a，move(s,a)和move(t,a)在的同一个组中；用新划分的组替代G，形成新的划分new；endloop；第2章 词 法 分 析若new=，令final=，并转向步骤；否则，令=new并重复步骤；在final的每个组Gi中选一个代表si，使得D中从Gi中所有状态出发的状态转移在D中均从si出发，D中所有转向Gi中状态的状态转移在D中均转向si；含有D中s0的状态组G0的代表s0称为D的初态，D中所有含F中状态的Gj的代表sj构成D的终态集F；若D中有状态d，它不是终态且对于所有输入字符均转向其自身，则称d为死状态；将d从D中删除，同时也删除所有从初态不可到达的状态，从其它状态到d的任何状态转移被认为无意义。第2章 词 法 分 析例2.17用算法2.6对图2.14中的DFA进行状态化简:初始化划分=A，B，C，D，E。考察当前划分。E自身一个组，不能再分，ABCD在一个组，查看它们的状态转移：move(A,a)=B,move(A,b)=Cmove(B,a)=B,move(B,b)=Dmove(C,a)=B,move(C,b)=Cmove(D,a)=B,move(D,b)=E第2章 词 法 分 析其中move(D,b)=E使得D与ABC不能在同一组中，分离D形成新的划分:new=A，B，C，D，Enew，令=new，重复。考察当前划分。ABC在一个组，查看它们的状态转移：move(A,a)=B,move(A,b)=Cmove(B,a)=B,move(B,b)=Dmove(C,a)=B,move(C,b)=C其中move(B,b)=D使得B与AC不能在同一组中，分离B形成新的划分:new=A，C，B，D，E第2章 词 法 分 析new，令=new，重复。考察当前划分。AC在一个组，查看它们的状态转移：move(A,a)=B,move(A,b)=Cmove(C,a)=B,move(C,b)=C显然A和C是不可区分的，使得new=A，C，B，D，E第2章 词 法 分 析=new，令final=，转向。在final的每个组中选一个代表，用A代表A，C，其余均自己代表自己，最后形成仅有4个状态的最小DFAD；如果将状态A、B、D、E分别编号为0、1、2、3，则D如图2.8所示。第2章 词 法 分 析2.4.4 由由DFA构造词法分析器构造词法分析器 1表驱动型词法分析器表驱动型词法分析器如果将DFA用状态转换矩阵表示，则它与模拟DFA的算法(算法2.1)构成了一个表驱动型的词法分析器，其中转换矩阵是分析器的分析表，而算法2.1就是分析器的驱动器。表驱动型词法分析器的一般工作模式如图2.15所示，它实际上就是有限自动机的工作模型。第2章 词 法 分 析图2.15表驱动型词法分析器第2章 词 法 分 析算法2.1是一个简化了的概念模式，实际的驱动器需要根据情况进行修改。最大的修改是关于输入序列。算法2.1假设仅识别以eof结束的一个记号，而实际的源程序是由许多记号组成的记号流。例如result:=expr就是由标识符、赋值号、标识符三个记号组成的。对于驱动器来说，判定是否识别出一个记号的条件不应是遇到eof，而是一个更合理的方法。一般采用的方法是所谓的最长匹配原则，即对于任何输入序列，总是尽量匹配，直到没有下一状态转移为止。例如，abbabb被识别为一个而不是两个记号，而abbab不被接受。使用最长匹配原则，对上述result:=expr的第一个标识符的匹配一直要遇到冒号时才会因找不到下一状态转移而识别出一个属性为result的标识符，不应误识别出r、re、或res等。第2章 词 法 分 析 2直接编码型词法分析器直接编码型词法分析器另一类词法分析器无需分析表指导分析动作，而直接将DFA转换为程序，即直接用程序代码模拟DFA的行为。将DFA用直观的状态转换图表示，它实质上就是一个抽象的程序流图。转换图忽略了程序的实现细节，着力刻划了记号识别的本质。转换图与程序结构之间存在下述对应关系，并可据此构造相应的程序：初态对应程序的开始；终态对应程序的结束，一般是一条返回语句，且不同的终态对应不同的返回语句；状态转移对应分情况或者条件语句；转换图中的环对应程序中的循环语句；终态返回时，应满足最长匹配原则。第2章 词 法 分 析例2.18根据上述转换图与程序结构的简单对应关系，可以将图2.8所示的DFA转换为下述示意性的词法分析器。其中的标号s0、s1、s2、s3分别表示语句与状态的对应，除了s0和s1之外，其余的标号均无实际意义。beginch:=getchar；s0:loopwhilech=bloopch:=getchar；endloop；s1:whilech=aloopch:=getchar；endloop；casechis第2章 词 法 分 析a:null;s2:b:ch:=getchar；casechisa:gotos1;s3:b:ch:=getchar;casechisa:gotos1;b:gotos0;eof:return(yes)；第2章 词 法 分 析others:return(no);endcase;others:return(no)；endcase；others:return(no)；endcase；endloop；end；第2章 词 法 分 析 3两类分析器的比较两类分析器的比较直接编码词法分析器和表驱动词法分析器的工作原理完全相同，它们的基本依据都是DFA。但是，二者在与模式的关系、分析器的构造以及分析器的分析效率诸方面均有很大差别。从分析器与模式之间的关系讲，表驱动型分析器的驱动器仅对分析表的内容进行操作，而与所识别的记号无关，具体识别什么记号，由分析表中与模式密切相关的数据来控制，是一种典型的数据与操作分离的工作模式，构造不同的词法分析器实质上成为构造不同的分析表。而直接编码型的词法分析器，是通过程序的控制流转移来完成对输入字符串的响应，可以说程序的每一条语句都与模式密切相关，一旦模式改变，则程序必须改变。第2章 词 法 分 析从分析器的构造方法讲，表驱动型词法分析器的数据与操作分离的模式，为词法分析器的自动生成提供了极大的方便。因为，从正规式到DFA的转换矩阵表示，均可以通过成熟的算法由计算机来自动完成。而对于直接编码的词法分析器，需要将状态转换图变为程序代码，即便有一般的对应关系，但转换图的复杂性和程序代码的多样性均使得这一过程并不容易。从例2.18可以看出，即使处理这样一个简单的模式，其程序设计也并不简单，更何况构造分析多个复杂模式的分析器了。一般来讲，直接编码型的词法分析器适用于词法比较简单的情况，并且也无需教条地按照正规式、NFA、DFA、程序代码的步骤去构造，而是直接由正规式手工构造状态转换图，然后翻译为程序代码，或者干脆直接根据正规式编写程序代码。第2章 词 法 分 析从分析器的工作效率讲，表驱动词法分析器在工作中需要查表确定分析器的动作，每一步分析多了至少一次间接访问的工作，在分析输入序列的效率上比直接编码分析器的效率要低。但是随着计算机技术的发展，软件的损失已被硬件速度的提高弥补。归纳起来，两类分析器的特点如表2.8所示。第2章 词 法 分 析表表2.8 两类分析器的比较两类分析器的比较 分析器速度程序与模式的关系分析器的规模适合的编写方法表驱动慢无关较大工具生成直接编码快相关较小手工编写第2章 词 法 分 析2.4.5 词法分析器生成器简介词法分析器生成器简介回顾词法分析器的构造过程：正规式NFADFA最小化DFA词法分析器(分析表)，每一步都可以借助于成熟的算法来构造，无需人工干预。词法分析器生成器，就是将这些算法组合起来所形成的软件，利用这样的软件，只需将所需的词法分析器识别的记号用正规式的方式描述出来，生成器就会自动生成相应的词法分析器。当前最成熟、最被广泛应用的词法分析器生成器是LEX和与LEX相似的工具，不妨统称为LEX。第2章 词 法 分 析例2.19例2.6中关于id和num的说明，可以用LEX的形式表示如下，其中的辅助定义和规则以LEX提供的形式书写，而语义动作也仅是示意性的。需要指出，此处是重载的，它既可以用来标记对辅助定义名字的引用，如char、digit等，也可以用来界定用户书写的相关语义动作，如 printf(id: %s,yytext);return(ID);等。%#include%chara-zA-Z第2章 词 法 分 析digit0-9digitsdigit+optional_fraction(.digits)?optional_exponent(E(+|)?digits)?%char(char|digit)*printf(id:%s,yytext);return(ID);digitsoptional_fractionoptional_exponentprintf(number:%s,yytext);return(NUM);第2章 词 法 分 析利用LEX设计词法分析器，关键需要了解和掌握两点：LEX提供什么形式的正规式集，如何运用正规式集设计记号的模式；LEX提供什么样的机制支持语义动作的嵌入，如何运用这些机制收集识别出的记号信息，并合理地返回它们或者过滤掉它们(如果不需要的话)。归纳起来，就是如何用LEX语言进行程序设计，从而将词法分析器的构造简化为进行正规式和必须的语义动作的设计；而对分析器的任何修改，也简化为对正规式和相关语义动作的修改。当然，这样的程序设计是建立在充分了解词法分析器构造原理和LEX语言基础之上的。第2章 词 法 分 析2.5 本本 章章 小小 结结 词法分析器是编译器与源程序打交道的唯一阶段，可以被认为是编译器的预处理阶段，它有以下几个重要作用：滤掉源程序中的无用成分、处理与具体操作系统或机器有关的输入、识别单词并交给语法分析器、调用符号表管理器和出错处理器进行相关处理。对于单词的识别，首先应该有单词形成的规则，称为构词规则，然后根据构词规则识别输入序列，称为词法分析。本章涉及的基本概念包括：构词规则、模式、记号、单词、状态转换图、状态转换矩阵(分析表)、正规式、正规集、NFA、确定化、DFA、_闭包、子集法、最小化DFA、可区分等。通过对本章的学习能够掌握下述主要内容：第2章 词 法 分 析1记号、模式与单词记号、模式与单词模式(pattern)：规定记号识别的规则；记号(token)：按照某个模式(规则)识别出的一类单词；单词(lexeme)：被识别出的字符串本身。第2章 词 法 分 析 2记号的说明记号的说明模式的形式化描述模式的形式化描述正规式与正规集：正规式与正规集的表示方法，正规式与正规集的定义，正规式的等价问题以及利用正规式的等价对正规式进行化简；用正规式对模式进行形式化描述：从单词一级看程序设计语言，它是一个正规集；如何用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等；正规式的简化形式以及辅助定义与规则。第2章 词 法 分 析 3记号的识别记号的识别有限自动机有限自动机NFA与DFA的定义：M=(S,move,s0,F)；NFA与DFA的表示：定义、状态转换图、状态转换矩阵；NFA与DFA的关键区别：NFA的不确定性；用NFA识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收，以及回溯带来的问题；模拟DFA的算法(用DFA识别记号)。第2章 词 法 分 析 4从正规式到词法分析器从正规式到词法分析器构造NFA的Thompson算法；模拟NFA的“并行”算法；从NFA构造DFA：构造DFA的子集法，smove(S,a)函数和_闭包(T)的计算；DFA的最小化：利用可区分的概念，将所有不可区分的状态看作是一个状态；两种类型的词法分析器：表驱动型与直接编码型；它们各自的特点；词法分析器生成工具LEX：LEX的工作原理，使用LEX的基本方法。