上一篇文章對(duì)大部分文法都構(gòu)造出了一個(gè)使用的狀態(tài)機(jī)了，這次主要來(lái)講右遞歸的情況。右遞歸不像左遞歸那么麻煩，因?yàn)榇蟛糠钟疫f歸寫成循環(huán)也不會(huì)過(guò)分的讓語(yǔ)法樹變得難以操作，不過(guò)仍然有少數(shù)情況是我們?nèi)匀幌ＭＡ暨f歸的語(yǔ)法樹形狀，譬如C++的連等操作，因此這里就來(lái)講一下這個(gè)問(wèn)題。

右遞歸是怎么形成的呢？在這里我們先不想這個(gè)問(wèn)題，我們來(lái)看一個(gè)普通的文法。在上一篇文章我們已經(jīng)說(shuō)過(guò)了，如果一條文法有一個(gè)非終結(jié)符引用了另一條文法，那么就要做一條shift和reduce來(lái)從這個(gè)狀態(tài)機(jī)穿插到那個(gè)狀態(tài)機(jī)上：

在這里需要講一下，綠色的箭頭是shift，紫色的箭頭是reduce，他們都是ε邊。更進(jìn)一步說(shuō)，如果A剛好以B作為結(jié)尾，那么A的最后一個(gè)輸入就不是終結(jié)符輸入，不過(guò)因?yàn)樗皇怯疫f歸，所以現(xiàn)在看起來(lái)還沒(méi)什么問(wèn)題：

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

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

但是一旦當(dāng)你涉及到創(chuàng)建語(yǔ)法樹的問(wèn)題，你就等于給每一條邊都加上了一些semantic actions。這個(gè)時(shí)候shift和reduce就不是簡(jiǎn)單地可以互相抵消的關(guān)系了，于是你就不能把一個(gè)循環(huán)的ε reduce邊壓縮成一條，那怎么辦呢？

方法其實(shí)很簡(jiǎn)單，只要我們?cè)跔顟B(tài)機(jī)走著走著發(fā)現(xiàn)無(wú)路可走的時(shí)候，看看有沒(méi)有一條右遞歸reduce可以給我們“試一試”就好了。為什么可以這樣做呢？我們還記得，當(dāng)我們把整個(gè)狀態(tài)及壓縮到?jīng)]有ε邊的時(shí)候，每一個(gè)輸入都需要對(duì)堆棧的情況進(jìn)行一次匹配。令人欣慰的事，沒(méi)有什么邊可以跟右遞歸的reduce邊一樣產(chǎn)生同樣的匹配結(jié)構(gòu)（但是我不想在這里證明），所以這樣做是安全的。

到了這里，我們已經(jīng)把構(gòu)造不帶lookahead狀態(tài)機(jī)的所有情況都說(shuō)清楚了。一個(gè)文法如果需要構(gòu)造lookahead的話，其實(shí)就等于在邊的匹配規(guī)則里面加上一條對(duì)未來(lái)的一些token的要求，并沒(méi)有本質(zhì)上改變語(yǔ)法分析的結(jié)構(gòu)。但是我們知道，還有兩種上下文無(wú)關(guān)文法是不在這里面的，C語(yǔ)言全占了。我在這里舉兩個(gè)簡(jiǎn)單的例子：

變量聲明：對(duì)于一個(gè)已經(jīng)typedef過(guò)的結(jié)構(gòu)我們完全可以寫出這樣的代碼：A*B;。這個(gè)時(shí)候A如果是類型，那這就需要走VariableDeclarationStatement的rule。如果A是一個(gè)表達(dá)式，那這就需要走ExpressionStatement的rule。但是對(duì)于語(yǔ)法分析來(lái)說(shuō)，A就是一個(gè)簡(jiǎn)單的token（除了typedef過(guò)的類型以外，所有C語(yǔ)言的類型都是以關(guān)鍵字開(kāi)頭的，所以如果你們想做簡(jiǎn)單的C語(yǔ)言的parser，就去掉typedef吧，啊哈哈哈哈），在語(yǔ)法分析的時(shí)候是無(wú)法做出預(yù)測(cè)的。

這種時(shí)候有兩種方法，第一種是準(zhǔn)備更加豐富的semantic actions，讓符號(hào)表可以在parse的時(shí)候構(gòu)造出來(lái)。那到了這里，我們根據(jù)A究竟是不是一個(gè)類型，就可以賺到不同的分支上了。另一種就是，我們保留一個(gè)AmbiguousStatement的語(yǔ)法樹節(jié)點(diǎn)，把語(yǔ)法樹的一顆子樹遇到的不能處理的歧義的情況都寫進(jìn)去。我們可能回想，為什么我們不干脆一個(gè)parser返回多個(gè)分析結(jié)果呢？因?yàn)槿绻贿@么做的話，一個(gè)函數(shù)里面有10個(gè)這樣子的變量聲明，那你就有1024個(gè)結(jié)果了。如果我們把歧義收縮到一顆子樹上，那其實(shí)還是1個(gè)結(jié)果，只是多了10顆子樹，效果完全不同。

強(qiáng)制類型轉(zhuǎn)換：寫C語(yǔ)言的時(shí)候是不可能沒(méi)有強(qiáng)制類型轉(zhuǎn)換的，但是當(dāng)parser看到類似這樣的代碼的時(shí)候：(A*****)B，因?yàn)轭愋偷慕Y(jié)構(gòu)和表達(dá)式的結(jié)構(gòu)是不一樣的，但是你這個(gè)時(shí)候并不能在看到“(”的時(shí)候就做lookahead——因?yàn)檫@個(gè)lookahead是無(wú)限長(zhǎng)的，括號(hào)里面的表達(dá)式或者類型都可以無(wú)限長(zhǎng)。不過(guò)就算你想把他局限成有限長(zhǎng)，就算你給100個(gè)token，那也會(huì)長(zhǎng)出成千上萬(wàn)種lookahead的模式，所以在這里我們就不要用lookahead了。

那怎么做呢？我們只需要把這個(gè)狀態(tài)機(jī)當(dāng)成NDA（因?yàn)榈搅诉@里他已經(jīng)是NDA了），從deterministic push-down automaton變成了non-deterministic push-down automaton，我們也唯有讓我們的parser也變成non-deterministic了。關(guān)于這個(gè)內(nèi)容，就等到下一篇——也就是這個(gè)系列的最后一篇文章——來(lái)詳細(xì)講解了。