有限オートマトンと字句解析器の実装
正規表現はトークンのパターンを**仕様化**するツールであり、有限オートマトンはそれを**認識**する実行モデルです。この記事ではNFA、DFA、およびそれらの間の変換を扱います。
1. 有限オートマトン（Finite Automata）概要
有限オートマトンは文字列を認識する数学的モデルです。2つの種類があります。
- **NFA（Nondeterministic Finite Automaton）**: 非決定性有限オートマトン
- **DFA（Deterministic Finite Automaton）**: 決定性有限オートマトン
どちらも正規言語を認識し、表現力は同じです。しかし実装特性が異なります。
正規表現 <=> NFA <=> DFA
- NFA: 構成が簡単だが実行が複雑
- DFA: 構成が複雑だが実行が高速
2. NFA（非決定性有限オートマトン）
NFAは5-タプルで定義されます: (S, Sigma, delta, s0, F)
- **S**: 状態の有限集合
- **Sigma**: 入力アルファベット
- **delta**: 遷移関数（状態と入力に対して**状態の集合**を返す）
- **s0**: 開始状態
- **F**: 受理状態の集合
NFAの主要な特徴
1. 一つの入力に対して**複数の遷移**が可能です。
2. **イプシロン（epsilon）遷移**: 入力なしでも状態を遷移できます。
NFAの例: `(a|b)*abb`
a
+--------+
| |
v a | b b
--> 0 -----> 1 -----> 2 -----> ((3))
|
+--b--+
| |
+<----+
遷移テーブル
状態 | a | b
-----+--------+--------
0 | {0, 1} | {0}
1 | - | {2}
2 | - | {3}
3 | - | -
状態0で入力 `a` を読むと状態0または状態1に行くことができます。これが**非決定性**の意味です。
NFAの文字列受理
NFAは入力文字列に対して開始状態から受理状態へのパスが**一つでも存在**すればその文字列を受理します。
入力: "aabb"
可能なパス:
0 -a-> 0 -a-> 0 -b-> 0 -b-> 0 (受理状態ではない)
0 -a-> 0 -a-> 1 -b-> 2 -b-> 3 (受理状態!) -> 受理
0 -a-> 1 (次のaに対する遷移なし) -> 失敗
3. DFA（決定性有限オートマトン）
DFAはNFAの特殊な場合で、以下の制約があります。
1. 各状態で各入力記号に対して**正確に1つの遷移**のみあります。
2. **イプシロン遷移がありません。**
DFAの例: `(a|b)*abb`
b
+--------+
| |
v a | b b
--> 0 -----> 1 -----> 2 -----> ((3))
^ | |
| b | a | a
+--------+ |
| |
+-----------------+
遷移テーブル
状態 | a | b
-----+-----+-----
0 | 1 | 0
1 | 1 | 2
2 | 1 | 3
3 | 1 | 0
DFAは各状態で各入力に対する遷移が**一意**です。そのため実行が簡単で高速です。
DFAシミュレーションアルゴリズム
public boolean simulate(DFA dfa, String input) {
int state = dfa.startState;
for (char ch : input.toCharArray()) {
state = dfa.transition[state][ch];
if (state == DFA.ERROR) {
return false; // エラー状態
}
}
return dfa.isAccepting(state);
}
DFAのシミュレーションは入力長に比例する**O(n)**時間がかかります。
4. 正規表現からNFAへ: Thompson構成
**Thompson構成（Thompson's Construction）**は正規表現をNFAに変換する体系的な方法です。
基本構成要素
1. 単一文字 a:
(i) --a--> ((f))
2. イプシロン（epsilon）:
(i) --epsilon--> ((f))
和集合: r | s
epsilon NFA(r) epsilon
+----------> (i_r) ...> (f_r) ----------+
| |
(i) ---+ +---> ((f))
| |
+----------> (i_s) ...> (f_s) ----------+
epsilon NFA(s) epsilon
連接: rs
(i_r) --> NFA(r) --> (f_r/i_s) --> NFA(s) --> ((f_s))
rの受理状態とsの開始状態を統合します。
閉包: r\*
epsilon
+-------------------+
| |
(i) --epsilon--> (i_r) --> NFA(r) --> (f_r) --epsilon--> ((f))
| ^
+-------------------epsilon------------------------------+
Thompson構成の例: `(a|b)*abb`
段階的に構成すると以下の通りです。
ステップ1: aのNFA
(2) --a--> (3)
ステップ2: bのNFA
(4) --b--> (5)
ステップ3: a|bのNFA
(1) --eps--> (2) --a--> (3) --eps--> (6)
(1) --eps--> (4) --b--> (5) --eps--> (6)
ステップ4: (a|b)*のNFA
(0) --eps--> (1) --...--> (6) --eps--> (7)
(0) --eps--> (7)
(6) --eps--> (1)
ステップ5: (a|b)*abb完成
... --eps--> (7) --a--> (8) --b--> (9) --b--> ((10))
Thompson構成の特徴は以下の通りです。
- NFAの状態数は正規表現の長さの**最大2倍**です。
- 各状態から出る遷移は**最大2つ**です。
- 開始状態と受理状態が**それぞれ1つ**です。
5. NFAからDFAへ: 部分集合構成
**部分集合構成（Subset Construction）**はNFAを等価なDFAに変換するアルゴリズムです。
核心アイデア
DFAの各状態はNFA状態の**集合**です。NFAが同時に存在できる全ての状態を一つのDFA状態として表現します。
必要な演算
epsilon-closure(s): 状態sからepsilon遷移のみで到達可能な全状態の集合
epsilon-closure(T): 状態集合Tの各状態に対するepsilon-closureの和集合
move(T, a): 状態集合Tから入力aの遷移で到達可能な状態の集合
アルゴリズム
Dstatesにepsilon-closure(s0)を追加し「未処理」とマーク
while (未処理状態TがDstatesに存在) do
Tを「処理済み」とマーク
for (各入力記号a) do
U = epsilon-closure(move(T, a))
if (UがDstatesにない)
UをDstatesに追加し「未処理」とマーク
Dtran[T, a] = U
end for
end while
部分集合構成の例
NFA状態: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
NFA開始: 0, NFA受理: 10
DFA状態 A = epsilon-closure(0) = {0, 1, 2, 4, 7}
move(A, a) = {3, 8}
epsilon-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B
move(A, b) = {5}
epsilon-closure({5}) = {1, 2, 4, 5, 6, 7} = C
DFA状態 B = {1, 2, 3, 4, 6, 7, 8}
move(B, a) = {3, 8} -> B
move(B, b) = {5, 9}
epsilon-closure({5, 9}) = {1, 2, 4, 5, 6, 7, 9} = D
DFA状態 C = {1, 2, 4, 5, 6, 7}
move(C, a) = {3, 8} -> B
move(C, b) = {5} -> C
DFA状態 D = {1, 2, 4, 5, 6, 7, 9}
move(D, a) = {3, 8} -> B
move(D, b) = {5, 10}
epsilon-closure({5, 10}) = {1, 2, 4, 5, 6, 7, 10} = E
DFA状態 E = {1, 2, 4, 5, 6, 7, 10} (10を含む -> 受理状態)
move(E, a) = {3, 8} -> B
move(E, b) = {5} -> C
結果のDFA遷移テーブル:
状態 | a | b | 受理?
-----+-----+-----+------
A | B | C | X
B | B | D | X
C | B | C | X
D | B | E | X
E | B | C | O
6. DFA最小化
部分集合構成で作られたDFAには不要な状態が存在する可能性があります。**DFA最小化**は等価な最小状態DFAを求めます。
Hopcroftアルゴリズム
1. 初期分割: {受理状態}, {非受理状態}
2. 繰り返し: 各グループを検査して、同じグループ内で
ある入力に対して異なるグループへ遷移する状態を分離
3. これ以上分離できなくなったら終了
最小化の例
初期分割:
G1 = {A, B, C, D} (非受理)
G2 = {E} (受理)
入力'b'に対する検査:
A -> C (G1), B -> D (G1), C -> C (G1), D -> E (G2)
Dは異なるグループへ行くので分離！
新しい分割:
G1 = {A, B, C}
G3 = {D}
G2 = {E}
入力'b'に対する検査:
A -> C (G1), B -> D (G3), C -> C (G1)
Bを分離！
最終分割:
{A, C}, {B}, {D}, {E}
7. Lexツールを活用した字句解析器の生成
**Lex**（またはFlex）は正規表現でトークンパターンを記述すると字句解析器を自動生成してくれるツールです。
Lexプログラムの構造
宣言部（declarations）
%%
翻訳規則（translation rules）
%%
補助関数（auxiliary functions）
Lexプログラムの例
%{
#include <stdio.h>
#include "y.tab.h"
%}
digit [0-9]
letter [a-zA-Z]
%%
if { return IF; }
else { return ELSE; }
while { return WHILE; }
{letter}({letter}|{digit})* { return ID; }
{digit}+ { return NUM; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return DIVIDE; }
"=" { return ASSIGN; }
"==" { return EQ; }
"<" { return LT; }
"<=" { return LE; }
"(" { return LPAREN; }
")" { return RPAREN; }
";" { return SEMI; }
[ \t\n]+ { /* 空白を無視 */ }
. { printf("Unexpected: %s\n", yytext); }
%%
Lexの動作原理
Lex仕様 (.lファイル)
|
v
+----------+
| Lex | (Lexコンパイラ)
+----------+
|
v
lex.yy.c (Cソースコード)
|
v
+----------+
| Cコンパイラ |
+----------+
|
v
字句解析器（実行ファイル）
Lexの規則衝突解決
複数のパターンが同時にマッチした場合の規則です。
1. **最長一致（Longest Match）**: 最も長くマッチするパターンを選択します。
- 入力が `ifx` の場合、キーワード `if` ではなく識別子 `ifx` として認識します。
2. **規則優先順位（Rule Priority）**: 同じ長さなら先に記述された規則を選択します。
- `if` は識別子パターンよりキーワード規則が先にあるのでキーワードとして認識します。
8. 正規表現からDFAへの直接変換
Thompson構成と部分集合構成を経ずに、正規表現からDFAを直接構成する方法もあります。
主要な関数
正規表現の構文木のノードnに対して以下を計算します。
- **nullable(n)**: ノードnが空文字列を生成できるかどうか
- **firstpos(n)**: nから生成される文字列の最初の位置になり得る位置の集合
- **lastpos(n)**: nから生成される文字列の最後の位置になり得る位置の集合
- **followpos(p)**: 位置pの次に来ることができる位置の集合
nullable規則:
epsilonノード -> true
位置iノード -> false
cat(c1, c2)ノード -> nullable(c1) AND nullable(c2)
or(c1, c2)ノード -> nullable(c1) OR nullable(c2)
star(c1)ノード -> true
この方法は中間段階のNFAを経由しないため、状態数の少ない効率的なDFAを直接得ることができます。
まとめ
| 概念 | 核心内容 |
| ------------ | ------------------------------------------- |
| NFA | 非決定性、イプシロン遷移可能、構成が簡単 |
| DFA | 決定性、各入力に遷移1つ、実行が高速（O(n)） |
| Thompson構成 | 正規表現をNFAに体系的に変換 |
| 部分集合構成 | NFAをDFAに変換（状態爆発の可能性あり） |
| DFA最小化 | 等価な最小状態DFAの構成 |
| Lex | 正規表現から字句解析器を自動生成 |
| 最長一致 | 複数パターンマッチ時に最も長いものを選択 |
有限オートマトンは字句解析の理論的基盤であり実装の核心です。次の記事では構文解析段階に進み、Top-DownパーシングとLLパーサを見ていきます。
현재 단락 (1/246)
正規表現はトークンのパターンを**仕様化**するツールであり、有限オートマトンはそれを**認識**する実行モデルです。この記事ではNFA、DFA、およびそれらの間の変換を扱います。