26 编译原理及实践 China-pub.com 下载 是：的优先权最低，连结次之，*则最高。另外还注意到在这个定义中，6个符号一一中、、 卜*、（和）都有了元字符的含义。 本节后面将给出一些示例来详述上述定义，但它们并不经常作为记号描述在程序设计语言 中出现。2.2.3节将讨论一些经常作为记号在程序设计语言中出现的常用正则表达式。 在下面的示例中，被匹配的串通常是英语描述，其任务是将描述翻译为正则表达式。包含 了记号描述的语言手册是编译器的程序员最常见的。偶尔还需要变一下，也就是将正则表达式 翻译为英语描述，我们也有一些此类的练习。 例2.1在仅由字母表中的3个字符组成的简单字母表Σ={a,b,c}中，考虑在这个字母表上的仅 包括一个b的所有串的集合，这个集合由正则表达式 (alc)*b(alc)* 产生。尽管b出现在正则表达式的正中间，但字母b却无需位于被匹配的串的正中间。实际上， 在b之前或之后的a或c的重复会发生不同的次数。因此，串b、abc、abaca、baaaac、ccbaca 和ccccccb都与上面的正则表达式匹配 例22在与上面相同的字母表中，如果集合是包括了最多一个b的所有串，则这个集合的正则 表达式可通过将上例的解作为一个解（与那些仅为一个b的串匹配），而正则表达式(a|c)* 则作为另一个解（与b根本不匹配）来获取。因此有以下解： (alc)*l (alc)*b(alc)* 下面是一个既允许b又允许空串在重复的a或c之间出现的另一个解： (alc)*(blE)(alc)* 本例引出了正则表达式的一个重要问题：不同的正则表达式可生成相同的语言。虽然在实际中 从未尝试着证实已找到了“最简单的”，例如最短的，正则表达式，但通常总是试图用尽可能 简单的正则表达式来描述串的集合。这里有两个原因：首先在现实中极少有标准的“最短的” 解：其次，在研究用作识别正则表达式的方法时，那儿的算法无需首先将正则表达式简化就可 将识别过程简化了。 例2.3在字母表∑={a,b}上的串S的集合是由一个b及在其前后有相同数目的a组成 S=b.aba.aabaa,aaabaaa....=a'bdn 正则表达式并不能描述这个集合，其原因在于重复运算只有闭包运算*一种，它允许有任意次 的重复。因此加要写出表达式aa★（尽可能接折地得到S的正则表达式），就不能保证在方前 后的的数量是否相等了，它通常表示为“不能计算的正则表达式”。但若要给出一个数学论 证，则需使用有关正则表达式的称作Pumping引理(Pumping lemma)的著名定理，这将在自 动机理论中学到，现在就不谈了。 很明显，并非用简单术语描述的所有串都可由正则表达式产生，因此为了与其他集合相区 分，作为正则表达式语言的串集合称作正则集合(regular set)。非正则集合偶尔也作为串出现 在需要由扫描程序识别的程序设计语言中，通常是在出现时才处理它们，我们也将其放在扫描 程序一节中讨论。 例2.4在字母表∑={a,b,c;上的串S中，任意两个b都不相连，所以在任何两个b之间都至 少有一个a或c。可分几步来构造这个正则表达式，首先是在每一个b后都有一个a或c,它 写作：
是：｜的优先权最低，连结次之， * 则最高。另外还注意到在这个定义中， 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, . . . } = { a n b a n | 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 编译原理及实践 下载
China-pub.com 第2章词法分析 27 下载 (b(alc))* 将其与表达式(a1c)*合并，(a1c)*是与完全不包含b的串匹配，则写作： ((alc)*1(b(ala))*) 或考虑到(x*1s*)*与(x1s)*所匹配的串相同，则： ((ale)l (b(ale)))+ 或 (alelbalbe)t (警告！这还不是正确答案)。 这个正则表达式产生的语言实际上具有了所需的特性，即：没有两个相连的b(但这还不正 确)。有时需要证明一下上面的这个说法，也就是证明在L(a1cIba1bc)*)中的所有串都不包 括两个相连的。该证明是通过对串长度（即串中字符数）的归纳实现的。很显然，它对于所有 长度为0、1和2的串是正确的：这些串实际是串e、a、c、aa、ac、ca、cc、ba和bc。现在假设 对于在长度i<n的语言中的所有串也为真，并令s是长度为n>2的语言中的一个串，那么5包 含了至少一个上面所列的非e的串，所以s=55,其中，和5，也是语言中的非e串 ,通过假设归 纳，证明了5，和5，都没有两个相连的b。因此要使s本身包括两个相连的b的唯一方法是使5以 一个b结尾，而，以一个开头。但又因为语言中的串都不以b结尾，所以这是不可能的。 论证中的最后一个事实，即由上面的正则表达式所产生的串都不以b结尾，也显示了我们 的解还不太正确：它不产生串b、ab和cb,这3个都不包括两个相连的b。可以通过为其添加 个可选的结尾b来修改它，如下所示 (alclbalbe)*(bl) 这个正则表达式的镜像也生成了指定的语言： (blE)(alclablcb)* 以下也可生成相同的语言： (notblb notb)*(bIE) 其中otb=ac。这是一个使用了下标表达式名字的例子。由于无需将原表达式变得更复杂就 可使0b的定义调整为包括了除b以外的所有字符，因此实际是在字母表较大时使用这个解。 例2.5本例给出了 一个正则表达式，要求用英语简要地描述它生成的语言。若有字母表 {a,bc},则正则表达式： ((blc)*a (blc)ta)+(blc)+ 生成了所有包括偶数个α的串的语言。为了看清它，可考虑外层左重复之中的表达式： (blc)*a(ble)*a 它生成的串是以a结尾且包含了两个a(在这两个a之前或之间可有任意个b和c)。重复这些串 则得到所有以a结尾的串，且a的个数是2的倍数（即偶数）。在最后附加重复(b1c)*(如前 例所示)则得到所需结果。 这个正则表达式还可写作： (nota*a nota a)*nota* 2.2.2正则表达式的扩展 前面已给出了正则表达式的一个定义，这个正则表达式使用了在所有应用程序中都常见到
( 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 = s 1 s 2，其中s 1 和s 2 也是语言中的非 串。通过假设归 纳，证明了s 1 和s 2 都没有两个相连的b。因此要使s 本身包括两个相连的b 的唯一方法是使s 1 以 一个b 结尾，而s 2 以一个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 下载
28 编译原理及实践 China-pub.C 下载 运算的最小集合，而且使上面的示例仅限于使用3种基本运算（包括括号）。但是从以上这些示 例中可看出仅利用这些运算符来编写正则表达式有时显得很笨拙，如果可用一个更有表达力的 运算集合，那么创律的正则表达式就会更复杂一些。例如，使任章字符的匹配具有一个表示法 很有用（我们现在须在一个长长的解中列出字母表中的每个字符）。除此之外，拥有字符范围 的正则表达式和除单个字符以外所有字符的正则表达式都十分有效。 下面几段文字将描述前面所讨论的标准正则表达式的一些扩展情况，以及与它及类似情况 相对应的新元符号。在大多数情况下并不存在通用术语，所以使用的是与在扫描程序生成器 Lex中用到的类似的表示法，本章后面将会讲到Lex。实际上，以后要谈到的很多情况都会在 对Lx的讨论中再次提到。并非所有使用正则表达式的应用程序都包括这些运算，即使是这样 也要用到不同的表示法。 下面是新坛算的列表 ()一个或多个重复 假若有一个正则表达式，r的重复是通过使用标准的闭包运算来描述，并写作r*。它允许 被重复0次或更多次。0次并非是最典型的情况， 一次或多次才是，这就要求至少有一个串四 配，但空串ε却不行。例如在自然数中需要有一个数字序列，且至少要出现一个数字。如要匹 配二进制数，就写作(011)*，它同样也可匹配不是一个数的空串。当然也可写作 (011)(011) 但是这种情况只出现在用+代替的这个相关的标准表示法被开发之前：x+表明”的一个或 多个重复。因此，前面的二进制数的正则表达式可写作： 《011)+ (②)任意字符 为字母表中的任意字符进行匹配需要一个通常状况：无需特别运算，它只要求字母表中 的每个字符都列在一个解中。句号“”表示任意字符匹配的典型元字符，它不要求真正将字 母表写出来。利用这个元字符就可为所有包含了至少一个b的串写出一个正则表达式，如下 所示： .b. (3)字符范围 我们经常需要写出字符的范围，例如所有的小写字母或所有的数字。直到现在都是在用表 示法a1b1.,,1z来表示小写字母，用0111，，19来表示数字。还可针对这种情况使用一个 特殊表示法，但常见的表示法是利用方括号和一个连字符，如【a-z】是指所有小写字母，【0 9]则指数字。这种表示法还可用作表示单个的解，因此alblci可写成[abc】,它还可用于多 个范围，如【a-zA-z]代表所有的大小写字母。这种普遍表示法称为字符类(character class)。 例如，【A-z]是假设位于A和Z之间的字符B、C等（一个可能的假设）且必须只能是A和Z之间 的大写字母(ASCI字符集也可)。但[A-z]则与[A-za-z】中的字符不匹配，甚至与ASCII字 符集中的字符也不匹配。 (④不在给定集合中的任意字符 正如前面所见的，能够使要匹配的字符集中不包括单个字符很有用，这点可由用元字符表 示“非”或解集合的互补运算来做到。例如，在逻辑中表示“非”的标准字符是波形符“ 那么表示字母表中非a字符的正则表达式就是~a。非a、b及c表示为： 在Lx中使用的表示法是在连结中使用插入符“”和上面所提的字符类来表示互补。例如
运算的最小集合，而且使上面的示例仅限于使用 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 编译原理及实践 下载
China-pub.com 第2章词法分析 29 下载 任何非a的字符可写作【^a],任何非a、b及c的字符则写作： 【abc】 (⑤可选的子表达式 有关串的最后一个常见的情况是在特定的串中包括既可能出现又可能不出现的可选部分： 例如，数字前既可有一个诸如+或-的先行符也可以没有。这可用解来表示，同在正则定义中 是一样的： natura.1=【0-9]+ signedNaturaF naturalI natural-natural 但这会很快变得麻烦起来，现在引入问号元字符r?来表示由r匹配的串是可选的（或显示r的0 个或1个拷贝)。因此上面那个先行符号的例子可写成： natura1=【0-9】+ signedNatura(+I-)?natural 2.2.3程序设计语言记号的正则表达式 在众多不同的程序设计语言中，程序设计语言记号可分为若干个相当标准的有限种类。第 1类是保留字的，有时称为关键字(keyword),它们是语言中具有特殊含意的字母表字符的固 定串。例如：在Pascal、.C和Ada语言中的if、while和do。另一个范围由特殊符号组成，它 包括算术运算符、赋值和等式。它们可以是一单个字符，如=，也可是多个字符如：=或++。 第3种由标识符(identifier)组成，它们通常被定义为以字母开头的字母和数字序列。最后 种包括了文字(literal)或常量(constant),如数字常量42和3.14159，如串文字“hello,world,”, 及字符“”和“b”。在这里仅讨论一下它们的典型正则表达式以及与记号识别相关的问题， 本章后面还会更详细地谈到实际识别问题。 1)数数可以仅是数字（自然数）、十进制数、或带有指数的数（由或E表示）的序列。 例如：2.71E-2表示数.0271。可用正则定义将这些数表示如下： nat=【0-9】+ signedNat=(+-?nat number=signedNat("."nat (E signedNat)? 此处，在引号中用了一个十进制的点来强调它应直接匹配且不可被解释为一个元字符。 2)保留字和标识符正则表达式中最简单的就是保留字了，它们由字符的固定序列表示。 如果要将所有的保留字收集到一个定义中，就可写成： reserved=if I while I do I... 相反地，标识符是不固定的字符串。通常，标识符必须由一个字母开头且只包含字母和数 字。可用以下的正则定义表示： 1 etter=【a-zA-2】 d1a1t=[0-9】 identifier=letter (letterl digit)* 3)注释注释在扫描过程中一般是被忽略的⊙。然而扫描程序必须识别注释并舍弃它们。 因此尽管扫描程序可能没有清晰的常量记号（可将其称为“伪记号pseudotoken'”),仍需要给 注释编写出正则表达式。注释可有若干个不同的格式。通常，它们可以是前后为分隔符的自由 日它们有时可包括编译目录
任何非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 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 下载 它们有时可包括编译目录
30 编译原理及实践 China-pub.com 载 格式，例如： this is a Pascal comment /t this is a c comment/ 或由一个或多个特殊字符开头并直到该行的结尾，如在 this is a Scheme comment this is an Ada comment 中。 为有单个字符的分隔符的注释如Pascal注释)编写正则表达式并不难，且为那些从行的特 殊字符到行尾编写正则表达式也不难。例如Pascal注释可写作： 其中，用~}表示“非)”，并假设字符1作为元字符没有意义（在Lx中的表示与之不同，本章 后面将会提到)。类似地， 个Ada注释可被正则表达式 --《new11ne)★ 匹配。其中，假设newline匹配一行的末尾（在许多系统中可写作\n),“-”字符作为元字符没 有意义，该行的结尾并未包括在注释本身之中(2.6节将谈到如何在Lx中书写它)。 为同C注释一样，其中的分隔符如多于一个字符时，则编写正则表达式就要困难许多。例 如串集合ba.(没有ab).ab(用ba.ab代替C的分隔符/1，这是因为星号，有时还有 前斜杠要求特殊处理的元字符)。不能简单地写作： ba(-(ab))tab 由于“非”运算通常限制为只能是单个字符而不能使用字符串。可尝试用~a、b和~(aIb)为 ~(ab)写出一个定义来，但这却没有多大用处。其中的一个解是。 bt(at-(a1b)bt)★a 然而这很难读取（且难证明是正确的）。因此，C注释的正则表达式是如此之难以至于在实际 中几乎从未编写过。实际上，这种情况在真正的扫描程序中经常是通过特殊办法解决的，本章 后面将会提到它。 最后，在识别注释时会遇到的另一个复杂的问题是：在一些程序设计语言中，注释可被嵌 套。例如Modula-2允许格式注释： (this is (ta Modula-2 +comment + 在这种嵌套注释中，注释分隔符必须成对出现，故以下注释在Moda-2中是不正确的： (this is (illegal in Modula-2 + 注释的嵌套要求扫描程序计算分隔符的数量，但我们又注意到在例2.3(2.2.1节)中，正则 表达式不能表示计数操作。实际上，一个简单的计算器配置可作为这个问题的特殊解（参见 练习) 4)二义性、空白格和先行在程序设计语言记号使用正则表达式的描述中，有一些串经 常可被不同的正则表达式匹配。例如：诸如1E和whi1的串可以既是标识符又可以是关键 字。类似地，串<>可解释为表示两个记号(“小于号”和“大于号”)或一单个符号(“不等 于”)。程序设计语言定义必须规定出应遵守哪个解释，但正则表达式本身却无法做到它。相 反地，语言定义必须给出无二义性规则(disambiguating rules),由其回答每一种情况下的 含义。 下面给出处理示例的两个典型规则。首先当串既可以是标识符也可以是关键字时，则通常 认为它是关键字。这暗示着使用术语保留字(reserved word),其含义只是关键字不能同时也
格式，例如： { 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 编译原理及实践 下载