可配置語法分析器開發紀事（六）——構造一個真正能用的狀態機（下）

上一篇文章對大部分文法都構造出了一個使用的狀態機了，這次主要來講右遞歸的情況。右遞歸不像左遞歸那么麻煩，因為大部分右遞歸寫成循環也不會過分的讓語法樹變得難以操作，不過仍然有少數情況是我們仍然希望保留遞歸的語法樹形狀，譬如C++的連等操作，因此這里就來講一下這個問題。

右遞歸是怎么形成的呢？在這里我們先不想這個問題，我們來看一個普通的文法。在上一篇文章我們已經說過了，如果一條文法有一個非終結符引用了另一條文法，那么就要做一條shift和reduce來從這個狀態機穿插到那個狀態機上：

在這里需要講一下，綠色的箭頭是shift，紫色的箭頭是reduce，他們都是ε邊。更進一步說，如果A剛好以B作為結尾，那么A的最后一個輸入就不是終結符輸入，不過因為她不是右遞歸，所以現在看起來還沒什么問題：

我們已經接近右遞歸的形狀了。右遞歸的一個根本特征當然是遞歸（廢話）。為了制作一個右遞歸，我們可以想一下，如果A和B不是兩個rule而是同一個rule會怎么樣？當然咋這么一看，好像就是A可以訪問自己了：

實際上這已經構成了一個ε邊的循環。左遞歸是shift的循環，右遞歸是reduce的循環，其實他們都一樣。那你可能會想，既然左遞歸和右遞歸只是相反的情況，為什么左遞歸處理起來就那么容易，右遞歸好像就沒什么方法呢？其實如果你只是想要檢查一個字符串是不是一個文法的其中一個元素而不建立語法樹的話，你完全可以把這條循環的ε reduce邊給壓縮成一條。為什么呢？在之前講到，我們可以判斷一個reduce是不是由左遞歸造成的，我們也可以判斷一個shift是不是由右遞歸造成的。這種shift只要不壓狀態進棧，那么右遞歸的reduce循環不管循環多少次，其實都是pop一個狀態出來，于是問題就沒有了。等價地，不處理語法樹的話，其實左遞歸也可以用相同的方法處理。

但是一旦當你涉及到創建語法樹的問題，你就等于給每一條邊都加上了一些semantic actions。這個時候shift和reduce就不是簡單地可以互相抵消的關系了，于是你就不能把一個循環的ε reduce邊壓縮成一條，那怎么辦呢？

方法其實很簡單，只要我們在狀態機走著走著發現無路可走的時候，看看有沒有一條右遞歸reduce可以給我們“試一試”就好了。為什么可以這樣做呢？我們還記得，當我們把整個狀態及壓縮到沒有ε邊的時候，每一個輸入都需要對堆棧的情況進行一次匹配。令人欣慰的事，沒有什么邊可以跟右遞歸的reduce邊一樣產生同樣的匹配結構（但是我不想在這里證明），所以這樣做是安全的。

到了這里，我們已經把構造不帶lookahead狀態機的所有情況都說清楚了。一個文法如果需要構造lookahead的話，其實就等于在邊的匹配規則里面加上一條對未來的一些token的要求，并沒有本質上改變語法分析的結構。但是我們知道，還有兩種上下文無關文法是不在這里面的，C語言全占了。我在這里舉兩個簡單的例子：

變量聲明：對于一個已經typedef過的結構我們完全可以寫出這樣的代碼：A*B;。這個時候A如果是類型，那這就需要走VariableDeclarationStatement的rule。如果A是一個表達式，那這就需要走ExpressionStatement的rule。但是對于語法分析來說，A就是一個簡單的token（除了typedef過的類型以外，所有C語言的類型都是以關鍵字開頭的，所以如果你們想做簡單的C語言的parser，就去掉typedef吧，啊哈哈哈哈），在語法分析的時候是無法做出預測的。

這種時候有兩種方法，第一種是準備更加豐富的semantic actions，讓符號表可以在parse的時候構造出來。那到了這里，我們根據A究竟是不是一個類型，就可以賺到不同的分支上了。另一種就是，我們保留一個AmbiguousStatement的語法樹節點，把語法樹的一顆子樹遇到的不能處理的歧義的情況都寫進去。我們可能回想，為什么我們不干脆一個parser返回多個分析結果呢？因為如果不這么做的話，一個函數里面有10個這樣子的變量聲明，那你就有1024個結果了。如果我們把歧義收縮到一顆子樹上，那其實還是1個結果，只是多了10顆子樹，效果完全不同。

強制類型轉換：寫C語言的時候是不可能沒有強制類型轉換的，但是當parser看到類似這樣的代碼的時候：(A*****)B，因為類型的結構和表達式的結構是不一樣的，但是你這個時候并不能在看到“(”的時候就做lookahead——因為這個lookahead是無限長的，括號里面的表達式或者類型都可以無限長。不過就算你想把他局限成有限長，就算你給100個token，那也會長出成千上萬種lookahead的模式，所以在這里我們就不要用lookahead了。

那怎么做呢？我們只需要把這個狀態機當成NDA（因為到了這里他已經是NDA了），從deterministic push-down automaton變成了non-deterministic push-down automaton，我們也唯有讓我們的parser也變成non-deterministic了。關于這個內容，就等到下一篇——也就是這個系列的最后一篇文章——來詳細講解了。