使用70行Python代码实现一个递归下降解析器的教程

 第一步：标记化

处理表达式的第一步就是将其转化为包含一个个独立符号的列表。这一步很简单，且不是本文的重点，因此在此处我省略了很多。
首先，我定义了一些标记（数字不在此中，它们是默认的标记）和一个标记类型：
 

token_map = {'+':'ADD', '-':'ADD',       '*':'MUL', '/':'MUL',       '(':'LPAR', ')':'RPAR'} Token = namedtuple('Token', ['name', 'value'])

下面就是我用来标记 `expr` 表达式的代码：
 

split_expr = re.findall('[/d.]+|[%s]' % ''.join(token_map), expr)tokens = [Token(token_map.get(x, 'NUM'), x) for x in split_expr]

第一行是将表达式分割为基本标记的技巧，因此
 

'1.2 / ( 11+3)' --> ['1.2', '/', '(', '11', '+', '3', ')']

下一行命名标记，这样分析器就能通过分类识别它们：
 

['1.2', '/', '(', '11', '+', '3', ')']->[Token(name='NUM', value='1.2'), Token(name='MUL', value='/'), Token(name='LPAR', value='('), Token(name='NUM', value='11'), Token(name='ADD', value='+'), Token(name='NUM', value='3'), Token(name='RPAR', value=')')]

任何不在 token_map 中的标记被假定为数字。我们的分词器缺少称为验证的属性，以防止非数字被接受，但幸运的是，运算器将在以后处理它。
就是这样
第二步: 语法定义

我选择的解析器实现自一个本地垂直解析器，其来源于LL解析器的一个简单版本。它是一个最简单的解析器实现，事实上，只有仅仅14行代码。它是一种自上而下的解析器，这意味着解析器从最上层规则开始解析（like:expression），然后以递归方式尝试按照其子规则方式解析，直至符合最下层的规则（like:number）。换句话解释，当自底向上解析器（LR）逐步地收缩标记，使规则被包含在其它规则中，直到最后仅剩下一个规则，而自顶向下解析器（LL）逐步展开规则并进入到少数的抽象规则，直到它能够完全匹配输入的标记。
在深入到实际的解析器实现之前，我们可对语法进行讨论。在我之前发表的文章中，我使用过LR解析器，我可以像如下方式定义计算器语法（标记使用大写字母表示）：
 

add: add ADD mul | mul;mul: mul MUL atom | atom;atom: NUM | '(' add ')' | neg;neg: '-' atom;

(如果您还不理解上述语法，请阅读我之前发表的文章)

现在我使用LL解析器，以如下方式定义计算器的语法：
 

rule_map = {  'add' : ['mul ADD add', 'mul'],  'mul' : ['atom MUL mul', 'atom'],  'atom': ['NUM', 'LPAR add RPAR', 'neg'],  'neg' : ['ADD atom'],}

大家可以看到，这里有一个微妙的变化。有关"add and mul"的递归定义被反转了。这是个非常重要的细节，我会向大家详细说明这一点。