遞歸下降解析器

在電腦科學中，遞歸下降解析器是一種自上而下解析器，由一組相互遞歸的程序（或等價的非遞歸程序）構建而成，其中每個程序都實現了文法中的一個非終結符。因此，這些程序的結構密切反映了它所識別的文法結構。

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

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

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

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

## 解析器例子

以下類似 EBNF 的文法（用於尼克勞斯·維爾特的 PL/0 程式語言，出自 演算法加數據結構等於程序）是 LL(1) 形式:

```ebnf
 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 的實現。

```c
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
- ANTLR
- Spirit Parser Framework – 一個不需要預編譯步驟的C++遞歸下降解析器生成器框架
- parboiled (Java) – 一個用於 Java 的遞歸下降 PEG 解析庫

## 參見

- 文法解析組合子 – 一個用於組合式解析的高階函數，是一種對遞歸遞歸解析器設計進行因子化的方法
- 解析表達文法 – 另一種代表遞歸下降文法的形式
- 遞歸上升解析器
- 尾遞歸解析器 – 一種遞歸下降解析器的變體

## 外部連結

上下文無關文法語法分析器· 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