コンテンツにスキップ

0953: re で作る字句解析器

問題

コンパイラの字句解析（トークン化）は、トークンの種別ごとの正規表現を | で合成した 1 つのパターンで実装できます。 このとき「今の位置から最も長く一致するトークンを選ぶ」規則を最長一致（maximal munch）と呼びます。 たとえば <= は < と = の 2 トークンではなく、1 つの <= として切り出します。

次の小さな式言語の字句解析器 tokenize(src: str) -> list[tuple[str, str]] を、re モジュールの名前付きグループ (?P<名前>...) と finditer()（または scanner 相当の繰り返しマッチ）で実装してください。 戻り値は出現順の (種別, 字句) のリストです。

トークンの種別は次の 3 つです。

種別 定義
NUMBER 1 文字以上の数字列。直後に . と 1 文字以上の数字列が続く場合はそこまで含む（例：42、3.14）
NAME ASCII の英字または _ で始まり、英数字と _ が続く並び
OP == != <= >= + - * / = < > ( ) のいずれか

空白（スペース、タブ）と改行はトークンにせず読み飛ばします。 どの種別にも一致しない文字に出会ったら、その位置（1 始まりの行番号と列番号）を含むメッセージの SyntaxError を送出します。

制約

  • src は str です。空文字列に対しては空のリストを返します。
  • 最長一致を満たすこと。3.14 は 1 つの NUMBER、<= や == は 1 つの OP になります。
  • 不正な文字に対する SyntaxError のメッセージは「例」に示す形式に合わせます。行番号と列番号は 1 始まりで、改行のたびに行番号を増やし列番号をリセットします。
  • 字句解析は入力を先頭から 1 回走査するだけで行います。種別ごとに入力を何度も走査してはいけません。

例

>>> tokenize("x = 3.14 + y2")
[('NAME', 'x'), ('OP', '='), ('NUMBER', '3.14'), ('OP', '+'), ('NAME', 'y2')]
>>> tokenize("a<=b == c")
[('NAME', 'a'), ('OP', '<='), ('NAME', 'b'), ('OP', '=='), ('NAME', 'c')]
>>> tokenize("f(x) - 2*y\n  + 10")
[('NAME', 'f'), ('OP', '('), ('NAME', 'x'), ('OP', ')'), ('OP', '-'), ('NUMBER', '2'), ('OP', '*'), ('NAME', 'y'), ('OP', '+'), ('NUMBER', '10')]
>>> tokenize("")
[]
>>> tokenize("x = 1\ny $ 2")
Traceback (most recent call last):
    ...
SyntaxError: 2行3列: 予期しない文字 '$'

発展

(種別, 字句, 行, 列) を持つトークンを yield するジェネレータ版を実装してください。 さらに、キーワード（if、else、while など）を導入し、NAME に一致した字句がキーワードなら種別を KEYWORD に振り替える処理を追加してください。 正規表現の | は最長一致ではなく左から順に試すことを踏まえて、NUMBER と NAME と OP の並べ方によって結果が変わる入力があるかも考察してください。

参考