wwwwpp.txt

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

或写作
digit digit*
其中
digit = 0|1|2|...|9
就是名字d i g i t的正则定义（regular definition）了。
正则定义的使用带来了巨大的方便，但是它却增加了复杂性，它的名字本身也变成一个元
符号，而且必须要找到一个方法能将这个名字与它的字符连结相区分开。在我们的例子中是用
斜体来表示它的名字。请注意，在名字的定义中不能使用名字（也就是递归地）——必须能够
用它代表的正则表达式替换它们。
在考虑用一些例子来详细描述正则表达式的定义之前，先将有关正则表达式定义的所有信
息收集在一起。
定义正则表达式（regular expression）是以下的一种：
1. 基本（b a s i c）正则表达式由一个单字符a（其中a 在正规字符的字母表.中），以及
元字符或元字符组成。在第1种情况下，L (a) = {a}；在第2种情况下，L ( ) =
{ }；在第3种情况下，L ( ) = {}。
2. r | s 格式的表达式：其中r 和s 均是正则表达式。在这种情况下，L (r | s) = L (r) è L (s)。
3. rs 格式的表达式：其中r 和s 是正则表达式。在这种情况下，L (r s) = L (r) L (s)。
4. r* 格式的表达式：其中r 是正则表达式。在这种情况下，L (r*) = L (r) *。
5. (r）格式的表达式：其中r 是正则表达式。在这种情况下，L ( (r)) = L (r)，因此，括
号并不改变语言，它们只调整运算的优先权。
我们注意到在上面这个定义中，（2）、（3）和（4）的优先权与它们所列的顺序相反，也就
第2章词法分析2 5
下载
是：｜的优先权最低，连结次之，* 则最高。另外还注意到在这个定义中， 6个符号—— 、、
|、*、( 和) 都有了元字符的含义。
本节后面将给出一些示例来详述上述定义，但它们并不经常作为记号描述在程序设计语言
中出现。2 . 2 . 3节将讨论一些经常作为记号在程序设计语言中出现的常用正则表达式。
在下面的示例中，被匹配的串通常是英语描述，其任务是将描述翻译为正则表达式。包含
了记号描述的语言手册是编译器的程序员最常见的。偶尔还需要变一下，也就是将正则表达式
翻译为英语描述，我们也有一些此类的练习。
例2.1 在仅由字母表中的3个字符组成的简单字母表. = {a, b, c}中，考虑在这个字母表上的仅
包括一个b 的所有串的集合，这个集合由正则表达式
( a | c ) * b ( a | c ) *
产生。尽管b出现在正则表达式的正中间，但字母b 却无需位于被匹配的串的正中间。实际上，
在b 之前或之后的a 或c 的重复会发生不同的次数。因此，串b、a b c、a b a c a、b a a a a c、c c b a c a
和ccccccb 都与上面的正则表达式匹配。
例2.2 在与上面相同的字母表中，如果集合是包括了最多一个b 的所有串，则这个集合的正则
表达式可通过将上例的解作为一个解（与那些仅为一个b 的串匹配），而正则表达式( a | c ) *
则作为另一个解（与b 根本不匹配）来获取。因此有以下解：
( a | c ) * | ( a | c ) * b ( a | c ) *
下面是一个既允许b 又允许空串在重复的a 或c 之间出现的另一个解：
( a | c ) * ( b | ) ( a | c ) *
本例引出了正则表达式的一个重要问题：不同的正则表达式可生成相同的语言。虽然在实际中
从未尝试着证实已找到了“最简单的”，例如最短的，正则表达式，但通常总是试图用尽可能
简单的正则表达式来描述串的集合。这里有两个原因：首先在现实中极少有标准的“最短的”
解；其次，在研究用作识别正则表达式的方法时，那儿的算法无需首先将正则表达式简化就可
将识别过程简化了。
例2.3 在字母表.= {a, b}上的串S的集合是由一个b及在其前后有相同数目的a 组成：
S = { b, aba, aabaa, aaabaaa, . . . } = { an b an | n≠0 }
正则表达式并不能描述这个集合，其原因在于重复运算只有闭包运算*一种，它允许有任意次
的重复。因此如要写出表达式a * b a *（尽可能接近地得到S的正则表达式），就不能保证在b 前
后的a 的数量是否相等了，它通常表示为“不能计算的正则表达式”。但若要给出一个数学论
证，则需使用有关正则表达式的称作P u m p i n g引理（Pumping lemma）的著名定理，这将在自
动机理论中学到，现在就不谈了。
很明显，并非用简单术语描述的所有串都可由正则表达式产生，因此为了与其他集合相区
分，作为正则表达式语言的串集合称作正则集合（ regular set）。非正则集合偶尔也作为串出现
在需要由扫描程序识别的程序设计语言中，通常是在出现时才处理它们，我们也将其放在扫描
程序一节中讨论。
例2.4 在字母表.= {a, b, c}上的串S中，任意两个b 都不相连，所以在任何两个b 之间都至
少有一个a 或c。可分几步来构造这个正则表达式，首先是在每一个b 后都有一个a 或c，它
写作：
2 6 编译原理及实践
下载
( b ( a | c ) ) *
将其与表达式( a | c ) *合并，( a | c ) *是与完全不包含b 的串匹配，则写作：
( ( a | c ) * | ( b ( a | c ) ) * ) *
或考虑到( r * | s * ) *与( r | s ) *所匹配的串相同，则：
( ( a | c ) | ( b ( a | c ) ) ) *
或
( a | c | b a | b c ) *
（警告！这还不是正确答案）。
这个正则表达式产生的语言实际上具有了所需的特性，即：没有两个相连的b（但这还不正
确）。有时需要证明一下上面的这个说法，也就是证明在L(( a | c | b a | b c ) *)中的所有串都不包
括两个相连的b。该证明是通过对串长度（即串中字符数）的归纳实现的。很显然，它对于所有
长度为0、1和2的串是正确的：这些串实际是串、a、c、a a、a c、c a、c c、ba 和b c。现在假设
对于在长度i < n 的语言中的所有串也为真，并令s 是长度为n > 2 的语言中的一个串，那么s 包
含了至少一个上面所列的非的串，所以s = s1s2，其中s1 和s2 也是语言中的非串。通过假设归
纳，证明了s1 和s2 都没有两个相连的b。因此要使s 本身包括两个相连的b 的唯一方法是使s1 以
一个b 结尾，而s2 以一个b 开头。但又因为语言中的串都不以b 结尾，所以这是不可能的。
论证中的最后一个事实，即由上面的正则表达式所产生的串都不以b 结尾，也显示了我们
的解还不太正确：它不产生串b、a b和c b，这3个都不包括两个相连的b。可以通过为其添加一
个可选的结尾b来修改它，如下所示：
( a | c | b a | b c ) * ( b | )
这个正则表达式的镜像也生成了指定的语言：
( b| ) ( a | c | a b | c b ) *
以下也可生成相同的语言：
(n o t b|b notb ) * ( b | )
其中n o t b = a | c。这是一个使用了下标表达式名字的例子。由于无需将原表达式变得更复杂就
可使n o t b的定义调整为包括了除b 以外的所有字符，因此实际是在字母表较大时使用这个解。
例2.5 本例给出了一个正则表达式，要求用英语简要地描述它生成的语言。若有字母表. =
{a, b, c}，则正则表达式：
( ( b | c ) * a ( b | c ) * a ) * ( b | c ) *
生成了所有包括偶数个a 的串的语言。为了看清它，可考虑外层左重复之中的表达式：
( b | c ) * a ( b | c ) * a
它生成的串是以a 结尾且包含了两个a（在这两个a 之前或之间可有任意个b 和c）。重复这些串
则得到所有以a 结尾的串，且a 的个数是2的倍数（即偶数）。在最后附加重复(b | c)*（如前
例所示）则得到所需结果。
这个正则表达式还可写作：
(n o t a* a nota* a)* n o t a*
2.2.2 正则表达式的扩展
前面已给出了正则表达式的一个定义，这个正则表达式使用了在所有应用程序中都常见到
第2章词法分析2 7
下载
运算的最小集合，而且使上面的示例仅限于使用3种基本运算（包括括号）。但是从以上这些示
例中可看出仅利用这些运算符来编写正则表达式有时显得很笨拙，如果可用一个更有表达力的
运算集合，那么创建的正则表达式就会更复杂一些。例如，使任意字符的匹配具有一个表示法
很有用（我们现在须在一个长长的解中列出字母表中的每个字符）。除此之外，拥有字符范围
的正则表达式和除单个字符以外所有字符的正则表达式都十分有效。
下面几段文字将描述前面所讨论的标准正则表达式的一些扩展情况，以及与它及类似情况
相对应的新元符号。在大多数情况下并不存在通用术语，所以使用的是与在扫描程序生成器
L e x中用到的类似的表示法，本章后面将会讲到L e x。实际上，以后要谈到的很多情况都会在
对L e x的讨论中再次提到。并非所有使用正则表达式的应用程序都包括这些运算，即使是这样，
也要用到不同的表示法。
下面是新运算的列表。
(1) 一个或多个重复
假若有一个正则表达式r，r 的重复是通过使用标准的闭包运算来描述，并写作r *。它允许
r 被重复0次或更多次。0次并非是最典型的情况，一次或多次才是，这就要求至少有一个串匹
配r，但空串却不行。例如在自然数中需要有一个数字序列，且至少要出现一个数字。如要匹
配二进制数，就写作( 0 | 1 ) *，它同样也可匹配不是一个数的空串。当然也可写作
( 0 | 1 ) ( 0 | 1 ) *
但是这种情况只出现在用+代替*的这个相关的标准表示法被开发之前： r +表明r 的一个或
多个重复。因此，前面的二进制数的正则表达式可写作：
( 0 | 1 ) +
(2) 任意字符
为字母表中的任意字符进行匹配需要一个通常状况：无需特别运算，它只要求字母表中
的每个字符都列在一个解中。句号“ .”表示任意字符匹配的典型元字符，它不要求真正将字
母表写出来。利用这个元字符就可为所有包含了至少一个b 的串写出一个正则表达式，如下
所示：
. * b . *
(3) 字符范围
我们经常需要写出字符的范围，例如所有的小写字母或所有的数字。直到现在都是在用表
示法a | b | . . . | z 来表示小写字母，用0 | 1 | . . . | 9来表示数字。还可针对这种情况使用一个
特殊表示法，但常见的表示法是利用方括号和一个连字符，如[ a - z ]是指所有小写字母，[ 0 -
9 ]则指数字。这种表示法还可用作表示单个的解，因此a | b | c可写成[ a b c ]，它还可用于多
个范围，如[ a - z A - Z ]代表所有的大小写字母。这种普遍表示法称为字符类（ character class）。
例如，[ A - Z ]是假设位于A和Z之间的字符B、C等（一个可能的假设）且必须只能是A和Z之间
的大写字母（A S C I I字符集也可）。但[ A - z ]则与[ A - Z a - z ]中的字符不匹配，甚至与A S C I I字
符集中的字符也不匹配。
(4) 不在给定集合中的任意字符
正如前面所见的，能够使要匹配的字符集中不包括单个字符很有用，这点可由用元字符表
示“非”或解集合的互补运算来做到。例如，在逻辑中表示“非”的标准字符是波形符“ ~”，
那么表示字母表中非a 字符的正则表达式就是~ a。非a、b 及c 表示为：
~ ( a | b | c )
在L e x中使用的表示法是在连结中使用插入符“^”和上面所提的字符类来表示互补。例如，
2 8 编译原理及实践
下载
任何非a 的字符可写作[ ^ a ]，任何非a、b 及c 的字符则写作：
[ ^ a b c ]
(5) 可选的子表达式
有关串的最后一个常见的情况是在特定的串中包括既可能出现又可能不出现的可选部分。
例如，数字前既可有一个诸如+或-的先行符也可以没有。这可用解来表示，同在正则定义中
是一样的：
natural = [0-9]+
signedNatural = natural | + natural | - n a t u r a l
但这会很快变得麻烦起来，现在引入问号元字符r?来表示由r 匹配的串是可选的（或显示r 的0
个或1个拷贝）。因此上面那个先行符号的例子可写成：
natural = [0-9]+
signedNatural= (+|-)? n a t u r a l
2.2.3 程序设计语言记号的正则表达式
在众多不同的程序设计语言中，程序设计语言记号可分为若干个相当标准的有限种类。第
1类是保留字的，有时称为关键字（ k e y w o r d），它们是语言中具有特殊含意的字母表字符的固
定串。例如：在P a s c a l、C和A d a语言中的i f、w h i l e和d o。另一个范围由特殊符号组成，它
包括算术运算符、赋值和等式。它们可以是一单个字符，如=，也可是多个字符如： =或+ +。
第3种由标识符（ i d e n t i f i e r）组成，它们通常被定义为以字母开头的字母和数字序列。最后一
种包括了文字（l i t e r a l）或常量（c o n s t a n t），如数字常量4 2和3 . 1 4 1 5 9，如串文字“hello, world,”，
及字符“a”和“ b”。在这里仅讨论一下它们的典型正则表达式以及与记号识别相关的问题，
本章后面还会更详细地谈到实际识别问题。
1) 数数可以仅是数字（自然数）、十进制数、或带有指数的数（由e 或E 表示）的序列。
例如：2 . 7 1 E - 2表示数. 0 2 7 1。可用正则定义将这些数表示如下：
nat = [0-9]+
signedNat = (+|-)? n a t