六、使用正則表達式構造詞法分析器

判斷一個字符串是否屬于某規則的算法介紹到這里就結束了?；氐轿覀円婚_始的問題上，我們需要使用一些規則來吧一個長的字符串斷開成記號，然后計算出每一個記號對應的規則。在解決這個問題之前，我們先考察一下能夠成功地被詞法分析器接受的字符串應該是什么樣子的。

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

首先按照上文的方法，把每一個記號類型對應的規則的正則表達式轉換成DFA，然后使用并聯的方法將他們組合起來，但是并不使用“重復”。但是這次我們要做一點修改，我們要把新的DFA的每一個狀態對應的規則的DFA狀態集合記住。

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

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

N：[0-9]+

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

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

按照規則構造出四個DFA并將它們組合起來：

 

圖6.1

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

舉個例子，使用上述狀態機分析”123.ABC”。

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

為什么我們在構造狀態機的時候不使用“重復”呢？因為在每一個記號被識別出的時候，我們都要做一些額外的工作。如果我們使用“重復”來構造詞法分析器的狀態機，我們將無從知道一個記號被識別出來的確切時間。

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

假如我們的詞法分析器有A和B兩個狀態，那么我們構造詞法分析器A|B的時候，將會得到一些包含DFA(A)和DFA(B)的結束狀態的新狀態。我們只需要檢查這些狀態是否具有以下特征，就可以判斷A和B的關系。我們假設DFA(A)為規則A的狀態機，DFA(B)為規則B的狀態機，DFA(L)為詞法分析器A|B的狀態機：

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

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

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

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

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

假設詞法分析器包含以下規則：

A：”if”

B：[a-z]+

對A|B構造DFA，我們將會得到如下狀態機：

七、尾聲

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

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

參考文獻

【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