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

小さな式言語の字句解析器を作る

数字・変数名・演算子を位置付きのトークンへ分け、空白、末尾、不正な文字の扱いを実行して確認します。

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

更新日

この記事の目次
  1. 入力と出力の契約を決める
  2. 実行前に文字の範囲を確認する
  3. 一文字ずつ位置を進める
  4. コードと期待する列を照合する
  5. 不正な文字を黙って消さない
  6. 条件を変えて規則の限界を見る
  7. 課題と解答を手で確認する
  8. この記事をロゲイアに質問する理解を確かめる

入力と出力の契約を決める

この実験では、12 + price_2という文字列から、整数、加算記号、変数名、入力末尾を表す四つのトークンを作ります。各トークンは種類、元の綴り、開始位置の三つ組です。整数を数値へ変換する処理はまだ行わず、12という文字列を残します。綴りを残しておけば、先頭のゼロを認めるかなどの規則を後から調べられます。開始位置はPython文字列の添字で、UTF-8のバイト数ではありません。この違いを曖昧にすると、表示したエラー位置と実際の入力がずれます。まず紙の上で、12は位置0、+は位置3、price_2は位置5と書き込んでください。期待する列を先に用意し、コードの出力に合わせて正解を作り変えないことが、この実験での確認方法です。

実行前に文字の範囲を確認する

Python 3.12以降の標準ライブラリだけを使います。コード全体をscanner.pyへ保存し、python scanner.pyで実行してください。認識する整数はASCIIの0から9、名前の先頭はASCII英字かアンダースコア、続く部分には数字も認めます。演算子と括弧は一文字ずつ読みます。空白としてはisspaceが真になる文字を飛ばしますが、名前や整数の認識へ同じ判定を流用していません。数字に見える文字や日本語の名前を試して拒否された場合、この小さな言語の対応範囲外という結果です。実用言語のUnicode対応を実装したことにはなりません。外部サービスやファイルの入力は使わず、コード中の短い文字列だけを処理するため、準備用のデータや終了後に削除するデータベースはありません。

一文字ずつ位置を進める

ループの変数iは、次にまだ読んでいない文字の位置です。空白ならiを一つ進め、それ以外ならその位置から規則に合うまとまりを探します。re.searchではなくre.matchを使うのは、後ろにある都合のよい文字を探して、不正な先頭文字を飛び越えないためです。整数の規則は数字の続く部分全体を読むので、12を1と2へ分けません。読めた綴りの長さだけiを増やすことで、次の処理は必ず先へ進みます。正規表現に空文字へ一致する選択肢を加えると、この性質を壊す可能性があります。修正するときは「成功する一回の処理で何文字を消費するか」も確認してください。全ての入力を読んだ後には、綴りが空のEOFを追加します。空入力にも同じ末尾トークンを返すので、後のパーサは入力の終わりを一つの方法で判定できます。

コードと期待する列を照合する

実行すると、12、+、price_2、EOFの三つ組が順に表示されます。assertは綴りと位置も含めて比較しているため、数字だけ正しく読めても、位置がずれれば失敗します。二つの空白だけを渡した試験では、位置2のEOFだけが残ります。空白をトークンへ出さないことと、入力位置を更新しないことは別です。また12aの試験では、12とaの二つのトークンが残ります。この字句解析器は二つの値の間に演算子が必要かまでは判定しません。後段のパーサが、最初の式の後にNAMEが余ったことを拒否する設計です。段階ごとの責務を分けるため、ここで何もかもエラーにする規則を足すのではなく、各段階が受け取る列と返す結果を明記します。位置情報が意図どおりか、表示されたタプルを元の文字列の添字へ戻して確かめてください。

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


source = "12 + price_2"
assert scan(source) == [('NUM','12',0), ('+','+',3), ('NAME','price_2',5), ('EOF','',12)]
assert scan("  ") == [('EOF','',2)]
assert scan("12a")[:2] == [('NUM','12',0), ('NAME','a',2)]
try:
    scan("1 + @")
except SyntaxError as error:
    assert str(error) == 'character at 4'
else:
    raise AssertionError('invalid character accepted')
print(scan(source))

不正な文字を黙って消さない

1 + @を渡す試験では、位置4を示すSyntaxErrorが出ることを期待しています。コードはその例外を捕まえて内容を確認するため、正常に検証できれば実験全体は終了コード0で終わります。ここでの成功は、不正な文字を受け入れたことではなく、想定した入力を想定した理由で拒否できたことです。@を空白へ置き換えると字句解析は通りますが、残る1 +は評価できる式ではありません。この変更は、字句解析の成功がプログラム全体の正しさを保証しないことを示します。例外が出なかった場合は、正規表現が広がっていないか、検索位置が固定されているかを確認します。環境によって例外の装飾表示が変わる場合も、元のメッセージと位置を調べ、端末の色やスタックトレース全体の一致だけに依存しない試験にします。

条件を変えて規則の限界を見る

次に変数名を_price2へ変え、名前全体が一つのNAMEになることを予想してから実行します。price-2へ変えると、NAME、減算、NUMの三つへ分かれます。ハイフンを変数名へ認めるように変更すると、同じ綴りを減算として読めなくなる場合があるため、記号の追加は文法と合わせて考える必要があります。<=を追加したい場合も、<と=の一文字の規則より先に二文字の規則を試すのか、最長一致をどう実装するのかを決めます。この教材のコードにはそれらの演算子はないので、実装していない記号が読めたと考えないでください。実験の範囲を保ったまま、空白の増減、名前の長さ、不正文字の場所を一つずつ変えると、どの契約が壊れたかを判断できます。巨大な入力の速度比較より、短い入力で境界を説明することが先です。

課題と解答を手で確認する

課題はa12 + 003の出力を、種類・綴り・位置まで書くことです。解答はNAMEのa12が位置0、+が位置4、NUMの003が位置6、EOFが位置9です。003を数値3へ変えていない点も確認してください。先頭ゼロを拒否する規則を追加したいなら、字句として読んだ後に整数リテラルの規則を検査する方法もあります。元の綴りを早い段階で捨てると、その判断に使う情報がなくなります。さらに1 + @の前へ空白を二つ足した場合、拒否する文字の位置は6になります。種類の列だけを比較する試験では、このずれを検出できません。この二つを自分の説明で追えたら、次はトークン列から木を作る再帰下降パーサへ進んでください。保存したscanner.pyはそのまま残して比較に使えます。作業を終える際に停止すべきサーバーや外部への接続はありません。

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

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

CS基礎を固める · STEP 20

学習コースから次を選ぶ