递归下降分析法（编译原理递归下降分析程序）

你想根据一组语法规则解析文本并执行命令，或者构造一个代表输入的抽象语法树。如果语法非常简单，你可以自己写这个解析器，而不是使用一些框架。

在这个问题中，我们集中讨论根据特殊语法去解析文本的问题。为了这样做，你首先要以 bnf(巴科斯范式)或者 ebnf(扩展巴科斯范式)形式指定一个标准语法。

具体关于bnf和ebnf的介绍，可以查看中国*：

bnf：
https://zh.wikipedia.org/wiki/巴科斯范式

ebnf：
https://zh.wikipedia.org/wiki/扩展巴科斯范式

比如，一个简单数学表达式语法可能像下面这样：

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多增加几个符号：

“[]”,表示可选项

“{}”，表示重复0次或者多次

引号本身，便于区分单个符号的终结符

在 ebnf 中，被包含在 {…}* 中的规则是可选的。 *代表 0 次或多次重复 (跟正则表达式中意义是一样的)。

上边例子中更加易读的写法应该是：

# <expr>加个<>尖括号表示非终结符
<expr> ::= <expr> + <term>
      | <expr> - <term>
      | <term>
<term> ::= <term> * <factor>
      | <term> / <factor>
      | <factor>
<factor> ::= ( <expr> )
      | num

bnf例子，如正则表达式：”a(bb)*c”

<v0> ::=a<w>
<w>  ::=bb<w>|c

现在，如果你对 bnf 的工作机制还不是很明白的话，就把它当做是一组左右符号可相互替换的规则。一般来讲，解析的原理就是你利用 bnf 完成多个替换和扩展以匹配输入文本和语法规则。为了演示，假设你正在解析形如 2 + 3 * 4 的表达式。这个表达式先要通过使用介绍过的令牌解析技术分解为一组令牌流。结果可能是像下列这样的令牌序列：

num + num * num

在此基础上，解析动作会试着去通过替换操作匹配语法到输入令牌：

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

下面所有的解析步骤可能需要花点时间弄明白，但是它们原理都是查找输入并试着去匹配语法规则。第一个输入令牌是 num，因此替换首先会匹配那个部分。一旦匹配成功，就会进入下一个令牌 +，以此类推。当已经确定不能匹配下一个令牌的时候，右边的部分 (比如 {(*/)factor }* ) 就会被清理掉。在一个成功的解析中，整个右边部分会完全展开来匹配输入令牌流。

有了前面的知识背景，下面我们举一个简单示例来展示如何构建一个递归下降表达式求值程序：

"""
topic: 下降解析器
desc :
"""

import re
import collections
# token specification
num = r'(?p<num>\d+)'
plus = r'(?p<plus>\+)'
minus = r'(?p<minus>-)'
times = r'(?p<times>\*)'
divide = r'(?p<divide>/)'
lparen = r'(?p<lparen>\()'
rparen = r'(?p<rparen>\))'
ws = r'(?p<ws>\s+)'
master_pat = re.compile('|'.join([num, plus, minus, times, divide, lparen, rparen, ws]))
# tokenizer
token = collections.namedtuple('token', ['type', 'value'])


def generate_tokens(text):
    for matched_item in re.finditer(master_pat, text):
        tok = token(matched_item.lastgroup, matched_item.group())
        if tok.type != 'ws':
            yield tok


# parser
class expressionevaluator(object):
    """
    递归下降解析器的实现。 每种方法实现单个语法规则。 使用._accept()方法
    测试并接受当前的超前令牌。 使用._expect()完全匹配并丢弃输入的下一个标记的方法
    如果不匹配，则引发syntaxerror
    """
    def parse(self, text):
        self.tokens = generate_tokens(text)
        self.tok = none  # last symbol consumed
        self.next_tok = none  # next symbol tokenized
        self._advance()  # load first lookahead token
        return self.expr()

    def _advance(self):
        # advance one token ahead
        self.tok, self.next_tok = self.next_tok, next(self.tokens, none)

    def _accept(self, tok_type):
        # test and consume the next token if it matches tok_type
        if self.next_tok and self.next_tok.type == tok_type:
            self._advance()
            return true
        else:
            return false

    # consume next token if it matches tok_type or raise syntaxerror
    def _expect(self, tok_type):
        if not self._accept(tok_type):
            raise syntaxerror('expected ' + tok_type)

    # grammar rules follow
    def expr(self):
        # expression ::= term { ('+'|'-') term }*
        expr_val = self.term()
        while self._accept('plus') or self._accept('minus'):
            op = self.tok.type
            right = self.term()
            if op == 'plus':
                expr_val += right
            elif op == 'minus':
                expr_val -= right
        return expr_val

    def term(self):
        # term ::= factor { ('*'|'/') factor }*
        term_val = self.factor()
        while self._accept('times') or self._accept('divide'):
            op = self.tok.type
            right = self.factor()
            if op == 'times':
                term_val *= right
            elif op == 'divide':
                term_val /= right
        return term_val

    def factor(self):
        # factor ::= num | ( expr )
        if self._accept('num'):
            return int(self.tok.value)
        elif self._accept('lparen'):
            expr_val = self.expr()
            self._expect('rparen')
            return expr_val
        else:
            raise syntaxerror('expected number or lparen')


def descent_parser():
    e = expressionevaluator()
    print(e.parse('2'))	# 2
    print(e.parse('2 + 5'))	# 7
    print(e.parse('2 + 2 * 4'))	# 10
    print(e.parse('2 + (5 + 2) * 3'))	# 23


if __name__ == '__main__':
    descent_parser()

文本解析是一个很大的主题，一般会占很大的精力。如果你在找寻关于语法，解析算法等相关的背景知识的话，你应该去看一下编译器书籍。很显然，关于这方面的内容太多，不可能在这里全部展开。

尽管如此，编写一个递归下降解析器的整体思路是比较简单的。开始的时候，你先获得所有的语法规则，然后将其转换为一个函数或者方法。因此如果你的语法类似这样：

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

你应该首先将它们转换成一组像下面这样的方法

class expressionevaluator:

    def expr(self):
        pass
    def term(self):
        pass
    def factor(self):
        pass

每个方法要完成的任务很简单 – 它必须从左至右遍历语法规则的每一部分，处理每个令牌。从某种意义上讲，方法的目的就是要么处理完语法规则，要么产生一个语法错误。为了这样做，需采用下面的这些实现方法：

• 如果规则中的下个符号是另外一个语法规则的名字 (比如 term 或 factor)，就简单的调用同名的方法即可。这就是该算法中” 下降” 的由来 – 控制下降到另一个语法规则中去。有时候规则会调用已经执行的方法 (比如，在 factor ::= ‘(‘expr’)’ 中对 expr 的调用)。这就是算法中” 递归” 的由来。
• 如果规则中下一个符号是个特殊符号 (比如 ()，你得查找下一个令牌并确认是一个精确匹配)。如果不匹配，就产生一个语法错误。这一节中的 expect() 方法就是用来做这一步的。
• 如果规则中下一个符号为一些可能的选择项 (比如 + 或 -)，你必须对每一种可能情况检查下一个令牌，只有当它匹配一个的时候才能继续。这也是本节示例中accept() 方法的目的。它相当于 expect() 方法的弱化版本，因为如果一个匹配找到了它会继续，但是如果没找到，它不会产生错误而是回滚 (允许后续的检查继续进行)。
• 对于有重复部分的规则 (比如在规则表达式 ::= term { (‘+’|’-‘) term }* 中)，重复动作通过一个 while 循环来实现。循环主体会收集或处理所有的重复元素直到没有其他元素可以找到。
• 一旦整个语法规则处理完成，每个方法会返回某种结果给调用者。这就是在解析过程中值是怎样累加的原理。比如，在表达式求值程序中，返回值代表表达式解析后的部分结果。最后所有值会在最顶层的语法规则方法中合并起来。

尽管向你演示的是一个简单的例子，递归下降解析器可以用来实现非常复杂的解析。比如， python 语言本身就是通过一个递归下降解析器去解释的。如果你对此感兴趣，你可以通过查看 python 源码文件 grammar/grammar 来研究下底层语法机制。看完你会发现，通过手动方式去实现一个解析器其实会有很多的局限和不足之处。

其中一个局限就是它们不能被用于包含任何左递归的语法规则中。比如，加入你需要翻译下面这样一个规则：

items ::= items ',' item
      | item

为了这样做，你可能会像下面这样使用 items() 方法：

def items(self):
    itemsval = self.items()
    if itemsval and self._accept(','):
        itemsval.append(self.item())
    else:
        itemsval = [ self.item() ]

唯一的问题是这个方法根本不能工作，事实上，它会产生一个无限递归错误。关于语法规则本身你可能也会碰到一些棘手的问题。比如，你可能想知道下面这个

简单扼语法是否表述得当：

expr ::= factor { ('+'|'-'|'*'|'/') factor }*
factor ::= '(' expression ')'
        | num

这个语法看上去没啥问题，但是它却不能察觉到标准四则运算中的运算符优先级。比如，表达式 “3 + 4 * 5” 会得到 35 而不是期望的 23. 分开使用”expr” 和”term” 规则可以让它正确的工作。

对于复杂的语法，你最好是选择某个解析工具比如 pyparsing 或者是 ply。下面是使用 ply 来重写表达式求值程序的代码：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @author : cory
# @time : 2021/2/2223:20
# @email: [e-mail]
from ply.lex import lex
from ply.yacc import yacc
# token list
tokens = ['num', 'plus', 'minus', 'times', 'divide', 'lparen', 'rparen']
# ignored characters
t_ignore = ' \t\n'
# token specifications (as regexs)
t_plus = r'\+'
t_minus = r'-'
t_times = r'\*'
t_divide = r'/'
t_lparen = r'\('
t_rparen = r'\)'


# token processing functions
def t_num(t):
    r'\d+'
    t.value = int(t.value)
    return t


# error handler
def t_error(t):
    print('bad character: {!r}'.format(t.value[0]))
    t.skip(1)
    # build the lexer


lexer = lex()


# grammar rules and handler functions
def p_expr(p):
    """
    expr : expr plus term
        | expr minus term
    """
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]


def p_expr_term(p):
    """expr : term"""
    p[0] = p[1]


def p_term(p):
    """
    term : term times factor
         | term divide factor
    """
    if p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]


def p_term_factor(p):
    """
    term : factor
    """
    p[0] = p[1]


def p_factor(p):
    """
    factor : num
    """
    p[0] = p[1]


def p_factor_group(p):
    """
    factor : lparen expr rparen
    """
    p[0] = p[2]


def p_error(p):
    print('syntax error')


parser = yacc()
print(parser.parse('2'))	# 2

这个程序中，所有代码都位于一个比较高的层次。你只需要为令牌写正则表达式和规则匹配时的高阶处理函数即可。而实际的运行解析器，接受令牌等等底层动作已经被库函数实现了。

如果对编写语法与词法感兴趣，可以查看ply文档，以及查看更加详细的编译器的书籍，这里就不再赘述了。