ふと数式の簡単な構文解析くらいできないとダメだよなと思ってやってみたんですが、意外と苦戦してしまったので忘れないように書いてみました。今回は再帰降下法と操車場アルゴリズムの2つを試してみます。
実装対象
今回は+, -, *, /, () をサポートしたものを作ろうと思います。例えば myeval("1+2") では 3 が返ってきてくれるとうれしいです。
再帰降下法
再帰降下法は再帰的な構造を利用して構文解析を行う手法です。考え方を以下で説明していきます。
考え方
素朴な考え方
今回使用するBNF (Backus-Naur form)を考えます（知らなくても大丈夫です）。
数式はこのBFNを用いて以下のように書くことができます。
expr := <term> | <expr> + <term> | <expr> - <term>
term := <factor> | <term> * <factor> | <term> / <factor>
factor := (<expr>) | <number>
number := [0 - 9]*
ここで epxr は加減式、 term は乗除式、 factor は () でくくられた式または数、 number は数を表します。
たとえば、 (1+2)*3 を考えると (1+2)*3 全体が expr でこれは1つの term からなります。この term は term1 * factor2 と分解できて (term1 は (1+2) 、 factor1 は 3 に該当)、さらに term1 は factor1-1 からなります。 facotor2 は number で factor1-1 は (expr1-1-1) （expr1-1-1 は 1+2 に該当）と分解されます。（文字にするとややこしい...）
しかし、このBFNを直接実装すると問題が起こります。 expr を定義する際に、最初に評価するべき式が expr か term なのかわからないため、先読みを行ってどちらを評価すべきか決定する必要があります。
この問題は一見 expr := <term> | <term> + <expr> | <term> - <expr> とすれば解消できると思いますが、 これは間違いです。
なぜかというと上のように定義して再帰をまわすと右結合で評価されてしまうため、 1-2-3 といった式が 1-(2-3) として評価されてしまいます。
左再帰の解消
それではどのように考えればよいかというと、以下のようなEBNFを使うことで解決されます。
expr := <term>[+,-<term>]*
term := <factor>[*,/<factor>]*
factor := (expr) | number
number := [0-9]*
これは再帰というよりはwhile文で実装するイメージです。
以下のように考える方法もありますが、実装方針が上のほうがわかりやすかったので、こちらを採用します。
expr := <term> <expr'>
expr' := + <term> <expr'> | - <term> <expr'> | eps
term := <factor> <term'>
term' := * <factor> <term'> | / <factor> <term'> | eps
factor := (<expr>) | <number>
number := [0 - 9]*
なお、 eps は空文字です。
実装
実装はうえで考えたEBNFを素朴に書けば終わりです。ただしどこまでパースしたのかという位置情報をposとして持たせています。
pos = 0
def myeval(line):
global pos
pos = 0
return expr(line.replace(" ", ""))
def expr(line):
global pos
v = term(line)
while pos < len(line) and (line[pos] == "+" or line[pos] == "-"):
op = line[pos]
pos += 1
if op == "+":
v = v + term(line)
elif op == "-":
v = v - term(line)
return v
def term(line):
global pos
v = factor(line)
while pos < len(line) and (line[pos] == "*" or line[pos] == "/"):
op = line[pos]
pos += 1
if op == "*":
v = v * factor(line)
elif op == "/":
v = v / factor(line)
return v
def factor(line):
global pos
v = None
if line[pos] == "(":
pos += 1
v = expr(line)
if pos == len(line) or line[pos] != ")":
raise IllegalExpressionException()
pos += 1
else:
v = number(line)
return v
def number(line):
global pos
tmp = ""
is_float = False
while pos < len(line) and line[pos] in char_dct:
if line[pos] == ".":
is_float = True
tmp += line[pos]
pos += 1
if is_float:
return float(tmp)
else:
return int(tmp)
操車場アルゴリズム
操車場アルゴリズムは中置記法（普通の書き方）で書かれた式を後置記法（逆ポーランド記法）に直すアルゴリズムです。例えば、 1+2 は 1 2 +となり、 1+2*3 は 2 3 * 1 + といったイメージです。なぜ後置記法に直すかというと後置記法はstackを利用して簡単に計算ができるからです（たぶん）。このアルゴリズムでは出力用のキューのほかに演算子を一時的に格納しておくスタックを用意します。
考え方
wikiに詳しい説明があります。wikiのほうは関数などをサポートするようになっていますが、今回はそこまで複雑なことをしないので、トークンを読み込んだあとの処理を以下のように読み替えて使いました。
1. トークンが数値の場合、出力キューにそれを追加する
2. トークンが演算子o1の場合
2.1. スタックのトップが演算子o2で、o1の優先順位がo2以下の場合、o2をスタックからポップして出力キューに追加（これを繰り返す）
2.2. 2.1以外の場合とループを抜けた後場合、o1をスタックにプッシュする
3. トークンが(の場合、スタックにプッシュする
4. トークンが)の場合、(がポップされるまで出力キューにスタックからポップしたトークンをプッシュ（(自体はプッシュせずに捨てる）
これによって後置記法を得た後にスタックを用いて評価をします。
実装
操車場アルゴリズム部分
def make_rev_polish(line):
stack = []
result = []
pos = 0
number_flag = False
float_flag = False
tmp = ""
while pos < len(line):
c = line[pos]
pos += 1
if c in char_list:
if c == ".":
float_flag = True
number_flag = True
tmp += c
if (c not in char_list) and number_flag:
number_flag = False
if float_flag:
result.append(float(tmp))
else:
result.append(int(tmp))
float_flag = False
tmp = ""
if c in pri_dct:
while True:
if len(stack) == 0:
stack.append(c)
break
top = stack.pop()
if top in pri_dct and pri_dct[top] >= pri_dct[c]:
result.append(top)
else:
stack.append(top)
stack.append(c)
break
if c == "(":
stack.append(c)
if c == ")":
while True:
top = stack.pop()
if top == "(":
break
else:
result.append(top)
if number_flag:
if float_flag:
result.append(float(tmp))
else:
result.append(int(tmp))
for c in stack:
result.append(c)
return result
後置記法の評価
def calc_rev_polish(rev_list):
stack = []
for c in rev_list:
if c in pri_dct:
res = 0
v1 = stack.pop()
v2 = stack.pop()
if c == "+":
res = v2 + v1
if c == "-":
res = v2 - v1
if c == "*":
res = v2 * v1
if c == "/":
res = v2 / v1
stack.append(res)
else:
stack.append(c)
return stack.pop()
（エラー処理ががばがばです）
ソースコード
ぼくのgithubにあげておきます。テストケースは正常系だけ試しています（一応通ったからうまく動いていると思いたい）。
まとめ
最初、左再帰のBNFから実装をしようとしてしまいひたすらにバグらせていました（検索すると今回のEBNFで書かれているものが多く、最初のBNFでコーディングしているサイトがなかった...）。なんでだろう...？と考えていくと結構ちゃんと考えないとなんでwhile文を使うと書きやすかったかなどの理由がわかってきて個人的には楽しかったです（そもそもソラで実装できなかったのが恥ずかしい...）。