第3章: 構文解析の理論と抽象構文木
3.1 構文解析の理論的基礎
文脈自由文法（Context-Free Grammar）
Noam Chomskyは1956年の研究において、形式言語を4つの階層に分類した。構文解析が対象とするのはType 2 文脈自由文法（CFG: Context-Free Grammar）である。
文脈自由文法の形式的定義：
G = (V, Σ, R, S)
V : 非終端記号（変数）の有限集合
Σ : 終端記号（トークン）の有限集合
R : 生成規則の有限集合（A → α の形式、A ∈ V, α ∈ (V ∪ Σ)*）
S : 開始記号（S ∈ V）
文脈自由文法は、プログラミング言語の構文を記述するのに十分な表現力を持つ。
Backus-Naur Form（BNF）
John BackusとPeter Naurは、ALGOL 60の仕様記述のためにBNF（Backus-Naur Form）を開発した（1960年）。これは文脈自由文法を表記するための標準的な記法となった。
BNFの表記規則：
<非終端記号>: 非終端記号終端記号: 終端記号（リテラル）::=: 定義|: 選択（または）
ALGOL 60 Reportからの例：
<expression> ::= <term> | <expression> + <term> | <expression> - <term>
<term> ::= <factor> | <term> * <factor> | <term> / <factor>
<factor> ::= <primary> | <factor> ^ <primary>
Peter Naurは後に謙遜して「Backus Normal Form」と呼ぶべきだと述べたが、Donald Knuthが「Backus-Naur Form」という名称を提案し、これが定着した。
拡張BNF（EBNF）
Niklaus Wirthは、BNFを拡張したEBNF（Extended BNF）を提案した（1977年）。
EBNF追加記法：
{ }: 0回以上の繰り返し（Kleene閉包）[ ]: オプション（0回または1回）( ): グループ化
pipeline = command { "|" command }
command = word { word } { redirection }
redirection = ( "<" | ">" | ">>" | "<<" ) word
ISO/IEC 14977:1996として標準化されている。
3.2 構文解析アルゴリズムの歴史
初期の構文解析（1960年代）
構文解析アルゴリズムの研究は、ALGOL 60コンパイラの開発とともに始まった。
主要なマイルストーン：
トップダウン構文解析
トップダウン構文解析は、開始記号から入力文字列を導出する試みである。
主な手法：
- 再帰下降構文解析（Recursive Descent）: 各非終端記号に対応する関数を再帰呼び出し
- LL構文解析: 左から読み（Left-to-right）、最左導出（Leftmost derivation）
- 予測的構文解析: 先読みにより決定的に解析
LL(k)文法：k個のトークンを先読みすることで、適用すべき生成規則を一意に決定できる文法。
ボトムアップ構文解析
ボトムアップ構文解析は、入力文字列から開始記号への還元を試みる。
主な手法：
- LR構文解析: Donald Knuth（1965年）が発明
- LALR構文解析: LRの実用的な近似
- SLR構文解析: 単純化されたLR
LR(k)文法：左から読み（Left-to-right）、最右導出の逆（Rightmost derivation in reverse）、k個の先読み。
YACC（1975年）
Stephen C. JohnsonはBell LabsでYACC（Yet Another Compiler-Compiler）を開発した（1975年）。YACCはLALR(1)構文解析器を自動生成するツールである。
%token WORD PIPE REDIRECT_IN REDIRECT_OUT
%%
pipeline : command
| pipeline PIPE command
;
command : word_list
| word_list redirections
;
word_list: WORD
| word_list WORD
;
%%
GNU BisonはYACCの互換実装である。
3.3 再帰下降構文解析
再帰下降法の原理
再帰下降構文解析（Recursive Descent Parsing）は、各非終端記号に対して1つの関数を定義し、文法規則に従って再帰的に呼び出す手法である。
Niklaus Wirthは"Algorithms + Data Structures = Programs"（1976年）において、再帰下降パーサの実装技法を体系的に解説した。
再帰下降法の特徴：
- 文法規則とコードが1対1に対応
- 手書きで実装しやすい
- エラーメッセージの制御が容易
- LL(1)文法に適する
左再帰の除去
再帰下降パーサは左再帰（Left Recursion）を処理できない。
左再帰の例：
<expr> ::= <expr> + <term> | <term>
この文法を直接実装すると、parse_expr() が parse_expr() を呼び出し、無限ループになる。
左再帰の除去：
/* 左再帰 */
A ::= A α | β
/* 除去後 */
A ::= β A'
A' ::= α A' | ε
シェル文法への適用：
/* 元の文法（左再帰あり） */
<pipeline> ::= <pipeline> '|' <command> | <command>
/* 除去後 */
<pipeline> ::= <command> <pipeline'>
<pipeline'> ::= '|' <command> <pipeline'> | ε
実装では、これをwhileループとして表現：
t_cmd *parse_pipeline(t_parser *parser)
{
t_cmd *left = parse_command(parser);
while (current_token_is(parser, TOKEN_PIPE))
{
consume(parser); /* '|' を消費 */
t_cmd *right = parse_command(parser);
left = create_pipe_node(left, right);
}
return left;
}
3.4 抽象構文木（AST）
構文木の理論
構文木（Parse Tree / Derivation Tree）は、文法による導出過程を木構造で表現したものである。
入力: "ls | grep test"
構文木:
<pipeline>
/ | \
<command> '|' <command>
| |
<word> <word_list>
| / \
"ls" <word> <word>
| |
"grep" "test"
抽象構文木（AST）
抽象構文木（Abstract Syntax Tree / AST）は、構文木から冗長な情報を除去し、プログラムの本質的な構造のみを保持したものである。
入力: "ls | grep test"
AST:
PIPE
/ \
CMD CMD
| / \
"ls" "grep" "test"
ASTは以下の点で構文木より優れている：
- 簡潔性: 文法規則の詳細を隠蔽
- 効率性: 不要なノードを省略
- 意味的妥当性: プログラムの意味構造を反映
シェルのAST設計
シェルコマンドのASTノード種別：
/**
* ASTノードの種類
*/
typedef enum e_node_type
{
NODE_COMMAND, /* 単純コマンド: argv[] + redirects */
NODE_PIPE /* パイプ: left | right */
} t_node_type;
/**
* リダイレクトの種類
*/
typedef enum e_redir_type
{
REDIR_INPUT, /* < file */
REDIR_OUTPUT, /* > file */
REDIR_APPEND, /* >> file */
REDIR_HEREDOC /* << delimiter */
} t_redir_type;
3.5 シェル文法の形式的定義
MinishellのEBNF文法
42のMinishellプロジェクトのためのEBNF文法定義：
(* 最上位規則 *)
command_line = pipeline ;
(* パイプライン: 1つ以上のコマンドをパイプで接続 *)
pipeline = command { "|" command } ;
(* 単純コマンド: 引数とリダイレクトの混合 *)
command = { command_element }+ ;
(* コマンド要素: 単語またはリダイレクト *)
command_element = word | redirection ;
(* リダイレクト *)
redirection = redirect_op word ;
redirect_op = "<" | ">" | ">>" | "<<" ;
(* 単語: クォートあり/なし *)
word = WORD | SQUOTED_WORD | DQUOTED_WORD ;
文法の曖昧性
シェル文法には曖昧性（Ambiguity）がある場合がある。例えば、リダイレクトの位置：
# これらは等価
cat < file
< file cat
cat file < file2
この曖昧性は、構文解析時ではなく意味解析時に解決される。
3.6 構文解析器のデータ構造
パーサ状態構造体
/**
* 構文解析器の状態
*/
typedef struct s_parser
{
t_token *tokens; /* トークンリストの先頭 */
t_token *current; /* 現在のトークン */
int error; /* エラーフラグ */
char *error_msg; /* エラーメッセージ */
} t_parser;
リダイレクト構造体
/**
* リダイレクト情報
*/
typedef struct s_redirect
{
t_redir_type type; /* リダイレクトの種類 */
char *file; /* ファイル名またはdelimiter */
struct s_redirect *next; /* 次のリダイレクト */
} t_redirect;
ASTノード構造体
/**
* AST（抽象構文木）ノード
*/
typedef struct s_ast
{
t_node_type type; /* ノードの種類 */
char **argv; /* コマンドと引数（NULL終端） */
t_redirect *redirects; /* リダイレクトリスト */
struct s_ast *left; /* パイプの左側 */
struct s_ast *right; /* パイプの右側 */
} t_ast;
3.7 パーサのユーティリティ関数
トークン操作
/**
* 現在のトークンを参照（消費しない）
*/
t_token *parser_peek(t_parser *parser)
{
return (parser->current);
}
/**
* 現在のトークンが指定された種類かどうかを判定
*/
int parser_check(t_parser *parser, t_token_type type)
{
if (!parser->current)
return (0);
return (parser->current->type == type);
}
/**
* 現在のトークンを消費し、次に進む
*/
t_token *parser_advance(t_parser *parser)
{
t_token *token;
token = parser->current;
if (parser->current)
parser->current = parser->current->next;
return (token);
}
/**
* 指定された種類のトークンを期待し、消費する
* 一致しない場合はエラー
*/
int parser_expect(t_parser *parser, t_token_type type)
{
if (!parser_check(parser, type))
{
parser->error = 1;
return (0);
}
parser_advance(parser);
return (1);
}
/**
* 入力の終端かどうかを判定
*/
int parser_at_end(t_parser *parser)
{
return (parser->current == NULL);
}
判定関数
/**
* リダイレクトトークンかどうかを判定
*/
int is_redirect_token(t_token_type type)
{
return (type == TOKEN_REDIRECT_IN ||
type == TOKEN_REDIRECT_OUT ||
type == TOKEN_REDIRECT_APPEND ||
type == TOKEN_HEREDOC);
}
/**
* 単語トークンかどうかを判定
*/
int is_word_token(t_token_type type)
{
return (type == TOKEN_WORD);
}
/**
* コマンド要素の開始トークンかどうかを判定
*/
int is_command_element(t_token_type type)
{
return (is_word_token(type) || is_redirect_token(type));
}
3.8 再帰下降パーサの実装
エントリポイント
/**
* 構文解析のエントリポイント
* @param tokens トークンリスト
* @return AST、エラー時はNULL
*/
t_ast *parser_parse(t_token *tokens)
{
t_parser parser;
t_ast *ast;
if (!tokens)
return (NULL);
parser.tokens = tokens;
parser.current = tokens;
parser.error = 0;
parser.error_msg = NULL;
ast = parse_pipeline(&parser);
if (parser.error)
{
ast_free(ast);
return (NULL);
}
/* 残りのトークンがないか確認 */
if (!parser_at_end(&parser))
{
ft_putendl_fd("minishell: syntax error: unexpected token", 2);
ast_free(ast);
return (NULL);
}
return (ast);
}
パイプラインの解析
/**
* パイプラインを解析する
* pipeline = command { "|" command }
*/
t_ast *parse_pipeline(t_parser *parser)
{
t_ast *left;
t_ast *right;
t_ast *pipe_node;
left = parse_command(parser);
if (!left || parser->error)
return (left);
/* パイプが続く限り解析 */
while (parser_check(parser, TOKEN_PIPE))
{
parser_advance(parser); /* '|' を消費 */
/* パイプの右側が必要 */
if (parser_at_end(parser) ||
!is_command_element(parser->current->type))
{
ft_putendl_fd(
"minishell: syntax error near unexpected token `|'", 2);
parser->error = 1;
ast_free(left);
return (NULL);
}
right = parse_command(parser);
if (!right || parser->error)
{
ast_free(left);
return (NULL);
}
/* パイプノードを作成 */
pipe_node = ast_create_pipe(left, right);
if (!pipe_node)
{
ast_free(left);
ast_free(right);
return (NULL);
}
left = pipe_node;
}
return (left);
}
コマンドの解析
/**
* 単純コマンドを解析する
* command = { command_element }+
*/
t_ast *parse_command(t_parser *parser)
{
t_ast *cmd;
t_list *argv_list;
t_redirect *redirects;
argv_list = NULL;
redirects = NULL;
/* コマンド要素を収集 */
while (!parser_at_end(parser) &&
is_command_element(parser->current->type))
{
if (is_redirect_token(parser->current->type))
{
if (!parse_redirection(parser, &redirects))
return (free_and_null(&argv_list, &redirects));
}
else if (is_word_token(parser->current->type))
{
if (!list_add_back(&argv_list,
ft_strdup(parser->current->value)))
return (free_and_null(&argv_list, &redirects));
parser_advance(parser);
}
else
{
break;
}
}
/* 空のコマンドはエラー（リダイレクトのみは許可） */
if (!argv_list && !redirects)
{
ft_putendl_fd("minishell: syntax error: empty command", 2);
parser->error = 1;
return (NULL);
}
/* ASTノードを作成 */
cmd = ast_create_command(list_to_argv(argv_list), redirects);
list_free(&argv_list);
return (cmd);
}
リダイレクトの解析
/**
* リダイレクトを解析する
* redirection = redirect_op word
*/
int parse_redirection(t_parser *parser, t_redirect **redirects)
{
t_token *op_token;
t_token *file_token;
t_redirect *redir;
t_redir_type type;
op_token = parser_advance(parser);
/* リダイレクト種類を決定 */
if (op_token->type == TOKEN_REDIRECT_IN)
type = REDIR_INPUT;
else if (op_token->type == TOKEN_REDIRECT_OUT)
type = REDIR_OUTPUT;
else if (op_token->type == TOKEN_REDIRECT_APPEND)
type = REDIR_APPEND;
else if (op_token->type == TOKEN_HEREDOC)
type = REDIR_HEREDOC;
else
return (0);
/* ファイル名を取得 */
if (parser_at_end(parser) ||
!is_word_token(parser->current->type))
{
ft_putendl_fd(
"minishell: syntax error near unexpected token `newline'", 2);
parser->error = 1;
return (0);
}
file_token = parser_advance(parser);
/* リダイレクト構造体を作成 */
redir = redirect_create(type, file_token->value);
if (!redir)
return (0);
redirect_add(redirects, redir);
return (1);
}
3.9 ASTノードの生成
コマンドノード
/**
* コマンドノードを作成する
*/
t_ast *ast_create_command(char **argv, t_redirect *redirects)
{
t_ast *node;
node = malloc(sizeof(t_ast));
if (!node)
return (NULL);
node->type = NODE_COMMAND;
node->argv = argv;
node->redirects = redirects;
node->left = NULL;
node->right = NULL;
return (node);
}
パイプノード
/**
* パイプノードを作成する
*/
t_ast *ast_create_pipe(t_ast *left, t_ast *right)
{
t_ast *node;
node = malloc(sizeof(t_ast));
if (!node)
return (NULL);
node->type = NODE_PIPE;
node->argv = NULL;
node->redirects = NULL;
node->left = left;
node->right = right;
return (node);
}
リダイレクト操作
/**
* リダイレクト構造体を作成する
*/
t_redirect *redirect_create(t_redir_type type, const char *file)
{
t_redirect *redir;
redir = malloc(sizeof(t_redirect));
if (!redir)
return (NULL);
redir->type = type;
redir->file = ft_strdup(file);
if (!redir->file)
{
free(redir);
return (NULL);
}
redir->next = NULL;
return (redir);
}
/**
* リダイレクトをリストに追加する
*/
void redirect_add(t_redirect **list, t_redirect *new_redir)
{
t_redirect *current;
if (!*list)
{
*list = new_redir;
return;
}
current = *list;
while (current->next)
current = current->next;
current->next = new_redir;
}
3.10 変数展開
展開フェーズの位置づけ
POSIX規格では、シェルの処理順序は以下の通り：
変数展開は構文解析の後、実行の前に行われる。
展開の種類
POSIX準拠シェルでの展開順序：
{a,b,c} → a b c（Minishellでは不要）~ → ホームディレクトリ（Minishellでは不要）$VAR, ${VAR} → 変数の値$(cmd), ` cmd → コマンドの出力（Minishellでは不要）Minishellでは、主にパラメータ展開とクォート除去を実装する。
変数展開の実装
/**
* AST全体の変数を展開する
*/
void expand_ast(t_ast *ast, t_shell *shell)
{
int i;
if (!ast)
return;
if (ast->type == NODE_COMMAND)
{
/* argvの展開 */
i = 0;
while (ast->argv && ast->argv[i])
{
ast->argv[i] = expand_string(ast->argv[i], shell);
i++;
}
/* リダイレクトファイル名の展開 */
expand_redirects(ast->redirects, shell);
}
else if (ast->type == NODE_PIPE)
{
expand_ast(ast->left, shell);
expand_ast(ast->right, shell);
}
}
/**
* 文字列中の変数を展開する
*/
char *expand_string(char *str, t_shell *shell)
{
t_expander exp;
char *result;
if (!str || !ft_strchr(str, '展開器の実装
/**
* 展開器構造体
*/
typedef struct s_expander
{
const char *input;
size_t pos;
t_shell *shell;
char *result;
} t_expander;
/**
* 展開処理のメインループ
*/
char *expander_process(t_expander *exp)
{
while (exp->input[exp->pos])
{
if (exp->input[exp->pos] == '3.11 構文エラー処理
エラー検出
/**
* 構文エラーを報告する
*/
void parser_error(t_parser *parser, const char *msg)
{
ft_putstr_fd("minishell: ", STDERR_FILENO);
ft_putendl_fd(msg, STDERR_FILENO);
parser->error = 1;
}
/**
* 予期しないトークンのエラー
*/
void parser_unexpected_token(t_parser *parser, t_token *token)
{
ft_putstr_fd("minishell: syntax error near unexpected token `",
STDERR_FILENO);
if (token)
ft_putstr_fd(token->value, STDERR_FILENO);
else
ft_putstr_fd("newline", STDERR_FILENO);
ft_putendl_fd("'", STDERR_FILENO);
parser->error = 1;
}
事前構文チェック
/**
* トークン列の構文を事前チェックする
*/
int syntax_check(t_token *tokens)
{
t_token *current;
if (!tokens)
return (1); /* 空入力はOK */
/* パイプで始まる */
if (tokens->type == TOKEN_PIPE)
{
ft_putendl_fd(
"minishell: syntax error near unexpected token `|'", 2);
return (0);
}
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 (0);
}
/* パイプで終わる */
if (current->type == TOKEN_PIPE && !current->next)
{
ft_putendl_fd(
"minishell: syntax error near unexpected token `|'", 2);
return (0);
}
/* リダイレクトの後にファイル名がない */
if (is_redirect_token(current->type))
{
if (!current->next ||
!is_word_token(current->next->type))
{
ft_putendl_fd(
"minishell: syntax error near unexpected token `newline'", 2);
return (0);
}
}
current = current->next;
}
return (1);
}
3.12 メモリ管理
ASTの解放
/**
* ASTを再帰的に解放する
*/
void ast_free(t_ast *ast)
{
int i;
if (!ast)
return;
if (ast->type == NODE_PIPE)
{
ast_free(ast->left);
ast_free(ast->right);
}
else if (ast->type == NODE_COMMAND)
{
/* argvの解放 */
if (ast->argv)
{
i = 0;
while (ast->argv[i])
free(ast->argv[i++]);
free(ast->argv);
}
/* リダイレクトの解放 */
redirect_free_list(ast->redirects);
}
free(ast);
}
/**
* リダイレクトリストを解放する
*/
void redirect_free_list(t_redirect *list)
{
t_redirect *next;
while (list)
{
next = list->next;
free(list->file);
free(list);
list = next;
}
}
3.13 デバッグとテスト
AST可視化
/**
* ASTを可視化する（デバッグ用）
*/
void ast_print(t_ast *ast, int depth)
{
int i;
if (!ast)
return;
/* インデント */
for (i = 0; i < depth; i++)
printf(" ");
if (ast->type == NODE_PIPE)
{
printf("PIPE\n");
ast_print(ast->left, depth + 1);
ast_print(ast->right, depth + 1);
}
else if (ast->type == NODE_COMMAND)
{
printf("CMD:");
if (ast->argv)
{
i = 0;
while (ast->argv[i])
printf(" %s", ast->argv[i++]);
}
printf("\n");
/* リダイレクト表示 */
redirect_print(ast->redirects, depth + 1);
}
}
/**
* リダイレクトを表示する
*/
void redirect_print(t_redirect *redir, int depth)
{
int i;
const char *type_str;
while (redir)
{
for (i = 0; i < depth; i++)
printf(" ");
if (redir->type == REDIR_INPUT)
type_str = "<";
else if (redir->type == REDIR_OUTPUT)
type_str = ">";
else if (redir->type == REDIR_APPEND)
type_str = ">>";
else
type_str = "<<";
printf("REDIR: %s %s\n", type_str, redir->file);
redir = redir->next;
}
}
テストケース
/**
* パーサのテスト
*/
void parser_test(void)
{
t_token *tokens;
t_ast *ast;
printf("=== Parser Tests ===\n\n");
/* テスト1: 単純コマンド */
printf("Test 1: ls -la\n");
tokens = lexer_tokenize("ls -la");
ast = parser_parse(tokens);
ast_print(ast, 0);
ast_free(ast);
lexer_free_tokens(tokens);
/* テスト2: パイプ */
printf("\nTest 2: cat file | grep test\n");
tokens = lexer_tokenize("cat file | grep test");
ast = parser_parse(tokens);
ast_print(ast, 0);
ast_free(ast);
lexer_free_tokens(tokens);
/* テスト3: リダイレクト */
printf("\nTest 3: cat < in.txt > out.txt\n");
tokens = lexer_tokenize("cat < in.txt > out.txt");
ast = parser_parse(tokens);
ast_print(ast, 0);
ast_free(ast);
lexer_free_tokens(tokens);
/* テスト4: 複合 */
printf("\nTest 4: cat file | grep test | wc -l > result.txt\n");
tokens = lexer_tokenize("cat file | grep test | wc -l > result.txt");
ast = parser_parse(tokens);
ast_print(ast, 0);
ast_free(ast);
lexer_free_tokens(tokens);
}
3.14 まとめ
本章では、構文解析の理論と実装を学んだ：
文脈自由文法: Chomsky Type 2、BNF/EBNF
構文解析アルゴリズムの歴史: LR、LALR、YACC
再帰下降構文解析: Wirthの手法、左再帰の除去
抽象構文木（AST）: 構文木との違い、設計
シェル文法の定義: Minishell用EBNF
パーサ実装: パイプライン、コマンド、リダイレクト
変数展開: POSIX展開順序
エラー処理: 構文エラーの検出と報告 次章では、コマンド実行について学ぶ。ASTを解釈してプロセスを生成し、パイプとリダイレクトを設定する方法を解説する。
---
参考文献
Chomsky, N. (1956). "Three Models for the Description of Language", IRE Transactions on Information Theory, 2(3)
Backus, J. W. et al. (1960). "Report on the Algorithmic Language ALGOL 60", Communications of the ACM, 3(5)
Knuth, D. E. (1965). "On the Translation of Languages from Left to Right", Information and Control, 8(6)
Wirth, N. (1976). "Algorithms + Data Structures = Programs", Prentice Hall
Aho, A. V., Sethi, R., & Ullman, J. D. (1986). "Compilers: Principles, Techniques, and Tools", Addison-Wesley
Johnson, S. C. (1975). "YACC: Yet Another Compiler-Compiler", Bell Laboratories Computing Science Technical Report No. 32
ISO/IEC 14977:1996 "Syntactic metalanguage — Extended BNF"
IEEE (1992). "IEEE Std 1003.2-1992: Shell and Utilities", IEEE Computer Society
))
return (str);
expander_init(&exp, str, shell);
result = expander_process(&exp);
free(str);
return (result);
}
展開器の実装
___CODE_BLOCK_26___
3.11 構文エラー処理
エラー検出
___CODE_BLOCK_27___
事前構文チェック
___CODE_BLOCK_28___
3.12 メモリ管理
ASTの解放
___CODE_BLOCK_29___
3.13 デバッグとテスト
AST可視化
___CODE_BLOCK_30___
テストケース
___CODE_BLOCK_31___
3.14 まとめ
本章では、構文解析の理論と実装を学んだ：
文脈自由文法: Chomsky Type 2、BNF/EBNF
構文解析アルゴリズムの歴史: LR、LALR、YACC
再帰下降構文解析: Wirthの手法、左再帰の除去
抽象構文木（AST）: 構文木との違い、設計
シェル文法の定義: Minishell用EBNF
パーサ実装: パイプライン、コマンド、リダイレクト
変数展開: POSIX展開順序
エラー処理: 構文エラーの検出と報告 次章では、コマンド実行について学ぶ。ASTを解釈してプロセスを生成し、パイプとリダイレクトを設定する方法を解説する。
---
参考文献
Chomsky, N. (1956). "Three Models for the Description of Language", IRE Transactions on Information Theory, 2(3)
Backus, J. W. et al. (1960). "Report on the Algorithmic Language ALGOL 60", Communications of the ACM, 3(5)
Knuth, D. E. (1965). "On the Translation of Languages from Left to Right", Information and Control, 8(6)
Wirth, N. (1976). "Algorithms + Data Structures = Programs", Prentice Hall
Aho, A. V., Sethi, R., & Ullman, J. D. (1986). "Compilers: Principles, Techniques, and Tools", Addison-Wesley
Johnson, S. C. (1975). "YACC: Yet Another Compiler-Compiler", Bell Laboratories Computing Science Technical Report No. 32
ISO/IEC 14977:1996 "Syntactic metalanguage — Extended BNF"
IEEE (1992). "IEEE Std 1003.2-1992: Shell and Utilities", IEEE Computer Society
)
expand_variable(exp);
else
append_char(exp, exp->input[exp->pos++]);
}
return (exp->result);
}
/**
* 変数を展開する
*/
void expand_variable(t_expander *exp)
{
char *var_name;
char *var_value;
exp->pos++; /* '3.11 構文エラー処理
エラー検出
___CODE_BLOCK_27___
事前構文チェック
___CODE_BLOCK_28___
3.12 メモリ管理
ASTの解放
___CODE_BLOCK_29___
3.13 デバッグとテスト
AST可視化
___CODE_BLOCK_30___
テストケース
___CODE_BLOCK_31___
3.14 まとめ
本章では、構文解析の理論と実装を学んだ：
文脈自由文法: Chomsky Type 2、BNF/EBNF
構文解析アルゴリズムの歴史: LR、LALR、YACC
再帰下降構文解析: Wirthの手法、左再帰の除去
抽象構文木（AST）: 構文木との違い、設計
シェル文法の定義: Minishell用EBNF
パーサ実装: パイプライン、コマンド、リダイレクト
変数展開: POSIX展開順序
エラー処理: 構文エラーの検出と報告 次章では、コマンド実行について学ぶ。ASTを解釈してプロセスを生成し、パイプとリダイレクトを設定する方法を解説する。
---
参考文献
Chomsky, N. (1956). "Three Models for the Description of Language", IRE Transactions on Information Theory, 2(3)
Backus, J. W. et al. (1960). "Report on the Algorithmic Language ALGOL 60", Communications of the ACM, 3(5)
Knuth, D. E. (1965). "On the Translation of Languages from Left to Right", Information and Control, 8(6)
Wirth, N. (1976). "Algorithms + Data Structures = Programs", Prentice Hall
Aho, A. V., Sethi, R., & Ullman, J. D. (1986). "Compilers: Principles, Techniques, and Tools", Addison-Wesley
Johnson, S. C. (1975). "YACC: Yet Another Compiler-Compiler", Bell Laboratories Computing Science Technical Report No. 32
ISO/IEC 14977:1996 "Syntactic metalanguage — Extended BNF"
IEEE (1992). "IEEE Std 1003.2-1992: Shell and Utilities", IEEE Computer Society
))
return (str);
expander_init(&exp, str, shell);
result = expander_process(&exp);
free(str);
return (result);
}
展開器の実装
___CODE_BLOCK_26___
3.11 構文エラー処理
エラー検出
___CODE_BLOCK_27___
事前構文チェック
___CODE_BLOCK_28___
3.12 メモリ管理
ASTの解放
___CODE_BLOCK_29___
3.13 デバッグとテスト
AST可視化
___CODE_BLOCK_30___
テストケース
___CODE_BLOCK_31___
3.14 まとめ
本章では、構文解析の理論と実装を学んだ：
次章では、コマンド実行について学ぶ。ASTを解釈してプロセスを生成し、パイプとリダイレクトを設定する方法を解説する。
---
参考文献
3.11 構文エラー処理
エラー検出
___CODE_BLOCK_27___
事前構文チェック
___CODE_BLOCK_28___
3.12 メモリ管理
ASTの解放
___CODE_BLOCK_29___
3.13 デバッグとテスト
AST可視化
___CODE_BLOCK_30___
テストケース
___CODE_BLOCK_31___
3.14 まとめ
本章では、構文解析の理論と実装を学んだ：
次章では、コマンド実行について学ぶ。ASTを解釈してプロセスを生成し、パイプとリダイレクトを設定する方法を解説する。
---
参考文献
展開器の実装
___CODE_BLOCK_26___
3.11 構文エラー処理
エラー検出
___CODE_BLOCK_27___
事前構文チェック
___CODE_BLOCK_28___
3.12 メモリ管理
ASTの解放
___CODE_BLOCK_29___
3.13 デバッグとテスト
AST可視化
___CODE_BLOCK_30___
テストケース
___CODE_BLOCK_31___
3.14 まとめ
本章では、構文解析の理論と実装を学んだ：
次章では、コマンド実行について学ぶ。ASTを解釈してプロセスを生成し、パイプとリダイレクトを設定する方法を解説する。
---
参考文献
3.11 構文エラー処理
エラー検出
___CODE_BLOCK_27___
事前構文チェック
___CODE_BLOCK_28___
3.12 メモリ管理
ASTの解放
___CODE_BLOCK_29___
3.13 デバッグとテスト
AST可視化
___CODE_BLOCK_30___
テストケース
___CODE_BLOCK_31___
3.14 まとめ
本章では、構文解析の理論と実装を学んだ：
次章では、コマンド実行について学ぶ。ASTを解釈してプロセスを生成し、パイプとリダイレクトを設定する方法を解説する。
---
参考文献
展開器の実装
___CODE_BLOCK_26___
3.11 構文エラー処理
エラー検出
___CODE_BLOCK_27___
事前構文チェック
___CODE_BLOCK_28___
3.12 メモリ管理
ASTの解放
___CODE_BLOCK_29___
3.13 デバッグとテスト
AST可視化
___CODE_BLOCK_30___
テストケース
___CODE_BLOCK_31___
3.14 まとめ
本章では、構文解析の理論と実装を学んだ：
次章では、コマンド実行について学ぶ。ASTを解釈してプロセスを生成し、パイプとリダイレクトを設定する方法を解説する。
---