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