Pythonで数式を構文解析（1）

はじめに

プログラミング言語を作りたいと思ったので、まずは構文解析の練習を数式でやろうと思います。

仕様

自然数（0を含む）同士のカッコ付き四則演算ができるようにします。
ただし、除算の結果として出て来た小数だけは計算できます。
（つまり有理数は計算できるということですね）

字句解析

さて、まずは入力文字列をトークン（最小の意味単位）のリストに分解します。
英語でlexerとかtokenizerとかいうやつですね。
今回出てくるトークンの一覧は次の通りです。

• 自然数（number）
• "+" (plus)
• "-" (minus)
• "*" (multiply)
• "/" (divide)
• "(" (brace_open)
• ")" (brace_close)

作成に当たって、Pythonのドキュメントを参考にしました。

import re


class Token:
  '''実際にTokenizerが返すのはTokenのリスト'''
  def __init__(self, name, match):
    self.name = name
    self.match = match
  
  def __repr__(self):
    return "<Token name=\"{}\", match=\"{}\">".format(self.name, self.match)


class TokenType:
  '''TokenizerにTokenの種類を登録するためのクラス'''
  def __init__(self, name, regex):
    self.name = name
    self.regex = regex


class Tokenizer:
  def __init__(self):
    self.token_list = []
  
  def add(self, *token_list):
    self.token_list = self.token_list + list(token_list)
  
  def tokenize(self, input_string):
    pattern_str = '|'.join('(?P<{}>{})'.format(i.name, i.regex) for i in self.token_list)
    pattern = re.compile(pattern_str)

    for mo in pattern.finditer(input_string):
      name = mo.lastgroup
      match = mo.group(name)
      yield(Token(name, match))    # 何となくyieldにしたけど、たぶんリストで返してもいいと思います


tokenizer = Tokenizer()
token_type_ls = [
  TokenType('brace_open', '\('),
  TokenType('brace_close', '\)'),
  TokenType('multiply', r'\*'),
  TokenType('divide', '/'),
  TokenType('plus', r'\+'),
  TokenType('minus', '-'),
  TokenType('number', r'\d+')
]
tokenizer.add(*token_type_ls)
print(list(tokenizer.tokenize("5*9*7/8+(2+5)*3")))

次回はいよいよ構文解析の1回目。