wwwwpp.txt

这源码太强了。该程序实现的时词法分析器,通过了调试,能运行,能实现如++,--,等-the program when the lexical analyzer, the debug, can run,

图示与定义的第3个区别更为重要：定义将转换表示为一个函数T：S×.→S。这意味着
T (s, c）必须使每个s 和c 都有一个值。但在图中，只有当c 是字母时，才定义T (start, c）；而
也只有当c 是字母或数字时，才定义T (in_id, c）。那么，所丢失的转换跑到哪里去了呢？答案
是它们表示了出错——即在识别标识符时，我们不能接受除来自初始状态之外的任何字符以及
ì
第2章词法分析3 3
下载
这之后的字母或数字。按照惯例，这些出错
转换（ error transition）在图中并没有画出来
而只是假设它总是存在着。如果要画出它们，
则标识符的图示应如图2 - 2所示：
在该图中，我们将新状态e r r o r标出来了（这
是因为它表示出错的发生），而且还标出了出
错转换o t h e r。按照惯例， o t h e r表示并未
出现在来自于它所起源的状态的任何其他转
换中的任意字符，因此o t h e r的定义来自于
初始状态为：
other = ~l e t t e r
来自i n _ i d状态的o t h e r的定义是：
other = ~(l e t t e r|d i g i t)
请注意，来自出错状态的所有转换都要回到其本身（这些转换用a ny 标出以表示在这个转换
中得出的任何字符）。另外，出错状态是非接受的，因此一旦发生一个出错，则无法从出错状
态中逃避开来，而且再也不能接受串了。
下面是D FA的一些示例，其中也有一些是在上一节中提到过的。
例2.6 串中仅有一个b 的集合被下示的D FA接受：
请注意，在这里并未标出状态。当无需用名字来指出状态时就忽略标签。
例2.7 包含最多一个b 的串的集合被下示的D FA接受：
请注意这个D FA是如何修改前例中的D FA，它将初始状态变成另一个的接受状态。
例2.8 前一节给出了科学表示法中数字常量的正则表达式，如下所示：
nat = [0-9]+
signedNat = (+|-)? nat
number = signedNat ("." n a t)? (E s i g n e d N a t) ?
我们想为由这些定义匹配的串写出D FA，但是先如下重写它会更为有用：
digit = [0-9]
nat = d i g i t+
3 4 编译原理及实践
下载
在实际情况中，这些非文字数字的字符意味着根本就没有标识符(如果是在初始状态中)或遇到了一个结束标
识符的识别的分隔符(如果是在接受状态中)。本节后面将介绍如何处理这些情况。
图2-2 带有出错转换的标识符的有穷自动机
signedNat = (+|-)? n a t
number = signedNat ("." n a t)? (E s i g n e d N a t) ?
如下为n a t写出一个D FA是非常简单（请记住a+ = aa*对任意的a均成立）的：
由于可选标记，s i g n e d N a t要略难一些，但是可注意到s i g n e d N a t是以一个数字或一个标记
与数字开头，并写作以下的D FA：
在它上面添加可选的小数部分也很简单，如下所示：
请注意，它有两个接受状态，它们表示小数部分是可选的。
最后需要添加可选的指数部分。要做到它，就要指出指数部分必须是以字母E开头，且只
能发生在前面的某个接受状态之后，图2 - 3是最终的图。
图2-3 浮点数的有穷自动机
例2.9 使用D FA可描述非嵌套注释。例如，前后有花括号的注释可由以下的D FA接受：
在这种情况下， o t h e r意味着除了右边花括号外的所有字符。这个D FA与第2 . 2 . 4节中所写
的正则表达式{ (~} ) * }相对应。
我们注意到在2 . 2 . 4中，为被两个字符的序列分隔开的注释编写一个正则表达式很难， C注
释的格式/ * . . . ( n o * / s ) . . . / 就是这样的。编写接受这个注释的D FA比编写它的正则表达式
实际上要简单许多，图2 - 4中的D FA就是这样的C注释。
第2章词法分析3 5
下载
图2-4 有C风格注释的有穷自动机
在该图中，由状态3到其自身的o t h e r转换表示除“*”之外的所有字符，但由状态4到状
态3的o t h e r转换则表示除“ *”和“ /”之外的所有字符。为了简便起见，还给状态编了号，
但仍能为状态赋予更多有意义的名字，如下所示（在括号中带有其相应的编号）：start (1）、
entering_comment (2）、in_comment (3）、exiting_comment (4）和f i n i s h（5）。
2.3.2 先行、回溯和非确定性自动机
作为根据模式接受字符串的表示算法的一种方法，我们已经学习了D FA。正如同读者可能
早已猜到的一样，模式的正则表达式与根据模式接受串的D FA之间有很密切的关系，下一节我
们将探讨这个关系。但首先需要更仔细地学习D FA表示的精确算法，这是因为希望最终能将这
些算法变成扫描程序的代码。
我们早已注意到D FA的图表并不能表示出D FA所需的所有东西而仅仅是给出其运算的要
点。实际上，我们发现数学定义意味着D FA必须使每个状态和字符都具有一个转换，而且这些
导致出错的转换通常是不在D FA的图表中。但即使是数学定义也不能描述出D FA算法行为的所
有方面。例如在出错时，它并不指出错误是什么。在程序将要到达接受状态时或甚至是在转换
中匹配字符时，它也不指出该行为。
进行转换时发生的典型动作是：将字符从输入串中移到属于单个记号（记号串值或记号词）
累积字符的字符串中。在达到某个接受状态时的典型的动作则是将刚被识别的记号及相关属性
返回。遇到出错状态的典型动作则是在输入中备份（回溯）或生成错误记号。
在关于标识符最早的示例中有许多这里将要描述的行为，所以我们再次回到图2 - 4中。由
于某些原因，该图中的D FA并没有如希望的那样来自扫描程序的动作。首先，出错状态根本就
不是一个真正的错误，而是表示标识符将不被识别（如来自于初始状态）或是已看到的一个分
隔符，且现在应该接受并生成标识符记号。我们暂时假设（实际这是正确的操作）有其他的转
换可表示来自初始状态的非字母转换。接着指出可看到来自状态i n _ i d的分隔符，以及应被生成
的一个标识符记号，如图2 - 5所示。
图2-5 有分隔符和返回值的标识符的有穷自动机
在该图中，o t h e r转换前后都带有方括号，它表示了应先行考虑分隔字符，也就是：应先
将其返回到输入串并且不能丢掉。此外在该图中，出错状态已变成接受状态，且没有离开接受
状态的转换。因为扫描程序应一次识别一个记号并在每一个记号识别之后再一次从它的初始状
态开始，所以这正是所需要的。
3 6 编译原理及实践
下载
这个新的图示还表述了在2 . 2 . 4节中谈到的最长子串原理： D FA将一直（在状态i n _ i d中）
匹配字母和数字直到找到一个分隔符。与在读取标识符串时允许D FA在任何地方接受的旧图相
反，我们确实不希望发生某些事情。
现在将注意力转向如何在一开始就到达初始状态的问题上。典型的程序设计语言中都有许
多记号，且每一个记号都能被其自己的D FA识别出来。如果这每一个记号都以不同的字符开头，
则只需通过将其所有的初始状态统一到一个单独的初始状态上，就能很便利地将它们放在一起
了。例如，考虑串：=、< =和=给出的记号。其中每一个都是一个固定串，它们的D FA可写作：
因为每一个记号都是以不同的字符开始的，故只需通过标出它们的初始状态就可得出以下
的D FA：
但是假设有若干个以相同字符开头的记号，例如<、< =和< >，就不能简单地将其表示为如下的
图表了。这是因为它不是D FA（给出一个状态和字符，则通常肯定会有一个指向单个的新状态
的唯一转换）：
第2章词法分析3 7
下载
相反地，我们必须做出安排，以便在每一个状态中都有一个唯一的转换。例如下图：
在理论上是应该能够将所有的记号都合并为具有这种风格的一个巨大的D FA，但是它非常复杂，
在使用一种非系统性的方法时尤为如此。
解决这个问题的一个方法是将有穷自动机的定义扩展到包括了对某一特定字符一个状态存
在有多个转换的情况，并同时为系统地将这些新生成的有穷自动机转换成N F A开发一个算法。
这里会讲解到这些生成的自动机，但有关转换算法的内容要在下一节才能提到。
新的有穷自动机称作非确定性有穷自动机（ nondeterministic finite automaton）或简称为
N FA。在对它下定义之前，还需要为在扫描程序中应用有穷自动机再给出一个概括的讲法： -
转换的概念。
-转换（ - t r a n s i t i o n）是无需考虑输入串（且无需消耗任何字符）就有可能发生的转换。
它可看作是一个空串的“匹配”，空串在前面已讲过是写作的。-转换在图中的表示就好像
是一个真正的字符：
这不应同与在输入中的字符的匹配相混淆：如果字母表包括了这样一个字符，则必须与
使用作为表示- 转换的元字符相区别。
- 转换与直觉有些相矛盾，这是因为它们可以“同时”发生，换言之，就是无需先行和改
变到输入串，但它们在两方面有用：首先，它们可以不用合并状态就表述另一个选择。例如：
记号: =、< =和=的选择可表述为：为每一个记号合并自动机，如下所示：
这对于使最初的自动机保持完整并只添加一个新的初始状态来链接它们很有好处。-转换
3 8 编译原理及实践
下载
的第2个好处在于它们可以清晰地描述出空串的匹配：
当然，这与下面的D FA等同，该D FA表示接受可在无任何字符匹配时发生：
但是具有前面清晰的表示法也是有用的。
现在来讲述非确定性自动机的定义。它与D FA的定义很相似，但有一点不同：根据上面所
讨论的，需要将字母表.扩展到包括了。将原来写作.的地方（这假设最初并不属于.）改
写成.è{ }（即.和的并集）。此外还需要扩展T（转换函数）的定义，这样每一个字符都可
以导致多个状态，通过令T的值是状态的一个集合而不是一个单独的状态就可以做到它。例如
下示的图表：
使T (1,<) = {2,3}，即：在输入字符<上，由状态1可到状态2或状态3，且T成为一个将状态/符号
对映射到状态集合的函数。因此， T的范围是状态的S集合（ S的所有子集的集合）的幂集
（power set），写作(S)（S的草写的p 的集合）。下面给出定义。
定义：N FA（nondeterministic finite automaton）M由字母表.、状态的集合S、转换函
数T : S×( .è{ } )→ (S)、S 的初始状态s0，以及S的接受状态A的集合组成。由M接受
的语言写作L (M)，它被定义为字符c1c2 . . . cn ，其中每一个ci 都属于.è{ }，且存在
关系：s1 在T (s0 , c1 ) 中、s2 在T (s1 , c2 ) 中、. . .、sn 在T (sn-1 , cn ) 中，sn 是A 中的元素。
有关这个定义还需注意以下几点。在c1c2 . . . cn 中的任何ci 都有可能是，而且真正被接受
的串是删除了的串c1c2 . . . cn（这是因为s 和的联合就是s 本身）。因此，串c1c2 . . . cn 中真正的
字符数可能会少于n个。另外状态序列s1 . . . sn 是从状态集合T (s0 , c1 ) , . . . , T (sn-1 , cn ）选出的，
这个选择并不总是唯一确定的。实际上这就是为什么称这些自动机是非确定性的原因：接受特
定串的转换序列并不由状态和下一个输入字符在每一步中确定下来。实际上，任意个都可在
任一点上被引入到串中，并与N FA中- 转换的数量相对应。因此，N FA并不表示算法，但是却
可通过一个在每个非确定性选择中回溯的算法来模拟它，本节下面会谈到这一点。
首先看一些N FA的示例。
第2章词法分析3 9
下载
例2.10 考虑下面的N FA图。
下面两个转换序列都可接受串a b b：
实际上，a 上的由状态1向状态2的转换与b 上的由状态2向状态4的转换均允许机器接受串
a b，接着再使用由状态4向状态2的转换，所有的串与正则表达式a b +匹配。类似地，a 上的由
状态1向状态3的转换，和上的由状态3向状态4的转换也允许接受与a b *匹配的所有串。最后，
由状态1向状态4的- 转换可接受与b *匹配的所有串。因此，这个N FA接受与正则表达式
a b + | a b * | b *相同的语言。能够生成相同的语言的更为简单的正则表达式是( a | ) b *。下面
的D FA也接受这个语言：
例2 . 11 考虑下面的N FA：
它通过下面的转换接受串a c a b：
不难看出，这个N FA接受的语言实际上与由正则表达式( a | c ) * b生成的语言相同。
4 0 编译原理及实践
下载
2.3.3 用代码实现有穷自动机
将D FA或N FA翻译成代码有若干种方法，本节将会讲到它们。但并不是所有的方法对编译
器的扫描程序都有用，本章的最后两节将更详细地讲到与扫描程序相关的编码问题。
请再想一下最开始那个接受由一个字母及一个字母和/或数字序列组成的标识符的D FA的
示例，以及当它位于包含了先行和最长子串原理的修改格式（参见图2 - 5）：
模拟这个D FA最早且最简单的方法是在下面的格式中编写代码：
{ starting in state 1 }
if the next character is a letter t h e n
advance the input;
{ now in state 2 }