遞歸下降語(yǔ)法分析器

用java語(yǔ)言編寫的遞歸下降語(yǔ)法分析器，是一種適合手寫語(yǔ)法編譯器的方法，且非常簡(jiǎn)單。遞歸下降法對(duì)語(yǔ)言所用的文法有一些限制，但遞歸下降是現(xiàn)階段主流的語(yǔ)法分析方法，因?yàn)樗�可以由開發(fā)人員高度控制，在提供錯(cuò)誤信息方面也很有優(yōu)勢(shì)。就連微軟C#官方的編譯器也是手寫而成的遞歸下降語(yǔ)法分析器。

使用遞歸下降法編寫語(yǔ)法分析器無(wú)需任何類庫(kù)，編寫簡(jiǎn)單的分析器時(shí)甚至連前面學(xué)習(xí)的詞法分析庫(kù)都無(wú)需使用。我們來(lái)看一個(gè)例子：現(xiàn)在有一種表示二叉樹的字符串表達(dá)式，它的文法是：

其中終結(jié)符a表示任意一個(gè)英文字母，ε表示空。這個(gè)文法的含義是，二叉樹的節(jié)點(diǎn)要么是空，要么是一個(gè)字母開頭，并帶有一對(duì)括號(hào)，括號(hào)中逗號(hào)左邊是這個(gè)節(jié)點(diǎn)的左兒子，逗號(hào)右邊是這個(gè)節(jié)點(diǎn)的右兒子。例如字符串 A(B(,C(,)),D(,))就表示這樣一棵二叉樹：

注意

文法規(guī)定節(jié)點(diǎn)即使沒(méi)有兒子（兒子是空），括號(hào)和逗號(hào)也是不可省略的，所以只有一個(gè)節(jié)點(diǎn)的話也要寫成A(,)。現(xiàn)在我們要寫一個(gè)解析器，輸入這種字符串，然后在內(nèi)存中建立起這棵二叉樹。

其中內(nèi)存中的二叉樹是用下面這樣的類來(lái)表示的：

class Node
{
    public Node LeftChild { get; private set; }
    public Node RightChild { get; private set; }
    public char Label { get; private set; }

    public Node(char label, Node left, Node right)
    {
        Label = label;
        LeftChild = left;
        RightChild = right;
    }
}

這是一道微軟面試題，曾經(jīng)難倒了不少參加面試的候選人。不知在座各位是否對(duì)寫出這段程序有信心呢？不少參選者想到了要用棧，或者用遞歸，去尋找逗號(hào)的位置將字符串拆解開來(lái)等等方法。但是若是使用遞歸下降法，這個(gè)程序?qū)懫饋?lái)非常容易。

一般步驟：

使用一個(gè)索引來(lái)記錄當(dāng)前掃描的位置。通常將它做成一個(gè)整數(shù)字段。

為每個(gè)非終結(jié)符編寫一個(gè)方法。

如果一個(gè)非終結(jié)符有超過(guò)一個(gè)的產(chǎn)生式，則在這個(gè)方法中對(duì)采用哪個(gè)產(chǎn)生式進(jìn)行分支預(yù)測(cè)。

處理單一產(chǎn)生式時(shí)，遇到正確終結(jié)符則將第一步創(chuàng)建的掃描索引位置向前移動(dòng)；如遇到非終結(jié)符則調(diào)用第二步中創(chuàng)建的相應(yīng)方法。

如果需要產(chǎn)生解析的結(jié)果（比如本例中的二叉樹），在方法返回之前將它構(gòu)造出來(lái)。

我們馬上來(lái)試驗(yàn)一下。首先建立一個(gè)類，然后存放一個(gè)索引變量來(lái)保存當(dāng)前掃描位置。然后要為每一個(gè)非終結(jié)符創(chuàng)建一個(gè)方法，我們的文法中只有一個(gè)非終結(jié)符N，所以只需創(chuàng)建一個(gè)方法：

class BinaryTreeParser
{
    private string m_inputString;
    private int m_index;

    //初始化輸入字符串和索引的構(gòu)造函數(shù)，略

    Node ParseNode()
    {
        
    }
}

回到剛才的產(chǎn)生式，我們看到非終結(jié)符N有兩個(gè)產(chǎn)生式，所以在ParseNode方法的一開始我們必須做出分支預(yù)測(cè)。分支預(yù)測(cè)的方法是超前查看（look ahead）。就是說(shuō)我們先“偷窺”當(dāng)前位置前方的字符，然后判斷應(yīng)該用哪個(gè)產(chǎn)生式繼續(xù)分析。非終結(jié)符N的兩個(gè)產(chǎn)生式其中一個(gè)會(huì)產(chǎn)生a(N, N)這個(gè)的結(jié)構(gòu)，而另一個(gè)則直接產(chǎn)生空字符串。那現(xiàn)在知道，起碼有一種可能就是會(huì)遇到一個(gè)字母，這時(shí)候應(yīng)該采用N → a(N, N)這個(gè)產(chǎn)生式繼續(xù)分析。那么什么時(shí)候應(yīng)該采用N → ε進(jìn)行分析呢？我們觀察產(chǎn)生式右側(cè)所有出現(xiàn)N的地方，倘若N是空字符串，那么N后面的字符就會(huì)直接出現(xiàn)，也就是逗號(hào)和右括號(hào)。于是這就是我們的分支預(yù)測(cè)：

如果超前查看遇到英文字母，預(yù)測(cè)分支N → a(N, N)

如果超前查看遇到逗號(hào)、右括號(hào)預(yù)測(cè)分支N → ε

轉(zhuǎn)化成代碼就是這樣：

Node ParseNode()
{
    int lookAheadIndex = m_index;

    char lookAheadChar = m_inputString[lookAheadIndex];

    if (Char.IsLetter(lookAheadChar))
    {
        //采用N → a(N, N)繼續(xù)分析
    }
    else if (lookAheadChar == ',' || lookAheadChar == ')' )
    {
        //采用N → ε繼續(xù)分析
    }
    else
    {
        throw new Exception("語(yǔ)法錯(cuò)誤");
    }
}

接下來(lái)我們分別來(lái)看兩個(gè)分支怎么處理。先來(lái)看N → ε，這種情況下非終結(jié)符是個(gè)空字符串，所以我們不需要移動(dòng)當(dāng)前索引，直接返回null表示空節(jié)點(diǎn)。再來(lái)看N → a(N, N) 分支，倘若輸入的字符串沒(méi)有任何語(yǔ)法錯(cuò)誤，那就應(yīng)該依次遇到字母、左括號(hào)、N、逗號(hào)、N右括號(hào)。根據(jù)上面的規(guī)則，凡是遇到終結(jié)符，就移動(dòng)當(dāng)前索引，直接向前掃描；而要是遇到非終結(jié)符，就遞歸調(diào)用相應(yīng)節(jié)點(diǎn)的方法。所以（不考慮語(yǔ)法錯(cuò)誤）的完整方法代碼如下：

Node ParseNode()
{
    int lookAheadIndex = m_index;

    char lookAheadChar = m_inputString[lookAheadIndex];

    if (Char.IsLetter(lookAheadChar))
    {
        //采用N → a(N, N)繼續(xù)分析
        char label = m_inputString[m_index++]; //解析字母
        m_index++; //解析左括號(hào)，因?yàn)椴恍枰�使用它的值，所以直接跳過(guò)

        Node left = ParseNode(); //非終結(jié)符N，遞歸調(diào)用

        m_index++; //解析逗號(hào)，跳過(guò)

        Node right = ParseNode(); //非終結(jié)符N，遞歸調(diào)用

        m_index++; //解析右括號(hào)，跳過(guò)

        return new Node(label, left, right);
    }
    else if (lookAheadChar == ',' || lookAheadChar == ')')
    {
        //采用N → ε繼續(xù)分析
        //無(wú)需消耗輸入字符，直接返回null
        return null;
    }
    else
    {
        throw new Exception("語(yǔ)法錯(cuò)誤");
    }
}

因?yàn)榇嬖谡Z(yǔ)法約束，所以一旦我們完成了分支預(yù)測(cè)，就能清楚地知道下一個(gè)字符或非終結(jié)符一定是什么，無(wú)需再進(jìn)行任何判斷（除非要進(jìn)行語(yǔ)法錯(cuò)誤檢查）。因此根本就不需要尋找逗號(hào)在什么位置，我們解析到逗號(hào)時(shí)，逗號(hào)一定就在那，這種感覺是不是很棒？只需要寥寥幾行代碼就已經(jīng)寫出了一個(gè)完整的Parser。大家感興趣可以繼續(xù)補(bǔ)全一些輔助代碼，然后用真正的字符串輸入試驗(yàn)一下，是否工作正常。前面假設(shè)輸入字符串的語(yǔ)法是正確的，但真實(shí)世界的程序總會(huì)寫錯(cuò)，所以編譯器需要能夠幫助檢查語(yǔ)法錯(cuò)誤。在上述程序中加入語(yǔ)法錯(cuò)誤檢查非常容易，只要驗(yàn)證每個(gè)位置的字符，是否真的等于產(chǎn)生式中規(guī)定的終結(jié)符就可以了。這就留給大家做個(gè)練習(xí)吧。

上面我們采用的分支預(yù)測(cè)法是“人肉觀察法”，編譯原理書里一般都有一些計(jì)算FIRST集合或FOLLOW集合的算法，可以算出一個(gè)產(chǎn)生式可能開頭的字符，這樣就可以用自動(dòng)的方法寫出分支預(yù)測(cè)，從而實(shí)現(xiàn)遞歸下降語(yǔ)法分析器的自動(dòng)化生成。ANTLR就是用這種原理實(shí)現(xiàn)的一個(gè)著名工具。有興趣的同學(xué)可以去看編譯原理書。其實(shí)我覺得“人肉觀察法”在實(shí)踐中并不困難，因?yàn)榫幊陶Z(yǔ)言的文法都特別有規(guī)律，而且我們天天用編程語(yǔ)言寫代碼，都很有經(jīng)驗(yàn)了。

下面我們要研究一下遞歸下降法對(duì)文法有什么限制。首先，我們必須要通過(guò)超前查看進(jìn)行分支預(yù)測(cè)。支持遞歸下降的文法，必須能通過(guò)從左往右超前查看k個(gè)字符決定采用哪一個(gè)產(chǎn)生式。我們把這樣的文法稱作LL(k)文法。這個(gè)名字中第一個(gè)L表示從左往右掃描字符串，這一點(diǎn)可以從我們的index變量從0開始遞增的特性看出來(lái)；而第二個(gè)L表示最左推導(dǎo)，想必大家還記得上一篇介紹的最左推導(dǎo)的例子。大家可以用調(diào)試器跟蹤一遍遞歸下降語(yǔ)法分析器的分析過(guò)程，就能很容易地感受到它的確是最左推導(dǎo)的（總是先展開當(dāng)前句型最左邊的非終結(jié)符）。最后括號(hào)中的k表示需要超前查看k個(gè)字符。如果在每個(gè)非終結(jié)符的解析方法開頭超前查看k個(gè)字符不能決定采用哪個(gè)產(chǎn)生式，那這個(gè)文法就不能用遞歸下降的方法來(lái)解析。比如下面的文法：

當(dāng)我們編寫非終結(jié)符E的解析方法時(shí)，需要在兩個(gè)E產(chǎn)生式中進(jìn)行分支預(yù)測(cè)。然而兩個(gè)E產(chǎn)生式都以F開頭，而且F本身又可能是任意長(zhǎng)的表達(dá)式，無(wú)論超前查看多少字符，都無(wú)法判定到底應(yīng)該用乘號(hào)的產(chǎn)生式還是除號(hào)的產(chǎn)生式。遇到這種情況，我們可以用提取左公因式的方法，將它轉(zhuǎn)化為L(zhǎng)L(k)的文法：

我們將一個(gè)左公因式F提取出來(lái)，然后將剩下的部分做成一個(gè)新的產(chǎn)生式G。在解析G的時(shí)候，很容易進(jìn)行分支預(yù)測(cè)。而解析E的時(shí)候則無(wú)需再進(jìn)行分支預(yù)測(cè)了。在實(shí)踐中，提取左公因式不僅可以將文法轉(zhuǎn)化為L(zhǎng)L(k)型，還能有助于減少重復(fù)的解析，提高性能。

下面我們來(lái)看LL(k)文法的第二個(gè)重要的限制——不支持左遞歸。所謂左遞歸，就是產(chǎn)生式產(chǎn)生的第一個(gè)符號(hào)有可能是該產(chǎn)生式本身的非終結(jié)符。下面的文法是一個(gè)直截了當(dāng)?shù)淖筮f歸例子：

這個(gè)表達(dá)式類似于我們上篇末尾得到的無(wú)歧義二元運(yùn)算符的文法。但這個(gè)文法存在左遞歸：E產(chǎn)生的第一個(gè)符號(hào)就是E本身。我們想像一下，如果在編寫E的遞歸下降解析函數(shù)時(shí)，直接在函數(shù)的開頭遞歸調(diào)用自己，輸入字符串完全沒(méi)有消耗，這種遞歸調(diào)用就會(huì)變成一種死循環(huán)。所以，左遞歸是必須要消除的文法結(jié)構(gòu)。解決的方法通常是將左遞歸轉(zhuǎn)化為等價(jià)的右遞歸形式：

大家應(yīng)該牢牢記住這個(gè)例子，這不僅僅是個(gè)例子，更是解除大部分左遞歸的萬(wàn)能公式！我們將要在編寫miniSharp語(yǔ)法分析器的時(shí)候一次又一次地用到這種變換。