在介紹如何進(jìn)行詞法分析之前，先來說說一個(gè)不怎么被提及的問題——怎么從源文件中讀取字符流。為什么這個(gè)問題這么重要呢？是因?yàn)樵谠~法分析中，對(duì)字符流是有要求的，它必須能夠支持回退操作（就是將多個(gè)字符放回到流中，以后會(huì)再次被讀?。?。

先來解釋下為什么需要支持回退操作，舉個(gè)簡(jiǎn)單的例子來說，現(xiàn)在要對(duì)兩個(gè)模式進(jìn)行匹配：

圖 1 流的回退過程

上面是一個(gè)簡(jiǎn)單的匹配過程，僅為了展示回退過程，在后面實(shí)現(xiàn) DFA 模擬器時(shí)會(huì)詳細(xì)解釋是如何匹配詞素的。

現(xiàn)在來看看 C# 中與輸入相關(guān)的類，有 Stream，它支持流的查找，但是只能以字節(jié)方式訪問；BinaryReader 和 TextReader 雖然支持讀取字符，但是又不能支持回退。所以，就必須自己完成這個(gè)輸入緩沖類了，大致思路就是以 TextReader 作為底層的字符輸入，然后由自己的類完成對(duì)回退能力的支持。

《編譯原理》上給出了一種緩沖區(qū)對(duì)的方法，簡(jiǎn)單的說就是開辟兩個(gè)緩沖區(qū)，設(shè)緩沖區(qū)大小都是 N 個(gè)字符。每一次都將 N 個(gè)字符讀入到緩沖區(qū)中，并在這個(gè)緩沖區(qū)上實(shí)現(xiàn)字符操作。如果當(dāng)前緩沖區(qū)的數(shù)據(jù)已經(jīng)處理完畢，就將 N 個(gè)新字符讀入到另一個(gè)緩沖區(qū)中，接下來就換做操作新的緩沖區(qū)。

這樣的數(shù)據(jù)結(jié)構(gòu)效率很高，而且只要維護(hù)合適的指針，就可以很容易的實(shí)現(xiàn)回退功能。不過它的緩沖區(qū)大小是固定的，新讀入的字符會(huì)覆蓋舊的字符。如果需要回退的字符數(shù)量過多（比如在分析很長(zhǎng)的字符串時(shí)），就容易出現(xiàn)錯(cuò)誤。我通過使用多個(gè)緩沖區(qū)解決了舊字符被覆蓋的問題——如果緩沖區(qū)不足了，就開辟新緩沖區(qū)，而不是覆蓋舊數(shù)據(jù)。

如果僅僅是不斷的添加緩沖區(qū)，那么占用的內(nèi)存只會(huì)不斷增加，這樣是沒有什么意義的，因此我定義了三個(gè)釋放緩沖區(qū)的操作：Drop，Accept 和 AcceptToken。Drop 的作用是將當(dāng)前位置之前的所有數(shù)據(jù)標(biāo)記為無效（被拋棄），被標(biāo)記無效的數(shù)據(jù)占用的緩沖區(qū)就被釋放掉，可以拿來被重復(fù)利用了；Accept 則會(huì)將標(biāo)記為無效的數(shù)據(jù)以字符串形式返回，而不僅僅是簡(jiǎn)單的拋棄；類似的，AcceptToken 是以 Token 形式返回被無效化的數(shù)據(jù)，是為了方便進(jìn)行詞法分析。

這樣的數(shù)據(jù)結(jié)構(gòu)比較類似于 STL 中的 deque，不過這里不需要隨機(jī)訪問和插入、刪除數(shù)據(jù)，僅會(huì)在數(shù)據(jù)的頭、尾進(jìn)行操作，因此我直接將多個(gè)緩沖區(qū)使用雙向鏈表連成一個(gè)環(huán)，使用三個(gè)指針 current，first 和 last 指向鏈表中有數(shù)據(jù)的緩沖區(qū)，如下圖所示：

圖 2 多個(gè)緩沖區(qū)組成的鏈表，紅色的部分表示有數(shù)據(jù)，白色的部分沒有數(shù)據(jù)

其中，first 指向的是最早的數(shù)據(jù)緩沖區(qū)，last 指向的是最新的數(shù)據(jù)緩沖區(qū)，current 指向的是當(dāng)前正在訪問的數(shù)據(jù)緩沖區(qū)，current 總是在 [first, last] 范圍之內(nèi)。firstIndex 和 lastLen 之間紅色的部分，就是包含有效數(shù)據(jù)的緩沖區(qū)，idx 表示當(dāng)前正在訪問的字符。白色的部分表示空緩沖區(qū)，或是緩沖區(qū)中的數(shù)據(jù)已無效。

當(dāng)需要讀取下一個(gè)字符時(shí)，就從 current 中依次讀取數(shù)據(jù)，并將 idx 后移。如果 current 中的數(shù)據(jù)已經(jīng)讀取完畢，則將 current 移向 last（這里用移向，是因?yàn)?current 和 last 之間可能有多個(gè)緩沖區(qū)），同時(shí) idx 也要相應(yīng)的移動(dòng)。

圖 3 current 移向 last

如果需要繼續(xù)讀取字符，但是 current 中沒有新數(shù)據(jù)了，而此時(shí) current 已經(jīng)與 last 相同，表示緩沖區(qū)中已經(jīng)沒有更新的數(shù)據(jù)，那么就需要從 TextReader 中讀取數(shù)據(jù)，放到新的緩沖區(qū)中，同時(shí)后移 current 和 last（需要保證 last 總是指向最新的緩沖區(qū)）。

圖 4 current 和 last 向后移

現(xiàn)在來看看回退操作。進(jìn)行回退時(shí)，只需要將 current 向 first 的方向移動(dòng)（同樣，current 和 first 之間可能有多個(gè)緩沖區(qū)）。

圖 5 回退操作

Drop 操作（Accept 和 AcceptToken 也同理）的實(shí)現(xiàn)也很簡(jiǎn)單，只需要將 first 移動(dòng)到 current 位置，將 firstIndex 移動(dòng)到 idx 即可，這就表示 idx 之前的數(shù)據(jù)都看作無效數(shù)據(jù)。

圖 6 Drop 操作

這里需要注意的就是，Drop 操作完成后，被無效化的數(shù)據(jù)就有可能會(huì)被新數(shù)據(jù)覆蓋，因此應(yīng)該確定數(shù)據(jù)不再需要時(shí)再執(zhí)行 Drop 操作。Drop 操作的效率很高（移動(dòng)兩個(gè)引用），基本不用擔(dān)心會(huì)影響效率。

使用這種環(huán)形數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)是除了將字符填充到緩沖區(qū)之外，完全避免了數(shù)據(jù)的額外復(fù)制，無論是前進(jìn)、回退還是 Drop 操作都只有指針（引用）操作，效率很高。當(dāng) Drop 比較及時(shí)時(shí)，僅會(huì)使用兩個(gè)緩沖區(qū)，不會(huì)額外的占用內(nèi)存。當(dāng)占用的緩沖區(qū)過多時(shí)，還能夠?qū)崿F(xiàn)主動(dòng)釋放多余的內(nèi)存（這里現(xiàn)在沒有考慮）。

缺點(diǎn)就是實(shí)現(xiàn)起來會(huì)復(fù)雜些，需要仔細(xì)處理好 first、current 和 last 的關(guān)系，以及 firstIndex、index 和 lastLen 范圍限制，有時(shí)還會(huì)涉及到多個(gè)緩沖區(qū)的操作。

完整的代碼可見 SourceReader.cs。

在對(duì)源代碼進(jìn)行解析的時(shí)候，記錄每個(gè) Token 對(duì)應(yīng)的行號(hào)和列號(hào)顯然是很必要的工作，沒有人會(huì)喜歡面對(duì)一大堆 Error，而且還偏偏不告訴你到底是哪錯(cuò)了……因此，我認(rèn)為代碼定位絕對(duì)是詞法分析必備的功能，所以直接把這個(gè)功能內(nèi)置到了 SourceReader 類中了。

下面來說明如何實(shí)現(xiàn)代碼定位。代碼定位包含三維數(shù)據(jù)：索引、行號(hào)和列號(hào)。索引是從 0 開始的字符索引，主要是方便程序進(jìn)行處理；行號(hào)和列號(hào)則都是從 1 開始的，主要是為了人去看。

行定位比較簡(jiǎn)單，Unix 的換行符是 '\n'，Windows 的換行符是 "\r\n"，所以直接統(tǒng)計(jì) '\n' 的個(gè)數(shù)即可。

接下來是列定位。為了達(dá)到比較好的效果，需要考慮兩個(gè)因素：全角、半角字符和 Tab 字符。

一個(gè)中文字符（即全角字符）對(duì)應(yīng)的是兩列，英文字符（半角字符）對(duì)應(yīng)的則是一列，這樣在等寬字體下，每一列都是上下對(duì)齊的。在計(jì)算列數(shù)的時(shí)候，自然也應(yīng)當(dāng)如此，使用 Encoding.Default.GetByteCount() 而不是字符串的長(zhǎng)度。不過這里我發(fā)現(xiàn)了一個(gè)內(nèi)存問題（詳情參考這里），改用 Encoding.Default.GetEncoder() 的 GetByteCount 方法就可以了。

一個(gè) Tab 字符的長(zhǎng)度是不定的（一般是為 4 或 8，因人而異），所以定義了一個(gè) TabSize 來表示 Tab 字符的寬度。那么，一個(gè) Tab 字符就對(duì)應(yīng) TabSize 列么？并不是這樣的，雖然一般看來是這樣，但事實(shí)上，Tab 字符是讓下一字符對(duì)應(yīng)的列總是為 TabSize 的整數(shù)倍再加 1。如果 TabSize = 4，那么它的行為如下圖所示，其中 a 和 bcc 后面都是有兩個(gè) Tab 字符，bcccccc 和 bccccccc 后面都是有一個(gè) Tab 字符，每個(gè) Tab 字符我都用灰色箭頭標(biāo)出來了。

圖 7 Tab 字符實(shí)例

所以，實(shí)際的列號(hào)應(yīng)當(dāng)使用下面的公式計(jì)算，其中 currentCol 是 Tab 字符所在的列，nextCol 就是下一字符所在的列：

nextCol = tabSize * (1 + (currentCol - 1) / tabSize) + 1;

代碼定位的計(jì)算方法有了，然后就是計(jì)算的時(shí)機(jī)。如果每次 Read 的時(shí)候都計(jì)算當(dāng)前字符的位置，一是計(jì)算效率會(huì)略低，因?yàn)?GetByteCount 方法中，一次性計(jì)算較長(zhǎng)一個(gè)字符數(shù)組的效率，差不多是多次計(jì)算長(zhǎng)度為 1 的字符數(shù)組的一倍。二是回退的時(shí)候應(yīng)該怎么辦？如果將之前的位置計(jì)算結(jié)果都保存起來，內(nèi)存占用會(huì)是一個(gè)問題，如果不考慮的話，又無法根據(jù)當(dāng)前字符的位置推算出前一個(gè)字符的位置（比如當(dāng)前字符在第一列的話，前一個(gè)字符應(yīng)該在第幾列？）。

綜合考慮之后，我決定將代碼位置的計(jì)算放到 Drop 操作（Accept 和 AcceptToken 也一樣）中，一個(gè)是向上面所說的，計(jì)算效率會(huì)略高，另一個(gè)是一般僅當(dāng)識(shí)別出了一個(gè) Token 后才需要為它定位，此時(shí)恰好是 Drop 或 AcceptToken 的時(shí)機(jī)，識(shí)別 Token 的過程中就是定位了也沒有什么用處。

我將代碼定位的功能單獨(dú)封裝到了 SourceLocator.cs 類中。

下一篇將會(huì)介紹詞法分析中用到的正則表達(dá)式，以及如何解析正則表達(dá)式。

最新評(píng)論