递归下降解析器

在计算机科学中，递归下降解析器是一种自上而下的解析器（英语：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 （页面存档备份，存于互联网档案馆）