或寫作
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