일전에 수식을 직접 입력 받아 후위식으로 변환하여 계산하는, 사칙연산과 괄호를 처리할 수 있는 계산기를 만들어 본 적이 있는데, 1이 계산기는 지금까지 유용하게 잘 쓰고 있는 중임, 이번에는 좀 다른 계산기를 만들어보고자 한다. 사실 파서를 한 번 직접 구현해보고 싶어서 이리 저리 알아보다가 가장 간단하게 만들어 볼 수 있는 구현체가 수식 파서가 아닐까 해서, 정말 실용적으로 사용 가능한 수식 파서를 사용한 계산기를 구현해 보려고 한다.
문법
파서는 어떤 문자열을 정해진 문법에 따라서 토큰으로 나누고 이를 조합하여 트리를 생성하는 프로그램이다. 따라서 어떤 파서를 만드려고 할 때 가장 먼저 해야하는 일은 ‘잘 정의된 문법’을 만드는 것이다. 어떤 프로그래밍 언어의 레퍼런스 문서를 보면 이러한 문법 구조를 정의해놓은 것들을 찾아 볼 수 있다. 수식 계산기가 사용하는 문법은 다항식에 관한 것이며, 사실 대부분의 프로그래밍 언어가 기본적인 연산을 처리할 수 있기 때문에 다른 언어들의 표현식(expression) 문법을 참고하면 되었다.
계산기에서 처리해야 하는 수식은 기본적으로 다항식이다. 다항식은 여러 개의 단항식이 더하기나 빼기를 통해서 연결된 것이다. 그리고 각각의 항은 다시 여러 값들이 곱하기나 나누기로 연결된 것으로 볼 수 있다. 이 때 하나의 값은 정수값이거나 실수값일 수 있다. 그리고 괄호가 포함된 경우, 괄호로 묶여 있는 다항식도 하나의 값으로 보면 된다.
이 구조를 흔히 사용하는 BNF 표기를 사용해서 정의해보자. (거듭제곱 연산도 포함시켰다.) 대략 아래와 같은 문법으로 정리할 수 있다.
<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>;
<term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor>;
<factor> ::= <primary> | "+" <primary> | "-" <primary>;
<primary> ::= <INTEGER> | <FLOATING_POINT_NUMBER> | "(" <expression> ")" | <primary> "**" <primary>토큰
파서의 역할은 어떤 텍스트 데이터를 분해하고 해석해서 논리적인 데이터 구조를 만드는 것이다. 보통의 파서들은 그 결과로 트리 형태의 데이터를 생성한다. 이 트리의 각 노드를 토큰이라고 한다. 토큰은 입력된 문자열을 문법에서 사용하는 단위별로 자르고, 그 유형을 구분해놓은 것이다. 토큰은 문법 내에서 특정한 의미를 가지는 최소한의 단위가 되며, 기본적으로 트리에서 하나의 노드가 된다. 물론 모든 토큰이 트리 내에서 노드가 되는 것은 아니다. (공백 문자라든지, 주석으로 처리된 문자들은 파서의 구현에 따라서는 완전히 무시되어 트리에 추가되지 않는다.)
토큰은 기본적으로 자신을 다른 토큰의 종류와 구분할 수 있는 타입 정보와, 자신을 구성하는 문자열에 대한 정보를 가지게 된다. 또한 트리를 구성하는 노드가 되기 때문에 자식 노드 (필요에 따라서는 부모노드)에 대한 참조도 가져야 한다. 토큰 클래스에 대한 기본적인 구조는 다음과 같이 정의하도록 하겠ㄷ.
from enum import Enum
class TokenType(Enum):
pass
class Token:
def __init__(self, type_: TokenType, value=None):
self.type = type_
self.value = value
self.children = []
토큰의 종류 자체에 대해서는 단순히 문자열이나 상수로 정의해두어도 상관없는데, 편집기의 자동완성 기능의 도움을 받거나 하기 위해서 역시 별도의 타입으로 선언했다. 수식에서는 각 부호와 숫자를 구분해서 정의해주면 된다.
class TokenType(Enum):
SPACE = 0
INT = 1
FLOAT = 2
PLUS = 11
MINUS = 12
MUL = 13
DIV = 14
REMAIN = 15
POW = 16
LPAR = 21
RPAR = 22
END = 99
참고로, 파서에게 입력의 끝을 알려주기 위해 END 토큰이 필요하다. 여기까지 정의했으면 필요한 토큰의 정의가 완료되었다.
렉서
렉서는 파서의 구성 요소 중 하나로 입력된 텍스트를 ‘적절하게’ 잘라내서 토큰을 만드는 일을 담당한다. 보통 렉서는 텍스트를 한 글자씩 앞에서부터 읽어 처리하면서 토큰을 생성할 수 있는 분량까지 읽었을 때 읽어낸 텍스트로 토큰을 만드는 작업을 수행한다. 처음 만들어던 버전에서는 정규식으로 숫자값과 연산자 사이를 잘라서 처리하는 식으로 했는데, 정식으로 해보려고 하는 김에 렉서까지 만들어 보도록 하자.
렉서는 앞서 정의한 토큰 타입들을 문자열의 앞부분에서 찾고, 그만큼을 소모하여 토큰을 생성한다. 따라서 우선 각각의 토큰과, 그 토큰을 찾는데 사용하는 패턴을 정의해야 한다. 대부분은 한 글자 짜리 연산자라서 별 여러움은 없을 것이다. 다만 주의할 것은 실수형으로 인식이 가능한 문자열에 대해서 정수 패턴을 먼저 적용하면 제대로 처리가 안되기 때문에 실수 타입을 위한 패턴이 우선 적용되도록 순서를 지정해야 한다는 것이다. 파이썬처럼 거듭제곱을 ** 으로 사용하고 싶다면, 이 역시 곱셈 연산자보다 먼저 적용해보도록 해야한다.
patterns = [
(r"^\s+", TokenType.SPACE),
(r"^\d*\.\d+", TokenType.FLOAT),
(r"^\d+", TokenType.INT),
(r"^\+", TokenType.PLUS),
(r"^-", TokenType.MINUS),
(r"^\*{2}", TokenType.POW),
(r"^\^", TokenType.POW),
(r"^\*", TokenType.MUL),
(r"^\/", TokenType.DIV),
(r"^%", TokenType.REMAIN),
(r"^\(", TokenType.LPAR),
(r"^\)", TokenType.RPAR),
]
렉서의 구현은 간단하다. 문자열의 앞부분에서 패턴을 하나씩 적용해보고 들어맞는 패턴이 있으면 그만큼을 소모하여 토큰을 만든다. 맞는 패턴을 하나도 찾을 수 없다면 해석할 수 없는 입력이 들어온 것이니 예외로 처리하면 되겠다.
def lex(s, patterns=patterns):
res = []
l = len(s)
c = 0
while c < l:
for pat, t in patterns:
p = re.compile(pat)
m = p.match(s[c:])
if m:
d = m.group(0)
if t != TokenType.SPACE:
res.append(Token(t, d))
c += m.span()[1]
break
else:
raise ValueError(f"Invalid chracter at {c}: {s[c]}")
res.append(Token(TokenType.END))
return res
렉서가 제대로 작동하는지 보고자 한다. 렉서가 만들어내는 값들이 토큰 객체이기 때문에, 깔끔한 형태로 보고싶으면 토큰의 매직 메소드 하나를 오버라이드하여 주자.
class Token:
...
def __repr__(self):
return f'"{self.value}"'
s = "1.2 - 3 * (.4 / 5)^6"
ts = lex(s)
print(ts)
# ["1.2", "+", "3", "*", "(", ".4", "/", "5", ")", "^", "6", "None"]파서
토큰의 리스트를 만드는 것까지 했으니, 이번에는 실제 수식 트리를 생성하는 파서를 만들어보자. 파서는 정의된 문법의 유형만큼 생성하여주면 된다. 여기서는 1) 다항식 파서, 2) 단항식 파서, 3) 원시값 파서의 세 개 함수를 작성할 것이다. 각각의 함수는 문법 정의의 우측에 나타나는 하위 혹은 다른 상위 구조를 파싱하는 함수를 내부에서 호출할 것이다. 그 과정에서 토큰 리스트는 계속 소모하게 되는데, 좀 귀찮기는 하지만 각 함수가 파싱한 노드/트리를 리턴하는 것이 아니라 (트리, 남아있는 토큰들)을 리턴하는 구조로 만들겠다.
다항식 파서
먼저 다항식 부분을 파싱하는 함수를 작성해보자. 정의했던 문법의 구성을 그대로 따르면 된다. 다항식을 파싱하는 절차는 다음과 같다.
- 먼저 토큰 목록의 앞쪽을 소모해서 단항식을 하나 파싱해낸다. 이 단항식이 초기 루트노드가 된다.
- 남은 토큰의 맨 앞이 덧셈기호나 뺄셈기호이면 이를 취한다.
- 다시 남은 토큰의 앞부분에서 단항식을 파싱한다.
- 루트 노드와 덧붙이는 노드를 연산자 노드의 좌, 우 자식이 되도록 연결한다. 이제 연산자 노드가 루트 노드가 된다.
- 2~5의 과정을 가능한만큼 반복한다.
아직 단항식을 파싱하는 함수는 작성하기 전이지만, 있다고 가정하고 작성하면 코드는 아래와 같다.
def parse_expression(tokens: list[Token]) -> tuple[Token, list[Token]]:
root, remains = parse_term(tokens)
while remains[0].type in [TokenType.PLUS, TokenType.MINUS]:
op, remains = remains[0], remains[1:]
right, remains = parse_term(remains)
op.children = [root, right]
root = op
return root, remains
단항식 파서
단항식을 파싱하는 함수는 다항식을 파싱하는 함수와 완전히 동일한 형태와 구조를 가진다.
def parse_term(tokens: list[Token]) -> tuple[Token, list[Token]]:
root, remains = parse_factor(tokens)
while remains[0].type in (
TokenType.MUL,
TokenType.DIV,
TokenType.REMAIN,
):
op, remains = remains[0], remains[1:]
right, remains = parse_factor(remains)
op.children = [root, right]
root = op
return root, remains개별 값 파서
개별 값을 처리하는 함수이다. 먼저 +, – 가 앞에 붙어있는 값을 처리하기 위해 맨 앞의 토큰이 이러한 부호인지 판단하고, 부호인 경우 0 + expr, 0 – expr 의 형태로 취급하면 된다. 부호를 제외한 값은 INT, FLOAT 타입인 경우에는 그 토큰을 그대로 취하면 되고, 괄호로 시작되는 경우에는 다항식을 파싱한 후 닫는 괄호를 버린다.
괄호와 같이 사용하지 않고 버리는 토큰에 대해서는 타입을 확인하고 버리는 보조 함수를 하나 만들어서 사용한다. 이 보조함수에서는 토큰 타입이 매치하지 않으면 예외를 일으키도록 한다. 이게 필요한 이유는 괄호를 열기만하고 닫지 않은 상황을 방지하기 위해서이다.
거듭제곱은 단항 부호 연산보다도 우선한다. 밑이 되는 값을 파싱한 후 거듭제곱 연산자를 만나면 이를 다른 사칙 연산과 마찬가지로 처리해주면 된다.
def match_token(ts: list[Token], tt: TokenType) -> list[Token]:
t, ts = ts[0], ts[1:]
if t.type == tt:
return ts
raise ValueError(f"Invalid Token: {t}")
def parse_factor(tokens: list[Token]) -> tuple[Token, list[Token]]:
res = None
if tokens[0].type in (TokenType.PLUS, TokenType.MINUS):
res, remains = remains[0], remains[1:]
left = Token(TokenType.INT, "0")
right, tokens = parse_factor(tokens)
res.children = [left, right]
elif tokens[0].type in (TokenType.INT, TokenType.FLOAT):
res, remains = remains[0], remains[1:]
elif tokens[0].type == TokenType.LPAR:
tokens = match_token(tokens, TokenType.LPAR)
res, tokens = parse_expression(tokens)
tokens = match_token(tokens, TokenType.RPAR)
if res and tokens[0].type == TokenType.POW:
op, remains = remains[0], remains[1:]
right, tokens = parse_factor(tokens)
op.children = [res, right]
res = op
return res, tokens수식 평가하기
이것으로 파서의 구현은 마무리 됐다. 이제 실제 계산 기능을 구현하자. 계산 기능은 토큰 객체가 자신을 평가하는 것으로 수행되면 된다. 토큰의 타입이 정수나 실수이면 그 자신의 값으로 평가되면 되며, 연산자인 경우에는 왼쪽과 오른쪽 자식 노드를 해당 연산자로 연산하면 된다.
class Token:
....
def eval(self):
if self.type == TokenType.INT:
return int(self.value)
if self.type == TokenType.FLOAT:
return float(self.value)
l, r = map(lambda x: x.eval(), self.children)
if self.type == TokenType.PLUS:
return l + r
if self.type == TokenType.MINUS:
return l - r
if self.type == TokenType.MUL:
return l * r
if self.type == TokenType.DIV:
return l / r
if self.type == TokenType.POW:
return l**r
if self.type == TokenType.REMAIN:
return l % r
return None정리
이제 필요한 조각들은 다 준비되었다. 이제 계산기로 동작하는지 시험해보자. 입력 받은 수식을 파싱한 결과에서 남은 토큰은 [.END] 하나만 존재해야 한다. 만약 다른 토큰이 남아있다는 것은 “1 + 2 3” 과 같이 전체가 다 파싱될 수 있는 수식이 아닌 것이다.
def process(s: str):
e, x = parse_expression(lex(s))
if x[0].type != TokenType.END:
raise ValueError(f"Invalid Token: {x[0]}")
return e.eval()
if __name__ == "__main__":
s = input("=: ")
print(process(s))코드 전문은 아래 링크에 있다.