编译原理课件第2章.ppt

《编译原理课件第2章.ppt》由会员分享，可在线阅读，更多相关《编译原理课件第2章.ppt（123页珍藏版）》请在三一文库上搜索。

1、第2章 词 法 分 析,2.1 词法分析中的若干问题 2.2 模式的形式化描述 2.3 记号的识别有限自动机 2.4 从正规式到词法分析器 2.5 本章小结,2.1 词法分析中的若干问题,2.1.1 记号、模式与单词 自然语言中的句子通常由一个个单词和标点符号组成，可以根据其在句子中的作用，将它们划分为动词、名词、形容词、标点符号等不同的种类。程序设计语言与此相类似，组成语句的基本单元也可根据其在句子中的作用分类。最基本分类有四类： (1) 关键字(保留字)：这类单词在程序设计语言中有固定的意义，如begin、end、while等。若在程序设计语言中不允许用它们再表示其他的意思，则这类单词也被

2、称为保留字。,(2) 标识符：标识符是程序设计语言中最大的一个类别，它的作用是为某个实体起一个名字，以便于今后称呼(引用)，如draw_line、 sort等。可以用标识符来命名的实体包括类型、变量、过程、常量、类、对象、程序包、标号等，即类型名、变量名、过程名、常量名等。,(3) 字面量：字面量是指直接以其字面所表示的常量，如25、true、“This is a string“等。值得注意的是，字面量与常量是两个不同的概念，常量可以是一个字面量(直接表示)，也可以是一个常量名(命名表示)。例如可以在Pascal中声明：const max_length = 25，显然25是一个常量，max_l

3、ength也是一个常量，我们称25为字面量，而不称max_length为字面量。根据字面量的内容，可以将它们再进行更细的划分，如常数字面量(包括整型字面量、实型字面量、枚举字面量等)、字符串字面量等。,(4) 特殊符号：程序设计语言中的特殊符号，类似于自然语言中的标点符号，每个符号在程序设计语言中均有特殊用途。可以根据它们的用途，再细分为算符(如+、*、/等)、分隔符(如；、”、“等)。 显然，一个单词究竟是标识符、关键字，还是特殊符号，需要根据一定的构词规则来产生和识别。我们将产生和识别单词的规则称为模式(patten)，按照某个模式(规则)识别出的元素称为记号(token)，而单词(lex

4、eme)一词是指被识别出元素自身的值。,例2.1 对于语句：position := initial + rate * 60，可以识别出下述序列： 标识符 特殊符号 标识符 特殊符号 标识符 特殊符号 数字字面量 其中position、initial、rate均被识别为标识符，因为它们均符合同一条规则，即以字母打头的字母数字串。记号至少含有两个信息：一个是记号的类别，如“标识符”；另一个是记号的值，如“position”。显然，如果把记号看作是一个类型的话，则单词就是一个类型中的实例。由于我们总是说识别出一个标识符，而不说识别出一个position或rate，因而将词法分析器识别出的序列称为记号

5、流。,记号的类别、模式以及单词三者之间的关系可以用表2.1加以说明。其中，const和if分别是被细分的关键字，它们的特点是一个记号类别仅对应一个单词；relation表示关系运算符；id表示标识符；num表示数字字面量；literal表示字符串字面量；comment表示注释，它们的特点是一个记号类别可以对应若干个单词。由于语法分析及其后的阶段并不对注释进行分析，因而可在词法分析阶段中滤掉注释，即词法分析器可以不向语法分析器返回comment。而其他的记号，均是源程序中的有效成分，需要返回给语法分析器。,表2.1 记号、模式与单词,2.1.2 记号的属性 从例2.1中已经知道，记号至少包含两个

6、部分：记号类别和记号的其他信息。可以看出，记号的类别唯一标识一类记号，例如所有的关系运算符均可以由relation来标识，而所有字符串字面量均可以由literal来标识。所以，记号的类别可以被认为是记号的名字或记号的代表，在不引起混淆的情况下，将记号的类别简称为记号。记号的其他信息被称为记号的属性。例如，num可以取值3.1416，则称3.1416是num的属性，而literal可以取值“core dumped”(不含引号)，则称“core dumped”是literal的属性。由此可见，记号的类别标识一类记号，而记号的类别加属性标识一个记号实例。,在计算机内部，可以有不同的方式来表示记号的类

7、别和属性。一般情况下，记号的类别可以用整型编码或枚举类型表示，如表2.1中每个记号类别可以用括号中的整型编码表示，如01表示const，82表示id等。根据记号类别的不同，记号的属性的值可以有不同的表示方法。relation的属性值是一个有限可枚举集合，可以用每个属性值在集合中的位置来表示它，如1表示，2表示=，依此类推。id的属性值是一个无限可枚举集合，因此，只能用每个标识符的原始输入形式(字符串)来表示，如pi、draw_line等。字面量的属性根据情况，其表示方式也不同，如数字字面量可由转义后的实际值表示，如表示为3.1416而不是“3.1416”，而字符串字面量就无需转义。,例2.2

8、表达式mycount 25由表2.2的三个记号组成。其中标识符的属性值也可以由mycount在符号表中的入口(下标)来表示。,表2.2 记号的表示,2.1.3 词法分析器的作用与工作方式 词法分析器是编译器中唯一与源程序打交道的部分，从某种意义说，也可以被认为是整个编译器的预处理器。它的主要工作包括： (1) 滤掉源程序中的无用成分，如注释、空格、回车等。例如，表2.1中记号的种类除了comment之外，均有一个编码，表示需要递交给语法分析器进行后继的处理，而comment没有对应编码，表示注释成分可以过滤掉，不需要递交，因为语法分析及其之后的各个阶段已经不再需要它们。,(2) 处理与具体平台

9、有关的输入。不同的操作系统或相关软件构成的平台，对某些特殊符号(如文件结束符等)可能有不同表示，因此需要在词法分析阶段分情况处理。 (3) 识别记号，并交给语法分析器。这是词法分析器的主要任务，本章将在各节中详细讨论。,(4) 调用符号表管理器或出错处理器，进行相关处理。词法错误是源程序中常见的错误，如出现非法字符、拼错关键字、多或少字符等。值得注意的是，词法错误往往不是由词法分析器检查出来的，而是由语法分析器发现的。这是因为，源程序中除了非法字符之外的大部分字符或字符串，都可以被词法分析器的某个模式所匹配，从而被识别成一个记号。而这些记号的正确与否，在没有上下文对照的情况下，是很难判断的。例

10、如，12x被认为是一个非法的Pascal的标识符，但是，由于12可以被识别整型数的模式匹配，而x可以被识别标识符的模式匹配，因而词法分析器会分别识别出一个整型数和一个标识符，而不是报告一个错误。,根据编译器的总体需求，词法分析器在整个编译器中可以有不同的工作方式。 (1) 词法分析器作为语法分析器的子程序。最常采用，也最容易实现的工作方式是将词法分析器作为语法分析器的子程序，每当语法分析器需要一个记号时，就调用词法分析器，并得到一个识别出的记号。其工作方式如图2.1所示。 (2) 词法分析器进行单独的一遍扫描。另一种常用的工作方式，是安排词法分析器进行单独的一遍扫描，它以源程序为输入，输出是以

11、记号流形式表示的源程序。其工作方式如图2.2所示。,图2.1 作为子程序的词法分析器,图2.2 词法分析器进行单独一遍扫描,(3) 与语法分析器并行工作的模式。上述两种词法分析器的工作模式与语法分析器的关系均被认为是串行的。为了提高编译器的效率，可以通过一个队列，使词法分析器和语法分析器以生产/消费的形式并行工作。词法分析器将识别出的记号流输出到队列中，语法分析器从队列中取得记号，只要队列中有识别出的记号，则词法分析器和语法分析器就可以同时工作。其工作方式如图2.3所示。,图2.3 并行工作模式,2.1.4 输入缓冲区 词法分析器是编译器中读入源程序字符序列的唯一阶段，而相当可观的编译时间又消

12、耗在词法分析阶段，所以，加快词法分析是设计编译器时要考虑的重要问题之一。可以通过设立输入缓冲区来加快读入源程序字符序列的速度。 如果使用词法分析器生成器编写词法分析器，则生成器会提供读入和缓冲输入序列的例程；如采用通用程序设计语言编写词法分析器，就需要显式地管理源程序的读取。,输入缓冲区一般被设计为一块与磁盘扇区大小成倍数关系的内存。若一个扇区为1024字节，则输入缓冲区可以取1024、4096或8192字节等。这样可以保证对缓冲区的一次输入所需的I/O操作次数尽可能少。 输入缓冲区的安排一般采用单缓冲区或双缓冲区(缓冲区对)的方式。下边所介绍的是单缓冲区方式，它也是词法分析器生成器FLEX所

13、采用的方式。,图2.4是一个单缓冲区的示意图。有效输入序列从缓冲区的起始位置开始存放，最后添加一个特殊标记(此处用#表示)：若缓冲区一次装不下整个源程序，它就表示缓冲区的结束，否则它紧跟在文件结束符(eof)之后，表示整个输入源程序的结束。用两个指针c_ptr和f_ptr分别指向当前被识别记号的第一个字符和向前扫描的字符。最初，两个指针同时指向下一个被识别记号的第一个字符，f_ptr向前扫描，直到某个模式匹配成功。一旦这个记号被确定，f_ptr指向被识别出记号的右端字符，在此记号被处理后，两个指针都移向该记号之后的下一个字符。在f_ptr向前扫描的过程中，如果遇到文件结束标志，则表示输入序列已

14、被处理完。如果遇到特殊标记#，说明缓冲区中的内容需要更新。这时，首先将c_ptr到f_ptr所指的内容(不包括特殊标记)移到缓冲区的起始位置，然后将新的内容读进缓冲区，最后加上特殊标记。具体算法如下：,c_ptr f_ptr,图2.4 单缓冲区,procedure get_next_buffer(buffer，start，length) is - start和length是需仍保留在缓冲区中字符串的起始位置和长度 begin if length=buffer_size - buffer_size是缓冲区实际容量 then return error； else for i in lowlow+l

15、ength1 - low是缓冲区下界，假设从0开始 loop buffer(i) := buffer(start+ilow)； - 把剩余的输入移到缓冲区头部 end loop；,num_to_read := buffer_sizelength； if number_to_readblock_size - block_size应是磁盘扇区的整数倍 then number_to_read := block_size; end if ; read_buffer(buffer，length+low，num_to_read)； end if； end get_next_buffer；,假设被扫描的输入

16、序列的最大长度不超过max_length，则可以选择buffer_size = block_size + max_length，即缓冲区的大小是磁盘扇区大小的整数倍加上一个最长可能被扫描的输入序列。这种缓冲技术能胜任大多数情况，但在向前被扫描字符个数超过缓冲区长度的极端情况下会失效。早期的程序设计语言通常采用开括号与闭括号的方式标识注释，如表2.1中的comment，如果程序员不小心忘记书写闭括号，而词法分析器的设计又将comment作为一个完整的记号识别，就会出现被扫描字符个数超过缓冲区长度的情况。因此，后来设计的程序设计语言大多采用仅有开括号，而默认换行标志为闭括号的注释方式，如上述算法中

17、的“-”( Ada的注释方式)或者C+中的“/”，从根本上杜绝了这种极端情况。,2.2 模式的形式化描述,2.2.1 字符串与语言 从词法分析的角度看，程序设计语言是由记号组成的集合，每个记号又是由若干字母按照一定规则组成的字符串。为了讨论的简单性和准确性，本章对常用的术语以定义的方式给出。有一点需要强调，编译领域的很多名词术语的使用并不统一，因此希望读者掌握“是什么”，而不是“叫什么”。 在下述的讨论中，我们首先定义一个泛泛的“语言”，然后在此基础上规定一个正规集，而程序设计语言就是一个正规集。,定义2.1 语言L是有限字母表上有限长度字符串的集合。 定义2.1明确指出，语言是一个集合，集合

18、中的元素是字符串，并且强调了两个有限: 字母表是有限的，即字母表中元素是有限多个； 字符串的长度是有限的，即字符串中字符个数是有限多个。 这是由于计算机所能表示的字符个数和字符串的长度都是有限的。,由于字符串的有序性，使得以字符串作为元素的集合具有某些特性。字符串和集合的基本概念和特性，以表格的形式分别列在表2.3和表2.4中。其中，字符串的连接运算是一种新形式的运算，它表示两个字符串首尾相接，形成一个新的集合。例如，S1=“pre“，S2=“fix“， 则S1S2=“prefix“。值得注意的是，集合中连接运算所形成的新集合与交运算形成的新集合完全不同。例如，若L=“pre“，M=“fix“

19、，则LM=，而LM=“prefix“。,表2.3 字符串的基本概念,表2.4 字符串集合上的基本运算,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中和规

20、定了正规式的基本操作数或基本正规式。定义2.2的给出了正规式上的三种运算: (a)或运算、(b)连接运算和(c)闭包运算。对于由多个操作数和多个操作符组成的正规式，可以利用(d)所给的括号规定运算的先后次序。如果对或、连接和闭包运算进行如下约定: 三种运算均具有左结合性质； 运算的优先级从高到低顺序排列为: 闭包运算、连接运算、或运算。 则正规式中不必要的括号可以被省略。例如，(a)|(b)*(c)可以简化成a|b*c。,例2.3 设字母表=a，b，c，部分上的正规式和正规式所表示的正规集如表2.5所示。,表2.5 正规式与它表示的正规集,正规集是一个集合，而正规式是表示正规集的一种方法。正如

21、不同算术表达式可以表示同一个数(如3+5、5+3、2+6等均表示8)一样，不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。 例2.4 令 L(x)=a，b，L(y)=c，d，则 L(x|y)=a，b，c，d L(y|x)=a，b，c，d x|y和y|x表示同一个正规集。,定义2.3 若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。 正规式之间的一些恒等运算，被称为正规式的代数性质。表2.6给出了正规式的若干代数性质。利用这些性质，可以对复杂的正规式进行化简，使得可以用最简单形式的正规式表示一个集合。而简单的正规式意味着其所对应的识别器的构造也是简单的。,

22、表2.6 正规式的代数性质,2.2.3 记号的说明 表2.1中用自然语言对模式进行了非形式化的描述，例如标识符模式的非形式化描述是“以字母打头的字母数字串”。这一描述很不精确，存在一些问题，如哪些符号是字母，哪些符号是数字，字母数字串的长度可以是多少等等。 由于正规式是严格的数学表达式，采用正规式来描述模式，解决了精确描述模式的问题。另外，从词法分析器的角度上看程序设计语言，用正规式说明的记号是一个正规集。 用正规式说明记号的公式为：记号 = 正规式，可以读作为“(左边)记号定义为(右边)正规式”，或者“记号是正规式”。通常，在不引起混淆的情况下，也把说明记号的公式简称为正规式，或者规则。,例

23、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

24、|Y|Z|0|1|2|3|4|5|6|7|8|9)*,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个或若干个字母或数字的字符串”。,1简化正规式描述 为了简化正规式的描述，通常

25、可以采用如下的几种正规式的缩写形式。 (1) 正闭包。若r是表示L(r)的正规式，则r+是表示(L(r)+的正规式，且下述等式成立: r+ = rr* = r*r，r* = r+| +与*具有相同的运算优先级和结合性。 (2) 可缺省。若r是正规式，则(r)?是表示L(r)的正规式，且下述等式成立: r?=r |,(3) 字符组。字符组是或关系的缩写形式，它把所有存在或关系的字符集中在 里面。其中的字符可以有如下两种书写方式: 枚举方式: 如abc，它等价于a|b|c 分段方式: 如0-9a-z，它等价于 0123456789abcdefghijklmnopqrstuvwxyz,(4) 非字符

26、组。若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.6 引入正规式的缩写形式和辅助定义式后，id和num的正规

27、式可重写如下。 char = a-zA-Z digit = 0-9 digits = digit+ optional_fraction = ( . digits )? optional_exponent = ( E (+|)? digits )? id = char ( char|digit )* num = digits optional_fraction optional_exponent,2.3 记号的识别 有限自动机,2.3.1 不确定的有限自动机(Nondeterministic Finite Automata，NFA) 定义2.4 NFA是一个五元组(5-tuple) M =(S，

28、move，s0，F) 其中： S是有限个状态(state)的集合； 是有限个输入字符(包括)的集合；, move是一个状态转移函数，move(si，ch)=sj表示当前状态si下若遇到输入字符ch，则转移到状态sj； s0是唯一的初态(也称开始状态)； F是终态集(也称接受状态集)，它是S的子集，包含了所有的终态。,有限自动机是一个抽象的概念，可以用两种直观的方式状态转换图和状态转换矩阵来表示，这两种方式分别简称为转换图和转换矩阵。转换图是一个有向图，NFA中的每个状态对应转换图中的一个节点；NFA中的每个move函数对应转换图中的一条有向边，该有向边从si节点出发，进入sj节点，字符ch(或

29、)是边上的标记。显然，NFA的初态是转换图中没有前驱的节点，而NFA的终态在转换图中用有别于其他节点的方法表示。例如，若节点用一个圆圈表示，则终态节点可以用一个加粗的圆圈或者双圈表示。转换矩阵是一个二维数组，其中每个元素Msi, sj中的内容是从状态si到状态sj的边上的标记ch(或)。在转换矩阵中，一般以矩阵第一行所对应的状态为初态，而终态需要特别指出。,例2.7 识别由正规式(a|b)*abb说明的记号的NFA定义如下： S=0,1,2,3, =a,b， s0 = 0, F=3 move = move(0,a)=0, move(0,a)=1, move(0,b)=0, move(1,b)=

30、2, move(2,b)=3 它的转换图和转换矩阵表示如图2.5所示。在转换矩阵中，需指出0是初态，3是终态。,图2.5 识别(a|b)*abb的NFA (a) 转换图表示的NFA；(b) 转换矩阵表示的NFA,例2.8 识别表2.1中记号id、num和relation的转换图如图2.6所示。id和num依据的是例2.6中简化的正规式。不难看出，转换图识别的每一个记号实质上是从初态开始到某个终态的路径上的标记。例如，在识别relation的转换图中，从0开始到2的路径标记是“=”，表示在终态2处识别出一个关系运算符，语句return(relation, LE)表示此处可以返回记号的种类rela

31、tion和关系运算符的值LE(小于等于号)。,图2.6 状态转换图 (a) relation的转换图；(b) id的转换图；(c) num的转换图,NFA的特点是它的不确定性，即在当前状态下，对同一个字符ch，可能有多于一个的下一状态转移。不确定性反映在NFA的定义中，就是move函数是一对多的；反映在转换图中，就是从一个节点可通过多于一条标记相同字符的边转移到不同的状态；反映在转换矩阵中，就是Msi, sj中不是一个单一状态，而是一个状态的集合。,用NFA识别输入序列的方法是：从NFA的初态开始，对于输入序列中的每一个字符，寻找它的下一状态转移，直到没有下一状态转移为止。若此时所处状态是终态

32、，则从初态到终态路径上的所有标记，构成了一个识别出的记号。否则沿原路返回，并在返回的每一个节点试探可能的下一条路径，直到遇到第一个终态，或者一直返回到初态也没有遇到终态。对于输入序列，若试探了所有的路径也找不到下一状态转移或不能到达一个终态，则NFA不接受该序列，说明它不是语言中的合法记号。若到达一个终态，则NFA接受该序列，说明它是语言中的一个合法记号。,例2.9 用例2.7中的NFA来识别输入序列abb和abab。 识别过程如图2.7所示。对于abb的识别，有两条路径。第一条路径从状态0出发，经过字符a到达状态0，经过字符b到达状态0，再经过字符b到达状态0，此时输入序列已经结束，但是NF

33、A没有到达终态，所以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.

34、7(b)所示的三条路径可走。但是三条路径均不能到达终态，且再无路径可以试探,?所以NFA不接受输入序列abab,?也就是说，abab不是一个合法的记号。,图2.7 NFA识别输入序列abb和abab (a) abb的识别过程；(b)abab的识别过程,从例2.9中可以看出，用NFA识别记号存在下述问题： (1) 只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。 (2) 识别过程中需要进行大量的回溯，时间复杂度与输入序列成指数级增长，且算法复杂。 造成这种情况的原因是NFA的不确定性，即在当前的状态下，遇到的下一个字符可能有多于一条的路径可走

35、，而在当前状态下，这些路径中哪条路径可以到达终态或者全部路径均不能到达终态都是不可知的。,2.3.2 确定的有限自动机(Deterministic Finite Automata, DFA) 定义2.5 DFA是NFA的一个特例，其中： 没有状态具有状态转移(-transition)，即状态转换图中没有标记的边； 对每一个状态s和每一个字符a，最多有一个下一状态。,例2.10 识别由正规式(a|b)*abb说明的记号的DFA，其转换图和转换矩阵表示如图2.8所示。根据转换图，读者不难写出此DFA的定义。用它识别输入序列abb和abab的过程如图2.9所示。,图2.8 识别(a|b)*abb的D

36、FA (a) 转换图表示的DFA；(b) 转换矩阵表示的DFA,图2.9 DFA识别输入序列abb和abab,与NFA相比，DFA的特点就是它的确定性，即在当前状态下，对同一个字符ch，最多有一个下一状态转移。确定性反映在DFA的定义中，就是move函数是一对一的；反映在转换图中，就是从一个节点出发的任何不同的边上标记的字符均不同；反映在转换矩阵中，就是Msi, sj中是一个单一状态。 由于在DFA上识别输入序列时，在任何一个当前状态下遇到任何输入字符，其下一状态转移均是唯一确定的，因此，无论是接受还是不接受，均经历一条确定的路径，而无其他任何路径可走。也就是说，在DFA上识别输入序列无需回溯

37、，从而大大简化了记号的识别过程。,DFA识别输入序列的过程总结为算法2.1，被称为模拟器(模拟DFA的行为)，也被称为驱动器(用DFA的数据驱动分析动作)。模拟DFA算法的最大特点是方法与模式无关，它仅根据DFA的当前状态和状态转移进行一系列的动作，直到回答yes或者no。而所有与模式相关的信息均包含在DFA中。,算法2.1 模拟DFA 输入 DFA D和输入字符串x。x由文件结束符eof终止，D的初态为s0，终态集为F。 输出 若D接受x，回答“yes”，否则回答“no”。 方法 用下述过程识别x： s := s0； a := nextchar； while a eof loop s :=

38、move(s，a)； a := nextchar; end loop； if s is in F then return “yes“；else return “no“；end if；,2.3.3 有限自动机的等价 NFA和DFA统称为有限自动机(FA)。所谓有限，是指自动机的状态数是有限的，因此，有些教材中也称为有限状态自动机。与正规式的等价相似，FA之间也存在等价问题。 定义2.6 若有限自动机M和M识别同一个正规集，则称M和M是等价的，记为M=M。,图2.5和图2.8所示的FA均识别以正规式(a|b)*abb所表示的正规集，两个FA是等价的。由于DFA上识别记号的确定性和简单性，往往希望用

39、DFA而不是NFA来识别记号。很幸运，对于任何一个NFA，均可以找到一个与它等价的DFA。这一结果意味着，对任何正规集，均可以构造一个DFA去识别它。,2.4 从正规式到词法分析器,DFA和模拟DFA的算法2.1，实际上已经构成了词法分析器的基础，从而得到构造词法分析器的一般方法与步骤: 用正规式对模式进行描述； 为每个正规式构造一个NFA，它识别正规式所表示的正规集； 将构造出的NFA转换成等价的DFA，这一过程也被称为确定化； 优化DFA，使其状态数最少，这一过程也被称为最小化； 从优化后的DFA构造词法分析器。,2.4.1 从正规式到NFA 对任何的正规式，可以用下述的Thompson算

40、法构造一个NFA，它识别正规式所表示的正规集。 算法2.2 Thompson 算法 输入 字母表上的正规式r。 输出 接受L(r)的NFA N。,方法 首先，将r分解成最基本的正规式。由于分解是构造的逆过程，因此分解从正规式的最右端开始。然后按如下规则进行构造。每次构造的新状态都需重新命名，以使得所有状态的名字均不同。 对，构造NFA如图2.10(a)所示。其中，s0为初态，f为终态，该NFA接受； 对上的每一个字符a，构造NFA如图2.10(b)所示。其中，s0为初态，f为终态，该NFA接受；, 若N(p)和N(q)是正规式p和q的NFA，则： (a) 对正规式p|q，构造NFA如图2.10

41、(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.10 Thompson算法中NFA的构造,例2.11 用Thompson算法构造正规式r=(a|b)*abb的N(r)。 首先把正规式分解为如图2.11(a)所示的树结构，然后自下而上构造整个正规式的NFA，如图2.11(b)所示。具体步

42、骤为：运用算法2.2方法中的分别为正规式r1=a、r2=b、r6=a、r8=b、r10=b构造NFA N(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.11 构造正规式(a|b)*abb的NFA (a) 分解正规式；(b) 构造NFA,2.4.2 从NFA到DFA 1NFA识别记号

43、的“并行”方法 用NFA识别记号的过程，是在NFA上顺序地、一条路径一条路径试探的过程。由于需要进行回溯，所以算法构造复杂且工作效率低下。事实上，用NFA识别记号，并不采用这种“串行”的方法，而是采用一种“并行”的方法，从而可以消除识别时的不确定性，以避免回溯。,例2.12 从甲地到乙地，可以乘小汽车也可以骑自行车，具体路线如图2.12所示，其中c表示乘车，b表示骑自行车。现在要求从甲地到乙地，只许乘车而不许骑自行车，该如何走？ 此问题抽象在图2.12上，就是如何找到一条从甲地到乙地的路径，上边的标记均由c组成。首先，按照常规一条路径一条路径地试探： 甲 c 2 无路可走，退回 甲 c 1 c

44、 3 无路可走，退回 甲 c 1 c 乙 到达乙地，成功,图2.12 甲地到乙地的所有路径,为了避免回溯，设想有足够多的小汽车同时走若干条路。假设从甲地出发，第一站可以到达乘车所能到达地点的全体，再从第一站出发，第二站可以到达乘车所能到达地点的全体，依此类推，直到某一站中包含了乙地。按照这样的方法，从甲地到乙地的过程与路径如下所示： 甲 c 1, 2 c 3, 乙 到达乙地，成功,从识别由c组成的路径标记的角度看，两种方法的效果是一样的，但是第二种方法仅有一条确定的路径，所付出的代价是需要有足够的小汽车。 第二种方法的基本思想是将不确定的下一状态确定化：如果从当前状态出发经c可能到达不止一个状

45、态，则将所有这些状态组成一个集合，而虚拟地认为到达这一状态集。显然从当前状态出发经c到达这一状态集的路径是唯一确定的。,将这种确定化的思想应用于例2.12中特定交通工具的任何一种组合方式，从甲地出发的一条路径或者达到乙地，或者不能到达乙地，均是确定的，无需也再无其他路径可以试探。例如，若要求从甲地到乙地，先乘车，再骑自行车，然后再乘车，即在图2.12上找到一条标记为cbc的路径。则用这种确定化的方法可以找到这样一条路径：甲 c 1, 2 b 3。 由于在3处没有通过乘车可以到达乙地的路径，可以断定上述要求无法从甲地到达乙地。,将确定化的思想用于NFA上记号的识别，可得到下述与算法2.1相似的模

46、拟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.3 模拟NFA 输入 NFA N和输入字符串x。x由文件结束符eof终止，N的初态为s0，终态集为F 输出 若N接受x，回答“yes”，否则回

47、答“no” 方法 用下边的过程对x进行识别。S是一个状态的集合。,S := _闭包(s0); - 所有可能初态的集合 a := nextchar; while a eof loop S := _闭包(smove(S，a)； - 所有下一状态的集合 a := nextchar; end loop; if SF then return “yes“; else return “no“; end if;,表2.7 算法2.1与算法2.3的区别,定义2.7 状态集T的_闭包(T)是一个状态集，且满足： T中所有状态属于_闭包(T)； 任何smove(_闭包(T)，)属于_闭包(T)； 再无其他状态属于_

48、闭包(T)。,有关定义2.7中的三个条件的说明如下：状态集T自身在闭包中；若某状态已在闭包中，则从此状态出发的任何经状态转移所到达的下一状态也在闭包中。由此可知，_闭包(T)就是从状态集T出发，经所能达到的状态的全体。 根据_闭包的定义，不难得到计算_闭包的算法。由于_闭包是递归定义的，而反映递归的最佳数据结构是栈，所以算法中用一个栈来存放所有可能需要计算状态转移的状态。,算法2.4 求_闭包 输入 状态集T 输出 状态集T的_闭包 方法 用下面的函数计算_闭包 function_闭包(T) is begin for T中每个状态t loop 加入t到U; push(t); end loop; while 栈不空 loop pop(t); for 每个u=move(t, ) loop if u不在U中 then 加入u到U; push(u); end if; end loop; end loop; return U; end_闭包;,例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出发，