pparser.py

"""
expr   -> expr + term
        | expr - term
        | term
term   -> term * factor
        | term / factor
        | factor
factor -> digit | ( expr )


の左再帰を取り除く

expr   -> term E
E      -> + term E
        | - term E
        | e
term   -> factor T
T      -> * factor T
        | / factor T
        | e
factor -> digit | ( expr )
"""
import string
from typing import Optional


def is_digit(s) -> bool:
    return s in string.digits


class Parser:
    def __init__(self, input_str):
        self.input_str = input_str
        self.pos = 0

    @property
    def lookahead(self) -> Optional[str]:
        if self.pos >= len(self.input_str):
            return None
        return self.input_str[self.pos]

    def next(self) -> Optional[str]:
        self.pos += 1
        return self.lookahead

    def match(self, s) -> None:
        if self.lookahead and self.lookahead == s:
            self.next()
        else:
            raise Exception("syntax error")

    def expr(self):
        self.term()
        self.E()

    def E(self):
        if self.lookahead and self.lookahead == "+":
            self.match("+")
            self.term()
            self.E()
        elif self.lookahead and self.lookahead == "-":
            self.match("-")
            self.term()
            self.E()
        else:
            # 空列
            pass

    def term(self):
        self.factor()
        self.T()

    def T(self):
        if self.lookahead and self.lookahead == "*":
            self.match("*")
            self.factor()
            self.T()
        elif self.lookahead and self.lookahead == "/":
            self.factor("/")
            self.factor()
            self.T()
        else:
            # 空列
            pass

    def factor(self):
        if self.lookahead and is_digit(self.lookahead):
            self.match(self.lookahead)
        else:
            self.match("(")
            self.expr()
            self.match(")")


def main():
    parser = Parser("1+(2+3)")
    parser.expr()


if __name__ == "__main__":
    main()