編譯原理遞歸下降分析程序「遞歸下降分析法」

你想根據一組語法規則解析文本並執行命令，或者構造一個代表輸入的抽象語法樹。如果語法非常簡單，你可以自己寫這個解析器，而不是使用一些框架。

在這個問題中，我們集中討論根據特殊語法去解析文本的問題。為了這樣做，你首先要以 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: 1595610424@qq.com
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文檔，以及查看更加詳細的編譯器的書籍，這裡就不再贅述了。