下載
第2章詞法分析
本章要點
. 掃描處理. 從正則表達式到D FA
. 正則表達式. TINY掃描程序的實現
. 有窮自動機. 利用L e x自動生成掃描程序
編譯器的掃描或詞法分析（ lexical analysis）階段可將源程序讀作字符文件并將其分為若
干個記號。記號與自然語言中的單詞類似：每一個記號都是表示源程序中信息單元的字符序列。
典型的有：關鍵字（ k e y w o r d），例如i f和w h i l e，它們是字母的固定串；標識符（ i d e n t i f i e r）
是由用戶定義的串，它們通常由字母和數字組成并由一個字母開頭；特殊符號（special symbol）
如算術符號+和*、一些多字符符號，如> = 和< >。在各種情況中，記號都表示由掃描程序從剩
余的輸入字符的開頭識別或匹配的某種字符格式。
由于掃描程序的任務是格式匹配的一種特殊情況，所以需要研究在掃描過程中的格式說明
和識別方法，其中最主要的是正則表達式（regular expression）和有窮自動機（finite automata）。
但是，掃描程序也是處理源代碼輸入的編譯器部分，而且由于這個輸入經常需要非常多的額
外時間，掃描程序的操作也就必須盡可能地高效了。因此還需十分注意掃描程序結構的實際
細節。
掃描程序問題的研究可分為以下幾個部分：首先，給出掃描程序操作的一個概貌以及所涉
及到的結構和概念。其次是學習正則表達式，它是用于表示構成程序設計語言的詞法結構的串
格式的標準表示法。接著是有窮狀態機器或稱有窮自動機，它是對由正則表達式給出的串格式
的識別算法。此外還研究用正則表達式構造有窮自動機的過程。之后再討論當有窮自動機表示
識別過程時，如何實際編寫執行該過程的程序。另外還有T I N Y語言掃描程序的一個完整的實
現過程。最后再看到自動產生掃描器生成器的過程和方法，并使用L e x再次實現T I N Y的掃描程
序，它是適用于U n i x和其他系統的標準掃描生成器。
2.1 掃描處理
掃描程序的任務是從源代碼中讀取字符并形成由編譯器的以后部分（通常是分析程序）處
理的邏輯單元。由掃描程序生成的邏輯單元稱作記號（ t o k e n），將字符組合成記號與在一個英
語句子中將字母構成單詞并確定單詞的含義很相像。此時它的任務很像拼寫。
記號通常定義為枚舉類型的邏輯項。例如，記號在C中可被定義為：
L在一種沒有列舉類型的語言中，則只能將記號直接定義為符號數值。因此在老版本的C中有時可看到：
#define IF 256
#define THEN 257
#define ELSE 258
. . .
(這些數之所以是從2 5 6開始是為了避免與A S C I I的數值混淆。)
typedef enum
{ IF, THEN, ELS，EPLUS, MINUS, NUM, ID, ...}
T o k e n T y p e ;
記號有若干種類型，這其中包括了保留字（ reserved word），如I F和T H E N，它們表示字符
串“ i f”和“ t h e n”；第2類是特殊符號（ special symbol ），如算術符號加（ P L U S）和減
（M I N U S），它們表示字符“ +”和“-”。第3類是表示多字符串的記號，如N U M和I D，它們分
別表示數字和標識符。
作為邏輯項的記號必須與它們所表示的字符串完全區分開來。例如：保留字記號I F須與
它表示的兩個字符“ i f”的串相區別。為了使這個區別更明顯，由記號表示的字符串有時稱作
它的串值（string value）或它的詞義（l e x e m e）。某些記號只有一個詞義：保留字就具有這個
特性。但記號還可能表示無限多個語義。例如標識符全由單個記號I D表示，然而標識符有許
多不同的串值來表示它們的單個名字。因為編譯器必須掌握它們在符號表中的情況，所以不能
忽略這些名字。因此，掃描程序也需用至少一些記號來構造串值。任何與記號相關的值都是記
號的屬性（ a t t r i b u t e），而串值就是屬性的示例。記號還可有其他的屬性。例如， N U M記號可有
一個諸如“3 2 7 6 7”的串值屬性，它是由5個數字字符組成，但它還會有一個由其值計算所得的
真實值3 2 7 6 7組成的數字值屬性。在諸如P L U S這樣的特殊符號記號中，不僅有串值“ +”還有
與之相關的真實算術操作+。實際上，記號符號本身就可看作是簡單的其他屬性，而記號就是
它所有屬性的總和。
為了后面的處理，掃描程序要求至少具有與記號所需相等的屬性。例如要計算N U M記號的
串值，但由于從它的串值就可計算，因此也就無需立刻計算它的數字值了。另一方面，如果計
算它的數字值，就會丟棄掉它的串值。有時掃描程序本身會完成在恰當位置記錄屬性所需的操
作，或直接將屬性傳到編譯器后面的階段。例如，掃描程序能利用標識符的串值將其輸入到符
號表中，或在后面傳送它。
由于掃描程序必須計算每一個記號的若干屬性，所以將所有的屬性收集到一個單獨構造的
數據類型中是很有用的，這種數據類型稱作記號記錄（ token record）。可在C中將這樣的記錄
說明為：
typedef struct
{ TokenType tokenval;
char * stringval;
int numval;
} TokenRecord;
或可能作為一個聯合
typedef struct
{ TokenType tokenval;
u n i o n
{ char * stringval;
int numval;
} attribute;
} TokenRecord;
（以上假設只有標識符需要串值屬性，只有數字需要數值屬性）。對于掃描程序一個更普通
的安排是只返回記號值并將變量的其他屬性放在編譯器的其他部分訪問得到的地方。
盡管掃描程序的任務是將整個源程序轉換為記號序列，但掃描程序卻很少一次性地完成它。
實際上，掃描程序是在分析程序的控制下進行操作的，它通過函數從輸入中返回有關命令的下
2 2 編譯原理及實踐
下載
一個記號，該函數有與C說明相似的說明：
TokenType getToken( void );
這個方式中聲明的g e t T o k e n函數在調用時從輸入中返回下一個記號，并計算諸如記號串值這
樣的附加屬性。輸入字符串通常并不給這個函數提供參數，但參數卻被保存在緩沖區中或由系
統輸入設備提供。
請考慮在g e t T o k e n的操作示例中以下的C源代碼行，在第1章中已用到過它：
a [ index ] = 4 + 2
假定將這個代碼行放在一個輸入緩沖區中，它的下一個輸入字符由箭頭指出，如下所示：
一個對g e t T o k e n的調用現在需要跳過下面的4個空格，識別由單個字符a 組成的串“a”，并返
回記號值I D作為下個記號，此時的輸入緩沖區如下所示：
因此，g e t T o k e n隨后的調用將再次從左括號字符開始識別過程。
現在開始研究在字符串中定義和識別格式的方法。
2.2 正則表達式
正則表達式表示字符串的格式。正則表達式r完全由它所匹配的串集來定義。這個集合稱
為由正則表達式生成的語言（ language generated by the regular expression），寫作L（r）。此處
的語言只表示“串的集合”，它與程序設計語言并無特殊關系（至少在此處是這樣的）。該語言
首先依賴于適用的字符集，它一般是A S C I I字符的集合或它的某個子集。有時該集比A S C I I字
符的集合更普通一些，此處集合的元素稱作符號（ s y m b o l）。這個正規符號的集合稱作字母表
（a l p h a b e t）并且常寫作希臘符號.（s i g m a）。
正則表達式r還包括字母表中的字符，但這些字符具有不同的含義：在正則表達式中，所
有的符號指的都是模式。在本章中，所有模式都是用黑體寫出以與作為模式的字符區分開來。
因此，a 就是一個作為模式的字符a。
最后，正則表達式r還可包括有特殊含義的字符。這樣的字符稱作元字符（ m e t a c h a r a c t e r）
或元符號（m e t a s y m b o l）。它們并不是字母表中的正規字符，否則當其作為元字符時就與作為
字母表中的字符時很難區分了。但是通常不可能要求這種排斥，而且也必須使用一個慣例來區
分元字符的這兩種用途。在很多情況下，它是通過使用可“關掉”元字符的特殊意義的轉義字
符（escape character）做到的。源代碼層一般是反斜杠和引號。如果轉義字符是字母表中的正
規字符，則請注意它們本身也就是元字符了。
2.2.1 正則表達式的定義
現在通過講解每個模式所生成的不同語言來描述正則表達式的含義。首先講一下基本正則
第2章詞法分析2 3
下載
表達式的集合（它是由單個符號組成），之后再描述從已有的正則表達式生成一個新的正則表達
式的運算。它同構造算術表達式的方法類似：基本的算術表達式是由數字組成，如4 3和2 . 5。算
術運算的加法和乘法等可用來從已有的表達式中產生新的表達式，如在43 * 2.5和43 * 2.5 + 1.4
中。
從它們只包括了最基本的運算和元符號這一方面而言，這里所講到的一組正則表達式都是
最小的，以后還會講得更深一些。
1) 基本正則表達式它們是字母表中的單個字符且自身匹配。假設a是字母表.中的任一字
符，則指定正則表達式a 通過書寫L (a) = {a}來匹配a字符。而特殊情況還要用到另外兩個字符。
有時需要指出空串（ empty string）的匹配，空串就是不包含任何字符的串。空串用( e p s i l o n )
來表示，元符號（黑體）是通過設定L( ) = { }來定義的。偶爾還需要寫出一個與任何串都
不匹配的符號，它的語言為空集（empty set），寫作{ }。我們用符號來表示，并寫作L( ) = {}。
請注意{ }和{ }的區別：{ }集不包括任何串，而{ }則包含一個沒有任何字符的串。
2) 正則表達式運算在正則表達式中有3種基本運算：① 從各選擇對象中選擇，用元字符|
（豎線）表示。②連結，由并置表示（不用元字符）。③重復或“閉包”，由元字符*表示。后面
通過為匹配了的串的語言提供相應的集合結構依次討論以上3種基本運算。
3) 從各選擇對象中選擇如果r 和s 是正則表達式，那么正則表達式r | s 可匹配被r 或s 匹
配的任意串。從語言方面來看，r | s 語言是r 語言和s 語言的聯合（u n i o n），或L (r | s) = L (r)
èL (s)。以下是一個簡單例子：正則表達式a | b匹配了a 或b 中的任一字符，即L (a | b) = L (a)
èL (b) = {a}è{b} = {a, b}。又例如表達式a | 匹配單個字符a 或空串（不包括任何字符），也
就是L (a | ) = {a, }。
還可在多個選擇對象中選擇，因此L (a | b | c | d) = { a, b, c, d} 也成立。有時還用點號表示
選擇的一個長序列，如a | b |...| z，它表示匹配a~z 的任何小寫字母。
4) 連結正則表達式r 和正則表達式s 的連結可寫作r s，它匹配兩串連結的任何一個串，其
中第1個匹配r，第2個匹配s。例如：正則表達式a b只匹配a b，而正則表達式( a | b ) c 則匹配
串ac 和b c（下面將簡要介紹括號在這個正則表達式中作為元字符的作用）。
可通過由定義串的兩個集合的連結所生成的語言來講解連結的功能。假設有串S1 和S2 的兩
個集合，串S1S2 的連結集合是將串S2 完全附加到串S1 上的集合。例如若S1 = {aa, b}, S2 = {a, bb}，
則S1S2 = { aaa, aabb, ba, bbb}。現在可將正則表達式的連結運算定義如下：L (r s) = L (r) L (s)，
因此（利用前面的示例），L (( a | b ) c) = L ( a | b ) L (c) = {a, b} {c} = {ac, bc}。
連結還可擴展到兩個以上的正則表達式：L (r1r2 ... rn ) = L (r1 ) L (r2 ) ... L (rn ) = 由將每一個
L (r1 ), ..., L (rn ) 串連結而成的串集合。
5) 重復正則表達式的重復有時稱為K l e e n e閉包（（Kleene) closure），寫作r *，其中r 是一
個正則表達式。正則表達式r * 匹配串的任意有窮連結，每個連結均匹配r。例如a *匹配串、a、
a a、a aa . . .（它與匹配是因為是與a匹配的非串連結）。通過為串集合定義一個相似運算*，
就可用生成的語言定義重復運算了。假設有一個串的集合S，則
S* = { } è S è SS è SSS è. . .
這是一個無窮集的聯合，但是其中的每一個元素都是S中串的有窮連結。有時集合S*可寫作：
其中Sn = S . . . S，它是S 的n 次連結（S0 = { }）。
現在可如下定義正則表達式的重復運算：
2 4 編譯原理及實踐
下載
L (r*) = L (r) *
例：在正則表達式(a | b b) * (括號作為元字符的原因將在后面解釋）中，該正則表達式與以
下串任意匹配： 、a、b b、a a、a b b、b b a、b b b b、a a a、aabb 等等。在語言方面，L (( a | b b ) *)
= L (a | b b)* = {a, bb}* = { , a, b b, a a, a b b, b b a, b b b b, a a a, a a b b, a b b a, a b b b b, b b a a, . . . }。
6) 運算的優先和括號的使用前面的內容忽略了選擇、連結和重復運算的優先問題。例如
對于正則表達式a | b *，是將它解釋為( a | b )* 還是a | ( b* ) 呢（這里有一個很大的差別，因
為L (( a | b )*) = { , a, b, aa, ab, ba, bb, . . . }，但L ( a | ( b* )) = { , a, b, bb, bbb, . . . } )？標準
慣例是重復的優先權較高，所以第2個解釋是正確的。實際上，在這3個運算中， *優先權最
高，連結其次，| 最末。因此，a | b c * 就可解釋為a | ( b ( c* )），而a b | c * d 卻解釋為( a b )
| (( c* ) d )。
當需指出與上述不同的優先順序時，就必須使用括號。這就是為什么用( a | b ) c 能表示
選擇比連結有更高的優先權的原因。而a | b c 則被解釋為與a 或bc 匹配。類似地，沒有括號的
( a | b b )* 應解釋為a | b b*，它匹配a、b、b b、b b b. . . 。此處括號的用法與其在算術中類似：
（3 + 4) * 5 =35，而3 + 4 * 5 = 23，這是因為* 的優先權比+ 的高。
7) 正則表達式的名字為較長的正則表達式提供一個簡化了的名字很有用處，這樣就不再
需要在每次使用正則表達式時書寫長長的表達式本身了。例如：如要為一個或多個數字序列寫
一個正則表達式，則可寫作：
( 0 | 1 | 2 | . . . | 9 ) ( 0 | 1 | 2 | . . . | 9 ) *