遞歸下降語法分析器

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

使用遞歸下降法編寫語法分析器無需任何類庫，編寫簡單的分析器時甚至連前面學(xué)習的詞法分析庫都無需使用。我們來看一個例子：現(xiàn)在有一種表示二叉樹的字符串表達式，它的文法是：

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

注意

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

其中內(nè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)難倒了不少參加面試的候選人。不知在座各位是否對寫出這段程序有信心呢？不少參選者想到了要用棧，或者用遞歸，去尋找逗號的位置將字符串拆解開來等等方法。但是若是使用遞歸下降法，這個程序?qū)懫饋矸浅Ｈ菀住?/p>

一般步驟：

使用一個索引來記錄當前掃描的位置。通常將它做成一個整數(shù)字段。

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

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

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

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

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

class BinaryTreeParser
{
    private string m_inputString;
    private int m_index;

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

    Node ParseNode()
    {
        
    }
}

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

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

如果超前查看遇到逗號、右括號預(yù)測分支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("語法錯誤");
    }
}

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

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++; //解析左括號，因為不需要使用它的值，所以直接跳過

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

        m_index++; //解析逗號，跳過

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

        m_index++; //解析右括號，跳過

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

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

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

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

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

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

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

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

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