Python Recursive Descent Parser Example

recursive_descent_parser.py

#!/usr/bin/env python3

import re
from enum import Enum
from collections import namedtuple

"""
Simple Expression Grammar

expr → term {(+ | -) term}
term → factor {(* | /) factor}
factor → int | ( expr )

Note: No error handling, and input needs spaces between tokens
"""

class Token(Enum):
    INT = "[0-9]+",
    PLUS = "\\+",
    MINUS = "\\-",
    MUL = "\\*",
    DIV = "\\/",
    LPAREN = "\\(",
    RPAREN = "\\)",

TokenTuple = namedtuple('TokenTuple', 'token value')

class Parser:
    def __init__(self, _input):
        self.tape = []
        for input_word in _input.split(' '):
            for token in Token:
                if re.match(token.value[0], input_word):
                    self.tape.append(TokenTuple(token=token, value=input_word))
                    break
        self.nextToken = self.tape[0].token
        self.i = 0

    # expr -> term (("+" | "-") term)
    def expr(self):
        lhs = self.term()
        while self.nextToken == Token.PLUS or \
              self.nextToken == Token.MINUS:
            op = self.lex().token
            rhs = self.term()
            if op == Token.PLUS:
                lhs += rhs
            else:
                lhs -= rhs
        return lhs

    # term -> factor {(* | /) factor}
    def term(self):
        lhs = self.factor()
        while self.nextToken == Token.MUL or \
              self.nextToken == Token.DIV:
            op = self.lex().token
            rhs = self.factor()
            if op == Token.MUL:
                lhs *= rhs
            else:
                lhs /= rhs
        return lhs

    # factor -> int | ( expr )
    def factor(self):
        num = None
        if self.nextToken == Token.INT:
            num = int(self.lex().value)
        elif self.nextToken == Token.LPAREN:
            self.lex()
            num = self.expr()
            if self.nextToken == Token.RPAREN:
                self.lex()
        return num

    def lex(self):
        ret = self.tape[self.i]
        self.i = self.i + 1
        if self.i < len(self.tape):
            self.nextToken = self.tape[self.i].token
        else:
            self.nextToken = None
        return ret

print(Parser("2 + ( 3 - 1 )").expr())