第2章：形式言語とオートマトン理論 - パーサー設計の科学
2.1 形式言語理論の誕生
パーサーを設計するには、まず「言語とは何か」を数学的に理解する必要があります。形式言語理論は、言語を厳密に定義し、その構造を分析するためのツールを提供します。
2.1.1 Noam Chomskyと形式言語（1956年）
言語学者Noam Chomsky（ノーム・チョムスキー）は、1956年に発表した論文で、言語を数学的に分類するチョムスキー階層（Chomsky Hierarchy）を提案しました。
チョムスキーの目的は自然言語の文法を研究することでしたが、この理論はコンピュータサイエンスに革命をもたらしました。プログラミング言語の設計、コンパイラの構築、パターンマッチングなど、現代のコンピュータサイエンスの基礎となっています。
チョムスキー階層（Chomsky Hierarchy）:
Type-0: 無制限文法（Unrestricted Grammar）
┌─────────────────────────────────────────────────────┐
│ 認識機械: チューリングマシン │
│ 能力: 任意の計算が可能 │
│ 例: 任意のプログラミング言語 │
│ │
│ Type-1: 文脈依存文法（Context-Sensitive Grammar） │
│ ┌─────────────────────────────────────────────────┐ │
│ │ 認識機械: 線形有界オートマトン │ │
│ │ 能力: 文脈に応じた変換 │ │
│ │ 例: 自然言語の一部の構造 │ │
│ │ │ │
│ │ Type-2: 文脈自由文法（Context-Free Grammar） │ │
│ │ ┌─────────────────────────────────────────────┐ │ │
│ │ │ 認識機械: プッシュダウンオートマトン │ │ │
│ │ │ 能力: 入れ子構造の処理 │ │ │
│ │ │ 例: C言語の構文、括弧のマッチング │ │ │
│ │ │ │ │ │
│ │ │ Type-3: 正規文法（Regular Grammar） │ │ │
│ │ │ ┌─────────────────────────────────────────┐ │ │ │
│ │ │ │ 認識機械: 有限オートマトン │ │ │ │
│ │ │ │ 能力: 単純なパターンマッチング │ │ │ │
│ │ │ │ 例: printfフォーマット指定子 │ │ │ │
│ │ │ └─────────────────────────────────────────┘ │ │ │
│ │ └─────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────┘
2.1.2 各文法クラスの特徴
文法クラスの形式的定義:
文法 G = (N, Σ, P, S) は以下で構成:
- N: 非終端記号の集合（変数）
- Σ: 終端記号の集合（アルファベット）
- P: 生成規則の集合
- S: 開始記号
Type-3 (正規文法):
生成規則は A → aB または A → a の形式のみ
（右正規文法の場合）
Type-2 (文脈自由文法):
生成規則は A → α の形式（Aは非終端記号、αは任意の列）
Type-1 (文脈依存文法):
生成規則は αAβ → αγβ の形式（|γ| ≥ 1）
Type-0 (無制限文法):
生成規則に制限なし
printfフォーマット文字列はType-3（正規言語）
printfのフォーマット指定子は、有限オートマトンで認識可能な正規言語です。入れ子構造がないため、スタックを必要としません。
なぜprintfフォーマット指定子は正規言語なのか？
文脈自由言語の例（括弧のマッチング）:
{ (), (()), ((())), ... }
→ 開き括弧の数を数える必要がある
→ スタック（メモリ）が必要
→ 有限オートマトンでは認識不可能
printfフォーマット指定子:
{ %d, %-5d, %+10.5d, %#08x, ... }
→ 各要素は固定の順序で出現
→ 入れ子構造がない
→ 有限状態で十分
→ 有限オートマトンで認識可能
2.1.3 ポンプの補題（Pumping Lemma）
ある言語が正規言語かどうかを判定する重要な定理がポンプの補題です。
正規言語のポンプの補題:
Lが正規言語ならば、ある長さ p が存在して、
|w| ≥ p である任意の w ∈ L に対して、
w = xyz と分解でき、以下を満たす:
1. |y| > 0
2. |xy| ≤ p
3. すべての i ≥ 0 に対して、xy^i z ∈ L
つまり、十分に長い文字列は「ポンピング」できる部分を持つ。
ポンプの補題による証明例:
言語 L = { a^n b^n | n ≥ 0 } が正規言語でないことの証明:
1. Lが正規言語と仮定
2. ポンプの補題より、ある p が存在
3. w = a^p b^p ∈ L を考える（|w| = 2p ≥ p）
4. w = xyz と分解、|xy| ≤ p より、yは'a'のみからなる
5. y = a^k (k ≥ 1) とすると、
xy^2z = a^(p+k) b^p ∈ L であるべき
6. しかし p+k ≠ p なので a^(p+k) b^p ∉ L
7. 矛盾。よって L は正規言語ではない。
この言語は文脈自由文法で表現可能:
S → aSb | ε
2.2 有限オートマトンの理論
2.2.1 決定性有限オートマトン（DFA）
DFA（Deterministic Finite Automaton）は、正規言語を認識する最も基本的な計算モデルです。
/*
* DFA の形式的定義
*
* DFA M = (Q, Σ, δ, q₀, F) は以下で構成:
*
* Q: 有限状態集合
* Σ: 入力アルファベット
* δ: 遷移関数 (Q × Σ → Q)
* q₀: 初期状態 (q₀ ∈ Q)
* F: 受理状態集合 (F ⊆ Q)
*/
// DFA のC言語実装
typedef struct s_dfa {
int num_states; // |Q|
int alphabet_size; // |Σ|
int **transition; // δ[state][symbol] = next_state
int start_state; // q₀
int *accepting; // F (配列で表現)
} t_dfa;
// DFA による文字列の受理判定
int dfa_accepts(t_dfa *dfa, const char *input)
{
int current_state = dfa->start_state;
while (*input)
{
int symbol = char_to_symbol(*input);
if (symbol < 0 || symbol >= dfa->alphabet_size)
return 0; // 無効な入力
current_state = dfa->transition[current_state][symbol];
if (current_state < 0)
return 0; // 遷移が定義されていない
input++;
}
return dfa->accepting[current_state];
}
2.2.2 非決定性有限オートマトン（NFA）
NFA（Nondeterministic Finite Automaton）は、同じ入力に対して複数の遷移が可能なオートマトンです。
DFA vs NFA:
DFA（決定性）:
┌─────────────────────────────────────────┐
│ 各状態から、各入力記号に対して │
│ 遷移先は一意に決まる │
│ │
│ δ: Q × Σ → Q │
│ │
│ 利点: 実行が単純、O(n)時間で認識 │
│ 欠点: 状態数が指数的に増加する場合あり │
└─────────────────────────────────────────┘
NFA（非決定性）:
┌─────────────────────────────────────────┐
│ 各状態から、各入力記号に対して │
│ 複数の遷移先が可能 │
│ │
│ δ: Q × (Σ ∪ {ε}) → P(Q) │
│ （べき集合への遷移、ε遷移も可能） │
│ │
│ 利点: 設計が直感的、状態数が少ない │
│ 欠点: 実行時にバックトラックが必要 │
└─────────────────────────────────────────┘
重要な定理: DFAとNFAの等価性
DFAとNFAは同じ言語クラス（正規言語）を認識する
証明（概略）:
1. DFA → NFA: 自明（DFAはNFAの特殊ケース）
2. NFA → DFA（部分集合構成法）:
- NFAの状態集合の部分集合をDFAの1状態とする
- 最悪の場合、DFAの状態数は2^|Q|
例: NFA with 3 states → DFA with up to 8 states
2.2.3 ε遷移と拡張NFA
ε遷移（ε-transition）は、入力を消費せずに状態を遷移する機能です。
ε遷移の例:
NFA for (a|b)*:
ε a ε
→ q0 ──→ q1 ──→ q2 ──→ q0
│ ↑
│ b │
└──→ q3 ──┘
ε遷移の利点:
- 正規表現からNFAへの変換が容易
- 複数のパターンを合成しやすい
ε閉包（ε-closure）:
ε-closure(q) = qからε遷移のみで到達可能な状態の集合
2.2.4 正規表現とオートマトンの等価性
Stephen Kleene（1956年）は、正規表現と有限オートマトンが同じ言語を表現することを証明しました。
Kleeneの定理:
言語 L について、以下は同値:
1. L は正規表現で記述できる
2. L は DFA で認識できる
3. L は NFA で認識できる
4. L は正規文法から生成できる
変換アルゴリズム:
正規表現 → NFA: Thompson構成法
NFA → DFA: 部分集合構成法
DFA → 正規表現: 状態除去法
DFA → 正規文法: 直接変換
2.3 Thompson構成法：正規表現からNFAへ
2.3.1 Thompson構成法の概要
Ken Thompson（1968年）は、正規表現からNFAを構成するアルゴリズムを開発しました。これはUNIXのgrepコマンドの基礎となりました。
Thompson構成法の基本ルール:
1. 空文字列 ε:
→ ○──ε──◎
2. 単一文字 a:
→ ○──a──◎
3. 連結 RS:
[R のNFA]──ε──[S のNFA]
4. 選択 R|S:
ε──[R のNFA]──ε
/ \
→ ○ ◎
\ /
ε──[S のNFA]──ε
5. 閉包 R*:
ε
┌────────────┐
│ │
→ ○──ε──[R のNFA]──◎
│ │
└──────ε─────┘
2.3.2 Thompson構成法の実装
/*
* NFAのノード構造
*/
typedef struct s_nfa_node {
int id;
int is_accepting;
struct s_nfa_edge *edges; // このノードからの遷移
} t_nfa_node;
typedef struct s_nfa_edge {
int symbol; // -1 = ε遷移
t_nfa_node *target;
struct s_nfa_edge *next;
} t_nfa_edge;
typedef struct s_nfa {
t_nfa_node *start;
t_nfa_node *end;
} t_nfa;
/*
* 基本構成: 単一文字
*/
t_nfa *nfa_char(int symbol)
{
t_nfa *nfa = malloc(sizeof(t_nfa));
t_nfa_node *start = create_node();
t_nfa_node *end = create_node();
end->is_accepting = 1;
add_edge(start, symbol, end);
nfa->start = start;
nfa->end = end;
return nfa;
}
/*
* 連結: AB
*/
t_nfa *nfa_concat(t_nfa *a, t_nfa *b)
{
a->end->is_accepting = 0;
add_edge(a->end, -1, b->start); // ε遷移
t_nfa *result = malloc(sizeof(t_nfa));
result->start = a->start;
result->end = b->end;
return result;
}
/*
* 選択: A|B
*/
t_nfa *nfa_union(t_nfa *a, t_nfa *b)
{
t_nfa *result = malloc(sizeof(t_nfa));
t_nfa_node *start = create_node();
t_nfa_node *end = create_node();
end->is_accepting = 1;
a->end->is_accepting = 0;
b->end->is_accepting = 0;
add_edge(start, -1, a->start);
add_edge(start, -1, b->start);
add_edge(a->end, -1, end);
add_edge(b->end, -1, end);
result->start = start;
result->end = end;
return result;
}
/*
* Kleene閉包: A*
*/
t_nfa *nfa_star(t_nfa *a)
{
t_nfa *result = malloc(sizeof(t_nfa));
t_nfa_node *start = create_node();
t_nfa_node *end = create_node();
end->is_accepting = 1;
a->end->is_accepting = 0;
add_edge(start, -1, a->start);
add_edge(start, -1, end); // 空文字列を許容
add_edge(a->end, -1, a->start); // 繰り返し
add_edge(a->end, -1, end);
result->start = start;
result->end = end;
return result;
}
2.4 部分集合構成法：NFAからDFAへ
2.4.1 アルゴリズムの概要
部分集合構成法（Subset Construction）は、NFAをDFAに変換するアルゴリズムです。
部分集合構成法のアイデア:
NFA の状態集合を Q = {q0, q1, q2, ...} とする
DFA の各状態は、NFA の状態集合の部分集合に対応
例: DFA状態 {q0, q2} は、NFAが q0 または q2 にいる可能性を表す
DFA の初期状態:
ε-closure({q0}) = q0 から ε遷移で到達可能な全状態
DFA の遷移:
δ'(S, a) = ε-closure(⋃_{q∈S} δ(q, a))
（S の各状態から a で遷移した先の ε閉包）
DFA の受理状態:
NFA の受理状態を含む集合
2.4.2 アルゴリズムの実装
/*
* ε閉包の計算
*/
void epsilon_closure(t_nfa *nfa, int *states, int *closure, int *closure_size)
{
// BFSまたはDFSでε遷移を辿る
int visited[MAX_STATES] = {0};
int queue[MAX_STATES];
int front = 0, rear = 0;
// 初期状態をキューに追加
for (int i = 0; i < *closure_size; i++)
{
queue[rear++] = states[i];
visited[states[i]] = 1;
closure[i] = states[i];
}
while (front < rear)
{
int current = queue[front++];
t_nfa_node *node = nfa->nodes[current];
for (t_nfa_edge *e = node->edges; e; e = e->next)
{
if (e->symbol == -1 && !visited[e->target->id]) // ε遷移
{
visited[e->target->id] = 1;
queue[rear++] = e->target->id;
closure[(*closure_size)++] = e->target->id;
}
}
}
}
/*
* 部分集合構成法
*/
t_dfa *subset_construction(t_nfa *nfa)
{
// DFA の状態: NFA状態集合の集合
typedef struct {
int states[MAX_STATES];
int size;
int dfa_id;
} dfa_state;
dfa_state dfa_states[MAX_DFA_STATES];
int num_dfa_states = 0;
// 初期状態: ε-closure({start})
int initial[MAX_STATES] = {nfa->start->id};
int initial_size = 1;
int closure[MAX_STATES];
int closure_size = initial_size;
memcpy(closure, initial, sizeof(int) * initial_size);
epsilon_closure(nfa, initial, closure, &closure_size);
// キューを使った構成
// ... (完全な実装は省略)
return build_dfa(dfa_states, num_dfa_states);
}
2.4.3 状態爆発問題
状態爆発（State Explosion）:
NFAの状態数が n の場合、DFAの状態数は最悪 2^n
例: 正規表現 (a|b)*a(a|b)^{n-1} を認識するDFA
→ 少なくとも 2^n 状態が必要
対策:
1. 遅延構成（Lazy Construction）
- 必要な状態のみを構成
- 実際に到達する状態は少ないことが多い
2. NFA シミュレーション
- DFAに変換せずNFAを直接シミュレート
- 時間: O(n × m)（n=入力長、m=NFA状態数）
- grepの実装で使用される技法
2.5 字句解析（Lexical Analysis）の理論
2.5.1 コンパイラにおける字句解析の役割
コンパイラは複数のフェーズで構成されます。字句解析は最初のフェーズです。
コンパイラの構造:
ソースコード
│
▼
┌─────────────────────┐
│ 字句解析（Lexer） │ ← 文字列をトークンに分解
│ 正規言語を扱う │ Type-3 (Regular)
└─────────┬───────────┘
│ トークン列
▼
┌─────────────────────┐
│ 構文解析（Parser） │ ← トークンを構文木に
│ 文脈自由言語を扱う │ Type-2 (Context-Free)
└─────────┬───────────┘
│ 構文木
▼
┌─────────────────────┐
│ 意味解析 │ ← 型チェック、スコープ解決
│ 文脈依存の処理 │ (Type-1 の要素あり)
└─────────┬───────────┘
│
▼
(コード生成...)
2.5.2 lexとyacc：パーサージェネレータの歴史
Unix ツールの歴史:
1975年: lex（Mike Lesk, Bell Labs）
正規表現 → C言語の字句解析器を自動生成
1975年: yacc（Stephen Johnson, Bell Labs）
文脈自由文法 → C言語の構文解析器を自動生成
"Yet Another Compiler Compiler"
現代の後継:
flex: lex の高速化版
bison: yacc の GNU 版
ANTLR: より現代的なパーサージェネレータ
2.5.3 トークン化の理論
/*
* トークン（Token）の概念
*
* 字句解析器は入力文字列をトークン（字句）の列に分解する
*
* 例: "int x = 42;"
* → [KEYWORD:int] [IDENT:x] [ASSIGN:=] [NUMBER:42] [SEMICOLON:;]
*/
typedef enum e_token_type {
TOKEN_KEYWORD,
TOKEN_IDENTIFIER,
TOKEN_NUMBER,
TOKEN_OPERATOR,
TOKEN_PUNCTUATION,
TOKEN_EOF
} t_token_type;
typedef struct s_token {
t_token_type type;
char *lexeme; // 元の文字列
int line; // ソース位置
int column;
} t_token;
/*
* 最長一致規則（Maximal Munch）
*
* 複数のトークンにマッチする場合、最長のものを選択
*
* 例: "==" を解析
* "=" → ASSIGN
* "==" → EQUAL
* → 最長一致により EQUAL を選択
*/
/*
* 優先順位規則
*
* 同じ長さで複数にマッチする場合、定義順で優先
*
* 例: "if" を解析
* identifier: [a-z]+
* keyword: "if"
* → keyword が先に定義されていれば keyword を選択
*/
2.6 printfフォーマット文字列の形式的定義
2.6.1 BNF/EBNF記法
BNF（Backus-Naur Form）の歴史:
1959年: John Backus が ALGOL 58 の文法を記述
1960年: Peter Naur が ALGOL 60 で改良
EBNF（Extended BNF）の追加記法:
[...] オプション（0または1回）
{...} 繰り返し（0回以上）
(...) グループ化
| 選択
2.6.2 printfフォーマット指定子のEBNF
ft_printf フォーマット指定子の EBNF:
format_string = { ordinary_char | conversion_spec } ;
conversion_spec = '%' [ flags ] [ width ] [ '.' precision ] specifier ;
flags = { '-' | '+' | ' ' | '#' | '0' } ;
width = positive_digit { digit }
| '*' ;
precision = { digit }
| '*' ;
specifier = 'c' | 's' | 'p' | 'd' | 'i' | 'u' | 'x' | 'X' | '%' ;
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
positive_digit = '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
ordinary_char = ? any character except '%' ? ;
2.6.3 正規表現での表現
フォーマット指定子の正規表現:
%[-+#0 ]*([1-9][0-9]*|\*)?(\.[0-9]*|\.\*)?[cspddiuxX%]
解説:
% リテラル '%'
[-+#0 ]* フラグ（0回以上）
( 幅グループ開始
[1-9][0-9]* 正の整数
| または
\* アスタリスク
)? 幅はオプション
( 精度グループ開始
\.[0-9]* ドットに続く数字（空も可）
| または
\.\* ドットとアスタリスク
)? 精度はオプション
[cspddiuxX%] 変換指定子
2.7 printfパーサーのDFA設計
2.7.1 状態の定義
/*
* ft_printf パーサーの状態
*/
typedef enum e_parser_state {
STATE_NORMAL, // 通常テキスト
STATE_PERCENT, // '%' 検出後
STATE_FLAGS, // フラグ解析中
STATE_WIDTH, // 幅解析中
STATE_PRECISION_DOT, // '.' 検出後
STATE_PRECISION, // 精度解析中
STATE_SPECIFIER, // 変換指定子（終状態）
STATE_ERROR // エラー状態
} t_parser_state;
2.7.2 DFA状態遷移図
ft_printf パーサー DFA:
any_char
┌─────────────────┐
│ ▼
┌──────────┐ '%' ┌──────────┐
│ NORMAL ├───────▶│ PERCENT │
└──────────┘ └────┬─────┘
│
┌────────────────────┼────────────────────┐
│ │ │
│ '%' flags │ specifier
▼ ▼ ▼
┌──────────┐ ┌──────────┐ ┌──────────┐
│ OUTPUT │ │ FLAGS │───────▶│SPECIFIER │
│ '%' │ └────┬─────┘ └────┬─────┘
└──────────┘ │ │
│ digit/'*' (終状態)
▼
┌──────────┐ '.' ┌──────────┐
│ WIDTH ├─────────▶│PRECISION │
└────┬─────┘ │ DOT │
│ └────┬─────┘
│ │
specifier digit/'*'
│ ▼
└───────────────┌──────────┐
│PRECISION │
└────┬─────┘
│
specifier
│
▼
┌──────────┐
│SPECIFIER │
└──────────┘
遷移関数の形式化:
δ(NORMAL, '%') = PERCENT
δ(NORMAL, c) = NORMAL (c ≠ '%')
δ(PERCENT, '%') = OUTPUT_PERCENT
δ(PERCENT, flag_char) = FLAGS
δ(PERCENT, digit) = WIDTH
δ(PERCENT, '*') = WIDTH
δ(PERCENT, '.') = PRECISION_DOT
δ(PERCENT, spec_char) = SPECIFIER
...
2.7.3 遷移表の実装
/*
* 文字分類
*/
typedef enum e_char_class {
CC_OTHER, // その他
CC_PERCENT, // '%'
CC_FLAG, // '-', '+', ' ', '#', '0'
CC_DIGIT, // '1'-'9'
CC_ZERO, // '0' (フラグとしても使用)
CC_STAR, // '*'
CC_DOT, // '.'
CC_SPECIFIER // 'c', 's', 'd', 'i', 'u', 'x', 'X', 'p'
} t_char_class;
t_char_class classify_char(char c)
{
if (c == '%')
return CC_PERCENT;
if (c == '-' || c == '+' || c == ' ' || c == '#')
return CC_FLAG;
if (c == '0')
return CC_ZERO;
if (c >= '1' && c <= '9')
return CC_DIGIT;
if (c == '*')
return CC_STAR;
if (c == '.')
return CC_DOT;
if (ft_strchr("cspdiuxX%", c))
return CC_SPECIFIER;
return CC_OTHER;
}
/*
* 遷移表
*
* transition[current_state][char_class] = next_state
*/
const int transition_table[NUM_STATES][NUM_CHAR_CLASSES] = {
/* NORMAL */
[STATE_NORMAL] = {
[CC_OTHER] = STATE_NORMAL,
[CC_PERCENT] = STATE_PERCENT,
// ...
},
/* PERCENT */
[STATE_PERCENT] = {
[CC_FLAG] = STATE_FLAGS,
[CC_ZERO] = STATE_FLAGS,
[CC_DIGIT] = STATE_WIDTH,
[CC_STAR] = STATE_WIDTH,
[CC_DOT] = STATE_PRECISION_DOT,
[CC_SPECIFIER] = STATE_SPECIFIER,
[CC_PERCENT] = STATE_NORMAL, // %%
// ...
},
// ...
};
2.8 パーサーの実装
2.8.1 フォーマット情報構造体
/*
* パースされたフォーマット情報
*
* 設計原則:
* 1. 各フィールドは独立して処理可能
* 2. デフォルト値は「影響なし」を意味する
* 3. 不正な組み合わせは後で検証
*/
typedef struct s_format_spec {
// フラグ（ビットフィールドで効率化も可能）
unsigned int left_justify : 1; // '-'
unsigned int force_sign : 1; // '+'
unsigned int space_sign : 1; // ' '
unsigned int alt_form : 1; // '#'
unsigned int zero_pad : 1; // '0'
// 幅と精度
int width; // 0 = 未指定
int precision; // -1 = 未指定
// 変換指定子
char specifier;
} t_format_spec;
/*
* 構造体の初期化
*/
void init_format_spec(t_format_spec *spec)
{
spec->left_justify = 0;
spec->force_sign = 0;
spec->space_sign = 0;
spec->alt_form = 0;
spec->zero_pad = 0;
spec->width = 0;
spec->precision = -1;
spec->specifier = '\0';
}
2.8.2 DFAベースのパーサー
/*
* DFAベースのフォーマット指定子パーサー
*
* 戻り値: 次に処理すべき文字列位置
*/
const char *parse_conversion(const char *fmt, t_format_spec *spec,
va_list *args)
{
t_parser_state state = STATE_PERCENT;
init_format_spec(spec);
while (*fmt && state != STATE_SPECIFIER && state != STATE_ERROR)
{
t_char_class cc = classify_char(*fmt);
switch (state)
{
case STATE_PERCENT:
if (cc == CC_FLAG || cc == CC_ZERO)
{
state = STATE_FLAGS;
parse_flag(spec, *fmt);
}
else if (cc == CC_DIGIT)
{
state = STATE_WIDTH;
spec->width = *fmt - '0';
}
else if (cc == CC_STAR)
{
state = STATE_WIDTH;
spec->width = va_arg(*args, int);
if (spec->width < 0)
{
spec->left_justify = 1;
spec->width = -spec->width;
}
}
else if (cc == CC_DOT)
{
state = STATE_PRECISION_DOT;
}
else if (cc == CC_SPECIFIER)
{
spec->specifier = *fmt;
state = STATE_SPECIFIER;
}
else
{
state = STATE_ERROR;
}
break;
case STATE_FLAGS:
if (cc == CC_FLAG || cc == CC_ZERO)
{
parse_flag(spec, *fmt);
}
else if (cc == CC_DIGIT)
{
state = STATE_WIDTH;
spec->width = *fmt - '0';
}
// ... 他のケース
break;
case STATE_WIDTH:
if (cc == CC_DIGIT || cc == CC_ZERO)
{
spec->width = spec->width * 10 + (*fmt - '0');
}
else if (cc == CC_DOT)
{
state = STATE_PRECISION_DOT;
}
else if (cc == CC_SPECIFIER)
{
spec->specifier = *fmt;
state = STATE_SPECIFIER;
}
else
{
state = STATE_ERROR;
}
break;
case STATE_PRECISION_DOT:
spec->precision = 0; // '.' だけの場合は 0
if (cc == CC_DIGIT || cc == CC_ZERO)
{
state = STATE_PRECISION;
spec->precision = *fmt - '0';
}
else if (cc == CC_STAR)
{
state = STATE_PRECISION;
spec->precision = va_arg(*args, int);
if (spec->precision < 0)
spec->precision = -1; // 未指定として扱う
}
else if (cc == CC_SPECIFIER)
{
spec->specifier = *fmt;
state = STATE_SPECIFIER;
}
else
{
state = STATE_ERROR;
}
break;
case STATE_PRECISION:
if (cc == CC_DIGIT || cc == CC_ZERO)
{
spec->precision = spec->precision * 10 + (*fmt - '0');
}
else if (cc == CC_SPECIFIER)
{
spec->specifier = *fmt;
state = STATE_SPECIFIER;
}
else
{
state = STATE_ERROR;
}
break;
default:
state = STATE_ERROR;
break;
}
fmt++;
}
return fmt;
}
/*
* フラグの解析
*/
void parse_flag(t_format_spec *spec, char flag)
{
switch (flag)
{
case '-':
spec->left_justify = 1;
break;
case '+':
spec->force_sign = 1;
break;
case ' ':
spec->space_sign = 1;
break;
case '#':
spec->alt_form = 1;
break;
case '0':
spec->zero_pad = 1;
break;
}
}
2.8.3 フラグの相互作用
/*
* フラグの正規化（相互に排他的なフラグの処理）
*
* 標準Cの規則:
* 1. '-' と '0' が両方指定 → '0' は無視
* 2. '+' と ' ' が両方指定 → ' ' は無視
* 3. 精度が指定され、整数型 → '0' は無視
*/
void normalize_flags(t_format_spec *spec)
{
// '-' が指定されたら '0' は無効
if (spec->left_justify)
spec->zero_pad = 0;
// '+' が指定されたら ' ' は無効
if (spec->force_sign)
spec->space_sign = 0;
// 整数型で精度が指定されたら '0' は無効
if (spec->precision >= 0 && is_integer_specifier(spec->specifier))
spec->zero_pad = 0;
}
int is_integer_specifier(char spec)
{
return (spec == 'd' || spec == 'i' || spec == 'u' ||
spec == 'x' || spec == 'X');
}
2.9 エラー処理と回復
2.9.1 構文エラーの検出
/*
* 構文的に正しいが意味的に不正なケース
*
* 例: %s に整数を渡す → コンパイル時警告、実行時UB
* 例: 幅が負の値 → 仕様上は '-' フラグとして扱う
*/
typedef enum e_parse_error {
PARSE_OK,
PARSE_ERR_INVALID_SPECIFIER,
PARSE_ERR_INCOMPLETE,
PARSE_ERR_WIDTH_OVERFLOW,
PARSE_ERR_PRECISION_OVERFLOW
} t_parse_error;
/*
* パース結果
*/
typedef struct s_parse_result {
t_parse_error error;
t_format_spec spec;
const char *next; // 次の解析位置
const char *error_pos; // エラー位置（エラー時）
} t_parse_result;
2.9.2 エラー回復戦略
/*
* エラー回復の戦略
*
* 1. パニックモード回復
* - エラー後、次の '%' まで読み飛ばす
*
* 2. フレーズレベル回復
* - 不正な文字をスキップして続行
*
* 3. エラー生成規則
* - 不正な入力をエラートークンとして扱う
*/
// フレーズレベル回復の例
t_parse_result parse_with_recovery(const char *fmt, va_list *args)
{
t_parse_result result;
result.error = PARSE_OK;
// 通常の解析を試行
const char *pos = parse_conversion(fmt, &result.spec, args);
// エラーが発生した場合
if (result.spec.specifier == '\0')
{
result.error = PARSE_ERR_INCOMPLETE;
result.error_pos = pos;
// 回復: 次の '%' または文字列終端まで進む
while (*pos && *pos != '%')
pos++;
}
result.next = pos;
return result;
}
2.10 まとめと次章への準備
2.10.1 本章で学んだこと
学習内容のサマリー:
1. 形式言語理論
- チョムスキー階層（Type-0 〜 Type-3）
- 正規言語と有限オートマトン
- ポンプの補題
2. オートマトン理論
- DFA（決定性有限オートマトン）
- NFA（非決定性有限オートマトン）
- DFAとNFAの等価性
3. 変換アルゴリズム
- Thompson構成法（正規表現 → NFA）
- 部分集合構成法（NFA → DFA）
- 状態爆発問題
4. 字句解析の理論
- コンパイラにおける役割
- トークン化
- 最長一致規則
5. printfパーサーの設計
- EBNF による形式的定義
- DFA状態遷移図
- エラー処理と回復
6. 実装技法
- 遷移表によるDFA実装
- フラグの正規化
- 堅牢なエラー処理
2.10.2 次章の予告
第3章「文字エンコーディングと文字列の科学」では、以下の内容を扱います。
次章の内容:
1. 文字エンコーディングの歴史
- モールス符号からASCIIへ
- 8ビット拡張と混乱
- Unicodeの誕生
2. C言語における文字表現
- char型の歴史的背景
- ワイド文字とマルチバイト
- UTF-8の設計
3. ヌル終端文字列
- 設計上のトレードオフ
- セキュリティ上の問題
- 代替手法
4. 文字列処理の実装
- %c と %s の変換
- NULL ポインタの処理
- 精度と幅の適用
パーサーで解析したフォーマット情報を使って、
実際に文字と文字列を正しく出力する方法を学びます。
形式言語理論とオートマトン理論は、コンパイラ設計やパターンマッチングの基礎となる重要な概念です。printfパーサーという比較的単純な例を通じて、これらの理論的基盤を実践的に理解できたはずです。