# 递归下降解析器

## 解析器例子

``` 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 ")" .
```

### 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英语Coco/R
• ANTLR
• – 一个不需要预编译步骤的C++递归下降解析器生成器框架
• – 一个用于 Java 的递归下降 PEG 解析库

## 参见

• 文法解析组合子 – 一个用于组合式解析的高阶函数，是一种对递归递归解析器设计进行因子化的方法
• 解析表达文法 – 另一种代表递归下降文法的形式
• – 一种递归下降解析器的变体

## 参考资料

### 脚注

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剖析器