Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@hiro4669

意味解析

Last updated at Posted at 2018-12-05

概要

式の構文解析，AST作成ができたので，次は作成したASTを使って意味解析をしていく．意味解析では，

  • 変数や関数宣言の登録
  • 式の型を確定
  • キャストの追加

を行う．現在は式しかASTを作れていないので，式文，宣言文を文法に追加し，そのAST作成から始める．

準備

式文，宣言文を追加し，ASTを作るためには，以下を実行する

  1. 構文の追加
  2. Statement，Declaration構造体の追加
  3. Visitor/Traversorの追加や変更．

構文の追加

translation_unit
        : definition_or_statement  
        | translation_unit definition_or_statement 
	;
definition_or_statement
        : function_definition
        | statement  
        ;

function_definition
        : type_specifier IDENTIFIER LP RP SEMICOLON
        ;

statement
	: expression SEMICOLON 
        | declaration_statement
	;
        
declaration_statement
        : type_specifier IDENTIFIER SEMICOLON 
        | type_specifier IDENTIFIER ASSIGN_T expression SEMICOLON 
        ;

これまで，

translation_unit
        : statement_list
        ;
statement_list
        : statement
        : statement_list statement
        ;

としていたところを，変更した．これまで，expression SEMICOLONのアクションでCompilerに式をつないでいたが，今後はdefinition_or_statementのstatementのところで文(Statement)をつなぐようにする．

definition_or_statement
        : function_definition
        | statement  // ここ

式の要素を追加

csua.h

typedef struct {
    char          *name;
    TypeSpecifier *type;
    Expression    *initializer;
    int           index;    
} Declaration;

typedef enum {
    EXPRESSION_STATEMENT = 1,
    DECLARATION_STATEMENT,
    STATEMENT_TYPE_COUNT_PLUS_ONE
} StatementType;

struct Statement_tag {
    StatementType type;
    int           line_number;
    union {
        Expression   *expression_s;
        Declaration  *declaration_s;
    }u;
};

typedef struct StatementList_tag {
    Statement *stmt;
    struct StatementList_tag *next;
} StatementList;

これらの変更を加え，以下のテストプログラムのASTを作成してみる．

tests/prog1.cs
int i;
int j = 1;
a = 2;
print();

このASTをVisitorで表示した結果，以下を得る

enter declstmt name=i, type=1:
leave declstmt
enter declstmt name=j, type=1:
　enter intexpr : 1
　leave intexpr
leave declstmt
enter exprstmt :
　enter assignexpr : 1 
　　enter identifierexpr : a
　　leave identifierexpr
　　enter intexpr : 2
　　leave intexpr
　leave assignexpr
leave exprstmt
type = 1
enter exprstmt :
　enter function call :
　　enter identifierexpr : print
　　leave identifierexpr
　leave function call
leave exprstmt
no allocated memory

ASTになっていることが確認できる．

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

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

変数の登録と型の確定

すべての式(Expression)に対して型を付けていく．様々な式を定義しているが，ここでは以下のプログラムを考え，この時どのように型を確定させるかを考える．

int a; //(1)
a = 1; //(2)

(1)
これは宣言文で，文法的には

declaration_statement: type_specifier IDENTIFIER SEMICOLON

であり，type_specifierでaという識別子はintであることが確定する．この，"aがint型である"ということは，識別子"a"を用いた式の型を確定する時に使用する(例えば(2)のような式文)．なお，宣言文は"文"であり"式"はない．

(2)
左辺の"a"をみたとき，識別子なのでその前に定義されているはずである．そこで，(1)で得た情報を利用する．その結果，"a"は"int"型であることがわかる．次に，右辺の"1"を見ると，これは明らかに"int"型である．そのため，(2)の代入式全体の型は"int"型となる．

これをどのようにプログラムで実現するかを考えていく．プログラムは既にASTになっているので，それをVisitorで深さ優先探索で操作していく．そして，宣言文を発見したら，宣言文を記憶しておく(Listでつないでおく)．
次に代入文では，下図のようにしてVisitorはノードを操作していく．

1.png

まず，(p)で"a"ノードを訪問したときには何もしない．"a"ノードは子ノードを持たないので，(q)Visitorは親ノードに戻ろうとする．その時，"a"の型が何なのかを記憶しておいた宣言文を利用して型を確定させる(int確定)．
次に，(r)右辺のノードを訪問する．その時は何もせず，(s)親に戻る時に"1"が整数なので，int型確定とする．最後にVisitorが親に戻った時，左辺の型と右辺の型を比較し，同じであればこの代入式全体の型を左辺の型と同じくする(右辺でないのは，後述する型変換が必要な場合，右辺の型が変わるから)．

このようにASTを操作する時，ノードを戻りがけに型を確定させる処理を繰り返すことで，全部の式に型づけ可能である．

キャストノードの追加

式の型を確定していく時，変換可能ならば変更できるのが普通の言語仕様である．そこで，その仕組を導入する．具体的には，

int a;
a = 1.1;

このようなプログラムを実行した時"a"には"1"が入ってほしい．これを実現するため，型を確定させるときに値の変換が可能な肩同士であれば，ASTの形を変えキャストノードを追加する．具体的には次のように変形する．

2.png

この変形は，先の例で(s)の時に実行する．先の例では，左右のノードの型が同じならば左辺の型を式全体の型としていた．そこで，もし左右の型が違っており，かつ変換可能(int->double, double->int)ならば，変換を行う意味を表すキャストノードを生成し，右辺のノードをつないだ後，親ノードはこのキャストノードにつなぎ変える．こうすることで，コード生成の時に変換する命令を生成できる．

実装の変更

意味解析を実装してみる．追加するのは，

  • 宣言文を保持するためのリスト(DeclarationList)
  • 意味解析をするVisitor
  • キャスト式
  • その他便利関数(e.g., 識別子の検索など)

まず，csua.hにリストやキャスト式を追加する．

csua.h

// 変換のタイプを表す
typedef enum {
    CS_INT_TO_DOUBLE = 1,
    CS_DOUBLE_TO_INT,               
} CS_CastType;

typedef enum {
    BOOLEAN_EXPRESSION = 1,
    (略)
    CAST_EXPRESSION,　　　　　 // 追加
    EXPRESSION_KIND_PLUS_ONE
} ExpressionKind;

// キャスト式．変換タイプキャスト対象の式をつなぐメンバを持つ
typedef struct {
    CS_CastType ctype;
    Expression* expr;    
} CastExpression;

struct Expression_tag {
    ExpressionKind kind;
    TypeSpecifier* type; 
    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;
        CastExpression         cast_expression; // 追加
    } u;
};

// 宣言文を保持するリスト
typedef struct DeclarationList_tag {
    Declaration* decl;
    struct DeclarationList_tag *next;
} DeclarationList;

struct CS_Compiler_tag {
    MEM_Storage      storage;
    ExpressionList  *expr_list; 
    StatementList   *stmt_list;
    DeclarationList *decl_list; // 追加
};

宣言文で宣言された変数は，本来スコープがあり，そのスコープ単位で保持されるべきだが，今の段階ではスコープを表すブロックが存在しないので，すべてグローバルで管理する．そのため，DeclarationListはCS_Compilerに持たせる．

続いて，意味解析を行うMeanVisitorを追加する

visitor.h

struct MeanVisitor_tag {
    Visitor visitor;   // 従来のVisitorを継承
    CS_Compiler *compiler;
};

MeanVisitorは，従来のVisitorを継承する形で定義する．というのも，MeanVisitorは，ASTを操作していく時に何らのデータを保持する可能性があり，そうすると構造体の中にデータを定義しておいたほうが良い．しかし，enter/leaveする関数を保持するポインタは再定義せず，従来のものを使いまわしたい．なおかつ，traversorはVisitorのポインタを受け取ることを前提に書いている．という理由からである．
今回は，とりあえず宣言文をCS_Compilerで保持することにしているので，そのポインタを内部に持つ．

meanvisitor.c

MeanVisitor* create_mean_visitor() {
    visit_expr* enter_expr_list;
    visit_expr* leave_expr_list;
    visit_stmt* enter_stmt_list;
    visit_stmt* leave_stmt_list;

    MeanVisitor* visitor = MEM_malloc(sizeof(MeanVisitor));
    visitor->compiler = cs_get_current_compiler();
    if (visitor->compiler == NULL) {
        fprintf(stderr, "Compile is NULL\n");
        exit(1);
    }
    (略)
　　　// 親にキャストしてセットする．
　　 ((Visitor*)visitor)->enter_expr_list = enter_expr_list;　
    ((Visitor*)visitor)->leave_expr_list = leave_expr_list;
    ((Visitor*)visitor)->enter_stmt_list = enter_stmt_list;
    ((Visitor*)visitor)->leave_stmt_list = leave_stmt_list;
}
(略)
// 型のチェックとキャストノードの追加
static Expression* cast_type(TypeSpecifier* ltype, Expression* expr) {
    
　　// 左右の型が同じなら右辺をそのまま返す
    if (ltype->basic_type == expr->type->basic_type) {
        return expr;
    } else if ((ltype->basic_type == CS_INT_TYPE) && (expr->type->basic_type == CS_DOUBLE_TYPE) ) {
        // int = doubleなら，右辺をintに変換するキャストノードを生成し，右辺をつないで返す．
        Expression* cast = cs_create_cast_expression(CS_DOUBLE_TO_INT, expr);
        cast->type = cs_create_type_specifier(CS_INT_TYPE);
        return cast;
    } else if ((ltype->basic_type == CS_DOUBLE_TYPE) && (expr->type->basic_type == CS_INT_TYPE) ) {
　　　　　// double = intなら，右辺をdoubleに変換するキャストノードを生成し，右辺をつないで返す．
        Expression* cast = cs_create_cast_expression(CS_INT_TO_DOUBLE, expr);
        cast->type = cs_create_type_specifier(CS_DOUBLE_TYPE);        
        return cast;
    } else {
        // それ以外は型エラー
        fprintf(stderr, "Type Error\n");
        exit(1);
    }
    return expr;
}

(略)
static void leave_assignexpr(Expression* expr, Visitor* visitor) {   
    Expression* left  = expr->u.assignment_expression.left;
    Expression* right = expr->u.assignment_expression.right;
     
    // この関数が呼ばれた時点で，深さ優先探索の結果，子ノードの型は確定している
    // cast_typeの返り値をrightに代入することで，繋ぎ変えを実行する．
    expr->u.assignment_expression.right = cast_type(left->type, right);
}

// 宣言文を見つけたら，宣言を保持する
static void enter_declstmt(Statement* stmt, Visitor* visitor) {
    CS_Compiler* compiler = ((MeanVisitor*)visitor)->compiler;
    compiler->decl_list = cs_chain_declaration(compiler->decl_list, stmt->u.declaration_s);
    fprintf(stderr, "enter declstmt\n");    
    
}

// 宣言に初期値(を表す式)があったら，キャストの可能性を考える．
static void leave_declstmt(Statement* stmt, Visitor* visitor) {
    fprintf(stderr, "leave declstmt\n");
    Declaration* decl = stmt->u.declaration_s;
    if (decl->initializer != NULL) {
        decl->initializer = cast_type(decl->type, decl->initializer);
    }
}

このような実装を加えた後，以下のプログラムで意味解析を実行し，最後にASTを表示してみる．

boolean i;
double k;
int j = 1;
j = 2.1;

その結果，以下を得る．

enter declstmt name=i, type=0:
leave declstmt
enter declstmt name=k, type=2:
leave declstmt
enter declstmt name=j, type=1:
  enter intexpr : 1
  leave intexpr
leave declstmt
enter exprstmt :
  enter assignexpr : 1 
    enter identifierexpr : j
    leave identifierexpr
    enter castexpr : 2  //  キャストノードが追加されている
      enter doubleexpr : 2.100000
      leave doubleexpr
    leave castexpr
  leave assignexpr
leave exprstmt

このように，キャストノードが追加されていることがわかる．

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

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

他の式の意味解析方針

他の式の意味解析での型チェックの方針は以下の通り．

  • inc_dec_expression: インクリメント/デクリメントを受け付けるのはINT型だけなので，INT型以外はエラーにする．
  • function_call_expression: 関数呼び出し式は，関数の返り値型とする．
  • minux_expression: INT型もしくはDOUBLE型を受け付ける．それ以外はエラー．
  • logical_not_expression: BOOLEAN型を受け付ける．それ以外はエラー
  • binary_expression: 二項演算は演算子の種類に応じて対応が異なる．
    • add, sub, mul, div, modの算術演算子は，両辺が計算できるINT型またはDOUBLE型である必要がある．型があっていない場合にはDOUBLEに合わせる(キャストを挟む)．計算できない方を含む場合にはエラーとする．

    • < >= <=は，BOOLEAN以外の両辺が比較できる型じゃない場合エラーとする．型があっていない場合には合わせる．

    • ==, !=は，BOOLEANを含む両辺が比較できる方の場合にはOK．それ以外はエラーとする
    • &&, || は両辺がBOOLEAN型のみ許容する．それ以外はエラー．

この方針に基づいて実装し，なおかつエラーがあっても最後まで意味解析を続けるように(エラーを見つけたら即座にexitしない)実装した．わざと間違いのあるプログラムを用意し，意味解析してみた．

tests/prog2.cs(間違いのあるプログラム)
int print();
int i;
int j;
boolean t;
t = true;
i = true;
i = false;

i - t;
i != t;
t && 1;
t++;
-t;
!i;
t = print();

これを意味解析まで実行する

>./meant ./tests/prog2.cs
6: assignment type error int = boolean
7: assignment type error int = boolean
9: type mismatch in arithmetic binary expression left:int, right:boolean
10: type mismatch in equality binary expression left:int, right:boolean
11: && or || accept only boolean left:boolean, right:int
12: Operand is not INT type (boolean)
13: Operand is not INT or DOUBLE type (boolean)
14: Operand is not BOOLEAN type (int)
15: assignment type error boolean = int

6, 7行目：intの変数にbooleanを代入している．
9行目：intとbooleanで算術演算しようとしている．
10行目：intとbooleanを同値判定している．
11行目：booleanとintを論理演算しようとしている
12行目：intでない型をインクリメントしている
13行目：booleanにマイナス演算しようとしている
14行目：intを論理否定しようとしえいっる
15行目：intを返す関数呼び出しを実行し，boolean型の変数に入れようとしている．

正しくエラーを出しているように見える．
次に，正しいプログラムを実行してみる

tests/prog3.cs
int print();
int i;
int j;
boolean t;
boolean f;
double d;
t = true;
f = false;
i = 10;
j = 20;
d = 10.0;

i = d + 1;
i != d;
t && f;
i++;
-d;
!f;
i = print();

実行する

>./meant ./tests/prog3.cs
(略)
enter exprstmt :
  enter assignexpr : 1 
    enter identifierexpr : i
    leave identifierexpr(type:int)
    enter castexpr : 2   // iにdoubleの計算結果を合わせるためのキャストノード
      enter addexpr : +
        enter identifierexpr : d
        leave identifierexpr(type:double)
        enter castexpr : 1    // d+1の右辺をdouble型にするためのキャスト
          enter intexpr : 1
          leave intexpr(type:int)
        leave castexpr(type:double)
      leave addexpr(type:double)
    leave castexpr(type:int)
  leave assignexpr(type:int)
leave exprstmt
(略)

正しく実行すると，ASTを表示する．そして例えば

d = 10;
i = d + 1;

のASTをみると，d+1は型が違うので右辺の1のところにcastノードが追加され，計算結果がdoubleになり，int型の変数iに代入されるところでさらにintにキャストするためのノードが追加されていることがわかる．
というわけで，意味解析までうまく動いていそう．

ここまでの実装は，以下のコマンドで確認できる．

>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch finish_mean_analysis origin/finish_mean_analysis
>git checkout finish_mean_analysis
>make
>cd comp
>./meant ./tests/prog2.cs
>./meant ./tests/prog3.cs

目次に戻る

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?