遞歸下降解析器

在計算機科學中，遞歸下降解析器是一種自上而下的解析器（英語：Top-down parsing），由一組相互遞歸的程序（或等價的非遞歸程序）構建而成，其中每個程序都實現了文法中的一個非終結符。因此，這些程序的結構密切反映了它所識別的文法結構。^[1]

預測性解析器是一種不需要回溯的遞歸下降解析器。^[2]預測性解析只適用於 LL(k) 文法。這是一種上下文無關文法。這種文法允許遞歸下降解析器僅通過檢測之後 k 個標記決定當前標記（token）所使用的生成規則（英語：Production (computer science)）。LL(k) 文法由此排除了所有包含歧義和左遞歸的文法。雖然任何一種上下文無關文法都可以轉化為沒有左遞歸的等效文法，但是去除了左遞歸卻不一定能夠得到 LL(k) 文法。預測性解析器能夠在線性時間內運行。

具有回溯的遞歸下降是一種通過依次嘗試生成規則來生成結果的技術。具有回溯的遞歸下降不限於 LL(k) 文法，但只在文法是 LL(k) 文法的情況下才保證能夠停機。具有回溯的遞歸下降對於其他文法即使能夠停機，也可能需要指數時間運行。

儘管預測性解析器被廣泛使用，也經常被選擇用於手工編寫解析器，但程式設計師通常更願意使用由文法解析器生成器^{[來源請求]}產生的基於表的解析器，無論是對於 LL(k) 語言還是使用替代解析器，比如 LALR 或 LR。如果一個文法不是 LL(k) 文法，情況尤其如此，因為要把文法轉化為 LL 形式，使其適合預測性解析。預測性解析器也可以使用 ANTLR 之類的工具自動生成。

預測性解析器可以用每個非終結符號的過渡圖來描述，其中初始狀態和最終狀態之間的界限由生成規則右側的符號（終結符和非終結符）來界定。^[3]

解析器例子

以下類似 EBNF 的文法（用於尼克勞斯·維爾特的 PL/0（英語：PL/0） 程式語言，出自 算法加資料結構等於程序（英語：算法加数据结构等于程序））是 LL(1) 形式:

 program = block "." .
 
 block =
     ["const" ident "=" num {"," ident "=" num} ";"]
     ["var" ident {"," ident} ";"]
     {"procedure" ident ";" block ";"} statement .
 
 statement =
     ident ":=" expression
     | "call" ident
     | "begin" statement {";" statement } "end"
     | "if" condition "then" statement
     | "while" condition "do" statement .
 
 condition =
     "odd" expression
     | expression ("="|"#"|"<"|"<="|">"|">=") expression .
 
 expression = ["+"|"-"] term {("+"|"-") term} .
 
 term = factor {("*"|"/") factor} .
 
 factor =
     ident
     | number
     | "(" expression ")" .

終結符用引號表示。每個非終結符都由文法中的一條規則來定義，除了 ident 和 number，它們被認為是隱含的定義。

C 語言實現

下面是一個上述語言的遞歸下降解析器的 C 語言實現。該解析器讀取原始碼，如果代碼解析失敗，則退出並顯示錯誤消息，如果代碼解析正確，則靜默退出。

注意下面的預測性解析器與上面的文法多麼接近。文法中的每個非終結符都有一個對應的程序。解析以自上而下的方式進行，直到最後一個非終結符被處理。這個程序片段依賴於一個全局變量， sym ，它包含了輸入的當前符號，以及函數 nextsym ，它在調用時更新 sym。

簡單起見，下面省略了函數 nextsym 和 error 的實現。

typedef enum {ident, number, lparen, rparen, times, slash, plus,
    minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
    endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
    varsym, procsym, period, oddsym} Symbol;

Symbol sym;
void nextsym(void);
void error(const char msg[]);

int accept(Symbol s) {
    if (sym == s) {
        nextsym();
        return 1;
    }
    return 0;
}

int expect(Symbol s) {
    if (accept(s))
        return 1;
    error("expect: unexpected symbol");
    return 0;
}

void factor(void) {
    if (accept(ident)) {
        ;
    } else if (accept(number)) {
        ;
    } else if (accept(lparen)) {
        expression();
        expect(rparen);
    } else {
        error("factor: syntax error");
        nextsym();
    }
}

void term(void) {
    factor();
    while (sym == times || sym == slash) {
        nextsym();
        factor();
    }
}

void expression(void) {
    if (sym == plus || sym == minus)
        nextsym();
    term();
    while (sym == plus || sym == minus) {
        nextsym();
        term();
    }
}

void condition(void) {
    if (accept(oddsym)) {
        expression();
    } else {
        expression();
        if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {
            nextsym();
            expression();
        } else {
            error("condition: invalid operator");
            nextsym();
        }
    }
}

void statement(void) {
    if (accept(ident)) {
        expect(becomes);
        expression();
    } else if (accept(callsym)) {
        expect(ident);
    } else if (accept(beginsym)) {
        do {
            statement();
        } while (accept(semicolon));
        expect(endsym);
    } else if (accept(ifsym)) {
        condition();
        expect(thensym);
        statement();
    } else if (accept(whilesym)) {
        condition();
        expect(dosym);
        statement();
    } else {
        error("statement: syntax error");
        nextsym();
    }
}

void block(void) {
    if (accept(constsym)) {
        do {
            expect(ident);
            expect(eql);
            expect(number);
        } while (accept(comma));
        expect(semicolon);
    }
    if (accept(varsym)) {
        do {
            expect(ident);
        } while (accept(comma));
        expect(semicolon);
    }
    while (accept(procsym)) {
        expect(ident);
        expect(semicolon);
        block();
        expect(semicolon);
    }
    statement();
}

void program(void) {
    nextsym();
    block();
    expect(period);
}

例子

一些遞歸下降解析器生成器：

• TMG – 一個在 1960 年代和 1970 年代初期使用的早期編譯器編譯程序
• JavaCC
• Coco/R（英語：Coco/R）
• ANTLR
• Spirit Parser Framework（英語：Spirit Parser Framework） – 一個不需要預編譯步驟的C++遞歸下降解析器生成器框架
• parboiled (Java)（英語：parboiled (Java)） – 一個用於 Java 的遞歸下降 PEG 解析庫

參見

• 文法解析組合子 – 一個用於組合式解析的高階函數，是一種對遞歸遞歸解析器設計進行因子化的方法
• 解析表達文法 – 另一種代表遞歸下降文法的形式
• 遞歸上升解析器（英語：Recursive ascent parser）
• 尾遞歸解析器（英語：Tail recursive parser） – 一種遞歸下降解析器的變體

參考資料

腳註

1. Burge, W.H. 《递归编程技术》. 1975. ISBN 0-201-14450-6.
2. Watson, Des. 《一种实用的编译器构建方法》. Springer. 22 March 2017 [2021-05-03]. ISBN 978-3-319-52789-5. （原始內容存檔於2021-05-05）.
3. Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey. 《编译原理》 first. Addison Wesley. 1986: 183.

文獻

• 編譯原理 第一版 Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman, in particular Section 4.4.
• Modern Compiler Implementation in Java, Second Edition, Andrew Appel, 2002, ISBN 0-521-82060-X.
• Recursive Programming Techniques, W.H. Burge, 1975, ISBN 0-201-14450-6
• Crafting a Compiler with C, Charles N Fischer and Richard J LeBlanc, Jr, 1991, ISBN 0-8053-2166-7.
• Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X, 624
• Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
• Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6

外部連結

上下文無關文法 語法分析器
· LL剖析器
· 算符優先分析器
· LR剖析器
· SLR剖析器
· LALR剖析器

• Introduction to Parsing （頁面存檔備份，存於網際網路檔案館） - 簡單易懂的解析介紹，其中包含有關遞歸下降解析的完整章節
• How to turn a Grammar into C code （頁面存檔備份，存於網際網路檔案館） - 一個實現遞歸下降解析器的簡要教程
• Simple mathematical expressions parser （頁面存檔備份，存於網際網路檔案館） in Ruby
• Simple Top Down Parsing in Python （頁面存檔備份，存於網際網路檔案館）
• Jack W. Crenshaw: Let's Build A Compiler (1988-1995) （頁面存檔備份，存於網際網路檔案館）, in Pascal, with assembly language output, using a "keep it simple" approach
• Functional Pearls: Monadic Parsing in Haskell （頁面存檔備份，存於網際網路檔案館）