I am creating an simple descent expression evaluator that can evaluate simple math expressions using the Python Cookbook. (e. g (2 3) * 7)

However, I keep getting this error:

Traceback (most recent call last):
  File "...", line 111, in <module>
    print(evaluator.parse("2"))
  File "...", line 43, in parse
    self._advance()  # Load first lookahead token
  File "...", line 48, in _advance
    self.tok, self.nexttok = self.nexttok, next(self.tok, None)
TypeError: 'NoneType' object is not an iterator

My symbols:

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

My 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.tok, 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")

    # Grammer 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):
        """factor ::= NUM | ( expr )"""

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

However, when I tried to parse anything I got the error mentioned above. How can I make a actually working recursive descent parser?

CodePudding user response：

The problem here is that currently, self.tok is never set to anything other then None, hence the error. Just changing self.tok to sel.tokens solves the problem.

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