如何将Python递归下降解析器改写为长尾？

本文共计2488个文字，预计阅读时间需要10分钟。

1. 算术运算表达式求值+解释这类文本，需要了解特定的语法规则。在此，我们介绍上下文无关语法（context-free grammar）的巴科斯-诺尔范式（BNF）和扩展巴科斯-诺尔范式（EBNF）。

1. 算术运算表达式求值

要解析这类文本，需要另外一种特定的语法规则。我们这里介绍可以表示上下文无关文法（context free grammer）的语法规则巴科斯范式(BNF)和扩展巴科斯范式(EBNF)。从小到一个算术运算表达式，到大到几乎所有程序设计语言，都是利用上下文无关文法来定义的。

对于简单的算术运算表达式，假定我们已经用分词技术将其转化为输入的tokens流，如NUM+NUM*NUM（分词方法参见上一篇博文）。

在此基础上，我们定义BNF规则定义如下：

expr ::= expr + term | expr - term | term term ::= term * factor | term / factor | factor factor ::= (expr) | NUM

当然，这种计法还不够简洁明了，我们实际采用的为EBNF形式：

expr ::= term { (+|-) term }* term ::= factor { (*|/) factor }* factor ::= (expr) | NUM

BNF和EBNF每一条规则(形如::=的式子)都可以看做是一种替换，即左侧的符号可以被右侧的符号所替换。