Python实现递归下降表达式解析器触发TypeError如何解决

错误根因 #

代码的核心错误出在_advance方法的实现逻辑：你错误地调用next()读取self.tok，而实际存储分词迭代器的变量是self.tokens，第一次执行_advance时self.tok还是初始值None，自然会抛出TypeError: 'NoneType' object is not an iterator的错误。
另外还有一个不影响运行的注释错误：term方法的注释错误写成了factor的语法规则定义，可一并修正。

需要修改的代码段 #

1. 修正_advance方法 #

把next()的入参从self.tok改成self.tokens即可：

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

2. （可选）修正term方法的注释 #

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

完整可运行测试代码 #

需要先导入依赖的模块re和collections.namedtuple：

import re
from collections import namedtuple

# 符号规则和分词函数保持不变
NUM = r"(?P<NUM>\d+)"
ADD = r"(?P<ADD>\+)"
SUB = r"(?P<SUB>-)"
MUL = r"(?P<MUL>\*)"
TRUEDIV = r"(?P<TRUEDIV>/)"
LEFTPAR = r"(?P<LEFTPAR>\()"
RIGHTPAR = r"(?P<RIGHTPAR>\))"
WS = r"(?P<WS>\s+)"

master_pat = re.compile("|".join([NUM, ADD, SUB, MUL, TRUEDIV,
                                  LEFTPAR, RIGHTPAR, WS]))
Token = namedtuple("Token", ["type", "value"])

def generate_tokens(text):
    scanner = master_pat.scanner(text)
    for match in iter(scanner.match, None):
        tok = Token(match.lastgroup, match.group())
        if tok.type != "WS":
            yield tok

# 修正后的Evaluator类
class Evaluator:
    def parse(self, text):
        self.tokens = generate_tokens(text)
        self.tok = None  # Last symbol covered
        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("invalid syntax")

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

    def term(self):
        """term ::= factor { ('*'|'/') factor }*"""
        termval = self.factor()
        while self._accept("MUL") or self._accept("TRUEDIV"):
            op = self.tok.type
            right = self.factor()
            if op == "MUL":
                termval *= right
            elif op == "TRUEDIV":
                termval /= right
        return termval

    def factor(self):
        """factor ::= NUM | ( expr )"""
        if self._accept("NUM"):
            return int(self.tok.value)
        elif self._accept("LEFTPAR"):
            exprval = self.expr()
            self._expect("RIGHTPAR")
            return exprval
        else:
            raise SyntaxError("invalid syntax")

# 测试
if __name__ == "__main__":
    evaluator = Evaluator()
    print(evaluator.parse("2"))  # 输出 2
    print(evaluator.parse("(2 + 3) * 7"))  # 输出 35
    print(evaluator.parse("10 + 5 * 2"))  # 输出 20
    print(evaluator.parse("(10 - 3) / 2"))  # 输出 3.5

内容的提问来源于stack exchange，提问作者Alan Bagel