The Abstract Syntax Tree — AST 설계와 구축

📌단원 개요

Chapter 5의 단순한 expression AST를 넘어, 실제 언어(B-Minor) 전체를 표현하는 abstract syntax tree(AST)를 5개의 C structure로 정의한다. 이 AST는 semantic analysis의 출발점이다.

AST를 구성하는 5개의 C structure

6.1Overview

AST는 프로그램의 구조를 표현하는 internal data structure이며, parsing의 구체적 형식은 버린다.

6.2Declarations

완전한 B-Minor program은 declaration의 sequence다. 각 declaration은 variable 또는 function의 존재를 명시한다.

유효한 declaration 예시

b: boolean;
s: string = "hello";
f: function integer ( x: integer ) = { return x*x; }

struct decl

struct decl {
    char *name;
    struct type *type;
    struct expr *value;   // expression일 때
    struct stmt *code;    // function일 때
    struct decl *next;
};

struct decl * decl_create(
    char *name,
    struct type *type,
    struct expr *value,
    struct stmt *code,
    struct decl *next )
{
    struct decl *d = malloc(sizeof(*d));
    d->name  = name;
    d->type  = type;
    d->value = value;
    d->code  = code;
    d->next  = next;
    return d;
}

6.3Statements

function의 body는 statement의 sequence다. statement는 지정된 순서대로 특정 action(값 계산, loop, 분기 선택 등)을 수행하라는 지시이며, local variable의 declaration일 수도 있다.

struct stmt 와 stmt_t

struct stmt {
    stmt_t kind;
    struct decl *decl;
    struct expr *init_expr;
    struct expr *expr;
    struct expr *next_expr;
    struct stmt *body;
    struct stmt *else_body;
    struct stmt *next;
};

typedef enum {
    STMT_DECL,
    STMT_EXPR,
    STMT_IF_ELSE,
    STMT_FOR,
    STMT_PRINT,
    STMT_RETURN,
    STMT_BLOCK
} stmt_t;

kind 별로 사용하는 field

factory function

struct stmt * stmt_create( stmt_t kind,
    struct decl *decl, struct expr *init_expr,
    struct expr *expr, struct expr *next_expr,
    struct stmt *body, struct stmt *else_body,
    struct stmt *next );

6.4Expressions

Chapter 5의 단순 expression AST와 거의 같지만, 언어의 모든 operator(arithmetic, logical, comparison, assignment 등)에 대한 binary type과, 모든 leaf value(variable name, constant value 등)에 대한 type이 추가로 필요하다.

struct expr 와 expr_t

struct expr {
    expr_t kind;
    struct expr *left;
    struct expr *right;

    const char *name;
    int integer_value;
    const char *string_literal;
};

typedef enum {
    EXPR_ADD,
    EXPR_SUB,
    EXPR_MUL,
    EXPR_DIV,
    ...
    EXPR_NAME,
    EXPR_INTEGER_LITERAL,
    EXPR_STRING_LITERAL
} expr_t;

• name field는 EXPR_NAME에, integer_value field는 EXPR_INTEGER_LITERAL에 설정된다.
• integer, boolean, character literal 값은 모두 integer_value field에 저장할 수 있다.

factory functions

// binary operator용
struct expr * expr_create( expr_t kind,
                           struct expr *L,
                           struct expr *R );

// 각 leaf type용
struct expr * expr_create_name( const char *name );
struct expr * expr_create_integer_literal( int i );
struct expr * expr_create_boolean_literal( int b );
struct expr * expr_create_char_literal( char c );
struct expr * expr_create_string_literal( const char *str );

특별히 주의할 4가지 case

f(a,b,c) 의 AST — EXPR_CALL + EXPR_ARG의 unbalanced tree

6.5Types

struct type은 declaration에 등장하는 모든 variable과 function의 type을 인코딩한다. primitive type은 kind만 설정하면 되고, compound type은 여러 type structure를 연결해 만든다.

struct type / param_list / type_t

typedef enum {
    TYPE_VOID,
    TYPE_BOOLEAN,
    TYPE_CHARACTER,
    TYPE_INTEGER,
    TYPE_STRING,
    TYPE_ARRAY,
    TYPE_FUNCTION
} type_t;

struct type {
    type_t kind;
    struct type *subtype;
    struct param_list *params;
};

struct param_list {
    char *name;
    struct type *type;
    struct param_list *next;
};

compound type 구성

a: array [10] function integer ( x: integer );       // function 10개의 array
f: function function integer (x:integer) (y:integer); // function을 반환하는 function
g: function array [10]
       function integer (x:integer) (y:integer);     // function array를 반환하는 function

6.6Putting it All Together

개별 구성요소를 모두 봤으니, 완전한 B-Minor function 하나가 AST로 어떻게 표현되는지 본다.

예제 function

compute: function integer ( x:integer ) = {
        i: integer;
        total: integer = 0;
        for(i=0;i<10;i++) {
                total = total + i;
        }
        return total;
}

개략 구조 (statement chain)

6.7Building the AST

원칙적으로 nested function call로 AST를 손으로 만들 수도 있지만 현실적이지 않다. 대신 Bison(LR parser generator)이 rule reduce 시마다 creation function을 호출해 tree를 자동으로 엮게 한다.

손으로 만들기 (비현실적인 예) — square(x)=x*x

d = decl_create(
   "square",
   type_create(TYPE_FUNCTION,
       type_create(TYPE_INTEGER,0,0),
       param_list_create(
           "x",
           type_create(TYPE_INTEGER,0,0),
           0)),
   0,
   stmt_create(STMT_RETURN,0,0,
       expr_create(EXPR_MUL,
           expr_create_name("x"),
           expr_create_name("x")),
       0,0,0,0),
   0);

분명히 이렇게 코드를 쓸 수는 없다 → parser가 reduce될 때마다 creation function을 호출하게 한다.

Bison grammar에 action 심기

최상위: program은 declaration의 sequence

program : decl_list
          { parser_result = $1; }
        ;

declaration rule

decl : name TOKEN_COLON type TOKEN_SEMI
     { $$ = decl_create($1,$3,0,0,0); }
   | name TOKEN_COLON type TOKEN_ASSIGN expr TOKEN_SEMI
     { $$ = decl_create($1,$3,$5,0,0); }
   | /* and more cases here */
       . . .
   ;

decl_list: right-recursive로 linked list 구성

decl_list : decl decl_list
            { $$ = $1; $1->next = $2; }
          | /* epsilon */
            { $$ = 0; }
          ;

statement rule

stmt : TOKEN_IF TOKEN_LPAREN expr TOKEN_RPAREN stmt
       { $$ = stmt_create(STMT_IF_ELSE,0,0,$3,0,$5,0,0); }
     | TOKEN_LBRACE stmt_list TOKEN_RBRACE
       { $$ = stmt_create(STMT_BLOCK,0,0,0,0,$2,0,0); }
     | /* and more cases here */
       . . .
     ;

%union {
           struct decl *decl;
           struct stmt *stmt;
           . . .
           char *name;
};

%type <decl> program decl_list decl . . .
%type <stmt> stmt_list stmt . . .
. . .
%type <name> name

6.8Exercises (연습문제)

⭐핵심 정리 / 시험 포인트

📋한눈에 보기 — Cheat Sheet