[コンパイラ] 05. 有限オートマトンと字句解析器の実装

有限オートマトンと字句解析器の実装

正規表現はトークンのパターンを仕様化するツールであり、有限オートマトンはそれを認識する実行モデルです。この記事では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の主要な特徴

一つの入力に対して複数の遷移が可能です。
イプシロン（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つの遷移のみあります。
イプシロン遷移がありません。

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の規則衝突解決

複数のパターンが同時にマッチした場合の規則です。

最長一致（Longest Match）: 最も長くマッチするパターンを選択します。
- 入力が ifx の場合、キーワード if ではなく識別子 ifx として認識します。
規則優先順位（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. 有限オートマトン（Finite Automata）概要

2. NFA（非決定性有限オートマトン）

NFAの主要な特徴

NFAの例: (a|b)*abb

遷移テーブル

NFAの文字列受理

3. DFA（決定性有限オートマトン）

DFAの例: (a|b)*abb

遷移テーブル

DFAシミュレーションアルゴリズム

4. 正規表現からNFAへ: Thompson構成

基本構成要素

和集合: r | s

連接: rs

閉包: r*

Thompson構成の例: (a|b)*abb

5. NFAからDFAへ: 部分集合構成

核心アイデア

必要な演算

アルゴリズム

部分集合構成の例

6. DFA最小化

Hopcroftアルゴリズム

最小化の例

7. Lexツールを活用した字句解析器の生成

Lexプログラムの構造

Lexプログラムの例

Lexの動作原理

Lexの規則衝突解決

8. 正規表現からDFAへの直接変換

主要な関数

まとめ

NFAの例: `(a|b)*abb`

DFAの例: `(a|b)*abb`

Thompson構成の例: `(a|b)*abb`