wwwwpp.txt

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

number = signedNat ("." nat ) ? (E s i g n e d N a t) ?
此处，在引号中用了一个十进制的点来强调它应直接匹配且不可被解释为一个元字符。
2) 保留字和标识符正则表达式中最简单的就是保留字了，它们由字符的固定序列表示。
如果要将所有的保留字收集到一个定义中，就可写成：
reserved = if | while | do | ...
相反地，标识符是不固定的字符串。通常，标识符必须由一个字母开头且只包含字母和数
字。可用以下的正则定义表示：
letter = [ a - zA - Z ]
digit = [ 0 - 9 ]
identifier = letter (letter | d i g i t) *
3) 注释注释在扫描过程中一般是被忽略的。然而扫描程序必须识别注释并舍弃它们。
因此尽管扫描程序可能没有清晰的常量记号（可将其称为“伪记号p s e u d o t o k e n”），仍需要给
注释编写出正则表达式。注释可有若干个不同的格式。通常，它们可以是前后为分隔符的自由
第2章词法分析2 9
下载
它们有时可包括编译目录。
格式，例如：
{ this is a Pascal comment }
/* this is a C comment */
或由一个或多个特殊字符开头并直到该行的结尾，如在
; this is a Scheme comment
-- this is an Ada comment
中。
为有单个字符的分隔符的注释(如Pascal 注释)编写正则表达式并不难，且为那些从行的特
殊字符到行尾编写正则表达式也不难。例如Pascal 注释可写作：
{ (~} ) * }
其中，用~ }表示“非}”，并假设字符}作为元字符没有意义（在L e x中的表示与之不同，本章
后面将会提到）。类似地，一个A d a注释可被正则表达式
- - (~n e w l i n e) *
匹配。其中，假设n e w l i n e匹配一行的末尾（在许多系统中可写作\ n），“-”字符作为元字符没
有意义，该行的结尾并未包括在注释本身之中（ 2 . 6节将谈到如何在L e x中书写它）。
为同C注释一样，其中的分隔符如多于一个字符时，则编写正则表达式就要困难许多。例
如串集合b a. . .（没有a b）. . . a b（用b a. . . ab 代替C的分隔符/ * . . . * /，这是因为星号，有时还有
前斜杠要求特殊处理的元字符）。不能简单地写作：
b a (~( a b ) ) * a b
由于“非”运算通常限制为只能是单个字符而不能使用字符串。可尝试用~a、~b和~( a | b )为
~( a b )写出一个定义来，但这却没有多大用处。其中的一个解是：
b * ( a *~( a | b ) b * ) * a *
然而这很难读取（且难证明是正确的）。因此，C注释的正则表达式是如此之难以至于在实际
中几乎从未编写过。实际上，这种情况在真正的扫描程序中经常是通过特殊办法解决的，本章
后面将会提到它。
最后，在识别注释时会遇到的另一个复杂的问题是：在一些程序设计语言中，注释可被嵌
套。例如M o d u l a - 2允许格式注释：
(* this is (*a Modula-2 *) comment *)
在这种嵌套注释中，注释分隔符必须成对出现，故以下注释在M o d u l a - 2中是不正确的：
(* this is ( * illegal in Modula-2 *)
注释的嵌套要求扫描程序计算分隔符的数量，但我们又注意到在例2 . 3（2 . 2 . 1节）中，正则
表达式不能表示计数操作。实际上，一个简单的计算器配置可作为这个问题的特殊解（参见
练习）。
4) 二义性、空白格和先行在程序设计语言记号使用正则表达式的描述中，有一些串经
常可被不同的正则表达式匹配。例如：诸如i f和w h i l e的串可以既是标识符又可以是关键
字。类似地，串< >可解释为表示两个记号（“小于号”和“大于号”）或一单个符号（“不等
于”）。程序设计语言定义必须规定出应遵守哪个解释，但正则表达式本身却无法做到它。相
反地，语言定义必须给出无二义性规则（ disambiguating rules ），由其回答每一种情况下的
含义。
下面给出处理示例的两个典型规则。首先当串既可以是标识符也可以是关键字时，则通常
认为它是关键字。这暗示着使用术语保留字（ reserved word），其含义只是关键字不能同时也
3 0 编译原理及实践
下载
是标识符。其次，当串可以是单个记号也可以是若干记号的序列时，则通常解释为单个记号。
这常常被称作最长子串原理（ principle of longest substring）：可组成单个记号的字符的最长串
在任何时候都是假设为代表下一个记号。
在使用最长子串原理时会出现记号分隔符（ token delimiter）的问题，即表示那些在某时
不能代表记号的长串的字符。分隔符应是肯定为其他记号一部分的字符。例如在串
x t e m p = y t e m p中，等号将标识符x t e m p分开，这是因为=不能作为标识符的部分出现。通常
也认为空格、新行和制表位是记号分隔符：因此while x... 就解释为包含了两个记号——保
留字w h i l e和带有名字x的标识符，这是因为一个空格将两个字符串分开。在这种情况下，定
义空白格伪记号非常有用0它与注释伪记号相类似，但注释伪记号仅仅是在扫描程序内部区分
其他记号。实际上，注释本身也经常作为分隔符，因此例如C代码片段：
do / ** / if
表示的就是两个保留字d o和i f，而不是标识符d o i f。
程序设计语言中的空白格伪记号的典型定义是：
whitespace = (newline | blank | tab | c o m m e n t) +
其中，等号右边的标识符代表恰当的字符或串。请注意：空白格通常不是作为记号分隔符，而
是被忽略掉。指定这个行为的语言叫作自由格式语言（ free format）。除自由格式语言之外还可
以是一些诸如F O RT R A N的固定格式语言，以及各种使用缩排格式的语言，例如越位规则
（o ffside rule）（参见“注意与参考”一节）。自由格式语言的扫描程序必须在检查任意记号分
隔功能之后舍弃掉空白格。
分隔符结束记号串，但它们并不是记号本身的一部分。因此，扫描程序必须处理先行
（l o o k a h e a d）问题：当它遇到一个分隔符时，它必须作出安排分隔符不会从输入的其他部分中
删除，方法是将分隔符返回到输入串（“备份”）或在将字符从输入中删除之前先行。在大多数
情况下，只有单个字符才需要这样做（“单个字符先行”）。例如在串x t e m p = y t e m p中，当遇
到=时，就可找到标识符x t e m p的结尾，且=必须保留在输入中，这是因为它表示要识别下一
个记号。还应注意，在识别记号时可能不需要使用先行。例如，等号可能是以=开头的唯一字
符，此时无需考虑下一个字符就可立即识别出它了。
有时语言可能要求不仅仅是单个字符先行，且扫描程序必须准备好可以备份任意多个字符。
在这种情况下，输入字符的缓冲和为追踪而标出位置就给扫描程序的设计带来了问题（本章后
面将会讨论到其中的一些问题）。
F O RT R A N是一个并不遵守上面所谈的诸多原则的典型语言。它是固定格式语言，它的空
白格在翻译开始之前已由预处理器删除了。因此，下面的F O RT R A N行
I F ( X 2 . EQ. 0 ) THE N
在编译器中就是
I F ( X 2 . E Q . 0 ) T H E N
所以空白格再也不是分隔符了。F O RT R A N中也没有保留字，故所有的关键字也可以是标识符，
输入每行中字符串的位置对于确定将要识别的记号十分重要。例如，下面代码行在F O RT R A N
中是完全正确的：
IF(IF.EQ.0 )THENTHEN=1.0
第2章词法分析3 1
下载
有时这也称作“最大咀嚼”定理。
第1个I F和T H E N都是关键字，而第2个I F和T H E N则是表示变量的标识符。这样的结果是
F O RT R A N的扫描程序必须能够追踪代码行中的任意位置。例如：
D O 9 9 I = 1 , 1 0
它引起循环体为第9 9行代码的循环。在P a s c a l中，则表示为for i := 1 to 。10另一方面，
若将逗号改为句号：
D O 9 9 I = 1 . 1 0
就将代码的含义完全改变了：它将值1 . 1赋给了名字为D O 9 9 I的变量。因此，扫描程序只有到
它接触到逗号（句号）时才能得出起始的D O。在这种情况下，它可能只得追踪到行的开头并
且由此开始。
2.3 有穷自动机
有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法。特别
地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。当然有
穷自动机与正则表达式之间有着很密切的关系，在下一节中大家将会看到如何从正则表达式中
构造有穷自动机。但在学习有穷自动机之前，先看一个说明的示例。
通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义（假设已定义了
l e t t e r和d i g i t）：
identifier = letter ( letter | d i g i t) *
它代表以一个字母开头且其后为任意字母和/ 或数字序列的串。识别这样的一个串的过程可表
示为图2 - 1。在此图中，标明数字1和2的圆圈
表示的是状态（ s t a t e），它们表示其中记录已
被发现的模式的数量在识别过程中的位置。
带有箭头的线代表由记录一个状态向另一个
状态的转换（ t r a n s i t i o n），该转换依赖于所标
字符的匹配。在较简单的图示中，状态1是初
始状态（start state）或识别过程开始的状态。
按照惯例，初始状态表示为一个“不来自任何地方”且指向它的未作标识的箭头线。状态2代
表有一单个字母已被匹配的点（表示为从状态1到状态2的转换，且其上标有l e t t e r）。一旦
位于状态2中，就可看到任何数量的字母和/ 或数字，它们的匹配又使我们回到了状态2。代表
识别过程结束的状态称作接受状态（ accepting state），当位于其中时就可说明成功了，在图中
它表示为在状态的边界画出双线。它们可能不只一个。在上面的例图中，状态2就是一个接受
状态，它表示在看到一个字母之后，随后的任何字母和数字序列（也包括根本没有）都表示一
个正规的标识符。
将真实字符串识别为标识符的过程现在可通过列出在识别过程中所用到的状态和转换的序
列来表示。例如，将x t e m p识别为标识符的过程可表示为：
→1→ x
2→ t 2→ e
2→ m
2→ p
2
在此图中，用在每一步中匹配的字母标出了每一个转换。
2.3.1 确定性有穷自动机的定义
因为上面所示的例图很方便地展示出算法过程，所以它对于有穷自动机的描述很有用处。
3 2 编译原理及实践
下载
图2-1 标识符的有穷自动机
但是偶尔还需使用有穷自动机的更正式的描述，现在就给出一个数学定义。但绝大数情况并不
需要这么抽象，且在大多数示例中也只使用示意图。有穷自动机还有其他的描述，尤其是表格，
表格对于将算法转换成运行代码很有用途。在需要它的时候我们将会谈到它。
另外读者还需注意：我们一直在讨论的是确定性的（ d e t e r m i n i s t i c）有穷自动机，即：下
一个状态由当前状态和当前输入字符唯一给出的自动机。非确定性的有穷自动机是由它产生的。
本节稍后将谈到它。
定义：D FA（确定性有穷自动机）M由字母表.、状态集合S、转换函数T：S×.→S、
初始状态s0.S以及接受状态的集合A S组成。由M接受的且写作L (M) 被定义为字符
c1c2 . . . cn 串的集合，其中每个ci ..，存在状态s1 = T (s0, c1 ), s2 = T (s1, c2 ), . . . , sn = T
(sn-1 , cn )，其中sn 是A（即一个接受状态）的一个元素。
有关这个定义请注意以下几点。S×.指的是S 和.的笛卡尔积或叉积：集合对（ s, c），其
中s. S且c ..。如果有一个标为c 的由状态s 到状态s ' 的转换，则函数T记录转换：T (s, c) = s' 。
与M相应的示图片段如下：
当接受状态序列s1 = T (s0 , c1 ), s2 = T (s1 , c2 ), . . . , sn = T (sn-1 , cn）存在，且sn 是一个接受状态
时，它表示如下所示的意思：
在D FA的定义和标识符示例的图示之间有许多区别。首先，在标识符图中的状态使用了数
字，而定义并未用数字对状态集合作出限制。实际上可以为状态使用任何标识系统，这其中也
包括了名字。例如：下图与图2 - 1完全一样：
在这里就称作状态s t a r t（因为它是初始状态）和i n _ i d（因为我们发现了一个字母并识别
其后的任何字母和数字后面的标识符）。这个图示中的状态集合现在变成了{ s t a r t ,
i n _ i d }，而不是{ 1 , 2 }了。
图示与定义的第2个区别在于转换不是用字符标出而是表示为字符集合的名字。例如，名
字l e t t e r表示根据以下正则定义的字母表中的任意字母：
letter = [ a - zA - Z ]
因为如要为每个小写字母和每个大写字母画出总共5 2个单独的转换非常麻烦，所以这是定义的
一个便利的扩展。本章后面还会用到这个定义的扩展。