字句解析器の設計

字句解析器はソースコードを構文解析用にトークンに分割し、エラー報告、フォーマット、編集をサポートするのに十分な情報を保持します。設計の重点は、入力エンコーディング、ルールの優先順位、位置の単位、エラー時の動作、および参照されるソースコードの所有権を明確にすることです。

トークン：分類、原文、位置の役割分担

不変のソーススナップショットに適した表現は以下の通りです。例中の整数は10進数の数字列であり、演算子は2種類のみを列挙しています。実際の言語ではさらに拡張可能です。

#[derive(Clone, Copy)]
struct Span {
    file: u32,
    revision: u64,
    start: usize,
    end: usize, // UTF-8 バイトオフセット、半開区間
}

enum Operator { Add, Subtract }
enum TokenKind {
    Identifier,
    Integer,
    Operator(Operator),
    Eof,
    Invalid,
}
struct Token {
    kind: TokenKind,
    span: Span,
}

原文は、まだ生存しているスナップショットのスライスから span を通じて取得できるため、各トークンに文字列を保持する必要はありません。テキストを直接借用するか、識別子を SymbolId として留保することもできます。参照がソースバッファのライフサイクルを超えないようにする必要があります。文字列の生表記とエスケープ後の値は区別すべきであり、数値の構文認識とターゲット型でのオーバーフローチェックは段階的に行うことも可能です。

パーサーは Operator(Add) によって加算記号を判断でき、各演算子が列挙体のトップレベルのバリアントである必要はありません。粒度は利用者に奉仕するものであり、DFA（決定性有限オートマトン）の状態数から唯一の表現を逆算してはなりません。

一致ルール：キーワードは分類戦略の一つに過ぎない

最長一致を優先し、同じ長さの場合の衝突を解決します。ifx は完全な識別子として扱われ、キーワード if と x に先に分割されてはいけません。

キーワードは生成器のルールに直接書き込むこともできますし、まず識別子として認識してからキーワードテーブルを参照することもできます。前者はオートマトンが共通接頭辞を共有するため有利であり、後者は言語バージョンや予約語の一元管理が容易です。通常のハッシュテーブル、完全ハッシュ、ソート済みテーブル、または長さによる分岐など、適用される場面があります。キーワードが少数だからといって、必ず状態の爆発を引き起こすわけではありません。

文脈依存キーワードは、まず Identifier として保持し、パーサーがその位置が合法かどうかを判断することがあります。生識別子、文字列補間、インデントトークン、ネストされたコメントなどは、字句状態、状態スタック、またはカウンターを必要とする場合があります。字句解析器と構文解析器の境界は言語設計と実装の選択によるものであり、すべてのルールを正規表現だけで完遂できるわけではありません。

Span：スナップショットにバインドし、半開区間を使用する

[start, end) は長さとスライスの計算が容易であり、空の区間は欠落したトークンの挿入位置を表すこともできます。バイトオフセットは、所属するソースコードのバージョン内でのみ有効です。先頭に1文字挿入すると、それ以降のオフセットは変化します。IDE は新しいスナップショットで再解析するか、編集マッピングを通じて変換する必要があります。古いオフセットをバージョンを跨ぐ安定したアイデンティティとして扱うことはできません。

行頭テーブルは各行の開始バイトオフセットを保持しており、通常は 0 で始まります。位置 offset が属する行を照会するには、offset 以下で最後の行頭を探す必要があります。offset が行頭のいずれかと完全に一致することを要求してはいけません。

from bisect import bisect_right

def byte_line_column(line_starts, offset):
    # 前提条件：テーブルは同一スナップショットに属し、0 <= offset <= ファイルバイト数
    row = bisect_right(line_starts, offset) - 1
    return row + 1, offset - line_starts[row] + 1

assert byte_line_column([0, 6], 4) == (1, 5)
assert byte_line_column([0, 6], 6) == (2, 1)

これはバイト列であり、Unicode 符号点列、UTF-16 列、または画面列ではありません。タブ、結合文字、ワイド文字は表示幅に影響を与えます。エディタプロトコルとの間で位置を交換する際は、合意されたエンコーディングに従って変換する必要があります。LSP の関連規約については Language Server Protocol を参照してください。CRLF を1回の改行として数える方法や、ファイル末尾の空行の表現方法についても、ソースファイル管理層で統一する必要があります。

イテレーションインターフェースと先読みキャッシュ

基本インターフェースは next_token() だけで構いません。パーサーのトークンバッファ層が peek、advance、expect を提供します。最初の peek はスキャンをトリガーし、その後の peek はキャッシュを再利用します。peek を O(1) と主張するために、すべてのスキャンを事前に発生させることを強制する必要はありません。

固定 k 個のトークンの先読みには小さなキューを使用できます。試行解析をサポートする場合、チェックポイントはトークンカーソルと関連するパーサー状態をカバーする必要があります。字句解析器がパーサーによってモードが切り替えられる場合、ロールバック時にはモードの復元またはキャッシュの互換性を保証する必要があります。バイトカーソルを1つ戻すだけでは、すべての状態が復元されたと見なしてはいけません。

EOF は安定した終了状態であるべきです。上位層が EOF で繰り返し peek しても境界外エラーを引き起こしてはいけません。復旧ループも、EOF を繰り返し受信することを進捗として誤認してはいけません。

入力管理：ファイル全体とストリーミングウィンドウの両方が妥当

通常のソースファイルは、スパンのスライス、複数回の解析、診断のために不変バッファに直接読み込まれることがよくあります。ファイル全体を読み取ることは有効な設計であり、メモリを多く占有するかどうかはプロジェクトの規模、並列ファイル数、保持ポリシーに依存します。

ストリーミングスキャンは常驻入力を削減できますが、トークンはバッファ境界を跨ぐ可能性があります。実装は未完了のトークンとロールバック範囲を保持し、必要に応じて拡張、移動、またはコピーする必要があります。4 KiB を超えるからといって、長い文字列が自然に無効になるわけではありません。

ダブルバッファリングが自動的に I/O とスキャンの並列化を意味するわけではありません。並列化には明確な非同期またはスレッドメカニズムが必要です。mmap はオンデマンドマッピングを提供しますが、ファイルのライフサイクル、マッピングの無効化、ランダムアクセスのコストに関する考慮を免除するものではありません。re2c はバッファの補充と境界チェックを統合コードの設定に委ねています。re2c 入力処理

入力ブロックの終了はトークンの終了ではなく、文字の終了でもないかもしれません

入力の最初のブロックがちょうど if であると仮定します。次のブロックが x で始まる場合、完全なトークンが ifx になる可能性があるため、今すぐキーワードを出力することはできません。入力ブロックは、中 という文字の3つの UTF-8 バイトの途中でも停止する可能性があります。デコーダは継続バイトを待つ必要があり、字句解析器はトークンの境界を決定するのに十分な文字を待つ必要があります。2つの状態はそれぞれの責任を持っています。

以下は、非常に小さなバッチフィードインターフェースを実装したものです。識別子は ASCII に限定され、キーワードは if のみ、整数は10進数字のみを受け付けます。演算子は = と == で、空白はスペース/タブ/CR/LFのみです。他の有効な Unicode 符号点は Invalid を生成し、無効な UTF-8 は終了してデコードエラーを投げます。中 や絵文字を「無効な UTF-8」として扱うわけではありません。

import codecs
import re

class StreamingLexer:
    def __init__(self):
        self.decoder = codecs.getincrementaldecoder("utf-8")("strict")
        self.pending = ""
        self.offset = 0
        self.closed = False

    def feed(self, data, final=False):
        if self.closed:
            raise ValueError("input already finalized")
        self.pending += self.decoder.decode(data, final=final)
        result = []
        while self.pending:
            first = self.pending[0]
            match = re.match(r"[A-Za-z_][A-Za-z_0-9]*|[0-9]+", self.pending)
            if match:
                text = match.group()
                if len(text) == len(self.pending) and not final:
                    break  # 後続の識別子/数字文字が続く可能性がある
                kind = "If" if text == "if" else "Integer" if text[0].isdigit() else "Identifier"
            elif first == "=":
                if len(self.pending) == 1 and not final:
                    break  # 次のブロックで = が == に延長される可能性がある
                text = "==" if self.pending.startswith("==") else "="
                kind = "Equal" if text == "==" else "Assign"
            else:
                text = first
                kind = "Whitespace" if first in " \t\r\n" else "Invalid"
            end = self.offset + len(text.encode("utf-8"))
            if kind != "Whitespace":
                result.append((kind, text, self.offset, end))
            self.offset = end
            self.pending = self.pending[len(text):]
        if final:
            self.closed = True
            result.append(("Eof", "", self.offset, self.offset))
        return result


def lex_chunks(chunks):
    lexer, result = StreamingLexer(), []
    for chunk in chunks:
        result.extend(lexer.feed(chunk))
    return result + lexer.feed(b"", final=True)

raw = "ifx == 中 😀 if 12".encode("utf-8")
expected = lex_chunks([raw])
assert [(kind, text) for kind, text, start, end in expected] == [
    ("Identifier", "ifx"), ("Equal", "=="), ("Invalid", "中"),
    ("Invalid", "😀"), ("If", "if"), ("Integer", "12"), ("Eof", "")]
for cut in range(len(raw) + 1):
    assert lex_chunks([raw[:cut], raw[cut:]]) == expected
assert lex_chunks([bytes([b]) for b in raw]) == expected
for kind, text, start, end in expected:
    assert raw[start:end].decode("utf-8") == text
for invalid in (b"\xff", b"\xe4\xb8", b"\xc0\xaf"):
    try:
        lex_chunks([invalid])
    except UnicodeDecodeError:
        pass
    else:
        raise AssertionError("invalid UTF-8 accepted")

考えられるすべてのバイトの切り替え位置を試すことで、if/x、=/=、および 中 や絵文字内部の分割を同時にカバーします。出力されるトークンの原文とバイト範囲は完全に一致し、I/O チャンクの変化に左右されてはいけません。末尾の final=True は重要です。これにより、保留中の if がキーワードとして分類され、デコーダが未完成の UTF-8 シーケンスを報告するよう要求されます。Python 増分デコーダインターフェース

この教育用実装は pending 文字列をコピーし、終了していない長いトークンを最初から繰り返しマッチングするため、線形時間や固定メモリを保証しません。実際のストリーミング字句解析器は、スキャン状態とカーソルを保存し、適切なリソース予算を設定する必要があります。また、空白をスキップするため、損失のないトークンストリームを構成していません。feed を閉じた後はデータの追加提出を拒否します。パーサー向けの peek/next 包装層は最後の Eof をキャッシュし、安定した終了照実装を実現できます。

バイトが届いたからといって、文字とトークンが完全に整うわけではない？

受信の進捗をそのままスキャンの完了進捗として扱うことはできません。以下では、意図的にスライダーを if の後、単一の等号の後、中国語バイトの途中、絵文字バイトの途中に停止させます。これらの位置では、それぞれトークンの境界証拠または完全な文字が不足しています。確認済みのトークンは元のバイト範囲を使用します。まだデコードされていないバイトは、無効な Unicode 文字として偽装されません。EOF は追加の事実であり、事前に EOF を宣言すると、有効な短い入力になることもあれば、切り捨てエラーになることもあります。

Unicode：デコードルールと識別子ルールを分離する

UTF-8 のデコードでは、継続バイト、過長エンコーディング、サロゲート符号点、符号点の上限をチェックする必要があります。先頭バイトだけを見て長さを判断し、盲目的にスキップしてはいけません。入力タイプが有効な UTF-8 であることがすでに保証されている場合は、標準ライブラリのイテレーション境界を利用できます。そうでない場合は、無効なバイトの診断と復旧戦略をまず決定する必要があります。

デコードして符号点を得た後、言語仕様に基づいて識別子が合法かどうかを判断する必要があります。Rust は XID_Start、XID_Continue に関連するルールを使用し、アンダースコアの参加を許可し、NFC 正規化などの要件を規定しています。単独のアンダースコアと生識別子には追加のルールがあります。\w は汎用の言語識別子仕様ではありません。Rust 識別子

正規化後のシンボル比較と元のソースコードの表記を同時に保持できます。名前解決は正規化形式を使用し、診断ではユーザー入力をハイライト表示します。Unicode のバージョンも言語互換性の一部です。

エラー復旧：消費戦略は現在の状態に適合する必要がある

無効な文字は Invalid トークンを生成して有効な符号位を消費できます。無効な UTF-8 は、定められたバイト復旧戦略に従って進行します。閉じられていない文字列、コメント、または補間には、それぞれの終了条件が必要であり、「文字を1つスキップする」と一律に扱うことはできません。複数行の文字列が合法である場合、改行は当然エラー境界ではありません。

1回の復旧は、入力を消費し、状態を変更し、次のステップで進行を保証するか、または明示的に EOF で停止する必要があります。プレースホルダトークンを生成して元の位置に残り、同じエラーを繰り返し報告すると、無限ループを引き起こします。診断はトークンとは別に返すことができ、パーサーがエラー範囲を認識しながら、同じ字句問題を繰り返し報告する必要がなくなります。

手書きかジェネレータか

選択は言語ルールと測定結果によって支持されるべきです。両方とも、最長一致、バッファを跨ぐトークン、Unicode 境界、EOF、および復旧進捗を検証する必要があります。その後、トークンをエラー情報を保持する木にどのように組み立てるかについては、AST 設計とエラー復旧 を参照してください。

Keywords: lexer, token, span, source snapshot, maximal munch, lookahead, Unicode, UTF-8, line table, recovery, re2c