search

2.5 構文解析

字句解析が出力したトークン列を読み込んで、構文木を出力する処理を構文解析と呼びます。 本書の構文木は、後述の非終端記号や括弧が含まれるため、一般的に解析木や具象構文木と呼ばれているものです。 この章で作るコンパイラでは、 int_calc_compiler/src/lib/tp_compiler/tp_make_parse_tree.carrow-up-right ：tp_make_parse_tree 関数が該当します。

hashtag
2.5.1 初歩的な構文解析の方法

例として、以下のようなソースコードをコンパイルできることを前提としています。

int32_t value1 = (1 + 2) * 3;
int32_t value2 = 2 + (3 * value1);
value1 = value2 + 100;

字句解析が出力したトークン列を、トークン列の末尾 TP_SYMBOL_NULL に到達するまで、以下のような文法に従って構文を解釈し、構文木を出力します。 文法の左辺は非終端記号と呼び、基本的に対応する C 言語の関数を作成します。文法の右辺は、C 言語の関数本体のコード内容を表したものと思ってください。 文法の右辺に出現する非終端記号は、対応する C 言語の関数呼び出しになります。文法の右辺に出現する非終端記号以外の要素は、終端記号と呼びます。 終端記号は、字句解析が出力したトークンです。文法の右辺の記載ルールは、正規表現的なものになっています。正規右辺文法と呼んでいる書籍も存在するようです。

Program -> Statement+
Statement -> Type? variable '=' Expression ';'
Expression -> Term (('+' | '-') Term)*
Term -> Factor (('*' | '/') Factor)*
Factor -> '(' Expression ')' | ('+' | '-')? (variable | constant)
Type -> int32_t

上記の文法の非終端記号 Expression は、Term -> Factor -> Expression と、自分自身を呼び出す実行経路を持ちます。いわゆる再帰呼び出しです。 本書では、このような再帰呼び出しで構文を解釈する、再帰降下構文解析を扱います。再帰降下構文解析では、左再帰の問題を解決する必要がありますが、次章で説明します。

構文木は、 int_calc_compiler/src/lib/tp_compiler/tp_compiler.harrow-up-right の記号表(TP_SYMBOL_TABLE 構造体)の TP_PARSE_TREE* member_tp_parse_tree; に格納され、 意味解析(tp_semantic_analysis.c)と、中間コード生成(tp_make_wasm.c)で参照されます。構文木を表す TP_PARSE_TREE 構造体は、以下の通りです。 TP_PARSE_TREE_GRAMMER member_grammer; に文法の種類、size_t member_element_num; に文法に含まれる要素数、TP_PARSE_TREE_ELEMENT* member_element; に文法の要素が格納されます。 文法の要素は、トークン・構文木の他の部分(部分木と呼びます)・文法の要素の末尾 TP_PARSE_TREE_TYPE_NULL が含まれます。文法の種類は、部分木の種類であるとも言えます。

typedef enum TP_PARSE_TREE_TYPE_
{
    TP_PARSE_TREE_TYPE_NULL = 0,
    TP_PARSE_TREE_TYPE_TOKEN,
    TP_PARSE_TREE_TYPE_NODE
}TP_PARSE_TREE_TYPE;

typedef union tp_parse_tree_element_union_{
    TP_TOKEN* member_tp_token;
    struct tp_parse_tree_* member_child;
}TP_PARSE_TREE_ELEMENT_UNION;

typedef struct tp_parse_tree_element_{
    TP_PARSE_TREE_TYPE member_type;
    TP_PARSE_TREE_ELEMENT_UNION member_body;
}TP_PARSE_TREE_ELEMENT;

typedef enum TP_PARSE_TREE_GRAMMER_
{
    TP_PARSE_TREE_GRAMMER_PROGRAM,
    TP_PARSE_TREE_GRAMMER_STATEMENT_1,
    TP_PARSE_TREE_GRAMMER_STATEMENT_2,
    TP_PARSE_TREE_GRAMMER_EXPRESSION_1,
    TP_PARSE_TREE_GRAMMER_EXPRESSION_2,
    TP_PARSE_TREE_GRAMMER_TERM_1,
    TP_PARSE_TREE_GRAMMER_TERM_2,
    TP_PARSE_TREE_GRAMMER_FACTOR_1,
    TP_PARSE_TREE_GRAMMER_FACTOR_2,
    TP_PARSE_TREE_GRAMMER_FACTOR_3
}TP_PARSE_TREE_GRAMMER;

typedef struct tp_parse_tree_{
    TP_PARSE_TREE_GRAMMER member_grammer;
    size_t member_element_num;
    TP_PARSE_TREE_ELEMENT* member_element;
}TP_PARSE_TREE;

前節で既出ですが、参照しやすいように、トークンを表す TP_TOKEN 構造体を再掲します。

コンパイル対象のソースコードの 1 行目を、もう一度見てみましょう。

この代入文の右辺は、以下の文法の 2 行目から Expression が対応することが分かります。

右辺の最初にコンパイルされる部分は、終端記号 '(' と ')' が出現することから、文法： Factor -> '(' Expression ')' が対応しますので、以下の式であることが分かります。

上記の式に関係のない部分を除外して簡略化した文法は、以下のようになります。

ソースコードを構文解析して得られた構文木は、デバッグ用途のために int_calc_parse_tree.log ファイルに出力できるようになっています。 以下は、上記の TP_PARSE_TREE 構造体をテキスト表現にしたものです。これは 1 + 2 の構文解析結果です。まず、数値 1 が見つかり、次に数値 2 が見つかり、 最後に 1 + 2 が組み立てられました。このように木構造が成長していくことで、最終的に構文木全体を完成させます。構文木はトークンを含むため、 TP_TOKEN 構造体も出力されています。

hashtag
2.5.2 具体的な構文解析の処理の例(簡略化したソースコードによる説明)

前項で検討した以下の式について、

上記の式に関係のない部分を除外して簡略化した文法は、以下のようになると書きました。

以下は、文法： Expression -> Term ('+' Term)* に対応した parse_expression 関数の例です。非終端記号 Term に対応した parse_term 関数を呼んでいるのが分かると思います。 冒頭の TP_TOKEN* backup_token_position = TP_POS(symbol_table); で、読んでいるトークンの現在位置を保存しておき、構文エラーだったら保存しておいた トークンの位置まで戻る処理の TP_POS(symbol_table) = backup_token_position; まで goto し、構文解析失敗(文法にマッチしなかった)を意味する NULL ポインタを返しています。 これは、部分木を呼び出し元の関数に返さないことを意味しています。構文解析に成功すると(文法にマッチすると)、MAKE_PARSE_SUBTREE マクロで構文木の部分木を出力します。 これは、次項で説明します。なお、式が入れ子になる段数を無制限にしてしまうと、スタックを確保できる上限を超えてコンパイラが異常終了するため、 NESTING_LEVEL_OF_EXPRESSION_MAXIMUM 以上の入れ子になった場合は、NULL ポインタを返してコンパイル・エラーになるようにしています。

以下は、文法： Term -> Factor に対応した parse_term 関数の例です。非終端記号 Factor に対応した parse_factor 関数を呼んでいるのが分かると思います。

以下は、文法： Factor -> '(' Expression ')' | constant に対応した parse_factor 関数の例です。非終端記号 Expression に対応した parse_expression 関数を呼んでいるのが 分かると思います。読み込んだトークン列が、文法： Factor -> '(' Expression ')' にマッチしなかった場合、トークンの位置を後戻り(バックトラック)して、 文法： Factor -> constant にマッチするか、試みるようになっています。文法： Factor -> constant にマッチした場合、calc_const_value 関数を呼び出し、 トークンの文字列を数値に変換しています。この関数の内容は省略します。式 (1 + 2) は、文法： Factor -> '(' Expression ')' にマッチし、parse_expression 関数が呼ばれ、 parse_expression 関数にて、それ以上は文法： Factor -> '(' Expression ')' にはマッチしないため、その結果として、文法： Expression -> constant '+' constant のように解釈されます。 前項で示した、構文木をテキスト表現にした log ファイルの例のようになります。

hashtag
2.5.3 構文木の部分木を出力する MAKE_PARSE_SUBTREE マクロの仕組み

前項までに検討した以下の式について、

上記の式に関係のない部分を除外して簡略化した文法は、以下のようになると書きました。

以下は、文法： Expression -> Term ('+' Term)* に対応した parse_expression 関数で、構文解析に成功(文法にマッチ)した際に、 MAKE_PARSE_SUBTREE マクロで構文木の部分木を出力する部分を抜き出したものです。1 + 2 の各要素は揃っていて、部分木に組み立てる場面です。

以下の、MAKE_PARSE_SUBTREE マクロで構文木の部分木を出力する部分は、

MAKE_PARSE_SUBTREE マクロの可変長引数が以下のように展開され、TP_PARSE_TREE_ELEMENT 構造体が複数並んだ状態になり、MAKE_PARSE_SUBTREE マクロが 展開された先の make_parse_subtree 関数の第 3 引数に、TP_PARSE_TREE_ELEMENT 構造体の配列として、第 4 引数に TP_PARSE_TREE_ELEMENT 構造体の配列の要素数が渡ります。 MAKE_PARSE_SUBTREE マクロが可変長引数を受け付けるようになっているため、文法の右辺の要素数を固定化する必要がなくなり、MAKE_PARSE_SUBTREE マクロの呼び出しで、 多様な種類の部分木を構築することが可能になっています。

make_parse_subtree 関数では、構文木の部分木のメモリ領域を確保し、引数で渡される TP_PARSE_TREE_ELEMENT 構造体の配列などを、確保したメモリ領域にコピーしています。 また、文法の要素の最後に、文法の要素の末尾を示す TP_PARSE_TREE_TYPE_NULL を追加します。部分木だけでなく、トークンについてもポインタがコピーされるだけですから、 トークンの実体は字句解析で確保したメモリ領域であることに注意する必要があります。トークンのメモリ領域を解放する場合は、 記号表(TP_SYMBOL_TABLE 構造体)の TP_TOKEN* member_tp_token; のメモリ領域を解放する必要があります。その他の領域のポインタを free してしまうと多重解放になり、 不具合が生じる原因になります。

前へ2.4 字句解析次へ2.6 意味解析

最終更新