遞迴下降解析器

在計算機科學中，遞迴下降解析器是一種，由一組相互遞迴的程式構建而成，其中每個程式都實現了文法中的一個非終結符。因此，這些程式的結構密切反映了它所識別的文法結構。預測性解析器是一種不需要回溯的遞迴下降解析器。預測性解析只適用於 LL("k") 文法。這是一種上下文無關文法。這種文法允許遞迴下降解析器僅透過檢測之後 "k" 個標記決定當前標記所使用的。LL("k") 文法由此排除了所有包含和左遞迴的文法。雖然任何一種上下文無關文法都可以轉化為沒有左遞迴的等效文法，但是去除了左遞迴卻不一定能夠得到 LL("k") 文法。預測性解析器能夠線上性時間內執行。具有回溯的遞迴下降是一種透過依次嘗試生成規則來生成結果的技術。具有回溯的遞迴下降不限於 LL("k") 文法，但只在文法是 LL("k") 文法的情況下才保證能夠停機。具有回溯的遞迴下降對於其他文法即使能夠停機，也可能需要指數時間執行。儘管預測性解析器被廣泛使用，也經常被選擇用於手工編寫解析器，但程式設計師通常更願意使用由文法解析器生成器產生的基於表的解析器，無論是對於 LL("k") 語言還是使用替代解析器，比如 LALR 或 LR。如果一個文法不是 LL("k") 文法，情況尤其如此，因為要把文法轉化為 LL 形式，使其適合預測性解析。預測性解析器也可以使用 ANTLR 之類的工具自動生成。預測性解析器可以用每個非終結符號的過渡圖來描述，其中初始狀態和最終狀態之間的界限由生成規則右側的符號來界定。解析器例子.以下類似 EBNF 的文法是 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);例子.一些遞迴下降解析器生成器：