実験・実装 · 基礎から応用へ

再帰下降パーサで式の構造を確かめる

優先順位と左結合を文法へ落とし込み、構文木の形とエラー位置を実行結果から確認します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 値ではなく木を比較する
  2. 文法を三つの関数へ分ける
  3. 左結合を繰り返しで作る
  4. 独立したファイルで実行する
  5. 入力の終わりも検査する
  6. 規則を変える前に比較する
  7. 課題は二つの木を描き分ける
  8. この記事をロゲイアに質問する理解を確かめる

値ではなく木を比較する

この実験で作るのは、式から答えを計算する電卓ではなく、式のまとまりを表すパーサです。1 + 2 * 3からは加算を根に持つ木を、(1 + 2) * 3からは乗算を根に持つ木を作ります。どちらも演算子と三つの整数を含みますが、親子関係が違います。数値だけを比較すると、たまたま同じ値になる式では木の誤りを見逃すため、assertではタプルの入れ子そのものを照合します。節点の先頭には種類を置き、整数はnumと値、変数はnameと名前、二項演算は記号と二つの子を持つ規則に統一します。括弧は読む順序を変えるために使い、その役割を果たした後は木へ残しません。まず紙に二つの木を描き、根がなぜ変わるかを説明してからコードへ進んでください。

文法を三つの関数へ分ける

式は項の列、項は原子の列、原子は整数・名前・括弧内の式として実装します。加減算の繰り返しをexprへ、乗除算の繰り返しをtermへ置くと、termが返るまで内側の乗除算が完成します。括弧を見たatomはexprを呼び、その呼出しが戻った後で閉じ括弧を要求します。この往復によって、括弧の中にも通常の式と同じ規則が使われます。先頭からexprをすぐ呼ぶ形の左再帰は使いません。入力を一つも消費せず同じ関数を呼び続ける可能性があるためです。単項負号、指数、関数呼出しも今回の文法にはありません。見慣れたPythonの式として解釈せず、この小さな言語が宣言した範囲だけを扱います。どの関数がどこまでトークンを読むかを、呼出しの境界ごとに確かめてください。

左結合を繰り返しで作る

8 - 3 - 1の最初の項は8です。次の減算を読むと、leftは8と3を子に持つ減算の木へ変わります。さらに減算を読むと、その木全体を左の子、1を右の子とする新しい木を作ります。最初に作った木を捨てているのではなく、より大きい木の一部として組み込んでいます。この形なら、後の評価器は木をたどるだけで左結合の意味を実現できます。右側にexprを再帰的に呼ぶ別の実装へ変えると、同じ入力でも右結合になることがあるので注意してください。減算のように結合の向きで値が変わる例を試験に使うと、その違いが見えます。加算の小さい整数だけを試すと、木が違っても答えが一致してしまいます。演算の性質を利用して試験入力を選ぶことも、文法を検証する際の工夫です。

独立したファイルで実行する

Python 3.12以降でコード全体をparser.pyへ保存し、python parser.pyを実行します。字句解析器も含めた単独ファイルなので、前の実験で作ったファイルを変更する必要はありません。字句解析の種類と位置の規則は前の実験と同じです。出力される木では根が+、その右の子が*、さらに右の子が-になっていることを確認してください。ソース中の括弧自体は節点に現れません。テストには二つの正常な木と三つの不正入力が含まれ、全てを確認できれば終了コード0になります。ここで実行できたのは短い式の構文解析であり、任意に深い入れ子や巨大入力を扱える保証ではありません。再帰の深さや保持するトークン数にも上限があるため、外部入力を受けるサービスへ応用する際には別の資源制限が必要です。

python
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


assert Parser("1 + 2 * 3").parse() == ('+', ('num',1), ('*',('num',2),('num',3)))
assert Parser("8 - 3 - 1").parse() == ('-', ('-',('num',8),('num',3)), ('num',1))
for source, expected in [("1 2", 'expected EOF at 2'), ("(1+2", 'expected ) at 4'), ("", 'atom at 0')]:
    try:
        Parser(source).parse()
    except SyntaxError as error:
        assert str(error) == expected
    else:
        raise AssertionError(source)
print(Parser("12 + 3 * (4 - 1)").parse())

入力の終わりも検査する

parseはexprから木を受け取った後、EOFを要求します。これにより1 2のような入力を、1という正しい式だけがあったものとして受け入れなくなります。エラーは位置2でEOFを期待したと報告します。一方、(1+2では式の計算構造は作れても閉じ括弧がなく、位置4で)を要求したと報告します。空入力では原子が一つもないので位置0で止まります。これらは別々の不完全さであり、単に末尾へ何かを付ければ全て直るわけではありません。例外が想定どおりかを確認する試験は、エラー処理を消して正常入力だけ通す変更を防ぎます。表示の見た目より、何を期待し、どの位置の入力に出会ったかを追うことが重要です。実用的な診断では行番号や前後の文字も示せますが、それらの表示を増やす前に、元の位置が正しいことを検証します。

規則を変える前に比較する

加算より弱い演算子を追加するなら、exprより外側に新しい段階を作る方法があります。逆に指数のように右結合にしたい演算子では、今回のleftを更新する繰り返しをそのまま流用できるとは限りません。まず期待する木を決め、その木になる規則を書いてからコードを変えます。括弧の対応が正しいかを調べる際も、括弧の個数が同じというだけでは足りません。)(は個数が一致していても、現在の原子の規則には合いません。文法の責務を文字数の集計だけで置き換えないでください。実験を拡張した場合は、もとの正常入力と拒否入力の試験も残し、変える予定のない規則まで壊していないかを確認します。ここでは新しい演算子の完成品を提供するのではなく、仕様、木、試験、実装の順に変更を考える手順を練習します。

課題は二つの木を描き分ける

課題として、9 - (4 - 1)と9 - 4 - 1の木を描いてください。前者の根は減算で、右の子が4から1を引く減算です。後者の根も減算ですが、左の子が9から4を引く減算になります。後の評価ではそれぞれ6と4になるため、括弧は単なる装飾ではありません。次に1 + )を入力し、原子を期待している位置4で拒否されることを予想します。もし違う位置が出たら、まずscanの位置情報、次にtakeがトークンを進める時点を調べます。木の形だけ正しくても、失敗位置がずれていれば診断の契約は満たしていません。自分でこの二種類の結果を説明できたら、構文木を変数環境と合わせて評価する実験へ進みます。実験はファイル中の文字列だけを扱うため、後片付けは保存したコードを作業用に整理するだけで十分です。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 20

学習コースから次を選ぶ