第2章: 字句解析の理論と有限オートマトン

2.1 字句解析の理論的基礎

コンパイラにおける字句解析の位置づけ

Alfred V. Aho、Ravi Sethi、Jeffrey D. Ullmanの著書"Compilers: Principles, Techniques, and Tools"（1986年、通称「Dragon Book」）は、コンパイラ設計の教科書として決定版的な地位を占める。

この教科書によれば、コンパイラのフロントエンドは3つの段階に分けられる：

ソースコード
    ↓
┌─────────────────┐
│  字句解析       │ ← Lexical Analysis (Scanning)
│  (Lexer)        │    文字列 → トークン列
└─────────────────┘
    ↓
┌─────────────────┐
│  構文解析       │ ← Syntactic Analysis (Parsing)
│  (Parser)       │    トークン列 → 構文木
└─────────────────┘
    ↓
┌─────────────────┐
│  意味解析       │ ← Semantic Analysis
│  (Analyzer)     │    型検査、スコープ解決
└─────────────────┘
    ↓
中間表現

字句解析（Lexical Analysis）の役割：

入力文字ストリームをトークン（token）に分割
空白やコメントの除去
リテラル値の認識（数値、文字列）
キーワードと識別子の区別

トークンの形式的定義

Dragon Bookによるトークンの定義：

> "A token is a pair consisting of a token name and an optional attribute value." > （トークンは、トークン名とオプションの属性値のペアである）

形式的には：

Token = (TokenType, Attribute)

例:
  "42"     → (NUMBER, 42)
  "hello"  → (IDENTIFIER, "hello")
  "+"      → (PLUS, null)
  "|"      → (PIPE, null)

語彙素とパターン

語彙素（Lexeme）：ソースプログラム中の文字列で、トークンのインスタンスを形成する。

パターン（Pattern）：トークンの語彙素が取りうる形式を記述する規則。

| トークン | パターン | 語彙素の例 | |---------|---------|-----------| | WORD | 英数字とアンダースコアの列 | "ls", "file_name", "test123" | | PIPE | \| | "\|" | | REDIRECT_OUT | > | ">" | | REDIRECT_APPEND | >> | ">>" | | NUMBER | 数字の列 | "42", "123" |

2.2 正規言語と有限オートマトン

Stephen Kleeneの正規表現理論（1956年）

Stephen Kleeneは1956年の論文"Representation of Events in Nerve Nets and Finite Automata"において、正規表現（Regular Expression）と有限オートマトン（Finite Automaton）の等価性を証明した。

正規表現の帰納的定義：

基底ケース：

- ε（空文字列）は正規表現 - 任意の記号 a ∈ Σ は正規表現

帰納ステップ：r, s が正規表現のとき：

- (r|s) は正規表現（選択） - (rs) は正規表現（連結） - (r) は正規表現（Kleene閉包）
シェルのトークンパターンを正規表現で表現：
WORD = [a-zA-Z_][a-zA-Z0-9_]* PIPE = \| REDIR_IN = < REDIR_OUT = > REDIR_APPEND = >> HEREDOC = << ENV_VAR = \$[a-zA-Z_][a-zA-Z0-9_]* SQUOTE_STR = '[^']*' DQUOTE_STR = "([^"\\]|\\.)*"
有限オートマトンの定義
決定性有限オートマトン（DFA: Deterministic Finite Automaton）は5つ組として定義される：
DFA = (Q, Σ, δ, q₀, F) Q : 状態の有限集合 Σ : 入力アルファベット δ : 遷移関数 Q × Σ → Q q₀ : 初期状態 (q₀ ∈ Q) F : 受理状態の集合 (F ⊆ Q)
非決定性有限オートマトン（NFA: Nondeterministic Finite Automaton）：
NFA = (Q, Σ, δ, q₀, F) δ : 遷移関数 Q × (Σ ∪ {ε}) → P(Q) （P(Q)はQの冪集合）
NFAでは、同じ入力に対して複数の遷移が可能であり、ε遷移（入力を消費しない遷移）も許される。
Thompsonの構成法（1968年）
Ken Thompsonは1968年の論文"Programming Techniques: Regular Expression Search Algorithm"において、正規表現からNFAを構成する体系的な方法を提案した。
Thompson構成の基本規則：
空文字列 ε：

──→ (i) ──ε──→ ((f))
単一記号 a：

──→ (i) ──a──→ ((f))
連結 rs：

──→ [NFA for r] ──→ [NFA for s] ──→
選択 r|s：

┌──ε──→ [NFA for r] ──ε──┐ ──→ (i) ─┤ ├──→ ((f)) └──ε──→ [NFA for s] ──ε──┘

Kleene閉包 r：

           ┌────────────ε────────────┐
           │                          │
  ──→ (i) ─┼──ε──→ [NFA for r] ──ε──┼──→ ((f))
           │          │     ↑        │
           │          └──ε──┘        │
           └────────────ε────────────┘

部分集合構成法（Subset Construction）

Michael O. Rabinと Dana S. Scottは1959年の論文"Finite Automata and Their Decision Problems"において、NFAからDFAへの変換アルゴリズムを提案した（この業績で1976年チューリング賞受賞）。

部分集合構成法：

NFAの状態集合の部分集合をDFAの状態とする
ε閉包を計算して初期状態を決定
各入力記号に対する遷移を計算

ε-closure(T) = Tに含まれる状態からε遷移のみで
               到達可能な全状態の集合

move(T, a) = Tに含まれる状態からaで遷移できる
             全状態の集合

2.3 字句解析器生成系の歴史

Lex（1975年）

Mike LeskとEric Schmidtは1975年にBell LabsでLexを開発した。Lexは正規表現からC言語の字句解析器を自動生成するツールである。

Lex仕様ファイルの構造：

%{
/* Cコードの宣言 */
#include <stdio.h>
%}

%%
/* パターンとアクション */
[0-9]+      { printf("NUMBER: %s\n", yytext); }
[a-zA-Z]+   { printf("WORD: %s\n", yytext); }
[ \t\n]     { /* 空白を無視 */ }
.           { printf("UNKNOWN: %s\n", yytext); }
%%

/* 追加のCコード */
int main() {
    yylex();
    return 0;
}

Lexは内部でNFAを構成し、DFAに変換して最適化を行う。

Flex（1987年）

Vern PaxsonはGNUプロジェクトの一環としてFlex（Fast Lexical Analyzer Generator）を開発した。FlexはLexの高速な互換実装である。

Flexの最適化技術：

テーブル圧縮: 遷移テーブルのサイズ削減
直接コード生成: テーブル参照を避けるコード生成
バッファリング: 効率的な入力処理

手書き字句解析器 vs 生成系

シェルのような小規模な言語では、手書きの字句解析器が適している理由：

シンプルさ: 正規表現で記述するほど複雑ではない
エラー処理: より詳細なエラーメッセージが可能
文脈依存性: クォート内の特殊処理が容易
依存関係: 外部ツールへの依存を避ける

42のMinishellプロジェクトでは、手書きの字句解析器を実装する。

2.4 有限オートマトンによるトークナイザ設計

シェル字句解析器の状態設計

シェルの字句解析器を有限オートマトンとして設計する：

状態集合 Q = {
    INITIAL,      // 初期状態
    IN_WORD,      // 単語の途中
    IN_SQUOTE,    // シングルクォート内
    IN_DQUOTE,    // ダブルクォート内
    IN_VAR,       // 環境変数名の途中
    SAW_LESS,     // '<' を見た直後
    SAW_GREATER,  // '>' を見た直後
    ACCEPT        // 受理状態
}

入力アルファベット Σ = {
    ALPHA,        // 英字
    DIGIT,        // 数字
    UNDERSCORE,   // '_'
    SQUOTE,       // '\''
    DQUOTE,       // '"'
    DOLLAR,       // '
状態遷移図
                    WHITESPACE
                   ┌────────┐
                   ↓        │
              ┌─────────────┴──┐
              │   INITIAL      │
              └───────┬────────┘
                      │
    ┌─────────────────┼─────────────────┬──────────────────┐
    │ ALPHA/DIGIT/_   │ SQUOTE          │ DQUOTE           │ DOLLAR
    ↓                 ↓                 ↓                  ↓
┌────────┐      ┌──────────┐      ┌──────────┐      ┌─────────┐
│IN_WORD │      │IN_SQUOTE │      │IN_DQUOTE │      │ IN_VAR  │
└────┬───┘      └────┬─────┘      └────┬─────┘      └────┬────┘
     │               │                 │                 │
     │ delim         │ SQUOTE          │ DQUOTE          │ delim
     ↓               ↓                 ↓                 ↓
┌────────┐      ┌──────────┐      ┌──────────┐      ┌─────────┐
│ ACCEPT │      │  ACCEPT  │      │  ACCEPT  │      │ ACCEPT  │
│ (WORD) │      │ (SQUOTE) │      │ (DQUOTE) │      │(ENV_VAR)│
└────────┘      └──────────┘      └──────────┘      └─────────┘
演算子の認識
              ┌─────────────────┐
              │    INITIAL      │
              └────────┬────────┘
                       │
    ┌──────────────────┼──────────────────┐
    │ '<'              │ '>'              │ '|'
    ↓                  ↓                  ↓
┌───────────┐    ┌───────────┐    ┌─────────────┐
│ SAW_LESS  │    │SAW_GREATER│    │   ACCEPT    │
└─────┬─────┘    └─────┬─────┘    │   (PIPE)    │
      │                │          └─────────────┘
  ┌───┴───┐        ┌───┴───┐
  │'<'    │other   │'>'    │other
  ↓       ↓        ↓       ↓
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ACCEPT│ │ACCEPT│ │ACCEPT│ │ACCEPT│
│(<<)  │ │(<)   │ │(>>)  │ │(>)   │
└──────┘ └──────┘ └──────┘ └──────┘
2.5 字句解析器のデータ構造
トークン構造体
/**
 * トークンの種類
 * POSIXシェル文法に基づく分類
 */
typedef enum e_token_type
{
    TOKEN_WORD,             /* 通常の単語 */
    TOKEN_PIPE,             /* | パイプ */
    TOKEN_REDIRECT_IN,      /* < 入力リダイレクト */
    TOKEN_REDIRECT_OUT,     /* > 出力リダイレクト */
    TOKEN_REDIRECT_APPEND,  /* >> 追記リダイレクト */
    TOKEN_HEREDOC,          /* << ヒアドキュメント */
    TOKEN_EOF               /* 入力終端 */
}   t_token_type;

/**
 * トークン構造体
 * 連結リストとして実装
 */
typedef struct s_token
{
    t_token_type    type;       /* トークンの種類 */
    char            *value;     /* トークンの文字列値 */
    int             quoted;     /* クォートフラグ: 0=なし, 1=single, 2=double */
    struct s_token  *next;      /* 次のトークンへのポインタ */
}   t_token;
字句解析器状態構造体
/**
 * 字句解析器の状態
 */
typedef enum e_lexer_state
{
    STATE_INITIAL,      /* 初期状態 */
    STATE_IN_WORD,      /* 単語の途中 */
    STATE_IN_SQUOTE,    /* シングルクォート内 */
    STATE_IN_DQUOTE,    /* ダブルクォート内 */
    STATE_IN_VAR        /* 変数名の途中 */
}   t_lexer_state;

/**
 * 字句解析器構造体
 */
typedef struct s_lexer
{
    const char      *input;     /* 入力文字列 */
    size_t          pos;        /* 現在位置 */
    size_t          len;        /* 入力長 */
    t_lexer_state   state;      /* 現在の状態 */
    t_token         *head;      /* トークンリストの先頭 */
    t_token         *tail;      /* トークンリストの末尾 */
    int             error;      /* エラーフラグ */
}   t_lexer;
2.6 字句解析器の実装
初期化
/**
 * 字句解析器を初期化する
 * @param lexer 字句解析器構造体へのポインタ
 * @param input 入力文字列
 */
void    lexer_init(t_lexer *lexer, const char *input)
{
    lexer->input = input;
    lexer->pos = 0;
    lexer->len = ft_strlen(input);
    lexer->state = STATE_INITIAL;
    lexer->head = NULL;
    lexer->tail = NULL;
    lexer->error = 0;
}
文字分類関数
/**
 * 空白文字かどうかを判定
 * POSIXでは空白は ' ' と '\t' のみ
 */
int is_whitespace(char c)
{
    return (c == ' ' || c == '\t');
}

/**
 * メタ文字（特殊文字）かどうかを判定
 * シェルで特別な意味を持つ文字
 */
int is_metachar(char c)
{
    return (c == '|' || c == '<' || c == '>' ||
            c == ' ' || c == '\t' || c == '\n' ||
            c == '\0');
}

/**
 * 単語を構成できる文字かどうかを判定
 */
int is_word_char(char c)
{
    return (c != '\0' && !is_whitespace(c) &&
            c != '|' && c != '<' && c != '>' &&
            c != '\'' && c != '"');
}

/**
 * 変数名に使える文字かどうかを判定
 * POSIX: [A-Za-z_][A-Za-z0-9_]*
 */
int is_var_char(char c, int is_first)
{
    if (is_first)
        return (ft_isalpha(c) || c == '_');
    return (ft_isalnum(c) || c == '_');
}
トークン生成
/**
 * 新しいトークンを生成する
 * @param type トークンの種類
 * @param value トークンの文字列値（複製される）
 * @param quoted クォートフラグ
 * @return 新しいトークン、失敗時はNULL
 */
t_token *token_create(t_token_type type, const char *value, int quoted)
{
    t_token *token;

    token = malloc(sizeof(t_token));
    if (!token)
        return (NULL);
    token->type = type;
    token->value = ft_strdup(value);
    if (!token->value)
    {
        free(token);
        return (NULL);
    }
    token->quoted = quoted;
    token->next = NULL;
    return (token);
}

/**
 * トークンをリストに追加する
 */
void    lexer_add_token(t_lexer *lexer, t_token *token)
{
    if (!lexer->head)
    {
        lexer->head = token;
        lexer->tail = token;
    }
    else
    {
        lexer->tail->next = token;
        lexer->tail = token;
    }
}
メイン字句解析ループ
/**
 * 入力文字列をトークン化する
 * @param input 入力文字列
 * @return トークンリストの先頭、エラー時はNULL
 */
t_token *lexer_tokenize(const char *input)
{
    t_lexer lexer;
    char    c;

    if (!input)
        return (NULL);
    lexer_init(&lexer, input);

    while (lexer.pos < lexer.len && !lexer.error)
    {
        c = lexer.input[lexer.pos];

        if (is_whitespace(c))
            lexer_skip_whitespace(&lexer);
        else if (c == '\'')
            lexer_handle_squote(&lexer);
        else if (c == '"')
            lexer_handle_dquote(&lexer);
        else if (c == '|')
            lexer_handle_pipe(&lexer);
        else if (c == '<')
            lexer_handle_less(&lexer);
        else if (c == '>')
            lexer_handle_greater(&lexer);
        else
            lexer_handle_word(&lexer);
    }

    if (lexer.error)
    {
        lexer_free_tokens(lexer.head);
        return (NULL);
    }
    return (lexer.head);
}
2.7 演算子の処理
パイプ演算子
/**
 * パイプ演算子 '|' を処理する
 */
void    lexer_handle_pipe(t_lexer *lexer)
{
    t_token *token;

    token = token_create(TOKEN_PIPE, "|", 0);
    if (!token)
    {
        lexer->error = 1;
        return ;
    }
    lexer_add_token(lexer, token);
    lexer->pos++;
}
リダイレクト演算子
/**
 * '<' で始まるトークンを処理する
 * '<' (入力リダイレクト) または '<<' (ヒアドキュメント)
 */
void    lexer_handle_less(t_lexer *lexer)
{
    t_token *token;

    if (lexer->pos + 1 < lexer->len &&
        lexer->input[lexer->pos + 1] == '<')
    {
        /* << ヒアドキュメント */
        token = token_create(TOKEN_HEREDOC, "<<", 0);
        lexer->pos += 2;
    }
    else
    {
        /* < 入力リダイレクト */
        token = token_create(TOKEN_REDIRECT_IN, "<", 0);
        lexer->pos++;
    }

    if (!token)
    {
        lexer->error = 1;
        return ;
    }
    lexer_add_token(lexer, token);
}

/**
 * '>' で始まるトークンを処理する
 * '>' (出力リダイレクト) または '>>' (追記リダイレクト)
 */
void    lexer_handle_greater(t_lexer *lexer)
{
    t_token *token;

    if (lexer->pos + 1 < lexer->len &&
        lexer->input[lexer->pos + 1] == '>')
    {
        /* >> 追記リダイレクト */
        token = token_create(TOKEN_REDIRECT_APPEND, ">>", 0);
        lexer->pos += 2;
    }
    else
    {
        /* > 出力リダイレクト */
        token = token_create(TOKEN_REDIRECT_OUT, ">", 0);
        lexer->pos++;
    }

    if (!token)
    {
        lexer->error = 1;
        return ;
    }
    lexer_add_token(lexer, token);
}
2.8 単語の処理
単語トークンの抽出
/**
 * 単語トークンを処理する
 * クォートなしの通常の単語
 */
void    lexer_handle_word(t_lexer *lexer)
{
    size_t  start;
    size_t  end;
    char    *word;
    t_token *token;

    start = lexer->pos;

    /* 単語の終端まで進む */
    while (lexer->pos < lexer->len)
    {
        char c = lexer->input[lexer->pos];

        /* メタ文字またはクォートで終了 */
        if (is_metachar(c) || c == '\'' || c == '"')
            break;

        lexer->pos++;
    }

    end = lexer->pos;

    /* 部分文字列を抽出 */
    word = ft_substr(lexer->input, start, end - start);
    if (!word)
    {
        lexer->error = 1;
        return ;
    }

    token = token_create(TOKEN_WORD, word, 0);
    free(word);

    if (!token)
    {
        lexer->error = 1;
        return ;
    }
    lexer_add_token(lexer, token);
}
2.9 クォート処理
クォート処理の理論
シェルにおけるクォートは、特殊文字の解釈を制御する：
| クォート | 変数展開 | コマンド置換 | 特殊文字の無効化 |
|---------|---------|-------------|-----------------|
| なし | する | する | しない |
| シングル '...' | しない | しない | する（すべて） |
| ダブル "..." | する | する | 一部のみ |
POSIX規格によるダブルクォート内の特殊文字：
$ : 変数展開（有効）
`  ` : コマンド置換（有効、Minishellでは不要）

" : ダブルクォート終端

\ : 次の文字をエスケープ（$,   `, ", \`, 改行のみ）
シングルクォートの処理
/**
 * シングルクォートで囲まれた文字列を処理する
 * シングルクォート内では全ての文字がリテラルとして扱われる
 */
void    lexer_handle_squote(t_lexer *lexer)
{
    size_t  start;
    size_t  end;
    char    *content;
    t_token *token;

    lexer->pos++;  /* 開始クォートをスキップ */
    start = lexer->pos;

    /* 閉じクォートを探す */
    while (lexer->pos < lexer->len &&
           lexer->input[lexer->pos] != '\'')
    {
        lexer->pos++;
    }

    /* 閉じられていない場合はエラー */
    if (lexer->pos >= lexer->len)
    {
        ft_putendl_fd("minishell: syntax error: unclosed quote", 2);
        lexer->error = 1;
        return ;
    }

    end = lexer->pos;
    lexer->pos++;  /* 閉じクォートをスキップ */

    /* 内容を抽出 */
    content = ft_substr(lexer->input, start, end - start);
    if (!content)
    {
        lexer->error = 1;
        return ;
    }

    token = token_create(TOKEN_WORD, content, 1);  /* quoted = 1 */
    free(content);

    if (!token)
    {
        lexer->error = 1;
        return ;
    }
    lexer_add_token(lexer, token);
}
ダブルクォートの処理
/**
 * ダブルクォートで囲まれた文字列を処理する
 * $による変数展開は後の展開フェーズで処理される
 */
void    lexer_handle_dquote(t_lexer *lexer)
{
    size_t  start;
    size_t  end;
    char    *content;
    t_token *token;

    lexer->pos++;  /* 開始クォートをスキップ */
    start = lexer->pos;

    /* 閉じクォートを探す */
    while (lexer->pos < lexer->len &&
           lexer->input[lexer->pos] != '"')
    {
        /* バックスラッシュエスケープの処理 */
        if (lexer->input[lexer->pos] == '\\' &&
            lexer->pos + 1 < lexer->len)
        {
            char next = lexer->input[lexer->pos + 1];
            /* POSIX: $, `, ", \, newline のみエスケープ可能 */
            if (next == '
2.10 隣接トークンの結合
結合の必要性
シェルでは、クォートされた文字列と通常の文字列が隣接している場合、1つの単語として扱われる：
echo hello"world"'!'
# → "helloworld!" として解釈される

echo "file"$VAR".txt"
# → "file" + $VARの値 + ".txt" が結合される
結合アルゴリズム
/**
 * 隣接する単語トークンを結合する
 * 演算子で区切られていない連続した単語を1つに統合
 */
void    lexer_merge_adjacent_words(t_token **head)
{
    t_token *current;
    t_token *next;
    char    *merged;

    current = *head;
    while (current && current->next)
    {
        next = current->next;

        /* 両方が単語トークンで、間に空白がない場合 */
        if (current->type == TOKEN_WORD &&
            next->type == TOKEN_WORD)
        {
            /* 値を結合 */
            merged = ft_strjoin(current->value, next->value);
            if (!merged)
                return ;

            free(current->value);
            current->value = merged;

            /* 次のトークンをリストから削除 */
            current->next = next->next;
            free(next->value);
            free(next);

            /* 同じ位置で再チェック（3つ以上連続する可能性） */
            continue;
        }
        current = current->next;
    }
}
2.11 構文エラーの検出
字句レベルでの構文チェック
構文解析の前に、字句レベルで検出できるエラーがある：
/**
 * トークン列の構文をチェックする
 * @param tokens トークンリスト
 * @return エラーがある場合は1、正常なら0
 */
int lexer_check_syntax(t_token *tokens)
{
    t_token *current;

    /* 空のコマンドは許可 */
    if (!tokens)
        return (0);

    /* パイプで始まる */
    if (tokens->type == TOKEN_PIPE)
    {
        ft_putendl_fd(
            "minishell: syntax error near unexpected token `|'", 2);
        return (1);
    }

    current = tokens;
    while (current)
    {
        /* 連続するパイプ */
        if (current->type == TOKEN_PIPE &&
            current->next &&
            current->next->type == TOKEN_PIPE)
        {
            ft_putendl_fd(
                "minishell: syntax error near unexpected token `|'", 2);
            return (1);
        }

        /* パイプで終わる */
        if (current->type == TOKEN_PIPE && !current->next)
        {
            ft_putendl_fd(
                "minishell: syntax error near unexpected token `|'", 2);
            return (1);
        }

        /* リダイレクトの後にファイル名がない */
        if (is_redirect_token(current->type))
        {
            if (!current->next ||
                current->next->type != TOKEN_WORD)
            {
                ft_putendl_fd(
                    "minishell: syntax error near unexpected token `newline'", 2);
                return (1);
            }
        }

        current = current->next;
    }

    return (0);
}

/**
 * リダイレクトトークンかどうかを判定
 */
int is_redirect_token(t_token_type type)
{
    return (type == TOKEN_REDIRECT_IN ||
            type == TOKEN_REDIRECT_OUT ||
            type == TOKEN_REDIRECT_APPEND ||
            type == TOKEN_HEREDOC);
}
2.12 メモリ管理
トークンリストの解放
/**
 * トークンを1つ解放する
 */
void    token_free(t_token *token)
{
    if (!token)
        return ;
    if (token->value)
        free(token->value);
    free(token);
}

/**
 * トークンリスト全体を解放する
 */
void    lexer_free_tokens(t_token *head)
{
    t_token *current;
    t_token *next;

    current = head;
    while (current)
    {
        next = current->next;
        token_free(current);
        current = next;
    }
}
2.13 デバッグとテスト
トークンの可視化
/**
 * トークン種別を文字列に変換
 */
const char  *token_type_str(t_token_type type)
{
    static const char *names[] = {
        "WORD",
        "PIPE",
        "REDIRECT_IN",
        "REDIRECT_OUT",
        "REDIRECT_APPEND",
        "HEREDOC",
        "EOF"
    };

    if (type >= 0 && type <= TOKEN_EOF)
        return (names[type]);
    return ("UNKNOWN");
}

/**
 * トークンリストを表示する（デバッグ用）
 */
void    lexer_print_tokens(t_token *head)
{
    t_token *current;
    int     index;

    printf("=== TOKEN LIST ===\n");
    current = head;
    index = 0;
    while (current)
    {
        printf("[%d] %-15s | value: '%s' | quoted: %d\n",
               index,
               token_type_str(current->type),
               current->value,
               current->quoted);
        current = current->next;
        index++;
    }
    printf("==================\n");
}
テストケース
/**
 * 字句解析器のテスト
 */
void    lexer_test(void)
{
    t_token *tokens;

    /* テスト1: 基本的なコマンド */
    printf("\n--- Test 1: Simple command ---\n");
    tokens = lexer_tokenize("ls -la");
    lexer_print_tokens(tokens);
    lexer_free_tokens(tokens);

    /* テスト2: パイプとリダイレクト */
    printf("\n--- Test 2: Pipe and redirect ---\n");
    tokens = lexer_tokenize("cat file | grep pattern > output.txt");
    lexer_print_tokens(tokens);
    lexer_free_tokens(tokens);

    /* テスト3: クォート */
    printf("\n--- Test 3: Quotes ---\n");
    tokens = lexer_tokenize("echo 'hello world' \"$USER\"");
    lexer_print_tokens(tokens);
    lexer_free_tokens(tokens);

    /* テスト4: ヒアドキュメント */
    printf("\n--- Test 4: Heredoc ---\n");
    tokens = lexer_tokenize("cat << EOF");
    lexer_print_tokens(tokens);
    lexer_free_tokens(tokens);

    /* テスト5: 隣接する単語 */
    printf("\n--- Test 5: Adjacent words ---\n");
    tokens = lexer_tokenize("echo hello\"world\"");
    lexer_merge_adjacent_words(&tokens);
    lexer_print_tokens(tokens);
    lexer_free_tokens(tokens);
}
2.14 完全なヘッダファイル
/* lexer.h */
#ifndef LEXER_H
# define LEXER_H

# include <stdlib.h>
# include <unistd.h>
# include "libft.h"

/*
** トークン種別
*/
typedef enum e_token_type
{
    TOKEN_WORD,
    TOKEN_PIPE,
    TOKEN_REDIRECT_IN,
    TOKEN_REDIRECT_OUT,
    TOKEN_REDIRECT_APPEND,
    TOKEN_HEREDOC,
    TOKEN_EOF
}   t_token_type;

/*
** トークン構造体
*/
typedef struct s_token
{
    t_token_type    type;
    char            *value;
    int             quoted;
    struct s_token  *next;
}   t_token;

/*
** 字句解析器状態
*/
typedef enum e_lexer_state
{
    STATE_INITIAL,
    STATE_IN_WORD,
    STATE_IN_SQUOTE,
    STATE_IN_DQUOTE
}   t_lexer_state;

/*
** 字句解析器構造体
*/
typedef struct s_lexer
{
    const char      *input;
    size_t          pos;
    size_t          len;
    t_lexer_state   state;
    t_token         *head;
    t_token         *tail;
    int             error;
}   t_lexer;

/*
** 公開インターフェース
*/
t_token     *lexer_tokenize(const char *input);
void        lexer_free_tokens(t_token *head);
int         lexer_check_syntax(t_token *tokens);
void        lexer_merge_adjacent_words(t_token **head);

/*
** デバッグ
*/
void        lexer_print_tokens(t_token *head);
const char  *token_type_str(t_token_type type);

#endif
2.15 まとめ
本章では、字句解析の理論と実装を学んだ：
理論的基礎: Dragon Bookによるコンパイラ設計の基礎
正規言語と有限オートマトン: Kleeneの定理、Thompson構成
字句解析器生成系の歴史: Lex/Flexの発展
状態機械による設計: シェルトークナイザの状態遷移
実装: トークン生成、演算子処理、クォート処理
隣接トークンの結合: シェル固有の処理
エラー検出: 構文エラーの早期発見
次章では、構文解析（Parser）について学ぶ。トークン列を抽象構文木（AST）に変換する再帰下降パーサの理論と実装を解説する。
---
参考文献
Aho, A. V., Sethi, R., & Ullman, J. D. (1986). "Compilers: Principles, Techniques, and Tools", Addison-Wesley
Kleene, S. C. (1956). "Representation of Events in Nerve Nets and Finite Automata", Automata Studies, Princeton University Press
Thompson, K. (1968). "Programming Techniques: Regular Expression Search Algorithm", Communications of the ACM, 11(6)
Rabin, M. O. & Scott, D. (1959). "Finite Automata and Their Decision Problems", IBM Journal of Research and Development, 3(2)
Lesk, M. E. & Schmidt, E. (1975). "Lex - A Lexical Analyzer Generator", Bell Laboratories Computing Science Technical Report No. 39
Paxson, V. (1995). "Flex - Fast Lexical Analyzer Generator", Free Software Foundation
IEEE (1992). "IEEE Std 1003.2-1992: Shell and Utilities", IEEE Computer Society

    PIPE_CHAR,    // '|'
    LESS,         // '<'
    GREATER,      // '>'
    WHITESPACE,   // ' ', '\t', '\n'
    OTHER         // その他
}

`状態遷移図`

___CODE_BLOCK_13___

`演算子の認識`

___CODE_BLOCK_14___

`2.5 字句解析器のデータ構造`

`トークン構造体`

___CODE_BLOCK_15___

`字句解析器状態構造体`

___CODE_BLOCK_16___

`2.6 字句解析器の実装`

`初期化`

___CODE_BLOCK_17___

`文字分類関数`

___CODE_BLOCK_18___

`トークン生成`

___CODE_BLOCK_19___

`メイン字句解析ループ`

___CODE_BLOCK_20___

`2.7 演算子の処理`

`パイプ演算子`

___CODE_BLOCK_21___

`リダイレクト演算子`

___CODE_BLOCK_22___

`2.8 単語の処理`

`単語トークンの抽出`

___CODE_BLOCK_23___

`2.9 クォート処理`

`クォート処理の理論`

シェルにおけるクォートは、特殊文字の解釈を制御する：

| クォート | 変数展開 | コマンド置換 | 特殊文字の無効化 | |---------|---------|-------------|-----------------| | なし | する | する | しない | | シングル '...' | しない | しない | する（すべて） | | ダブル "..." | する | する | 一部のみ |

POSIX規格によるダブルクォート内の特殊文字：

$ : 変数展開（有効）


`  ` : コマンド置換（有効、Minishellでは不要）

" : ダブルクォート終端

\ : 次の文字をエスケープ（$,   `, ", \`, 改行のみ）
シングルクォートの処理
___CODE_BLOCK_24___
ダブルクォートの処理
___CODE_BLOCK_25___
2.10 隣接トークンの結合
結合の必要性
シェルでは、クォートされた文字列と通常の文字列が隣接している場合、1つの単語として扱われる：
___CODE_BLOCK_26___
結合アルゴリズム
___CODE_BLOCK_27___
2.11 構文エラーの検出
字句レベルでの構文チェック
構文解析の前に、字句レベルで検出できるエラーがある：
___CODE_BLOCK_28___
2.12 メモリ管理
トークンリストの解放
___CODE_BLOCK_29___
2.13 デバッグとテスト
トークンの可視化
___CODE_BLOCK_30___
テストケース
___CODE_BLOCK_31___
2.14 完全なヘッダファイル
___CODE_BLOCK_32___
2.15 まとめ
本章では、字句解析の理論と実装を学んだ：
理論的基礎: Dragon Bookによるコンパイラ設計の基礎
正規言語と有限オートマトン: Kleeneの定理、Thompson構成
字句解析器生成系の歴史: Lex/Flexの発展
状態機械による設計: シェルトークナイザの状態遷移
実装: トークン生成、演算子処理、クォート処理
隣接トークンの結合: シェル固有の処理
エラー検出: 構文エラーの早期発見
次章では、構文解析（Parser）について学ぶ。トークン列を抽象構文木（AST）に変換する再帰下降パーサの理論と実装を解説する。
---
参考文献
Aho, A. V., Sethi, R., & Ullman, J. D. (1986). "Compilers: Principles, Techniques, and Tools", Addison-Wesley
Kleene, S. C. (1956). "Representation of Events in Nerve Nets and Finite Automata", Automata Studies, Princeton University Press
Thompson, K. (1968). "Programming Techniques: Regular Expression Search Algorithm", Communications of the ACM, 11(6)
Rabin, M. O. & Scott, D. (1959). "Finite Automata and Their Decision Problems", IBM Journal of Research and Development, 3(2)
Lesk, M. E. & Schmidt, E. (1975). "Lex - A Lexical Analyzer Generator", Bell Laboratories Computing Science Technical Report No. 39
Paxson, V. (1995). "Flex - Fast Lexical Analyzer Generator", Free Software Foundation
IEEE (1992). "IEEE Std 1003.2-1992: Shell and Utilities", IEEE Computer Society

 || next == '`' ||
                next == '"' || next == '\\' || next == '\n')
            {
                lexer->pos++;  /* バックスラッシュをスキップ */
            }
        }
        lexer->pos++;
    }

    /* 閉じられていない場合はエラー */
    if (lexer->pos >= lexer->len)
    {
        ft_putendl_fd("minishell: syntax error: unclosed quote", 2);
        lexer->error = 1;
        return ;
    }

    end = lexer->pos;
    lexer->pos++;  /* 閉じクォートをスキップ */

    /* 内容を抽出 */
    content = ft_substr(lexer->input, start, end - start);
    if (!content)
    {
        lexer->error = 1;
        return ;
    }

    token = token_create(TOKEN_WORD, content, 2);  /* quoted = 2 */
    free(content);

    if (!token)
    {
        lexer->error = 1;
        return ;
    }
    lexer_add_token(lexer, token);
}

2.10 隣接トークンの結合

結合の必要性

シェルでは、クォートされた文字列と通常の文字列が隣接している場合、1つの単語として扱われる：

___CODE_BLOCK_26___

結合アルゴリズム

___CODE_BLOCK_27___

2.11 構文エラーの検出

字句レベルでの構文チェック

構文解析の前に、字句レベルで検出できるエラーがある：

___CODE_BLOCK_28___

2.12 メモリ管理

トークンリストの解放

___CODE_BLOCK_29___

2.13 デバッグとテスト

トークンの可視化

___CODE_BLOCK_30___

テストケース

___CODE_BLOCK_31___

2.14 完全なヘッダファイル

___CODE_BLOCK_32___

2.15 まとめ

本章では、字句解析の理論と実装を学んだ：

理論的基礎: Dragon Bookによるコンパイラ設計の基礎

正規言語と有限オートマトン: Kleeneの定理、Thompson構成

字句解析器生成系の歴史: Lex/Flexの発展

状態機械による設計: シェルトークナイザの状態遷移

実装: トークン生成、演算子処理、クォート処理

隣接トークンの結合: シェル固有の処理

エラー検出: 構文エラーの早期発見

次章では、構文解析（Parser）について学ぶ。トークン列を抽象構文木（AST）に変換する再帰下降パーサの理論と実装を解説する。

---

参考文献

Aho, A. V., Sethi, R., & Ullman, J. D. (1986). "Compilers: Principles, Techniques, and Tools", Addison-Wesley

Kleene, S. C. (1956). "Representation of Events in Nerve Nets and Finite Automata", Automata Studies, Princeton University Press

Thompson, K. (1968). "Programming Techniques: Regular Expression Search Algorithm", Communications of the ACM, 11(6)

Rabin, M. O. & Scott, D. (1959). "Finite Automata and Their Decision Problems", IBM Journal of Research and Development, 3(2)

Lesk, M. E. & Schmidt, E. (1975). "Lex - A Lexical Analyzer Generator", Bell Laboratories Computing Science Technical Report No. 39

Paxson, V. (1995). "Flex - Fast Lexical Analyzer Generator", Free Software Foundation

IEEE (1992). "IEEE Std 1003.2-1992: Shell and Utilities", IEEE Computer Society

PIPE_CHAR, // '|' LESS, // '<' GREATER, // '>' WHITESPACE, // ' ', '\t', '\n' OTHER // その他 }

状態遷移図

___CODE_BLOCK_13___

演算子の認識

___CODE_BLOCK_14___

2.5 字句解析器のデータ構造

トークン構造体

___CODE_BLOCK_15___

字句解析器状態構造体

___CODE_BLOCK_16___

2.6 字句解析器の実装

初期化

___CODE_BLOCK_17___

文字分類関数

___CODE_BLOCK_18___

トークン生成

___CODE_BLOCK_19___

メイン字句解析ループ

___CODE_BLOCK_20___

2.7 演算子の処理

パイプ演算子

___CODE_BLOCK_21___

リダイレクト演算子

___CODE_BLOCK_22___

2.8 単語の処理

単語トークンの抽出

___CODE_BLOCK_23___

2.9 クォート処理

クォート処理の理論

シェルにおけるクォートは、特殊文字の解釈を制御する：

| クォート | 変数展開 | コマンド置換 | 特殊文字の無効化 | |---------|---------|-------------|-----------------| | なし | する | する | しない | | シングル '...' | しない | しない | する（すべて） | | ダブル "..." | する | する | 一部のみ |

POSIX規格によるダブルクォート内の特殊文字：

$ : 変数展開（有効）
` ` : コマンド置換（有効、Minishellでは不要）

" : ダブルクォート終端

\ : 次の文字をエスケープ（$, `, ", \`, 改行のみ）

シングルクォートの処理

___CODE_BLOCK_24___

ダブルクォートの処理

___CODE_BLOCK_25___