2.8　簡單的遞歸下降分析器實(shí)現(xiàn)

解析器可以通過語法規(guī)則解析文本并執(zhí)行命令實(shí)現(xiàn)，或者構(gòu)造一個代表輸入的抽象語法樹實(shí)現(xiàn)。如果語法非常簡單，可以不使用框架，而是自己手動實(shí)現(xiàn)解析器。

要想手動實(shí)現(xiàn)解析器，需根據(jù)特殊語法去解析文本。首先以BNF或者EBNF形式指定一個標(biāo)準(zhǔn)語法。一個簡單的數(shù)學(xué)表達(dá)式語法示例如下：

---

expr ::= expr + term
    |   expr - term
    |   term

term ::= term * factor
    |   term / factor
    |   factor

factor ::= ( expr )
    |   NUM

---

或者以EBNF形式指定標(biāo)準(zhǔn)語法，示例如下：

---

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

term ::= factor { (*|/) factor }*

factor ::= ( expr )
    |   NUM

---

在EBNF形式中，被包含在{...}*中的規(guī)則是可選的。*代表0次或多次重復(fù)（與在正則表達(dá)式中的意義一樣）。

如果你對BNF的工作機(jī)制還不是很明白，可把它當(dāng)作一組左右符號可相互替換的規(guī)則。

一般來講，解析的原理就是利用BNF完成多個替換和擴(kuò)展以匹配輸入文本和語法規(guī)則。

假設(shè)正在解析形如3+4×5的表達(dá)式，首先要使用前面介紹的技術(shù)將其分解為一組令牌流。分解結(jié)果可能是像下面這樣的令牌序列：

---

NUM + NUM * NUM

---

在此基礎(chǔ)上，通過替換操作匹配語法到輸入令牌，代碼如下：

---

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，因此替換操作首先會匹配該部分。一旦匹配成功，就會進(jìn)入下一個令牌，以此類推。當(dāng)已經(jīng)確定不能匹配下一個令牌的時候，令牌右邊的部分（比如{(*/)factor}*）就會被清理掉。在一個成功的解析中，整個令牌右邊部分會完全展開來匹配輸入令牌流。

下面通過一個簡單示例來展示如何構(gòu)建一個遞歸下降表達(dá)式求值程序，相關(guān)代碼（simple_recursion_1.py）示例如下：

---

"""
下降解析器
"""
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):
    scanner = master_pat.scanner(text)
    for m in iter(scanner.match, None):
        tok = Token(m.lastgroup, m.group())
        if tok.type != 'WS':
            yield tok


# Parser
class ExpressionEvaluator:
    '''
    Implementation of a recursive descent parser. Each method
    implements a single grammar rule. Use the ._accept() method
    to test and accept the current lookahead token. Use the ._expect()
    method to exactly match and discard the next token on on the input
    (or raise a SyntaxError if it doesn't match).
    '''

    def parse(self, text):
        self.tokens = generate_tokens(text)
        self.tok = None  # Last symbol consumed
        self.nexttok = None  # Next symbol tokenized
        self._advance()  # Load first lookahead token
        return self.expr()

    def _advance(self):
        'Advance one token ahead'
        self.tok, self.nexttok = self.nexttok, next(self.tokens, None)

    def _accept(self, toktype):
        'Test and consume the next token if it matches toktype'
        if self.nexttok and self.nexttok.type == toktype:
            self._advance()
            return True
        else:
            return False

    def _expect(self, toktype):
        'Consume next token if it matches toktype or raise SyntaxError'
        if not self._accept(toktype):
            raise SyntaxError('Expected ' + toktype)

    # Grammar rules follow
    def expr(self):
        "expression ::= term { ('+'|'-') term }*"
        exprval = self.term()
        while self._accept('PLUS') or self._accept('MINUS'):
            op = self.tok.type
            right = self.term()
            if op == 'PLUS':
                exprval += right
            elif op == 'MINUS':
                exprval -= right
        return exprval

    def term(self):
        "term ::= factor { ('*'|'/') factor }*"
        termval = self.factor()
        while self._accept('TIMES') or self._accept('DIVIDE'):
            op = self.tok.type
            right = self.factor()
            if op == 'TIMES':
                termval *= right
            elif op == 'DIVIDE':
                termval /= right
        return termval
    def factor(self):
        "factor ::= NUM | ( expr )"
        if self._accept('NUM'):
            return int(self.tok.value)
        elif self._accept('LPAREN'):
            exprval = self.expr()
            self._expect('RPAREN')
            return exprval
        else:
            raise SyntaxError('Expected NUMBER or LPAREN')


def descent_parser():
    e = ExpressionEvaluator()
    print(f"parse 2 result:{e.parse('2')}")
    print(f"parser 2 + 3 result:{e.parse('2 + 3')}")
    print(f"parser 2 + 3 * 4 result:{e.parse('2 + 3 * 4')}")
    print(f"parser 2 + (3 + 4) * 5 result:{e.parse('2 + (3 + 4) * 5')}")
    print(f"parser 2 + (3 + * 4) result:{e.parse('2 + (3 + * 4)')}")


if __name__ == '__main__':
    descent_parser()

---

執(zhí)行py文件，輸出結(jié)果如下：

---

parse 2 result:2
parser 2 + 3 result:5
parser 2 + 3 * 4 result:14
parser 2 + (3 + 4) * 5 result:37
Traceback (most recent call last):
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 112, in <module>
    descent_parser()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 108, in descent_parser
    print(f"parser 2 + (3 + * 4) result:{e.parse('2 + (3 + * 4)')}")
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 46, in parse
    return self.expr()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 71, in expr
    right = self.term()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 80, in term
    termval = self.factor()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 95, in factor
    exprval = self.expr()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 71, in expr
    right = self.term()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 80, in term
    termval = self.factor()
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter2/simple_recursion_1.py", line 99, in factor
    raise SyntaxError('Expected NUMBER or LPAREN')
SyntaxError: Expected NUMBER or LPAREN

---

文本解析是一個很大的主題，如果你在學(xué)習(xí)關(guān)于語法、解析算法等相關(guān)的背景知識，建議看一些編譯器書籍。關(guān)于解析方面的內(nèi)容太多，這里不能全部展開講解。

盡管如此，編寫一個遞歸下降解析器的整體思路是比較簡單的，首先獲得所有的語法規(guī)則，然后將其轉(zhuǎn)換為一個函數(shù)或者方法。若語法類似這樣：

---

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

term ::= factor { ('*'|'/') factor }*

factor ::= '(' expr ')'
    | NUM

---

則將它們轉(zhuǎn)換成如下的方法：

---

class ExpressionEvaluator:
    ...
    def expr(self):
    ...
    def term(self):
    ...
    def factor(self):
    ...

---

每個方法要完成的任務(wù)很簡單——從左至右遍歷語法規(guī)則，處理每個令牌。從某種意義上講，上述方法的目的要么是處理完語法規(guī)則，要么是產(chǎn)生一個語法錯誤，具體如下。

1）如果規(guī)則中的下一個符號是另外一個語法規(guī)則的名字（比如：term或factor），簡單地調(diào)用同名的方法即可，這就是該算法中下降的由來。有時候，規(guī)則會調(diào)用已經(jīng)執(zhí)行的方法（比如，在factor::='('expr')'中對expr的調(diào)用），這就是算法中遞歸的由來。

2）如果規(guī)則中的下一個符號是一個特殊符號，比如()，則需要查找下一個令牌并確認(rèn)其是一個精確匹配。如果令牌不匹配，就產(chǎn)生一個語法錯誤。上面示例中，_expect()方法就是用來做這一步的。

3）如果規(guī)則中的下一個符號為一些可能的選擇項(xiàng)（比如：+或-），必須對每一種可能情況檢查下一個令牌，只有當(dāng)它匹配一個令牌的時候才能繼續(xù)。這也是上面示例中_accept()方法的目的。它相當(dāng)于_expect()方法的弱化版本，因?yàn)槿绻粋€匹配找到了它會繼續(xù)，但是如果沒找到，不會產(chǎn)生錯誤而是回滾（允許后續(xù)的檢查繼續(xù)進(jìn)行）。

4）對于有重復(fù)部分的規(guī)則（比如在規(guī)則表達(dá)式::=term{('+'|'-')term}*中），重復(fù)動作通過一個while循環(huán)來實(shí)現(xiàn)。循環(huán)主體會收集或處理所有的重復(fù)元素，直到找不到其他元素。

5）一旦整個語法規(guī)則處理完成，每個方法會返回某種結(jié)果給調(diào)用者。這就是在解析過程中值累加的原理。如在表達(dá)式求值程序中，返回值代表表達(dá)式解析后的部分結(jié)果。

6）最后所有值會在最頂層的語法規(guī)則方法中合并起來。

遞歸下降解析器可以用來實(shí)現(xiàn)非常復(fù)雜的解析。如Python語言本身是通過一個遞歸下降解析器去解釋的。如果你對此感興趣，可以通過查看Python代碼文件Grammar來研究底層語法機(jī)制。

其實(shí)，通過手動方式去實(shí)現(xiàn)一個解析器會有很多局限。其中，一個局限就是它們不能被用于包含任何左遞歸的語法規(guī)則。如需翻譯如下規(guī)則：

---

items ::= items ',' item
    | item

---

為了翻譯上面的規(guī)則，可能會使用items()方法，代碼如下：

---

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

---

不過，這個方法根本不能工作，它會產(chǎn)生一個無限遞歸錯誤。

語法規(guī)則本身也存在一定的局限。如我們想知道下面這個簡單語法表述是否得當(dāng)：

---

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

factor ::= '(' expression ')'
    | NUM

---

這個語法對標(biāo)準(zhǔn)四則運(yùn)算中的運(yùn)算符優(yōu)先級不敏感。如表達(dá)式3+4×5會得到35而不是期望的23，分開使用expr和term規(guī)則可以得到正確結(jié)果。

對于復(fù)雜的語法，最好選擇某個解析工具，比如PyParsing或者PLY。下面使用PLY來重寫表達(dá)式求值程序：

---

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()

---

該示例中，所有代碼位于一個比較高的層次，只需要為令牌寫正則表達(dá)式和規(guī)則匹配時的高階處理函數(shù)。實(shí)際上，運(yùn)行解析器、接收令牌等底層動作已經(jīng)被庫函數(shù)實(shí)現(xiàn)了。

如果你想在編程過程中來點(diǎn)挑戰(zhàn)和刺激，編寫解析器和編譯器是不錯的選擇。