正規表現とオートマトン

正規表現は文字列の集合を記述し、有限オートマトンは入力がその集合に属するかどうかを判定します。字句解析器はこの上に、現在位置からどれくらいの長さの文字列を切り取り、どのトークンに分類するかを答える役割も果たします。この三つの問題の違いを理解して初めて、オートマトン理論を実際の字句解析器に応用できます。

正規言語：有限種類の状態しか記憶できない

連結 ab、選択 a|b、反復 a*、および空文字列と空言語は、古典的な正規表現の基本的な演算を構成します。文字クラスや +、? などは利便性のための構文糖衣です。例えば [0-9]+ は 1 文字以上の 10 進数字を表します。

有限オートマトンの「有限」とは、状態の数が固定されており、入力の長さが増加しても変化しないことを指します。小数点が既に出現したかどうか、文字列が特定の接尾辞で終わるかどうかといった情報を記憶することはできますが、任意の深さの括弧のネストを固定された状態数で記憶することは一般にできません。ネストされたコメントなどの言語規則は、字句解析器が追加のカウンタを用いて処理できますが、これは純粋な有限オートマトンの範疇を超えています。

現代の正規表現ライブラリの構文は、必ずしも古典的な正規言語と一致しません。⁠キャプチャグループはマッチ位置を記録するだけであり、言語の表現力を正規言語の範囲外には拡張しません。一方、後方参照は以前にマッチした任意の長さのコンテンツを再度マッチすることを要求するため、非正規言語を記述する可能性があります。 RE2 はキャプチャグループをサポートしていますが、後方参照はサポートしていません。RE2 構文

NFA：成功する可能性のある経路をすべて並列に保持する

NFA では、同じ状態から同じ文字に対して複数の遷移先が存在することが許され、文字を消費しない ε 遷移も許可されます。入力が受理される条件は、受理経路が少なくとも一つ存在することであり、すべての経路が成功である必要はありません。

トンプソン構成（Thompson construction）は、各正規表現の部分式を入口と出口を持つフラグメントに変換し、それらを組み合わせていきます。連結は前のフラグメントの出口を次のフラグメントの入口に接続し、選択は ε による分岐と合流を追加し、反復（スター演算）は「フラグメント全体をスキップする経路」と「出口から入口に戻って繰り返す経路」の両方を追加します。後戻り用の辺がないグラフでは、1 回のオプションしか表現できず、任意の回数の反復は表現できません。

展開された基本的な正規表現に対して、構成される状態数は式規模に比例します。この結論はオートマトンのサイズに関するものであり、バックトラックエンジンによるマッチング時間の直接比較には使用できません。

NFA のシミュレーションは、アクティブな状態の集合を維持し、文字を読み取るたびに集合を更新し、ε 遷移で到達可能な状態を補完します。各ステップで状態を重複除去することで、同じ「状態、入力位置」の組み合わせを繰り返し探索することを防ぎます。NFA の状態数を m、入力長を n とすると、単純なトンプソンシミュレーションの時間計算量は O(mn)、アクティブ集合の空間計算量は O(m) です。固定されたパターンに対しては、入力に対して線形時間であるとして簡略化されることが多いです。Russ Cox：NFA シミュレーション

DFA：NFA の状態の集合を 1 つの状態として扱う

DFA では、各状態と入力記号に対して、遷移先がただ 1 つだけ存在します。部分集合構成（subset construction）は、「現在あり得る NFA の状態の集合」を事前に DFA の状態としてエンコードします。

図において、ab を読んだ後に q2 が含まれているため受理されます。さらに a を読むと集合 B に戻り、現在の全体文字列は ab で終わらなくなります。状態は、現在の接頭辞をすべて読んだ後に、まだ記憶しておく必要がある情報を表しています。

部分集合構成の手順は以下の通りです：

1. 初期集合は ε-closure({start}) であり、閉包には集合自身が含まれる。
2. 集合 S と文字 c に対して、T = ε-closure(move(S, c)) を計算する。
3. T がまだ番号付けされていない場合、新しい状態を割り当てて作業キューに追加し、S から c への T への遷移を記録する。
4. 新しい集合がなくなるまで繰り返す。任意の NFA の受理状態を含む集合は受理状態としてマークする。

空集合は明示的なデッド状態として表現することも、遷移の欠如として表現することもできます。実際の実装では、すべての Unicode コードポイントを列挙するのではなく、文字の同値クラスや区間を用いて処理するのが一般的です。

NFA に m 個の状態がある場合、潜在的な部分集合は最大で 2^m 個あります。到達可能な集合のみを生成しても、指数関数的に増大する可能性があります。実際の字句規則における NFA と DFA の状態数が近いとは限りません。

直感的な例として、(0|1)*1(0|1){k-1} が挙げられます。これは、末尾から k 番目の文字が 1 であることを要求します。NFA はどの 1 が目標なのかを推測できますが、DFA は直近の k 桁の組み合わせを区別する必要があります。異なる k 桁の接尾辞は、その後の入力で区別できるため、少なくとも 2^k 個の状態が必要です。一方、(a*)* と a* は同じ言語を表しますが、これは最小 DFA が指数関数的に増大する例ではありません。

部分集合構成の実装：図中の 3 つの集合をすべて計算する

図中の NFA は ε 遷移を持たないため、move 後の集合がそのまま次の集合になります。以下では、NFA を直接シミュレートするとともに、到達可能な DFA を構成し、最終的にアルファベット {a,b} に対して長さ 0 から 6 までのすべての 127 個の文字列について結果を比較します。

from collections import deque
from itertools import product

edges = {(0, "a"): {0, 1}, (0, "b"): {0}, (1, "b"): {2}}
start, accept = frozenset({0}), {2}


def move(states, char):
    return frozenset().union(*(edges.get((q, char), set()) for q in states))


numbers, subsets, transitions = {start: 0}, [start], {}
work = deque([start])
while work:
    current = work.popleft()
    for char in "ab":
        target = move(current, char)
        if target not in numbers:
            numbers[target] = len(subsets)
            subsets.append(target)
            work.append(target)
        transitions[numbers[current], char] = numbers[target]

assert set(subsets) == {frozenset({0}), frozenset({0, 1}), frozenset({0, 2})}
for length in range(7):
    for letters in product("ab", repeat=length):
        text = "".join(letters)
        nfa, dfa = start, 0
        for char in text:
            nfa = move(nfa, char)
            dfa = transitions[dfa, char]
        assert bool(nfa & accept) == bool(subsets[dfa] & accept) == text.endswith("ab")

遷移表は、なぜ受理状態が「永遠に成功」ではないかを示しています。C で a を読むと B に戻り、b を読むと A に戻ります。ここでは入力が全体として ab で終わるかどうかを判断しています。もし任意の位置に現れる ab を検索する必要がある場合、受理後の制御ロジックやオートマトンは別途定義する必要があります。

ε 遷移を追加すると、始点および move の結果ごとに閉包を取らなければなりません。以下の閉包モデルは ε ループを許可しており、visited 集合を用いて各状態が 1 回だけ展開されることを保証します。

def closure(seeds, epsilon):
    seen, work = set(seeds), list(seeds)
    while work:
        state = work.pop()
        for target in epsilon.get(state, ()):
            if target not in seen:
                seen.add(target)
                work.append(target)
    return frozenset(seen)


assert closure({0}, {0: {1}, 1: {0, 2}}) == frozenset({0, 1, 2})
assert closure({7}, {}) == frozenset({7})
assert closure(set(), {0: {1}}) == frozenset()

1 つの DFA 状態には、どの NFA 状態が含まれているのか？

ここで最も混乱しやすいのは、「1 本の経路だけをたどる」と「1 つの集合名だけを保存する」の違いです。以下では、同じ接頭辞のスキャンにおける 2 つの表現を並べて示します。NFA はすべての可能な状態を保持し、DFA は集合全体に A、B、C という名前を付けます。入力を直接変更したり接頭辞を選択したりすることで、両者の受理結果が常に一致することを確認できます。ab を読んだ後にさらに a を読むと、受理状態は外れます。「一度受理したからといって」永久に受理されるわけではありません。

$$S_{k+1}=\epsilon \text{-closure}(\mathrm{move}(S_k,c_k))$$

最小化：未来の振る舞いが同じである場合のみ結合可能

2 つの DFA 状態が同値であるとは、それらから出発して、任意の后续文字列に対して同じ受理結果が得られることを意味します。最小化では、まず出力に基づいて分類し、未来の振る舞いが異なる状態を繰り返し分割していきます。

通常の認識器では、受理状態と非受理状態にまず分類できます。⁠字句解析器では、受理動作をさらに区別する必要があります。 Identifier（識別子）と Number（数値）はどちらも受理状態ですが、受理の真偽値のみを見て結合すると、トークンの種類や規則の優先順位が失われます。

Hopcroft アルゴリズムは、分割器とその遷移の逆前駆を用いて分区を細分化し、作業キューと小さな部分集合の戦略を用いて重複処理を制御します。「変化しなくなるまで繰り返しスキャンする」というのは一般的な分割細分化であり、Hopcroft の計算量を証明するには不十分です。n 個の状態、アルファベットサイズ k の一般的な表記は O(kn log n) です。アルファベットが固定されている場合は O(n log n) と簡略化されます。これもすべての計算モデルに対する統一された最適下界を主張するものではありません。

最小状態数が、必ずしも最速の機械語マシンを意味するわけではありません。分岐の配置、テーブルのサイズ、キャッシュのヒット率、ベクトル化もスループットに影響します。最小化を行うかどうかや、具体的な生成形式は、ツールや設定によって決定されます。

最長一致と規則の優先順位

複数のトークン規則を認識器に組み込んだ後、1 回のスキャンでは、最後の受理位置と受理動作を保持し、これ以上進めなくなった時点でその位置に戻ってトークンを出力します。受理位置が一度も発生しない場合は、字句エラー処理に入ります。

re2c の規則選択は、まずマッチの長さを比較し、長さが等しい場合はより早い規則を選択します。キーワードは、まず識別子としてスキャンしてからテーブルで分類することもでき、どちらのルートも有効です。re2c マニュアル

「1 回の DFA 遷移は定数時間」という事実だけで、最長一致を行う字句解析器全体が線形時間になるとは限りません。例えば、規則 a と a*b があり、入力が大量の a の後に c が続く場合：単純なスキャナは b を見つけるために末尾までスキャンし、その後 1 文字の a のみ受理して戻ります。これを繰り返すと、二乗時間になる可能性があります。全体の計算量を議論するには、規則のバックトラック距離、実装のメモ化、または他のスキャン戦略を考慮する必要があります。

バックトラックのコストを定量化：遷移は安いが、同じ文字が何度もアクセスされる可能性がある

規則 a と a*b、入力 aaaaac を考えます。位置 0 から開始し、より長い a*b を試すために 5 個の a を読み、c に到達して完了できないことを確認します。最後の受理位置は 1 文字の a のみを出力することを許可しています。次のラウンドは位置 1 から始まり、さらに 4 個の a を読み、以下同様です。a 上での進歩だけでも 5+4+3+2+1=15 回になります。

def rescans(n):
    source = "a" * n + "c"
    visits = 0
    for start in range(n):
        cursor = start
        while source[cursor] == "a":
            visits += 1
            cursor += 1
        # a*b は失敗；1 文字の a の受理位置に戻り、次のラウンドは start+1 から開始。
    return visits


assert rescans(5) == 15
for n in (1, 10, 100):
    assert rescans(n) == n * (n + 1) // 2

ここでは、a を成功裏に跨ぐ回数のみを個別に集計しており、各ラウンドで c 上で失敗するチェックは含まれていません。二次項はすでに接尾辞の繰り返しスキャンに由来しており、各状態遷移自体を高価な操作にする必要はありません。改善には、規則のバックトラックを制限する、失敗した接尾辞情報を記録する、または適切なスキャンアルゴリズムを採用する必要があります。「DFA を使用しているから」という理由だけで、トークンストリーム全体の処理が線形時間であると証明することはできません。

遷移は安価なのに、なぜスキャンが二乗時間になるのか？

計算量を評価するには、同じ入力位置が何回アクセスされたかを数える必要があります。1 回のスキャンを 1 行として描画すると、末尾の c によって三角形が形成されているのがわかります。1 行目は n 個の a を跨ぎ、次の行は n-1 個、最後は 1 個のみを跨ぎます。末尾が b に変わると、規則 a*b は 1 回で文字列全体をカバーし、接尾辞の繰り返しスキャンは発生しません。図では a 上での進歩のみを集計しており、誤った文字 c の処理は別途計算されます。

$$W(n)=\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$$

オートマトンとバックトラックエンジンの比較

実際のライブラリでは複数の戦略が組み合わされることがあります。キャプチャ位置や貪欲な消去には追加の情報が必要ですが、それが実装に指数関数的なバックトラックを強制するわけではありません。信頼できないパターンに対しては、コンパイル時のメモリ制限を考慮する必要があります。信頼できない入力に対しては、マッチングの作業量を考慮する必要があり、これらを混同して「線形安全」というラベルを貼ってはなりません。

さらに読む

字句解析器の設計 では、これらの規則をトークン、位置、バッファ、およびエラーリカバリインターフェースに落とし込みます。再帰下降と LL 解析 では、トークン間のネスト構造の処理を続けます。

Keywords: regular language, Thompson construction, NFA, DFA, subset construction, epsilon closure, Hopcroft, maximal munch, capture, backreference, ReDoS