Source code for titan_pylib.algorithm.parser


[docs]
  1class Parser:
  2    """Parser
  3
  4    Examples:
  5        expression: < 四則演算の式 > ::= < 乗算除算の式 > (+ or -) < 乗算除算の式 > (+ or -) ...
  6        term      : < 乗算除算の式 > ::= < 括弧か数 > (* or /) < 括弧か数 > (* or /) ...
  7        term2 など
  8
  9        factor    : < 括弧か数 >     ::= '(' < 四則演算の式 > ')' or < 数 >
 10        number    : < 数 >          ::= ...
 11    """
 12
 13    def __init__(self, s: str) -> None:
 14        self.s: str = s
 15        self.n: int = len(s)
 16        self.ptr: int = 0
 17

[docs]
 18    def parse(self) -> int:
 19        return self.expression()

 20

[docs]
 21    def expression(self) -> int:
 22        """四則演算の式をパースして、その評価結果を返す。"""
 23        ret = self.term()
 24        while self.ptr < self.n:
 25            if self.get_char() == "+":
 26                self.consume("+")
 27                ret += self.term()
 28            elif self.get_char() == "-":
 29                self.consume("-")
 30                ret -= self.term()
 31            else:
 32                break
 33        return ret

 34

[docs]
 35    def term(self) -> int:
 36        """乗算除算の式をパースして、その評価結果を返す。"""
 37        ret = self.factor()
 38        while self.ptr < self.n:
 39            if self.get_char() == "*":
 40                self.consume("*")
 41                ret *= self.factor()
 42            elif self.get_char() == "/":
 43                self.consume("/")
 44                ret = ret // self.factor()  # 切り捨て
 45            else:
 46                break
 47        return ret

 48

[docs]
 49    def factor(self) -> int:
 50        """括弧か数をパースして、その評価結果を返す。"""
 51        if self.ptr >= self.n:
 52            return 0
 53        if self.get_char() == "(":
 54            self.consume("(")
 55            ret = self.expression()
 56            self.consume(")")
 57            return ret
 58        else:
 59            return self.number()

 60

[docs]
 61    def number(self) -> int:
 62        """数字の列をパースして、その数を返す。"""
 63        ret = 0
 64        while self.ptr < self.n and self.get_char().isdigit():
 65            ret *= 10
 66            ret += int(self.get_char())
 67            self.ptr += 1
 68        return ret

 69

[docs]
 70    def consume(self, expected: str) -> None:
 71        """begin が expected を指していたら begin を一つ進める。"""
 72        assert (
 73            self.s[self.ptr] == expected
 74        ), f"Expected: {expected} but got {self.s[self.ptr]}, s={self.s}"
 75        self.ptr += 1

 76

[docs]
 77    def get_char(self) -> str:
 78        return self.s[self.ptr]


 79
 80
 81# import sys
 82# from lark import Lark
 83# from lark import Transformer
 84# from functools import reduce
 85
 86
 87# class CalcTransformer(Transformer):
 88#     def expr(self, tree):
 89#         return reduce(lambda x, y: x + y, tree)
 90
 91#     def term(self, tree):
 92#         return reduce(lambda x, y: x * y, tree)
 93
 94#     def factor(self, tree):
 95#         return tree[0]
 96
 97#     def number(self, tree):
 98#         return int(tree[0])
 99
100
101# G = """
102# expr  : term [ "+" expr ]
103# term  : factor [ "*" term ]
104# factor : number | "(" expr ")"
105# number : /[0-9]+/
106# """
107
108# text = "(1+5)*3+2"
109# parser = Lark(G, start="expr")
110# tree = parser.parse(text)
111# print(tree)
112# result = CalcTransformer().transform(tree)
113# print(result)