木と環境を別々に用意する
構文木が表すのは計算の構造です。x + 3 * (4 - 1)の木だけを見ても、xに対応する値は分かりません。そこで、名前から値への対応を持つ辞書を環境として渡します。xが12なら結果は21、xが2なら結果は11です。式の構造を変えずに入力条件だけを変えられるため、構文解析と評価の役割がはっきりします。実験では木を一度だけ作って二つの環境で使い、途中で木を書き換えていないことも確認します。環境という言葉はOSの環境変数を意味しているのではなく、この評価器へ明示的に渡す名前の対応表です。言語の実装を読むと同じ言葉が異なる範囲で使われるため、何が入っている表なのかを具体的に言えることを目標にしてください。
各節点が返す値を決める
numの節点は保持している整数を返し、nameの節点は環境から名前を検索します。演算子の節点では左の子、右の子の順に値を求め、その二つへ演算を適用します。ここでは整数演算を使い、/は数学的な床関数による整数除算として定義します。そのため、(0 - 7) / 3の結果は-3です。ゼロへ近づく方向へ切り捨てる別言語の規則とは同じではありません。Pythonの記号を似せて使っていても、自作言語の演算を決めずに実装することは避けてください。整数はこの実装のPython整数で表すので、固定ビット幅のオーバーフローを再現する教材でもありません。何を計算する機械を作ったのかを先に述べれば、負数や大きい値を試した結果を、実装ミスと仕様の違いに分けて説明できます。
小さい部分木から計算を追う
x + 3 * (4 - 1)では、加算の左の子を評価してxの値を得ます。次に右の乗算へ進み、その左の子から3、右の減算から3を得るので、乗算の値は9です。最後にxの値へ9を足します。再帰呼出しが戻るたびに、その部分木に対応する値が一つ得られると考えると、呼出しの順序を追いやすくなります。木を平らなトークン列へ戻し、再び優先順位を判定する必要はありません。優先順位はパーサが作った親子関係へ既に反映されています。同じxという名前が複数の場所にあれば、この実装ではその都度環境を検索します。読み取りの途中で環境を変える機構はないため、短い実験では同じ対応を使えます。代入や関数呼出しを追加する場合には、この前提を含めて評価順序と状態の扱いを設計し直します。
単独ファイルを実行する
コード全体をinterpreter.pyへ保存し、Python 3.12以降で実行します。字句解析器とパーサも含むため、外部から関数を読み込む準備は要りません。表示は21 11で、二つの数が同じ木を使った計算の結果です。負数の除算については、表示とは別のassertで-3を確認します。後半の二つの試験では、未定義変数とゼロ除算を意図的に起こし、期待する例外の種類を検査します。例外を確認できたときには実験全体は成功として終わります。エラーが表示されなかったことだけで正常と判断せず、どの経路で成功したのかをコードと対応させてください。環境の辞書は毎回新しく用意し、前の実験で設定したxの値がたまたま残っていたという状態を避けます。再実行しても同じ入力から同じ結果が得られる小さな実験になっています。
import re
def scan(source):
tokens = []
i = 0
while i < len(source):
if source[i].isspace():
i += 1
continue
match = re.match(r'[0-9]+|[A-Za-z_][A-Za-z_0-9]*|[()+*\-/]', source[i:])
if not match:
raise SyntaxError(f'character at {i}')
word = match.group()
kind = 'NUM' if word.isdecimal() else 'NAME' if word[0].isalpha() or word[0] == '_' else word
tokens.append((kind, word, i))
i += len(word)
tokens.append(('EOF', '', i))
return tokens
class Parser:
def __init__(self, source):
self.tokens = scan(source)
self.i = 0
def take(self, kind):
token = self.tokens[self.i]
if token[0] != kind:
raise SyntaxError(f'expected {kind} at {token[2]}')
self.i += 1
return token
def atom(self):
kind, word, pos = self.tokens[self.i]
if kind == 'NUM':
self.take('NUM')
return ('num', int(word))
if kind == 'NAME':
self.take('NAME')
return ('name', word)
if kind == '(':
self.take('(')
node = self.expr()
self.take(')')
return node
raise SyntaxError(f'atom at {pos}')
def term(self):
left = self.atom()
while self.tokens[self.i][0] in ('*', '/'):
op = self.take(self.tokens[self.i][0])[0]
left = (op, left, self.atom())
return left
def expr(self):
left = self.term()
while self.tokens[self.i][0] in ('+', '-'):
op = self.take(self.tokens[self.i][0])[0]
left = (op, left, self.term())
return left
def parse(self):
tree = self.expr()
self.take('EOF')
return tree
def evaluate(node, env):
kind = node[0]
if kind == 'num':
return node[1]
if kind == 'name':
return env[node[1]]
left, right = evaluate(node[1], env), evaluate(node[2], env)
if kind == '+': return left + right
if kind == '-': return left - right
if kind == '*': return left * right
if kind == '/':
if right == 0: raise ZeroDivisionError('zero divisor')
return left // right
raise ValueError(kind)
tree = Parser("x + 3 * (4 - 1)").parse()
assert evaluate(tree, {'x':12}) == 21
assert evaluate(tree, {'x':2}) == 11
assert evaluate(Parser("(0 - 7) / 3").parse(), {}) == -3
for source, env, error_type in [('x + 1', {}, KeyError), ('12 / 0', {}, ZeroDivisionError)]:
try:
evaluate(Parser(source).parse(), env)
except error_type:
pass
else:
raise AssertionError(source)
print(evaluate(tree, {'x':12}), evaluate(tree, {'x':2}))構文が正しいことと値が得られることを分ける
x + 1は構文木にできますが、空の環境ではxを検索できずKeyErrorになります。12 / 0も構文木にはできますが、評価中にZeroDivisionErrorになります。どちらもパーサが括弧や演算子の位置を読み違えた結果ではありません。エラーを全てSyntaxErrorへ変えてしまうと、利用者は式の書き方を直すべきか、値の渡し方を直すべきか判断できなくなります。この小さな実装は、例外を教材の観測点としてそのまま使います。実際の製品では、未定義名の箇所や演算子の位置を利用者向けの診断へ付け加えるとよいでしょう。ただし、それにはパーサが節点へ位置情報を残す設計が必要です。後から表示だけを工夫して、保存していない元の位置を正確に復元できるとは限りません。段階の境界でどの情報を渡すかが、診断の質にも関わります。
環境を変える試験と木を変える試験
xだけを変えた試験では、木の形を固定して入力値の影響を見ます。一方、括弧を外したり演算子を変えたりする試験は、木そのものを変える試験です。二つを同時に変えると、結果が変わった理由を切り分けにくくなります。まず同じ木へx=0、x=12を渡し、加算される9は変わらないことを確認します。次にxを12へ固定して、3 * (4 - 1)を3 * 4 - 1へ変えてください。この場合は右側のまとまりが変わり、式全体の値も変化します。読み取り専用の環境だけを扱うこの実験では、同じ木の再評価によって辞書の値が書き換わることはありません。外部入力の型検証や認可をしているわけでもないので、任意のPythonオブジェクトを混ぜる応用では別の制約が必要です。ここでは整数が入った辞書という前提を保ちます。
課題と解答で意味の選択を確認する
課題は、y * 2 + xという一つの木へ、x=1、y=4の環境と、x=5、y=4の環境を渡した結果を求めることです。解答は9と13で、変わったのは最後に加えるxの値だけです。yを省いた環境では、左側の乗算を評価する時点で未定義名の例外になります。次に(0 - 8) / 3の値を予想してください。床による整数除算なので答えは-3で、ゼロへ近い-2ではありません。この違いを説明できれば、ホスト言語の動作を無意識に持ち込まず、評価器の規則を読めています。演算規則を変える場合は、この期待値も仕様変更として見直します。最後に、コード中にPythonのevalを使っていないことを確認しましょう。自分で作った木の種類だけを扱うことが、この小さな処理系の構造を観察できる理由です。外部の式評価機能へ任せたことを、パーサや評価器を実装した実験と取り違えないでください。