pparser_mean.py

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

意味規則を追加する (後置記法に翻訳する)

expr   -> expr + term { print('+') }
        | expr - term { print('-') }
        | term
term   -> term * factor  { print('*') }
        | term / factor  { print('/') }
        | factor
factor -> digit { print(digit) }
        | (  expr )


の左再帰を取り除く

expr   -> term E
E      -> + term { print('+') } E
        | - term { print('-') } E
        | e
term   -> factor T
T      -> * factor { print('*') } T
        | / factor { print('/') } T
        | e
factor -> digit { print(digit) }
        | (  expr )


"""
import string
from typing import Optional


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


def sprint(s) -> None:
    print(s, end=" ")


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()
            sprint('+')
            self.E()
        elif self.lookahead and self.lookahead == "-":
            self.match("-")
            self.term()
            sprint('-')
            self.E()
        else:
            # 空列
            pass

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

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

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


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


if __name__ == "__main__":
    main()