六、使用正則表達(dá)式構(gòu)造詞法分析器

判斷一個(gè)字符串是否屬于某規(guī)則的算法介紹到這里就結(jié)束了。回到我們一開始的問題上，我們需要使用一些規(guī)則來吧一個(gè)長的字符串?dāng)嚅_成記號(hào)，然后計(jì)算出每一個(gè)記號(hào)對(duì)應(yīng)的規(guī)則。在解決這個(gè)問題之前，我們先考察一下能夠成功地被詞法分析器接受的字符串應(yīng)該是什么樣子的。

假設(shè)我們現(xiàn)在有規(guī)則A、B、C和D，分別對(duì)應(yīng)于四種記號(hào)類型，那么被詞法分析器接受的字符串就是A、B、C和D的任意組合，也就是(A|B|C|D)*。如果規(guī)定了輸入的字符串不能為空的話，那么被詞法分析器接受的字符串就是(A|B|C|D)+。但是單純地使用(A|B|C|D)+作為一個(gè)規(guī)則去應(yīng)用在輸入的字符串的話，我們只能夠判斷字符串是否是詞法分析器能夠接受的字符串。因此我們需要對(duì)這個(gè)方法進(jìn)行修改。

首先按照上文的方法，把每一個(gè)記號(hào)類型對(duì)應(yīng)的規(guī)則的正則表達(dá)式轉(zhuǎn)換成DFA，然后使用并聯(lián)的方法將他們組合起來，但是并不使用“重復(fù)”。但是這次我們要做一點(diǎn)修改，我們要把新的DFA的每一個(gè)狀態(tài)對(duì)應(yīng)的規(guī)則的DFA狀態(tài)集合記住。

這里給出一個(gè)例子，我們假設(shè)需要一個(gè)簡單語言的詞法分析器，規(guī)則如下：

I：[a-zA-Z_][a-zA-Z_0-9]*

N：[0-9]+

R：[0-9]+.[0-9]+

O：[=>+-*/|&]

按照規(guī)則構(gòu)造出四個(gè)DFA并將它們組合起來：

 

圖6.1

我們構(gòu)造出了I|N|R|O的DFA，并且標(biāo)識(shí)出了哪些狀態(tài)包含了原DFA的結(jié)束狀態(tài)。這樣做的一個(gè)好處是，當(dāng)我們把一個(gè)字符串放進(jìn)這樣的一個(gè)DFA之后，我們就一直等待整個(gè)字符串被接受，或者失敗。如果字符串被接受的話，我們就把當(dāng)前的結(jié)束狀態(tài)記下來。如果失敗的話，我們就把這個(gè)狀態(tài)機(jī)在分析字符串的時(shí)候經(jīng)過的最后一個(gè)結(jié)束狀態(tài)記下來。這個(gè)時(shí)候，結(jié)束狀態(tài)所代表的原DFA結(jié)束狀態(tài)的相應(yīng)記號(hào)類型就是我們所需要的信息了。如果得不到任何結(jié)束狀態(tài)的話，輸入的字符串就是不背詞法分析其接受的。

舉個(gè)例子，使用上述狀態(tài)機(jī)分析”123.ABC”。

首先從狀態(tài)0開始，依次經(jīng)過狀態(tài)N N N 2，然后宣告失敗。最后一個(gè)N(結(jié)束狀態(tài))以及當(dāng)時(shí)被接受的字符串”123”被識(shí)別，結(jié)果為(N，”123”)。然后從”.ABC”開始，輸入第一個(gè)記號(hào)就失敗了，于是”.”被識(shí)別為不可接受字串。最后輸入”ABC”，依次經(jīng)過狀態(tài)0 1 I I，然后字符串結(jié)束并且被接受，于是輸出(I，”ABC”)。

為什么我們?cè)跇?gòu)造狀態(tài)機(jī)的時(shí)候不使用“重復(fù)”呢？因?yàn)樵诿恳粋€(gè)記號(hào)被識(shí)別出的時(shí)候，我們都要做一些額外的工作。如果我們使用“重復(fù)”來構(gòu)造詞法分析器的狀態(tài)機(jī)，我們將無從知道一個(gè)記號(hào)被識(shí)別出來的確切時(shí)間。

算法到這里基本上就結(jié)束了，不過還存在一些小問題需要在細(xì)節(jié)上解決。一般來說我們給出的一些構(gòu)成詞法分析器的規(guī)則很少有沖突，不過偶爾會(huì)出現(xiàn)兩個(gè)規(guī)則所代表的字符串集合存在交集的情況。有了DFA這個(gè)工具，我們可以很輕易地識(shí)別出規(guī)則沖突。

假如我們的詞法分析器有A和B兩個(gè)狀態(tài)，那么我們構(gòu)造詞法分析器A|B的時(shí)候，將會(huì)得到一些包含DFA(A)和DFA(B)的結(jié)束狀態(tài)的新狀態(tài)。我們只需要檢查這些狀態(tài)是否具有以下特征，就可以判斷A和B的關(guān)系。我們假設(shè)DFA(A)為規(guī)則A的狀態(tài)機(jī)，DFA(B)為規(guī)則B的狀態(tài)機(jī)，DFA(L)為詞法分析器A|B的狀態(tài)機(jī)：

1：如果DFA(L)存在一個(gè)或多個(gè)狀態(tài)同時(shí)包含了DFA(A)和DFA(B)的結(jié)束狀態(tài)，那么A和B所代表的字符串存在交集。

2：如果DFA(L)不存在同時(shí)包含了DFA(A)和DFA(B)的結(jié)束狀態(tài)的狀態(tài)，那么A和B所代表的字符串不存在交集。

3：如果DFA(L)的某些狀態(tài)包含了DFA(A)的結(jié)束狀態(tài)，并且這些狀態(tài)都無一例外地包含了DFA(B)的結(jié)束狀態(tài)的話，那么A是B的子集。

4：如果DFA(L)的某些狀態(tài)包含了DFA(A)的結(jié)束狀態(tài)，但是這些狀態(tài)并沒有無一例外地包含DFA(B)的結(jié)束狀態(tài)的話，那么A不是B的子集。

在圖6.1的詞法分析器中，我們可以很清楚地看出I、N、R和O四個(gè)規(guī)則兩兩之間都不存在交集。我們可以嘗試構(gòu)造一個(gè)沖突的規(guī)則，并看一看詞法分析器的DFA是什么樣子的：

假設(shè)詞法分析器包含以下規(guī)則：

A：”if”

B：[a-z]+

對(duì)A|B構(gòu)造DFA，我們將會(huì)得到如下狀態(tài)機(jī)：

七、尾聲

使用DFA的方法完成的可配置詞法分析器的性能是相當(dāng)好的。筆者前不久曾經(jīng)做過實(shí)驗(yàn)，首先使用本文提到的算法開發(fā)一個(gè)這樣的詞法分析器，然后在一份C++代碼(這份代碼經(jīng)過多次復(fù)制而成件，一共有3.12M)中抽取所有數(shù)字、標(biāo)識(shí)符和注釋，吞吐速度高達(dá)46萬記號(hào)/秒（筆者的臺(tái)式電腦配置是奔騰4的超線程2.99GHz處理器，1G內(nèi)存），其中抽取出來的記號(hào)一共有22萬個(gè)。在分析的過程中，只有10%的時(shí)間花在了DFA上，90%的時(shí)間花在了處理結(jié)果的工作上。DFA本身造成的消耗是很小的。不過詞法分析的性能在很大程度上跟DFA的實(shí)現(xiàn)有很大關(guān)系。三個(gè)月前筆者也實(shí)現(xiàn)過一個(gè)同類的程序，但是吞吐速度僅有1.1萬記號(hào)/秒。

一般來說，比較高性能的DFA的實(shí)現(xiàn)是一張二維的表。行代表字符，列代表DFA的狀態(tài)，單元格代表該狀態(tài)經(jīng)輸入某個(gè)字符之后進(jìn)行轉(zhuǎn)移的目標(biāo)狀態(tài)。此外還有一張表用來記錄哪些狀態(tài)對(duì)應(yīng)哪些規(guī)則的結(jié)束狀態(tài)。筆者的詞法分析器是基于UTF-16編碼的字符串，一張表一共有65535行顯然是不現(xiàn)實(shí)的，因此還有另一張表把字符轉(zhuǎn)換成字符類。字符類是這樣定義的：假設(shè)現(xiàn)在已經(jīng)存在了65535行的一張大表，如果在某個(gè)字符區(qū)間所對(duì)應(yīng)的子表內(nèi)，任意一列的單元格的數(shù)據(jù)都一樣的話，那么這個(gè)區(qū)間內(nèi)的所有字符就可以被視為是等價(jià)的，這些字符就屬于同一個(gè)字符類。于是僅需要另外一張65535個(gè)單元的表用來把一個(gè)字符映射到字符類。這種做法可以大大的壓縮DFA所需要的空間。在筆者的程序里，識(shí)別字符類的算法被融入了DFA的構(gòu)造算法中

參考文獻(xiàn)

【1】：Alfred V.Aho Ravi Sethi Jeffrey D.Ullman ，Compilers Principles , Techniques , and Tools

【2】：Dick Grune Ceriel Jacobs ，Parsing Techniques ---- A Practical Guide

【3】：Kenneth C.Louden ，Compiler Construction Principles and Practice