第1章: コマンドインタプリタの理論とシェルの歴史

1.1 コマンドインタプリタの起源

バッチ処理からインタラクティブコンピューティングへ

1960年代以前、コンピュータはバッチ処理システムであった。プログラムはパンチカードに記録され、オペレータがカードデッキをマシンに投入し、結果は数時間後に返ってきた。

1961年、MITのFernando CorbatóらはCTSS（Compatible Time-Sharing System）を開発した。これはタイムシェアリングを実現し、複数のユーザーが1台のコンピュータを「同時に」利用できる最初のシステムであった。

CTSSには、ユーザーとシステムの間を仲介するコマンドインタプリタが必要だった。これがシェルの概念の萌芽である。

Multicsとシェルの誕生

1964年から1969年にかけて、MIT、Bell Labs、GEの共同プロジェクトとしてMultics（Multiplexed Information and Computing Service）が開発された。

Multicsは革命的なオペレーティングシステムであり、以下の概念を導入した：

  • 階層的ファイルシステム: ディレクトリ構造
  • 動的リンキング: 共有ライブラリ
  • プロセス管理: 複数プロセスの並行実行
  • セキュリティリング: アクセス制御

Multicsにおいて、ユーザーはコマンド言語を通じてシステムと対話した。Louis Pouzinは1964年にRUNCOMというコマンドインタプリタを開発し、これは「shell」という用語の起源となった。

Pouzinはフランス語で「シェル（coquille）」という言葉を使い、これがカーネルを「包む殻」という意味で用いられるようになった。

1.2 UNIXシェルの系譜

Thompson Shell（1971年）

Ken ThompsonとDennis RitchieがBell LabsでUNIXを開発した際、Thompsonは最初のUNIXシェルを作成した。

Thompson Shell（sh）の特徴：

  • パイプ記法がなかった（後に|として追加）
  • リダイレクション（<、>）のサポート
  • コマンドの連続実行（;）
  • バックグラウンド実行（&）

# Thompson Shellの例（1971年）
ls > /tmp/files
cat < input.txt
sleep 10 &

Thompsonは後に述べている：

> "The shell is just another user program. That's the whole idea." > （シェルは単なるユーザープログラムに過ぎない。それが全てのアイデアだ）

この「シェルは特別なプログラムではない」という思想は、UNIXの設計哲学の根幹を成す。

Bourne Shell（1977年）

Stephen BourneはBell LabsでBourne Shellを開発した。これは長年にわたり標準的なUNIXシェルとなった。

Bourne Shellの革新点：

  • 制御構文: if-then-else、while、for、case
  • シェル変数: VAR=value
  • コマンド置換: ` command （バッククォート）
  • Here Document: <<による複数行入力
  • シグナルトラップ: trapコマンド

    • #!/bin/sh
# Bourne Shell スクリプトの例

for file in *.c
do
    if [ -f "$file" ]
    then
        echo "Compiling $file"
        cc -c "$file"
    fi
done

    Bourneの設計思想は論文"An Introduction to the UNIX Shell"（Bell System Technical Journal, 1978）に詳述されている。

    C Shell（1978年）

    カリフォルニア大学バークレー校のBill JoyはC Shell（csh）を開発した。

    C Shellの特徴：

  • C言語風の構文: if (condition) then
  • ジョブ制御: fg、bg、jobs
  • 履歴機能: !による履歴展開
  • エイリアス: コマンドの別名定義
  • ファイル名補完: Tab キーによる補完

    • # C Shell の例
foreach file (*.c)
    if (-f $file) then
        echo "Processing $file"
    endif
end

    しかし、C Shellにはプログラミング言語としての欠陥があった。Tom Christiansenは"Csh Programming Considered Harmful"（1996年）において、cshのスクリプト機能の問題点を指摘している：

  • クォートの非一貫的な処理
  • パイプとリダイレクションの制限
  • 予期しない変数展開

    • Korn Shell（1983年）

    David KornはBell LabsでKorn Shell（ksh）を開発した。

    Korn Shellの特徴：

  • Bourne Shellとの後方互換性
  • C Shellの対話機能（履歴、エイリアス）
  • コプロセス: |&による双方向パイプ
  • 連想配列: typeset -A array
  • 算術評価: $((expression))

Korn Shellは商用UNIXで広く採用され、POSIX.2標準（1992年）の基礎となった。

Bash（1989年）

Brian FoxはGNUプロジェクトの一環としてBourne Again Shell（Bash）を開発した。

Bashの名前は二重の意味を持つ：

  • "Bourne Again" - Bourne Shellの再来
  • "Born Again" - 宗教的な「再生」のダジャレ

    • Bashの特徴：

  • Bourne Shell、Korn Shell、C Shellの機能を統合
  • プログラム可能な補完: complete コマンド
  • 配列変数: array=(a b c)
  • 拡張パターンマッチング: @()、()、+()
  • プロセス置換: <(command)、>(command)

    • Bashは現在、最も広く使用されているシェルであり、Linux、macOS、WSLのデフォルトシェルである。

    1.3 POSIX シェル標準

    IEEE Std 1003.2-1992

    POSIX.2（正式名称：IEEE Std 1003.2-1992）は、シェルとユーティリティの標準規格である。

    この標準は以下を定義する：

  • シェル言語: 文法、展開規則、実行モデル
  • ユーティリティ: 標準コマンドのセット
  • 正規表現: BRE（Basic）とERE（Extended）

POSIX準拠のシェルは以下の機能を実装する必要がある：

# 変数展開
${parameter}
${parameter:-word}    # デフォルト値
${parameter:=word}    # デフォルト値の代入
${parameter:?word}    # エラーメッセージ
${parameter:+word}    # 代替値

# パラメータ長
${#parameter}

# サブストリング削除
${parameter%word}     # 後方から最短マッチを削除
${parameter%%word}    # 後方から最長マッチを削除
${parameter#word}     # 前方から最短マッチを削除
${parameter##word}    # 前方から最長マッチを削除

シェル文法のBNF表現

POSIX.2はシェル言語の文法をBNF（Backus-Naur Form）で定義している：

<complete_command> ::= <list> <separator_op>
                    |  <list>

<list>             ::= <list> <separator_op> <and_or>
                    |  <and_or>

<and_or>           ::= <pipeline>
                    |  <and_or> '&&' <linebreak> <pipeline>
                    |  <and_or> '||' <linebreak> <pipeline>

<pipeline>         ::= <pipe_sequence>
                    |  '!' <pipe_sequence>

<pipe_sequence>    ::= <command>
                    |  <pipe_sequence> '|' <linebreak> <command>

<command>          ::= <simple_command>
                    |  <compound_command>
                    |  <compound_command> <redirect_list>

<simple_command>   ::= <cmd_prefix> <cmd_word> <cmd_suffix>
                    |  <cmd_prefix> <cmd_word>
                    |  <cmd_prefix>
                    |  <cmd_name> <cmd_suffix>
                    |  <cmd_name>

42のMinishellプロジェクトは、このPOSIX標準のサブセットを実装する。

1.4 形式言語理論の基礎

Noam Chomskyの言語階層（1956年）

言語学者Noam Chomskyは、形式言語を生成能力によって分類する階層を提案した（"Three Models for the Description of Language", 1956）：

| Type | 名称 | 文法 | オートマトン | |------|------|------|------------| | 0 | 無制限文法 | 任意の生成規則 | チューリングマシン | | 1 | 文脈依存文法 | αAβ → αγβ | 線形有界オートマトン | | 2 | 文脈自由文法 | A → γ | プッシュダウンオートマトン | | 3 | 正規文法 | A → aB または A → a | 有限オートマトン |

シェル言語は文脈自由文法（Type 2）に近いが、変数展開やエイリアス解決など、一部は文脈依存の特性を持つ。

字句解析と構文解析

シェルの処理は、伝統的なコンパイラ理論に従い、2つの段階に分けられる：

字句解析（Lexical Analysis / Tokenization）：

  • 入力文字列をトークン（語彙素）に分割
  • 正規言語で記述可能（有限オートマトンで実装）
  • 空白、クォート、特殊文字の処理

構文解析（Syntactic Analysis / Parsing）：

  • トークン列を構文木（AST）に変換
  • 文脈自由文法で記述（プッシュダウンオートマトンで実装）
  • 再帰下降法、LL解析、LR解析などの手法

Alfred V. Ahoらの教科書"Compilers: Principles, Techniques, and Tools"（1986年、通称「Dragon Book」）は、これらの技術の決定版的解説である。

有限オートマトンと正規表現

字句解析器は有限オートマトン（Finite Automaton）として実装できる。

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

シェルのトークナイザにおける状態遷移の例：

状態遷移図（トークン認識）:

    [START] --空白--> [START]
           --'---> [IN_SQUOTE]
           --"--> [IN_DQUOTE]
           --|--> [PIPE]
           --<--> [REDIR_IN]
           -->--> [REDIR_OUT]
           --$--> [ENV_VAR]
           --else--> [WORD]

    [IN_SQUOTE] --'--> [END_TOKEN]
                --else--> [IN_SQUOTE]

    [IN_DQUOTE] --"--> [END_TOKEN]
                --$--> [VAR_IN_DQUOTE]
                --else--> [IN_DQUOTE]

再帰下降構文解析

シェルの構文解析には再帰下降法（Recursive Descent Parsing）が適している。

Niklaus Wirthは"Algorithms + Data Structures = Programs"（1976年）において、再帰下降パーサの実装技法を解説している。

再帰下降パーサの特徴：

  • 文法規則とコードが1対1に対応
  • 左再帰を排除する必要がある
  • LL(1)文法に適する
  • 理解と実装が容易

シェル文法のための再帰下降パーサの骨格：

parse_complete_command():
    list = parse_list()
    if current_token is SEPARATOR
        consume(SEPARATOR)
    return list

parse_list():
    left = parse_pipeline()
    while current_token in {AND_IF, OR_IF}
        op = consume(current_token)
        right = parse_pipeline()
        left = create_node(op, left, right)
    return left

parse_pipeline():
    left = parse_command()
    while current_token is PIPE
        consume(PIPE)
        right = parse_command()
        left = create_pipe_node(left, right)
    return left

parse_command():
    if current_token is WORD or REDIRECT
        return parse_simple_command()
    error("Unexpected token")

1.5 プロセスモデルの理論

UNIXプロセスモデル

Dennis RitchieとKen Thompsonは、UNIXにおいて革新的なプロセスモデルを設計した（"The UNIX Time-Sharing System", Communications of the ACM, 1974）。

プロセスの定義： > "A process is the unit of resource allocation and the unit of protection." > （プロセスはリソース割り当てと保護の単位である）

UNIXのプロセスモデルの特徴：

  • fork-exec モデル: プロセス生成と実行の分離
  • 親子関係: 全てのプロセスはツリー構造
  • リソース継承: ファイルディスクリプタ、環境変数の継承

fork() システムコール

fork()は現在のプロセスを複製する：

呼び出し前:              呼び出し後:

[Parent Process]  --->   [Parent Process]
    PID: 100                 PID: 100
    Code: ...                fork() = 101  (子のPID)
                                 |
                                 |
                         [Child Process]
                             PID: 101
                             fork() = 0

Ken Thompsonはfork()の設計理由を次のように説明している：

> "Fork is cheap because of copy-on-write." > （コピーオンライトのおかげでforkは安価である）

コピーオンライト（Copy-on-Write）：

  • 親子プロセスは当初メモリを共有
  • 書き込み時にのみページを複製
  • メモリ使用量と複製時間を最小化

exec() ファミリ

exec()は現在のプロセスイメージを新しいプログラムで置き換える：

/* POSIXのexec関数ファミリ */
int execl(const char *path, const char *arg0, ... /* (char *)NULL */);
int execle(const char *path, const char *arg0, ... /*, (char *)NULL, char *const envp[] */);
int execlp(const char *file, const char *arg0, ... /* (char *)NULL */);
int execv(const char *path, char *const argv[]);
int execve(const char *path, char *const argv[], char *const envp[]);
int execvp(const char *file, char *const argv[]);

命名規則：

  • l: 引数をリスト形式で指定
  • v: 引数を配列（vector）形式で指定
  • e: 環境変数を明示的に指定
  • p: PATH環境変数を使用して検索

シェルにおいて、execve()が最も基本的であり、他は全てexecve()のラッパーである。

パイプとプロセス間通信

Douglas McIlroyは1964年にパイプの概念を提案した。これはUNIXの設計において最も影響力のあるアイデアの1つとなった。

McIlroyのメモ（1964年）：

> "We should have some ways of connecting programs like garden hose - screw in another segment when it becomes necessary to massage data in another way." > （庭のホースを繋ぐようにプログラムを接続する方法が必要だ。データを別の方法で処理する必要が生じたら、別のセグメントをねじ込めばいい）

パイプの実装：

        write()                    read()
[Process 1] ---> [Kernel Buffer] ---> [Process 2]
     |                                      |
  pipefd[1]                             pipefd[0]
  (書き込み端)                          (読み取り端)

パイプはカーネル内のバッファを通じて、プロセス間でデータをストリームとして転送する。

ファイルディスクリプタとリダイレクション

ファイルディスクリプタ（File Descriptor）は、開いているファイルへの参照を表す非負整数である。

標準のファイルディスクリプタ：

  • 0: 標準入力（stdin）
  • 1: 標準出力（stdout）
  • 2: 標準エラー出力（stderr）

dup2()システムコールはリダイレクションの実装に使用される：

int dup2(int oldfd, int newfd);

リダイレクションの実装例：

"ls > output.txt" の実行:

1. open("output.txt", O_WRONLY|O_CREAT|O_TRUNC) -> fd = 3
2. dup2(3, 1)  // fd 3 を fd 1 (stdout) に複製
3. close(3)    // 元のfdを閉じる
4. execve("/bin/ls", ...)  // lsの出力はoutput.txtへ

1.6 シグナルの理論

シグナルの歴史

シグナルはUNIX V7（1979年）で導入されたソフトウェア割り込み機構である。

シグナルの分類（IEEE Std 1003.1）：

| シグナル | 番号 | デフォルト動作 | 説明 | |---------|------|--------------|------| | SIGHUP | 1 | 終了 | ハングアップ | | SIGINT | 2 | 終了 | 割り込み (Ctrl+C) | | SIGQUIT | 3 | コアダンプ | 終了 (Ctrl+\) | | SIGKILL | 9 | 終了 | 強制終了（捕捉不可） | | SIGPIPE | 13 | 終了 | 壊れたパイプ | | SIGTERM | 15 | 終了 | 終了要求 | | SIGCHLD | 17 | 無視 | 子プロセスの状態変化 | | SIGSTOP | 19 | 停止 | 停止（捕捉不可） | | SIGTSTP | 20 | 停止 | 端末からの停止 (Ctrl+Z) | | SIGCONT | 18 | 継続 | 停止プロセスの再開 |

信頼性のあるシグナル（POSIX.1）

初期のUNIXシグナルには「信頼性がない」問題があった：

  • シグナルハンドラ実行後、デフォルト動作に戻る
  • シグナル処理中の再入不可
  • 「遅いシステムコール」の中断問題

    • POSIX.1シグナル（sigaction）はこれらの問題を解決：

    struct sigaction {
    void     (*sa_handler)(int);        /* シグナルハンドラ */
    void     (*sa_sigaction)(int, siginfo_t *, void *);
    sigset_t   sa_mask;                  /* ブロックするシグナル集合 */
    int        sa_flags;                 /* オプションフラグ */
};

    シェルにおけるシグナル処理：

  • インタラクティブモード: SIGINT で新しいプロンプト表示
  • フォアグラウンド実行中: SIGINT を子プロセスに転送
  • バックグラウンド実行: SIGINT を無視

1.7 環境変数の仕組み

環境変数の起源

環境変数はUNIX V7（1979年）でenvironグローバル変数として導入された。

extern char **environ;  /* 環境変数配列 */

環境変数の形式： 

NAME=value

環境変数の継承

fork()により、子プロセスは親の環境変数を継承する。execve()では、環境変数を明示的に渡す：

int execve(const char *pathname, char *const argv[], char *const envp[]);

シェルにおける変数の種類

  • シェル変数（ローカル変数）：
- VAR=value - 子プロセスに継承されない

  • 環境変数（エクスポート変数）：
- export VAR=value - 子プロセスに継承される

  • 特殊変数：
- $?: 最後のコマンドの終了ステータス - $!: 最後のバックグラウンドプロセスのPID - $$: 現在のシェルのPID - $0: シェルの名前

PATH環境変数

PATHは実行可能ファイルを検索するディレクトリのリストを指定する：

PATH=/usr/local/bin:/usr/bin:/bin

コマンド検索アルゴリズム：

  • コマンドに/が含まれる → 直接実行
  • PATHの各ディレクトリを順に検索
  • 最初に見つかった実行可能ファイルを使用
  • 見つからない場合 → "command not found"

    • 1.8 42 Minishellプロジェクトの仕様

    プロジェクトの目的

    42のMinishellプロジェクトは、以下のスキルを習得することを目的とする：

  • 字句解析と構文解析: コンパイラ理論の基礎
  • プロセス管理: fork、exec、waitの理解
  • パイプとリダイレクション: プロセス間通信
  • シグナル処理: 割り込み処理の実装
  • メモリ管理: 複雑なデータ構造の解放

実装が必要な機能

基本機能： 

# コマンド実行
ls -la

# パイプ
cat file | grep pattern | wc -l

# リダイレクション
echo "hello" > output.txt
cat < input.txt
echo "append" >> output.txt

# Here Document
cat << EOF
Line 1
Line 2
EOF

変数展開： 

echo $HOME
echo $USER
echo $?        # 終了ステータス

クォート処理： 

echo "Hello $USER"    # 変数展開あり
echo 'Hello $USER'    # 変数展開なし

ビルトインコマンド：

  • echo (-nオプション付き)
  • cd (相対・絶対パス)
  • pwd
  • export
  • unset
  • env
  • exit

    • 実装しない機能

  • セミコロン（;）によるコマンド区切り
  • 論理演算子（&&、||）
  • サブシェル（()）
  • ワイルドカード（）展開
  • バックスラッシュ（\`）によるエスケープ

出力形式

エラーメッセージはbashの形式に従う：

minishell: command: error message

例： 

minishell: cd: /nonexistent: No such file or directory
minishell: syntax error near unexpected token `|'
minishell: nonexistent: command not found

1.9 シェルの処理フロー

REPL（Read-Eval-Print Loop）

シェルはREPLパターンを実装する：

┌──────────────────────────────────────────────────────────┐
│                                                          │
│  ┌─────────────┐                                         │
│  │  1. Read    │ ← readline() でユーザー入力を取得       │
│  └─────┬───────┘                                         │
│        ↓                                                 │
│  ┌─────────────┐                                         │
│  │  2. Lex     │ ← 入力をトークンに分割                  │
│  └─────┬───────┘                                         │
│        ↓                                                 │
│  ┌─────────────┐                                         │
│  │  3. Parse   │ ← トークンをASTに変換                   │
│  └─────┬───────┘                                         │
│        ↓                                                 │
│  ┌─────────────┐                                         │
│  │  4. Expand  │ ← 変数展開、クォート除去                │
│  └─────┬───────┘                                         │
│        ↓                                                 │
│  ┌─────────────┐                                         │
│  │  5. Execute │ ← コマンド実行                          │
│  └─────┬───────┘                                         │
│        ↓                                                 │
│  ┌─────────────┐                                         │
│  │  6. Print   │ ← 結果を出力（暗黙的）                  │
│  └─────┬───────┘                                         │
│        │                                                 │
└────────┴─────────────────────────────────────────────────┘
         │
         └──→ Loop（ループして1に戻る）

メインループの構造

int main(int argc, char **argv, char **envp)
{
    t_shell shell;
    char    *line;
    t_token *tokens;
    t_ast   *ast;
    int     status;

    init_shell(&shell, envp);
    setup_signals();

    while (1)
    {
        line = readline("minishell$ ");
        if (!line)
            break;  /* Ctrl+D (EOF) */

        if (*line)
            add_history(line);

        tokens = lexer(line);
        if (tokens && !syntax_error(tokens))
        {
            ast = parser(tokens);
            if (ast)
            {
                expand(ast, &shell);
                status = execute(ast, &shell);
            }
            free_ast(ast);
        }
        free_tokens(tokens);
        free(line);
    }

    cleanup_shell(&shell);
    return (status);
}

1.10 データ構造の設計

トークン構造体

字句解析の結果を表現：

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;
    struct s_token  *next;
}   t_token;

AST（抽象構文木）構造体

構文解析の結果を表現：

typedef enum e_node_type
{
    NODE_COMMAND,   /* 単純コマンド */
    NODE_PIPE       /* パイプ */
}   t_node_type;

typedef struct s_redirect
{
    int                 type;       /* <, >, >>, << */
    char                *file;      /* ファイル名またはdelimiter */
    struct s_redirect   *next;
}   t_redirect;

typedef struct s_ast
{
    t_node_type     type;
    char            **argv;         /* コマンドと引数 */
    t_redirect      *redirects;     /* リダイレクトリスト */
    struct s_ast    *left;          /* パイプ左側 */
    struct s_ast    *right;         /* パイプ右側 */
}   t_ast;

シェル状態構造体

typedef struct s_env
{
    char            *key;
    char            *value;
    struct s_env    *next;
}   t_env;

typedef struct s_shell
{
    t_env   *env;           /* 環境変数リスト */
    int     last_status;    /* 最後の終了ステータス */
    int     stdin_backup;   /* 標準入力のバックアップ */
    int     stdout_backup;  /* 標準出力のバックアップ */
}   t_shell;

1.11 まとめ

本章では、シェルの理論的基盤と歴史を学んだ：

  • シェルの歴史: Thompson Shell（1971年）からBash（1989年）まで
  • POSIX標準: IEEE Std 1003.2によるシェル言語の標準化
  • 形式言語理論: Chomsky階層、正規言語、文脈自由文法
  • 字句解析と構文解析: 有限オートマトン、再帰下降法
  • プロセスモデル: fork-exec、パイプ、リダイレクション
  • シグナル: POSIX.1シグナルとシェルでの処理
  • 環境変数: 継承、PATH検索

    • 次章では、字句解析（Lexer）の実装について詳しく学ぶ。入力文字列をトークンに分割するアルゴリズムと、有限オートマトンによる実装方法を解説する。

    ---

    参考文献

  • Thompson, K. & Ritchie, D. M. (1974). "The UNIX Time-Sharing System", Communications of the ACM, 17(7)
  • Bourne, S. R. (1978). "An Introduction to the UNIX Shell", Bell System Technical Journal, 57(6)
  • Chomsky, N. (1956). "Three Models for the Description of Language", IRE Transactions on Information Theory, 2(3)
  • Aho, A. V., Sethi, R., & Ullman, J. D. (1986). "Compilers: Principles, Techniques, and Tools", Addison-Wesley
  • Wirth, N. (1976). "Algorithms + Data Structures = Programs", Prentice Hall
  • Kleene, S. C. (1956). "Representation of Events in Nerve Nets and Finite Automata", Automata Studies, Princeton University Press
  • IEEE (1992). "IEEE Std 1003.2-1992: Shell and Utilities", IEEE Computer Society
  • Christiansen, T. (1996). "Csh Programming Considered Harmful", UNIX-HATERS mailing list
  • Ramey, C. & Fox, B. (2019). "Bash Reference Manual", Free Software Foundation

Next →
字句解析とトークン化