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

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

N → ε

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

注意

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

其中內存中的二叉樹是用下面這樣的類來表示的：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;

}

}

這是一道微軟面試題，曾經難倒了不少參加面試的候選人。不知在座各位是否對寫出這段程序有信心呢？不少參選者想到了要用棧，或者用遞歸，去尋找逗號的位置將字符串拆解開來等等方法。但是若是使用遞歸下降法，這個程序寫起來非常容易。

一般步驟：

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

為每個非終結符編寫一個方法。

如果一個非終結符有超過一個的產生式，則在這個方法中對采用哪個產生式進行分支預測。

處理單一產生式時，遇到正確終結符則將第一步創建的掃描索引位置向前移動；如遇到非終結符則調用第二步中創建的相應方法。

如果需要產生解析的結果(比如本例中的二叉樹)，在方法返回之前將它構造出來。

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

{

private string m_inputString;

private int m_index;

//初始化輸入字符串和索引的構造函數，略

Node ParseNode()

{

}

}

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

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

如果超前查看遇到逗號、右括號預測分支N → ε

轉化成代碼就是這樣：Node ParseNode()

{

int lookAheadIndex = m_index;

char lookAheadChar = m_inputString[lookAheadIndex];

if (Char.IsLetter(lookAheadChar))

{

//采用N → a(N, N)繼續分析

}

else if (lookAheadChar == ',' || lookAheadChar == ')' )

{

//采用N → ε繼續分析

}

else

{

throw new Exception("語法錯誤");

}

}

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

{

int lookAheadIndex = m_index;

char lookAheadChar = m_inputString[lookAheadIndex];

if (Char.IsLetter(lookAheadChar))

{

//采用N → a(N, N)繼續分析

char label = m_inputString[m_index++]; //解析字母

m_index++; //解析左括號，因為不需要使用它的值，所以直接跳過

Node left = ParseNode(); //非終結符N，遞歸調用

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

Node right = ParseNode(); //非終結符N，遞歸調用

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

return new Node(label, left, right);

}

else if (lookAheadChar == ',' || lookAheadChar == ')')

{

//采用N → ε繼續分析

//無需消耗輸入字符，直接返回null

return null;

}

else

{

throw new Exception("語法錯誤");

}

}

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

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

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

F → ( E )

E → F * F

E → F / F

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

F → ( E )

G → * F

G → / FE → FG

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

下面我們來看LL(k)文法的第二個重要的限制——不支持左遞歸。所謂左遞歸，就是產生式產生的第一個符號有可能是該產生式本身的非終結符。下面的文法是一個直截了當的左遞歸例子：F → id

E → E + F

E → F

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

E → FG

G → + FG

G → ε

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

總結

以上是生活随笔為你收集整理的Java递归下降分析器_递归下降语法分析器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。