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個單獨的轉換非常麻煩，所以這是定義的
一個便利的擴展。本章后面還會用到這個定義的擴展。