構文解析2

### 概要
構文解析1で，自作の字句解析器とyaccを連携できたので，文法を追加し，抽象構文木(AST)を生成してみる．
簡単な言語とはいえ，それなりの構文を定義しなければいけないので，とりあえず式(Expression)に着目して構文木の生成とその確認をやってみる．方針としては，

1. yaccに式の文法を追加．
    1. 構文の追加
    1. パーサーで確認
1. メモリモジュールの追加
1. 式定義に必要な構造体とVisitorの準備
1. ASTの生成と確認

の順で構築していく．


### yaccに式の文法を追加

#### 構文の追加
これまでyaccに追加していたのは以下のような文法であった．

```
translation_unit
    : statement
    ;
statement
    : IDENTIFIER LP RP SEMICOLON
    ;
```

これだと，関数呼び出ししかかけないので，C言語など現在のプログラミング言語で定義できる式の構文を追加していく．この言語で扱える演算子をとりあえず以下のように定義し，優先度も定義する．優先度は生成される解析木の深さで表現する．つまり，優先度が高い構文ほど構文をより深いところで定義する．

| 種類 | 演算子 | 優先度 |
|--------------:|------------:|:------------:|
| インクリメント，デクリメント，関数呼出し | ++, --, () | 高い |
|符号の反転 | -, ! |  |
|乗算，除算，剰余 | *, /, % |  |
|加算，減算 | +, - | |
|大小比較 |>=,<=,>,<| |
|同値比較 |==, !=| |
|論理積 |&&| |
|論理和 | &#124;&#124;| |
|代入 | =, +=, -=, *=, /=, %=| 低い|

実際に定義した構文ファイル．

```
(略)
%%
translation_unit
	: statement_list
	;

statement_list
        : statement
        | statement_list statement
        ;

statement
/*	: IDENTIFIER LP RP SEMICOLON */
	: expression SEMICOLON
	;

expression
	: assignment_expression
	;


assignment_expression
        : logical_or_expression
        | postfix_expression assignment_operator assignment_expression {printf("assign\n");}
        ;
assignment_operator
        : ASSIGN_T        { printf("=\n"); }
        | ADD_ASSIGN_T    { printf("+=\n"); }
        | SUB_ASSIGN_T    { printf("-=\n"); }
        | MUL_ASSIGN_T    { printf("*=\n"); }
        | DIV_ASSIGN_T    { printf("/=\n"); }
        | MOD_ASSIGN_T    { printf("%% =\n"); }
        ;

logical_or_expression
        : logical_and_expression
        | logical_or_expression LOGICAL_OR logical_and_expression { printf("LOR\n"); }
        ;
logical_and_expression
        : equality_expression
        | logical_and_expression LOGICAL_AND equality_expression  { printf("LAND\n"); }
        ;

equality_expression
        : relational_expression
        | equality_expression EQ relational_expression { printf("EQ\n"); }
        | equality_expression NE relational_expression { printf("NE\n"); }
        ;

relational_expression
        : additive_expression
        | relational_expression GT additive_expression { printf("gt\n"); }
        | relational_expression GE additive_expression { printf("ge\n"); }
        | relational_expression LT additive_expression { printf("lt\n"); }
        | relational_expression LE additive_expression { printf("ge\n"); }
        ;

additive_expression
        : multiplicative_expression
        | additive_expression ADD multiplicative_expression  { printf("add\n"); }
        | additive_expression SUB multiplicative_expression  { printf("sub\n"); }
        ;

multiplicative_expression
        : unary_expression
        | multiplicative_expression MUL unary_expression { printf("mul\n"); }
        | multiplicative_expression DIV unary_expression { printf("div\n"); }
        | multiplicative_expression MOD unary_expression { printf("mod\n"); }
        ;

unary_expression
        : postfix_expression   
        | SUB unary_expression          { printf("unary sub\n"); }
        | EXCLAMATION unary_expression  { printf("unary exclamation\n"); }
        ;

postfix_expression
        : primary_expression
        | postfix_expression LP RP     { printf("function call\n"); }
        | postfix_expression INCREMENT { printf("increment\n"); }
        | postfix_expression DECREMENT { printf("decrement\n"); }
        ;

primary_expression
	: LP expression RP { printf("LP expr RP\n"); }
	| IDENTIFIER  { printf("IDENTIFIER\n"); }
	| INT_LITERAL { printf("INT_LITERAL\n");}
	| DOUBLE_LITERAL { printf("DOUBLE_LITERAL\n");}
	| TRUE_T      { printf("TRUE_T\n");}
	| FALSE_T     { printf("FALSE_T\n");}
	;
%%
```
基本的には，上の表で決めた構文をそのまま定義している．ただし，以降行うテストのために，複数の式を書けたほうが良いので，暫定的に式は式文として複数書けるようにした．

```
translation_unit
	: statement_list    // プログラムは式文ある．
	;
statement_list
        : statement
        | statement_list statement  // 式文の繰り返し
        ;
statement
	: expression SEMICOLON  // 式文は式+セミコロン
```

#### パーサーで確認
定義した文法からパーサを生成し，テストプログラムを実行する．前回構文のテストで用いた`prog1.cs`を以下のように変更

```c:tests/prog1.cs
#print();
# for primary expression
1;
10.9;
true;
false;
(true);
var;

# for postfix_expression
var++;
var--;
print();
(略)
```

```
>./prst
```
とすると，以下の出力を得る．

```
(略)
IDENTIFIER
=
INT_LITERAL
assign
IDENTIFIER
+=
INT_LITERAL
assign
IDENTIFIER
-=
INT_LITERAL
assign
```
エラーは出ていないので，パースは成功している．

ここまでの実装/実行は，以下のコマンドで確認可能

```
>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch parse_expression origin/parse_expression
>git checkout parse_expression
>make
>cd comp
>./prst
```

### メモリモジュールの追加
今後，ASTのノードを作るときに何度もメモリを確保し，開放する必要がある．Cでのメモリ獲得・解放は一歩間違うとメモリリークのもととなる．また，ASTのノードは細かい単位で何度も生成するので，その度に`malloc`するのはなんとなく効率が悪い．メモリがキチンと開放されているかどうか，また，一度のに一定のメモリを確保し(PAGESIZE)，そこからこまいかい単位でメモリを割り当て，最後に一気に開放するようなモジュールを追加する．モジュールの詳細は省略するが，以下の関数を用意する．

| 関数 | 機能 |
|--------------:|:------------|
|void* MEM_malloc(size_t size) | size分の領域を確保する|
|void* MEM_realloc(void* ptr, size_t size) | ptrの領域をsize分増やす|
|void MEM_free(void* ptr) | ptrの領域を開放する|
|void MEM_dump_memory() | 確保して開放していないメモリを表示する|
|||
|MEM_Storage MEM_open_storage(int page_size) | page_size分一気に領域を確保する．|
|void* MEM_storage_malloc(MEM_Storage storage, size_t size) | 確保した領域からsize分メモリを確保し，返す．|
|void MEM_dispose(MEM_Storage storage) | 一気に確保した領域を開放する．|


これらの関数をテストするために，以下のテストプログラムを書き，動作を確かめる．

```c:memtest.c
int main(int argc, char** argv) {
   
    char *ptr;
    ptr = (char*)MEM_malloc(10);   // (1)10バイトメモリ確保
    for (int i = 0; i < 10; ++i) {
        ptr[i] = 0xaa;
    }
    MEM_dump_memory();　　　　　　　 // (1)表示する
    MEM_free(ptr);                //    開放する
    MEM_dump_memory();            //    解放後．表示する
    

    MEM_Storage storage = MEM_open_storage(0); // (2) デフォルトのページサイズを一気に確保
    ptr = MEM_storage_malloc(storage, 17);     // 　　確保した領域から17バイト切り出し，0xeeを書き込む
    for (int i = 0; i < 17; ++i) {
        ptr[i] = 0xee;
    }
    ptr = MEM_storage_malloc(storage, 10);     //  　さらに10バイト切り出して0xefを書き込む
    for (int i = 0; i < 10; ++i) {
        ptr[i] = 0xef;
    }

    printf("-----------------------\n");
    MEM_dump_memory();
    MEM_dispose(storage);
    MEM_dump_memory();
       
    return (EXIT_SUCCESS);
```

(1)
このテストは，10バイト領域を確保し，そこに`0xaa`を書き込む．そして，確保したメモリを表示した後開放し，再びメモリを表示しようとしている．この部分を実行すると，以下の結果を得る．

```
-----------------------------------
-- size:10, file:memtest.c, line:26 -- 
-- head:0x7fe243402840, begin:0x7fe243402870 --
-----------------------------------

0a 00 00 00 cc cc cc cc 89 cf f0 0d 01 00 00 00 
1a 00 00 00 cc cc cc cc 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 cd cd cd cd cd cd cd cd 
aa aa aa aa aa aa aa aa aa aa cd cd cd cd 

no allocated memory
```

この結果を見ると，先頭から48バイトがヘッダなので，その後`0xaa`が10バイト続いていることがわかる．そして，2回めの目盛表示では，既にその前に開放しているので，"no allocated memory"と表示されている．この結果より，うまく動いていることがわかる．

(2)
ここでは，最初にある一定の領域を確保し，そこから2回メモリを切り出している．この部分の実行結果は次のようになる．

```
-----------------------------------
-- size:8208, file:memtest.c, line:37 -- 
-- head:0x7fe243801000, begin:0x7fe243801030 --
-----------------------------------

10 20 00 00 cc cc cc cc 89 cf f0 0d 01 00 00 00 
25 00 00 00 cc cc cc cc 00 00 00 00 00 00 00 00 
80 28 40 43 e2 7f 00 00 cd cd cd cd cd cd cd cd 
00 04 00 00 05 00 00 00 00 00 00 00 00 00 00 00 
ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee   // 17バイト分0xeeが書着込まれている
ee cc cc cc cc cc cc cc ef ef ef ef ef ef ef ef   // その後，切りの良いところから0xefが10バイト続く
ef ef cc cc cc cc cc cc cc cc cc cc cc cc cc cc 
(略)
```
この結果より，うまく動いていることがわかる．

メモリモジュールの動作確認は，以下のコマンドで確認できる

```
>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch memory_module origin/memory_module
>git checkout memory_module
>cd mamory
>make
>./memtest
```

### 式定義に必要な構造体とVisitorの準備
式をパースすることができるので，次はASTを作るために式を表現する構造体を定義し，さらにその構造体を生成する関数，トラバースするVisitorを追加していく．

#### 式の構造を定義
"csua.h"ヘッダを作成し，ここに構造体を定義する．

```c:csua.h
typedef enum {
    CS_FALSE = 0,
    CS_TRUE = 1    
} CS_Boolean;

typedef enum {
    BOOLEAN_EXPRESSION = 1,
    DOUBLE_EXPRESSION,
    INT_EXPRESSION,
    IDENTIFIER_EXPRESSION,
    INCREMENT_EXPRESSION,
    DECREMENT_EXPRESSION,
    FUNCTION_CALL_EXPRESSION,
    MINUS_EXPRESSION,
    LOGICAL_NOT_EXPRESSION,
    MUL_EXPRESSION,
    DIV_EXPRESSION,
    MOD_EXPRESSION,
    ADD_EXPRESSION,
    SUB_EXPRESSION,
    GT_EXPRESSION,
    GE_EXPRESSION,
    LT_EXPRESSION,
    LE_EXPRESSION,
    EQ_EXPRESSION,
    NE_EXPRESSION,
    LOGICAL_AND_EXPRESSION,
    LOGICAL_OR_EXPRESSION,
    ASSIGN_EXPRESSION,
    EXPRESSION_KIND_PLUS_ONE
} ExpressionKind;



typedef struct {
    Expression  *function;    
} FunctionCallExpression;

typedef struct {
    char *name;    
} IdentifierExpression;

typedef struct {
    Expression *left;
    Expression *right;    
} BinaryExpression;

typedef enum {
    ASSIGN = 1,
    ADD_ASSIGN,
    SUB_ASSIGN,
    MUL_ASSIGN,
    DIV_ASSIGN,
    MOD_ASSIGN,
    ASSIGN_PLUS_ONE    
} AssignmentOperator;

typedef struct {
    AssignmentOperator aope;
    Expression         *left;
    Expression         *right;        
} AssignmentExpression;

struct Expression_tag {
    ExpressionKind kind;
    union {
        double                 double_value;
        int                    int_value;
        CS_Boolean             boolean_value;
        IdentifierExpression   identifier;
        Expression             *inc_dec;
        FunctionCallExpression function_call_expression;
        Expression             *minus_expression;
        Expression             *logical_not_expression;        
        BinaryExpression       binary_expression;
        AssignmentExpression   assignment_expression;
    } u;
};
```

式には様々な種類があるので，種類をenum型の`ExpressionKind`で定義する．
式の定義本体は`Expression_tag`で，式の種類によって構造が変わるので，構造の異なる式ごとに構造体を定義し，`Expression_tag`の中でunionを使ってまとめる．例えば式の代入は，`式 代入記号 式`(`a=1`)のようになるので，式の構造は次のようになる．

```c:
typedef struct {
    AssignmentOperator aope; // 代入記号
    Expression         *left; // 代入される式
    Expression         *right; // 代入する式
} AssignmentExpression;
```
ただし，マイナス(-)や論理否定などは，式の値をマイナスにする，true/falseを入れ替えるだけなので，特別な構造体は設けずに直接unionの中に`Expression`のポインタで定義する．また，算術演算や比較演算で構成される式は，`式 演算子 式`となり，左辺と右辺を計算するので，`BinaryExpression`でまとめて表現する．

#### 式の構造を生成する関数
式の構造体のインスタンスを生成する関数を生成していく．これらの構造体はASTを構成し，ASTはコード生成したら一気に不要になるので，`MEM_storage_malloc`で生成して最後に一気に削除する，という方針を取る．

```c:create.c
#include <stdio.h>
#include "csua.h"
#include "../memory/MEM.h"

static MEM_Storage storage;

static void init_storage() {
    if (storage == NULL) { 
        storage = MEM_open_storage(0);
        printf("init_storage\n");
    }
}

void delete_storage() {
    if (storage != NULL) {
        MEM_dispose(storage);
    }
}

static Expression* cs_create_expression(ExpressionKind ekind) {
    init_storage();
    Expression *expr = (Expression*)MEM_storage_malloc(storage, sizeof(Expression));    
    expr->kind = ekind;
    return expr;
}
(略)
```

#### Visitorの準備
C言語でVisitorを実現するために，式の種類ごとにenter/leaveの関数を用意し，それをVisitorを表す構造体の中に配列で格納する．配列の添字(番号)を式の種類を識別する`ExpressionKind`と一致させる．Visitor構造体は`visitor.h`に，enter/leaveは`visitor.c`に定義し，`create_visitor/delete_visitor`関数を用意する．

```c:visitor.h
typedef void (*visit_expr)(Expression* expr);

struct Visitor_tag {
    visit_expr* enter_expr_list;
    visit_expr* leave_expr_list;
};

Visitor* create_treeview_visitor();
void delete_visitor(Visitor* visitor);
```
とりあえず，`INT_EXPRESSION`式に対応するenter/leave関数を用意する．

```c:visitor.c
(略)

static void enter_intexpr(Expression* expr) {
    print_depth();
    fprintf(stderr, "enter intexpr : %d\n", expr->u.int_value);
    increment();
}

static void leave_intexpr(Expression* expr) {
    decrement();
    print_depth();
    fprintf(stderr, "leave intexpr\n");
}

Visitor* create_treeview_visitor() {
    visit_expr* enter_expr_list;
    visit_expr* leave_expr_list;
    
    Visitor* visitor = MEM_malloc(sizeof(Visitor));
    // 関数ポインタのサイズ x 式の種類の領域を確保する
    enter_expr_list = (visit_expr*)MEM_malloc(sizeof(visit_expr) * EXPRESSION_KIND_PLUS_ONE);
    leave_expr_list = (visit_expr*)MEM_malloc(sizeof(visit_expr) * EXPRESSION_KIND_PLUS_ONE);


    enter_expr_list[INT_EXPRESSION] = enter_intexpr; // 対応する番号に関数ポインタを格納
    leave_expr_list[INT_EXPRESSION] = leave_intexpr;

    visitor->enter_expr_list = enter_expr_list;  // 最後にvisitorに配列をセット
    visitor->leave_expr_list = leave_expr_list;
    return visitor;
}

void delete_visitor(Visitor* visitor) {
    MEM_free(visitor->enter_expr_list);
    MEM_free(visitor->leave_expr_list);
    MEM_free(visitor);
}
```

続いて，VisitorとExpressionを使ってASTを深さ優先探索で探索するtraversorを実装する．まだINT_EXPRESSIONの式しかないので，とりあえずそれだけ実装する．

```c:traversor.c

void traverse_expr(Expression* expr, Visitor* visitor) {
    printf("traverse_expr\n");
    if (expr) {
        if (visitor->enter_expr_list[expr->kind] == NULL) {
            fprintf(stderr, "enter->type(%d) it null\n", expr->kind);
            exit(1);
        }

        visitor->enter_expr_list[expr->kind](expr); // enterを実行
        traverse_expr_children(expr, visitor);      // 子を探索
        visitor->leave_expr_list[expr->kind](expr); // leaveを実行

    }    
}

static void traverse_expr_children(Expression* expr, Visitor *visitor) {
    switch(expr->kind) {
        case INT_EXPRESSION: {
            break;
        }
        default:
            fprintf(stderr, "No such expr->kind %d\n", expr->kind);
    }
}
```

最後に，ここまで作った関数を使って，INT_EXPRESSION(だけ)を探索するサンプルを作成する．これがうまく動いたら，それぞれの式に対応する構造体，enter/leaveの実装，traversorの実装をしていけば良い．

```c:treetest.c

#include "visitor.h"
#include "../memory/MEM.h"

int main(void) {
    Expression* expr = cs_create_int_expression(10);　// INT_EXPRESSIONを作成
    printf("treetest\n");
    
    Visitor* visitor = create_treeview_visitor();    //  Visitorを作成
    traverse_expr(expr, visitor);                    //  探索の実行
    
    delete_visitor(visitor);                        // メモリの開放
    delete_storage();
    MEM_dump_memory();
    
    return 0;
}
```

実行

```
>comp/treet
init_storage
treetest
traverse_expr
enter intexpr : 10
leave intexpr
no allocated memory
```

うまく動いているようだ．

ここまでの動作確認は，以下のコマンドで確認できる

```
>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch prepare_visitor origin/prepare_visitor
>git checkout prepare_visitor
>make
>./comp/treet
```
この後，`csua.h`に定義した`Expression`の種類を生成する関数(`cs_create_xxx`)，対応するVisitorの関数(`enter/leave_xxx`)を追加していけばよい．

### ASTの生成と確認
ここまではノードを自前で生成し，ASTの確認をしていたが，ここからは構文解析をやりながらASTを作っていけるように変更する．つまり，`csua.y`のアクションで，`create.c`に定義した`cs_create_xxx`を実行する．そして，解析中に生成したASTのノードを保持し，最後にVisitorで生成後のASTを確認する．
そこで，今後のことを考え，複数の`Expression`を保持しておくための構造を用意し，`yacc`の以下のアクションでつなげることを考える．なお，本来は複数のStatementをつなげるようにすべきだが，まだ`Statement`を表す構造を定義していないので，とりあえずこのような暫定処置をとる．

```
statement
   : expression SEMICOLON { //ここでExpressionをつなげる }
```

まず，Expressionをつなげるための構造体，`ExpressionList`を用意し，それを内包する構造体として`CS_Compiler`も定義する．

```c:csua.h
/* Temporary used */
typedef struct ExpressionList_tag {
    Expression *expression;
    struct ExpressionList_tag *next;
} ExpressionList;


struct CS_Compiler_tag {
    MEM_Storage storage;        // ノードを作成するときに使用するMEM_Storage
    ExpressionList *expr_list;　// ポインタでつなげる．
};
```

`create.c`では，これまで独自のMEM_Storageを使っていたが，これからは`CS_Compiler`の中に定義した`MEM_Storage`を利用する．ただし，treetest.cを単独で実行させたいので，-DSTORAGEオプションで使用する`MEM_Storage`を切り替えるようにしておく(詳しくは後述するソースを参照)．
さらに，この`CS_Compiler`の生成，削除，コンパイルを実行する関数をまとめるファイル，`interface.c`を用意する．

```c:interface.c

#include <stdio.h>
#include <stdlib.h>
#include "csua.h"



CS_Compiler* CS_create_compiler() {
    MEM_Storage storage;
    CS_Compiler *compiler;    
    storage = MEM_open_storage(0);  // MEM_Storageを初期化
    compiler = (CS_Compiler*)MEM_storage_malloc(storage, sizeof(CS_Compiler));　// CS_Compilerを生成
    compiler->storage = storage;   // compilerにstorageを内包
    compiler->expr_list = NULL;    // ExpressionListをNULLで初期化
    
    cs_set_current_compiler(compiler);  // コンパイラの参照をセット．詳しくは後述するutil.cを参照
    
    return compiler;
}

void CS_delete_compiler(CS_Compiler* compiler) {
    MEM_Storage storage = compiler->storage;  
    MEM_dispose(storage);      // Compilerもstorageで生成されているので，この関数一発でメモリ開放できる
}

void CS_compile(CS_Compiler* compiler, FILE *fin) {
    extern int yyparse(void);
    extern FILE *yyin;
    yyin = fin;
    if (yyin == NULL) {
        fprintf(stderr, "cannot open file\n");
        exit(1);
    }
    if (yyparse()) {
        fprintf(stderr, "Parse Error");
        exit(1);
    }    
}
```

生成したコンパイラのインスタンスを保持し，セットやゲットするための関数を定義するファイルとしてutil.cを用意する．

```c:util.c

#include <stdio.h>
#include "csua.h"

static CS_Compiler *current_compiler = NULL; // コンパイラのインスタンス．シングルトンみたいなもの

void cs_set_current_compiler(CS_Compiler *compiler) {
    current_compiler = compiler;
}

CS_Compiler* cs_get_current_compiler() {
    return current_compiler;
}
```

`cs_get_current_compiler`を呼び出すことにより，`CS_Compiler`のインスタンスを取得できる．このインスタンスは先に書いた`CS_create_compiler`でセットする．

さらに，`Expression`を`ExpressionList`につなげる関数として，`cs_chain_expression_list`を`create.c`に定義する．

```c:create.c
(略)
ExpressionList* cs_chain_expression_list(ExpressionList* list, Expression* expr) {
    ExpressionList* p = list;
    ExpressionList* nlist= (ExpressionList*)MEM_storage_malloc(storage, sizeof(ExpressionList));    
    nlist->next = NULL;
    nlist->expression = expr;    
    if (p != NULL) {
        while (p->next) p = p->next; // チェーンの最後まで移動
        p->next = nlist;   // 最後につなげて先頭を返す．
        return list;
    } 
    return nlist;   
}
(略)
```

ここまでの実装を踏まえ，構文解析をしながらASTを生成していく．まずは以下のプログラムに対応するASTを生成することを目指す．このプログラムは実際にはエラーにすべきであるが，文法としては正しく，最小限の変更で動作確認可能である．

```c:
true + false;
```

まず，`yacc`で終端記号，非終端記号にマッチしたときに返す型を変更する．ここではExpressionだけに着目するので，`csua.y`の`union`に`Expression*`を加える．また，式を表す非終端記号にマッチしたときに返す型を`Expression*`にする．

```csua.y
%{
#include <stdio.h>
#define YYDEBUG 1
#include "csua.h"    // Expressionのために追加
%}
%union{
    int iv;
    double dv;
    char *name;
    Expression* expression; // 追加
}
(略)
// 追加
%type <expression> expression assignment_expression logical_or_expression
                 logical_and_expression equality_expression relational_expression
                 additive_expression multiplicative_expression unary_expression
                 postfix_expression primary_expression

```
yaccでは，非終端記号の返す型を変更するため(デフォルトは`int`)，以下の構文を利用する．

```
%type <unionに定義した形の変数名> 非終端記号の集合
```
ここでは，`union`に`Expression*`の型の変数`expression`を定義したため，

```
%type <expression> expression....
```
のようにした．

こうした上で，`statement`, `primary_expression`のアクションを変更する．

```csua.y
statement
	: expression SEMICOLON 
        {
          CS_Compiler* compiler = cs_get_current_compiler();
          compiler->expr_list = cs_chain_expression_list(compiler->expr_list, $1); // 受け取ったExpressionをつなぐ
        }
	;
(略)
primary_expression
	| TRUE_T      { printf("TRUE_T\n"); $$ = cs_create_boolean_expression(CS_TRUE);}
	| FALSE_T     { printf("FALSE_T\n"); $$ = cs_create_boolean_expression(CS_FALSE);}
```

yaccでは，各アクションで返す値がある場合，`$$`を利用する．よって，ここでは`TRUE_T/FALSE_T`にマッチしたときに`Expression*`を返すようにし，`statement`で`CS_Compiler`の`ExpressionList`につないでいる．

こうした上で，以下のテストプログラムを書いて動作を確認する．

```c:asttest.c
#include <stdio.h>
#include <stdlib.h>
#include "csua.h"

#include "../memory/MEM.h"
int main(void) {
    
    FILE *fin = fopen("tests/prog1.cs", "r");
    CS_Compiler* compiler = CS_create_compiler();  // CS_Compilerの生成
    CS_compile(compiler, fin);                     // コンパイルの実行．今はASTの作成
    
    printf("--------------\n");
    ExpressionList* expr_list = compiler->expr_list;   // ExpressionListを受け取る．
    while(expr_list) {
        printf("kind = %d\n", expr_list->expression->kind); // Expressionごとのkindを表示する．
        expr_list = expr_list->next;
    }
    
    fclose(fin);
    CS_delete_compiler(compiler);
    MEM_dump_memory();
    return 0;
}
```
このテストで実行するプログラムは以下の通り．

```c:tests/prog1.cs
true;
false;
true + false;
```
実行すると以下の結果を得る．

```
>./astt
TRUE_T
type = 1
FALSE_T
type = 1
TRUE_T
FALSE_T
add
type = 13
--------------
kind = 1
kind = 1
kind = 13
no allocated memory
```
kindが1, 1, 13と出ており，BOOLEAN_EXPRESSION, ADD_EXPRESSIONが生成されていることがわかる．

ここまでの動作確認は，以下のコマンドで確認できる

```
>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch begin_ast origin/begin_ast
>git checkout begin_ast
>make
>./comp/astt
```

さらに，すべての`Expression`に対応したブランチ

```
>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch ast_for_expr origin/ast_for_expr
>git checkout ast_for_expr
>make
>cd comp
>./astt
```
[目次](https://qiita.com/hiro4669/items/563466ccce42eb8342b9)に戻る