遞歸 - 詞法分析與語法分析的分界

一般來說使套，決定詞法分析和語法分析的界限是是否需要遞歸。
詞法分析是將輸入的符號流轉(zhuǎn)換成一個個獨(dú)立的token鞠柄。比如說侦高，996是個數(shù)值型或者更精確一些整型的token。
這個token解析的過程厌杜，它前面是什么符號奉呛，后面是什么符號，完全沒有關(guān)系夯尽。
token也不存在遞歸的可能性瞧壮，token之間相互獨(dú)立，不可能是嵌套的關(guān)系匙握。
所以咆槽，詞法分析可以用正則表達(dá)式來實(shí)現(xiàn)。只要一個串符合[0-9]+圈纺，我們就可以確定地認(rèn)為罗晕，這是一個整數(shù)。
詞法分析可以從左到右赠堵，完全線性的方式實(shí)現(xiàn)小渊。它不需要樹的結(jié)構(gòu)，自然沒有遞歸的需求茫叭。

而語法分析就有不同酬屉，比如一個表達(dá)式，它可能是"7 * 24"揍愁，也可能是"(8+1) * 5"呐萨，或者更復(fù)雜的組合。這樣的表達(dá)式就需要用一棵樹的結(jié)構(gòu)來表示莽囤。
比如我們這樣定義表達(dá)式：

表達(dá)式 = 數(shù)字
表達(dá)式 = 表達(dá)式 + 表達(dá)式
表達(dá)式 = 表達(dá)式 - 表達(dá)式

這樣谬擦，表達(dá)式"1+2+3+4"就可以表示成下圖這樣的一棵樹：

statement

自頂向下和自底向上

針對上面的圖，我們有兩種分析的辦法朽缎，一種是自頂向下惨远，一種是自底向上。

為了大家看起來方便话肖，我們不妨把上面的式子改成前綴表達(dá)式：

表達(dá)式 = 數(shù)字
表達(dá)式 = + 表達(dá)式 表達(dá)式
表達(dá)式 = - 表達(dá)式 表達(dá)式

自頂向下就是北秽，先掃描到一個"+"的token，然后分別對它后面的兩個token進(jìn)行分析最筒。第一個token是數(shù)字贺氓，不需要遞歸了。然后去看第二個表達(dá)式床蜘，發(fā)現(xiàn)還是一個"+"辙培，于是遞歸去分析+蔑水，以此類推。

總結(jié)起來扬蕊，自頂向下的思想是搀别，先預(yù)測是個什么，然后按照期待去找下一個token厨相。

而自底向上的思想不是這樣领曼，它是從左到右把token都讀進(jìn)來鸥鹉，然后去嘗試找目前已經(jīng)讀進(jìn)來的token們符合哪個式子的定義蛮穿。
以上面的例子為例：
第一步，讀到"+" 不符合上面三個式子的任何一個毁渗，繼續(xù)向右讀token践磅。這個過程叫做shift，中文譯成“移進(jìn)”灸异。
第二步府适，"+ 1"，數(shù)字1匹配了第一條肺樟，變成+ 表達(dá)式檐春，不能繼續(xù)匹配了，繼續(xù)讀token
第三步么伯，"+ 表達(dá)式 +"疟暖，什么鬼，不匹配田柔，繼續(xù)讀俐巴。
...
第五步，讀到"+ 表達(dá)式 + 表達(dá)式 +"硬爆，還是找不到可以匹配的式子欣舵，繼續(xù)向右讀。
...
第七步缀磕，讀到"+ 表達(dá)式 + 表達(dá)式 + 表達(dá)式 4"缘圈，4匹配了第一條，變成表達(dá)式袜蚕， "+ 表達(dá)式 表達(dá)式"匹配了第二條准验，也變成表達(dá)式。這種操作叫做“歸約”-reduce廷没。這一步歸約了"+ 3 4"
第八步糊饱，歸約"+2 表達(dá)式"
第九步，歸約"+1 表達(dá)式"

LR分析器

自底向上的方法的重要方法是LR方法颠黎，LR分析器的構(gòu)造一般如下圖所示：

LR分析

LR分析器是以一個狀態(tài)機(jī)的方向來運(yùn)作的另锋。
這其中有兩個重要的表：

• 一個是主要處理移進(jìn)的Action表
• 另一個是主要處理歸約的Goto表

Action表的輸入有兩項：

• 一是當(dāng)前的狀態(tài)滞项，從狀態(tài)棧頂可以取到；
• 另一個是輸入符號夭坪，可以從輸入串中取得文判。

Action表的輸出有4種情況：

• 移進(jìn)：這時候輸出一個移進(jìn)后的新狀態(tài)。輸入符號和新狀態(tài)壓入棧
• 歸約：這時候輸出一個歸約的表達(dá)式室梅。棧中的符號串戏仓，包括輸入符號和狀態(tài)，被替換成歸約后的新符號串亡鼠。這時候的要變成的狀態(tài)就要去Goto表中去查詢赏殃。輸入為歸約后的新符號串，也就是產(chǎn)生式的左端间涵，與這個符號串左邊的上一個狀態(tài)仁热，查出來之后，就是最新的狀態(tài)
• 接受：說明一次文法解析已經(jīng)完成勾哩，可以輸出語法分析樹了
• 出錯：走到了兩個表中查不到的狀態(tài)

我們看一個龍書上的例子抗蠢，構(gòu)造含有二元運(yùn)算符+和*的算術(shù)表達(dá)式的文法：

1. E -> E + T
2. E -> T
3. T -> T * F
4. T -> F
5. F -> (E)
6. F -> id

我把龍書上用符號表示的表用文字標(biāo)注上顏色，使大家更加容易記憶和理解思劳。
對應(yīng)的action表如下：

action table

goto表如下：

goto table

下面我們嘗試分析一下"id * id $".

1. 初始狀態(tài)是0. 輸入為id. 我們查0行id列的action表迅矛，是將id移進(jìn)棧，同時潜叛，狀態(tài)棧頂轉(zhuǎn)為5. 完成這一步后秽褒，棧中內(nèi)容[0 id 5]
2. 狀態(tài)5，輸入為钠导。查action表5行列震嫉，是使用公式6(F->id)進(jìn)行歸約。此時牡属，狀態(tài)5和id輸入票堵，都被從棧中歸約掉，變成F逮栅。這時的棧為[0 F]悴势，因為產(chǎn)生了歸約，所以要再去查goto表措伐，根據(jù)目前棧中的值特纤，去查0行F列，查到操作是轉(zhuǎn)到狀態(tài)3. 于是將3壓入棧中侥加，現(xiàn)在棧中的值是[0 F 3]
3. 狀態(tài)3下捧存，還是遇到剛才的輸入“*”。查action表，要做的是使用公式4(T->F)來歸約昔穴。同樣镰官，F(xiàn)和狀態(tài)3出棧，T入椔鸹酰∮具耄現(xiàn)在棧中的內(nèi)容是[0 T]，又產(chǎn)生了歸約宙搬，于是再查goto表笨腥，0行T列是轉(zhuǎn)到狀態(tài)2. 現(xiàn)在棧中的值是[0 T 2]
4. 狀態(tài)2下，剛才輸入的還在勇垛，繼續(xù)查表脖母。action表的2行列是移進(jìn)，下一狀態(tài)是7窥摄。終于把這個*移進(jìn)去了∠夥睿現(xiàn)在的棧中的內(nèi)容是：[0 T 2 * 7]
5. 狀態(tài)7下础淤，遇到id崭放。查action表，7行id列鸽凶，移進(jìn)币砂，下一狀態(tài)是5. 現(xiàn)在棧中內(nèi)容為：[0 T 2 * 7 id 5]
6. 狀態(tài)5下，遇到結(jié)束符$玻侥。查action表决摧，5行$列，歸約凑兰，使用公式6(F->id). id和狀態(tài)5出棧掌桩，F(xiàn)入棧」檬常現(xiàn)在的棧是[0 T 2 * 7 F]波岛，再去goto表中查7行F列，狀態(tài)為10音半。這一步的最終棧是：[0 T 2 * 7 F 10]
7. 狀態(tài)10下则拷，輸入還是$。查action表曹鸠，10行$列：使用公式3(T->T*F)歸約煌茬。請注意，除去狀態(tài)不計的話彻桃，[0 T 2 * 7 F 10]的值正是[T * F]坛善，于是將[T 2 * 7 F 10]全部出棧，將T入棧。歸約之后再查goto表眠屎，[0 T]笙纤，查0行T列，狀態(tài)是2. 這一步最終棧結(jié)果：[0 T 2]
8. 狀態(tài)2下组力，輸入還是$省容。查action表，歸約燎字，使用公式2(E -> T). T和2出棧腥椒，E入棧『蜓埽現(xiàn)在的棧為[0 E]笼蛛，再查goto表，0行E列蛉鹿，狀態(tài)為1滨砍。這一步最終結(jié)果是[0 E 1]
9. 狀態(tài)1下，輸入仍然是$沒變妖异。查action表惋戏，1行$列，接受他膳，解析成功响逢！

下面的問題就變成如何能夠構(gòu)造action表和goto表。LR下面的不同方法棕孙，就是如何生成這兩張表的過程舔亭。

子集構(gòu)造算法

子集構(gòu)造算法是將不確定的有窮自動機(jī)NFA轉(zhuǎn)換成確定的有窮自動機(jī)的算法。

從不確定的有窮自動機(jī)轉(zhuǎn)換成確定的有窮自動機(jī)的基本思想是將確定有窮自動機(jī)的一個狀態(tài)對應(yīng)于不確定有窮自動機(jī)的一個狀態(tài)集合蟀俊。

子集構(gòu)造算法

狀態(tài)集合初值為初始狀態(tài)的空閉包(ε-closure)钦铺，且不作標(biāo)記
while (狀態(tài)集合中還有未標(biāo)記的狀態(tài)T){
    標(biāo)記這個狀態(tài)T;
    for 每個輸入符號a in 輸入集合 {
        U = 空閉包(move(T,a));
        if(U不在狀態(tài)集合中){
            U添加到狀態(tài)集合中;
            U的狀態(tài)為未標(biāo)記;
        }
        Dtran[T,a]=U;
    }
}

其中，構(gòu)造子集算法使用到了求空閉包(ε-closure)的算法肢预。

求ε-closure的算法用人話講就是矛洞，從起點(diǎn)或者起點(diǎn)的集合，計算出走ε路徑可以到達(dá)的所有狀態(tài)误甚。我們可以把a(bǔ),b這些值理解為大于0的權(quán)值缚甩，而ε為權(quán)值為0. 求ε閉包的算法就是求從指定起點(diǎn)的權(quán)值之和為0的所有路徑的集合。

求ε-closure空閉包的算法

將T中所有的狀態(tài)壓入棧中; //這是所有的起點(diǎn)的集合
空閉包集合初始化為T; //清空棧
while (棧不空){
    棧頂元素t彈出棧; //取一個起點(diǎn)出來
    for 狀態(tài)u in 從t到u有一條標(biāo)記為ε的邊{ //起點(diǎn)和狀態(tài)之間有ε的邊
        if (u不在空閉包集合中){
            將u添加到空閉包集合中; //u是符合條件的值
            將u壓入棧中; //如果u下面還可以繼續(xù)傳導(dǎo)窑邦，后面還可以有ε的邊
        }
    }
}

我們看下面的龍書上的例子：

epsilon-closure

ε-closure(0)就是從0開始距離為ε的所有狀態(tài)擅威，直接跟0相連的有1和7。1又可以通達(dá)2冈钦，4. 所以ε-closure(0)為{0,1,2,4,7}

下面我們開始應(yīng)用到子集構(gòu)造算法的例子中：
初始狀態(tài)0的空閉包集合為{0,1,2,4,7}郊丛，我們用A來表示。
move({0,1,2,4,7},a) = {3,8}。這一步是從{0,1,2,4,7}厉熟，指定輸入為a時可以到達(dá)的狀態(tài)导盅，move(2,a)=3, move(7,a)=8，其他都不能到達(dá)揍瑟。
ε-closure({3,8})= {1,2,3,4,6,7,8}白翻，用B來表示.
move({1,2,3,4,6,7,8},a)={3,8},跟B重復(fù)
于是a的情況完成了，我們再遍歷輸入為b的情況绢片。
move({0,1,2,4,7},b)={5}
ε-closure({5})={1,2,4,5,6,7} = C
ε-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9} = D
ε-closure(move(C,a))=ε-closure({3,8}) = B
ε-closure(move(C,b))=ε-closure({5}) = C
ε-closure(move(D,a))=ε-closure({3,8}) = B
ε-closure(move(D,b))=ε-closure({5}) = C

最后生成的是這樣的狀態(tài)轉(zhuǎn)換圖：

state machine

SLR方法

拓廣文法

如果文法G的開始符號是S,那么文法G的拓廣文法G'是在G的基礎(chǔ)上增加一個新的開始符號S'和產(chǎn)生式S->S'滤馍。新產(chǎn)生式的目的是用做歸約的終點(diǎn)。

閉包運(yùn)算

閉包是：

• 初始項目集都是閉包的成員
• 如果A->α.Bβ在閉包中底循，且存在產(chǎn)生式B->γ, 若B->.γ不在閉包中巢株，則將其加入閉包。重復(fù)直至所有的產(chǎn)生式都加入到閉包中熙涤。

例：

E' -> E
E -> E+T | T
T -> T*F | F
F -> (E) | id

closure{[E' -> .E]}包含：

根據(jù)規(guī)則1阁苞，E' -> .E 本身在閉包里
根據(jù)規(guī)則2，
E -> .E+T
E -> .T
T -> .T*F
T -> .F
F -> .(E)
F -> .id

goto函數(shù)

我們終于開始看到如何生成goto函數(shù)了祠挫。
goto(I,X)函數(shù)的定義為A->αX.β的閉包那槽。

例：若I是兩個項目的集合{[E'->.E],[E->E.+T]},則goto(I,+)包括：

E -> E + .T
T -> .T + F
T -> .F
F -> .(E)
F -> .id

項目集的構(gòu)造算法

算法：

C = {closure([S'->.S])};
do{
    for 項目集I in C, 文法符號X in C {
        if(goto(I,X)!=nullptr && inC(goto(I,X))
        C.add(goto(I,X));
    }
}while(還有更多的項目可以加入C);

SLR語法分析表的構(gòu)造

算法：

1. 構(gòu)造G'的LR(0)項目集規(guī)范族。采用上面介紹的項目集構(gòu)造算法茸歧。C={I0,I1,I2,...}
2. 從Ii構(gòu)造狀態(tài)i倦炒，它的分析動作確定如下：
   2.1. 如果[A->α.aβ]在Ii中显沈，并且 goto(Ii,a)=Ij,則置action[i,a]為"移進(jìn)j",這里的a必須是終結(jié)符
   2.2. 如果[A->α.]在Ii中软瞎，則對FOLLOW(A)中的所有a恩静，置action[i,a]="歸約A->α"叹洲，這里的A不能是S'.
   2.3. 如果[S'->.S]在Ii中婶芭，則置action[i,$]為“接受”
3. 對所有的非終結(jié)符A大磺，使用下面的規(guī)則構(gòu)造狀態(tài)i的goto函數(shù)：如果goto(Ii,A)=Ij芙委，則goto[i,A]=j
4. 不能由2和3構(gòu)造出來的表項都置為出錯咬清。

構(gòu)造規(guī)范LR語法分析表

SLR對于某些情況是無法歸約的谢澈，我們可以通過重新定義項目洒嗤，把更多的信息并入狀態(tài)中院尔，變成[A->α.β,a], 其中A->α.β是產(chǎn)生式蜻展，a是終結(jié)符或$。
這樣的對象叫做LR(1)項目邀摆。

構(gòu)造LALR語法分析表

LALR是(look-ahead-LR)的縮寫纵顾。它的優(yōu)點(diǎn)是比LR(1)的分析表要小得多。

喬姆斯基的文法分類

我們先看個喬姆斯基文法分類的示例圖：

chmosky

類似于我們上面所講的生成式栋盹，可以對應(yīng)到喬姆斯基的文法分類上施逾。
關(guān)于終結(jié)符和非終結(jié)符，我們就不需要做嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)定義了吧。像數(shù)字一樣不能推導(dǎo)出其他式子的汉额，就是終結(jié)符曹仗。像表達(dá)式這樣可以繼續(xù)推導(dǎo)的就是非終結(jié)符。

喬姆斯基將文法分成4類：

• 0型文法：這種文法只有一種要求蠕搜，就是左邊的式子里有一個非終結(jié)符怎茫。直觀理解就是，總要有一個能推導(dǎo)的式子啊妓灌。
• 1型文法：在0型的基礎(chǔ)上遭居，要求右部的長度比左式長。這樣旬渠，推導(dǎo)的話可以越推越長俱萍，歸約的話可以越歸約越短。
• 2型文法：在1型的基礎(chǔ)上告丢，要求左部必須為非終結(jié)符枪蘑，不能有終結(jié)符。
• 3型文法：在2型的基礎(chǔ)上岖免，左部只能有一個單獨(dú)的非終結(jié)符岳颇。而右部更有嚴(yán)格的限制，必須全部是終結(jié)符颅湘，或者終結(jié)符只能連接一個非連接符话侧。