式を解析する
構文木を構築します。
「式を解析する」はCoddyKit上の無料C Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
トークンから木構造へ
パースでは、平坦なトークンストリームを構造化された抽象構文木（AST）に変換します。この木は、生のトークンが暗黙的に示している優先順位とグループ化を表します。
3 + 4 * 2 の場合、ASTでは加算の下に乗算が入れ子になるため、14ではなく11と評価されます。
ASTノードの形
各ノードは、数値を持つ葉、または2つの子を持つ二項演算のいずれかです。タグ付き構造体と共用体を使うと、メモリをコンパクトに保てます。
実行時には、演算子の文字によって +、-、*、/ を区別します。
typedef struct Node {
enum { N_NUM, N_BINOP } kind;
union {
int value; /* N_NUM */
struct { /* N_BINOP */
char op;
struct Node *left, *right;
} bin;
};
} Node;ノードのアロケーション
2つの小さなコンストラクタで、ヒープ上にノードを割り当てます。木を下から構築するため、まず葉を作り、その後で演算子ノードに包みます。
実用的なインタープリタでは、後で解放できるように、これらのアロケーションを追跡します。
#include <stdlib.h>
static Node *num(int v) {
Node *n = malloc(sizeof *n);
n->kind = N_NUM; n->value = v;
return n;
}
static Node *binop(char op, Node *l, Node *r) {
Node *n = malloc(sizeof *n);
n->kind = N_BINOP;
n->bin.op = op; n->bin.left = l; n->bin.right = r;
return n;
}文法
典型的な優先順位文法を使用します。expr は + と - を処理し、term は * と / を処理し、factor は数値と括弧を処理します。
優先順位の高い規則ほど深い位置にあるため、乗算は自動的に加算より強く結び付きます。
/* Grammar (EBNF):
expr = term { ('+' | '-') term } ;
term = factor { ('*' | '/') factor } ;
factor = NUMBER | '(' expr ')' ; */トークンの照合
expect ヘルパーは、指定された種類のトークンを消費します。該当するトークンがなければ処理を中断します。これはパーサーと字句解析器の間の契約です。
トークナイザーのレッスンで作成した先読みヘルパー cur と bump を再利用します。
#include <stdio.h>
#include <stdlib.h>
static void expect(TokKind k) {
if (cur().kind != k) {
fprintf(stderr, "parse error: unexpected token\n");
exit(1);
}
bump();
}ファクターの解析
ファクターは文法における最小単位で、リテラルの数値または括弧で囲まれた部分式のいずれかです。括弧内では parse_expr を再帰的に呼び出します。
この再帰が、recursive-descent パーサー（再帰下降パーサー）という名前の由来です。
static Node *parse_expr(void);
static Node *parse_factor(void) {
if (cur().kind == TOK_NUM) {
int v = cur().value; bump();
return num(v);
}
expect(TOK_LPAREN);
Node *e = parse_expr();
expect(TOK_RPAREN);
return e;
}項の解析
項ではまず1つのファクターを解析し、その後 * または / が現れる間ループして、それぞれを左結合の二項演算ノードにまとめます。
左結合とは、8 / 4 / 2 が (8 / 4) / 2 = 1 として解析されることです。
static Node *parse_term(void) {
Node *left = parse_factor();
while (cur().kind == TOK_STAR || cur().kind == TOK_SLASH) {
char op = (cur().kind == TOK_STAR) ? '*' : '/';
bump();
left = binop(op, left, parse_factor());
}
return left;
}式の解析
最上位の規則は parse_term に対応していますが、+ と - を処理します。各層が次に優先順位の高い規則を呼び出すため、木は正しく入れ子になります。
この3つの関数による構造が、パーサーの中核です。
static Node *parse_expr(void) {
Node *left = parse_term();
while (cur().kind == TOK_PLUS || cur().kind == TOK_MINUS) {
char op = (cur().kind == TOK_PLUS) ? '+' : '-';
bump();
left = binop(op, left, parse_term());
}
return left;
}木の確認
このプログラムは式を解析し、完全に括弧で囲んだ形で再び出力します。これにより、優先順位がどのように解決されたかを確認できます。
pretty-printer は、パーサーが構築したものと同じノード構造を再帰的にたどります。
#include <stdio.h>
typedef struct Node {
int is_num; int value;
char op; struct Node *l, *r;
} Node;
static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }
static void show(Node *n){
if (n->is_num){ printf("%d", n->value); return; }
printf("("); show(n->l); printf(" %c ", n->op); show(n->r); printf(")");
}
int main(void){
/* 3 + 4 * 2 -> (3 + (4 * 2)) */
Node *ast = B('+', N(3), B('*', N(4), N(2)));
show(ast); printf("\n");
return 0;
}左再帰の回避
expr = expr '+' term のような素朴な文法では、parse_expr が自分自身を無限に呼び出してしまいます。recursive descent は直接的な左再帰を処理できません。
この規則を { '+' term } に対する while ループとして書き直せば、無限再帰を完全に回避できます。
ASTが必要な理由
AST は構文と実行を分離します。同じ木を、再解析することなく評価、最適化、またはバイトコードへのコンパイルに利用できます。
次は、この木をたどって値を計算します。
理解度チェック
文法の各層がどのように優先順位を適用しているか考えてみましょう。
まとめ
recursive-descent パーサーを作成しました。AST ノードの構造体とコンストラクター、そして優先順位と左結合性を表す expr/term/factor 関数を実装しました。
生成された木は評価の準備ができています。
よくある質問
「式を解析する」レッスンは無料ですか？
はい。「式を解析する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「式を解析する」で何を学びますか？
構文木を構築します。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「式を解析する」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。