streem language tag 201506 analysis
Goal Analysis
- yacc으로 인한 AST의 변환 가정 분석
- parse.y에서 함수 호출이나 if구조 분석 그리고 Action부분 분석
- AST를 실행하는 부분 분석
Start!
if(3>5){
//
}
else{
//
}
위와 같은 코드가 있을 경우 토큰부터 실행까지 분석하기
lex.l
(([1-9][0-9]*)|0) {
lval->nd = node_int_new(atol(yytext));
LEX_RETURN(lit_number);
};해당 정수 토큰이 발견될 경우 node_double_new 함수를 호출하여 토큰값 yytext를 node_int_new함수의 인자로 전달
if{TRAIL} LEX_RETURN(keyword_if);
{TRAIL}else{TRAIL} LEX_RETURN(keyword_else);
">"{TRAIL} LEX_RETURN(op_gt);if와 else, 연산자 토큰 처리
parse.y
%%
program : compstmt
{
p->lval = $1; //노드 최상위 포인터
}
;
compstmt : stmts opt_terms
;
stmts :
{
$$ = node_stmts_new();
}
이 파서는 Bottom-Up Parser이기 때문에 제일 처음에 이것을 수행하는것이 아닌 제일 최상위 논터미널로 reduce되었을 때 p→lval = $1을 하게 된다. 즉, compstmt($1)는 아래의 규칙들이 만들어진 최상의 노드의 포인터를 가지게 된다.
아 중요한것은 노드의 최상위 주소는 $$ = node_stmts_new()의 노드의 주소를 가지게된다.
node.h
typedef struct parser_state {
int nerr;
void *lval;
const char *fname;
int lineno;
int tline;
/* TODO: should be separated as another context structure */
node_ctx ctx;
} parser_state;
node.c
int node_parse_init(parser_state *p)
{
p->nerr = 0;
p->lval = NULL;
p->fname = NULL;
p->lineno = 1;
p->tline = 1;
p->ctx.exc = NULL;
return 0;
}
int node_parse_file(parser_state* p, const char* fname)
{
int r;
FILE* fp = fopen(fname, "rb");
if (fp == NULL) {
perror("fopen");
return 1;
}
r = node_parse_input(p, fp, fname);
fclose(fp);
return r;
}
int node_parse_input(parser_state* p, FILE *f, const char *fname)
{
int n;
/* yydebug = 1; */
yyrestart(f);
n = yyparse(p);
if (n == 0 && p->nerr == 0) {
return 0;
}
return 1;
}parser_state 구조체를 초기화하고 node_parser_input함수에 파일네임과 파일포인터, parser_state 구조체 포인터를 넘긴다. 그리고 yyparser()함수를 호출하여 파싱을 시작한다.
node.h
typedef struct {
NODE_HEADER;
node_value value;
} node
typedef struct {
NODE_HEADER;
int len;
int max;
void** data;
} node_values;p→lval에서 lval — node* 형으로 캐스팅된다. 즉 노드로 변경된다.
main.c
case NODE_STMTS:
printf("STMTS:\n");
{
node_values* arr0 = (node_values*)np;
for (i = 0; i < arr0->len; i++)
dump_node(arr0->data[i], indent+1);
}
break;처음시작시 최초의 AST node pointer는 NODE_STMTS tag를 가리키게 된다. 그리고 그 해당 np는
node_values 포인터로 캐스팅된다. 그리고 data[i]에는 각 각의 개별 AST들이 담겨져 있다.
그리고 담겨져 있는 AST를 실행하기 위해 dump_node라는 함수를 재귀적으로 호출하고 있다.
node*
node_values_new(node_type type) {
/* TODO: error check */
node_values* v = malloc(sizeof(node_values));
v->type = type;
v->len = 0;
v->max = 0;
v->data = NULL;
return (node*)v;
}
void
node_values_add(node_values* v, void* data) {
if (v->len == v->max) {
v->max = v->len + 10;
v->data = realloc(v->data, sizeof(void*) * v->max);
}
/* TODO: error check */
v->data[v->len] = data;
v->len++;
}
--------------------------------------------------------------
stmts :
{
$$ = node_stmts_new();
}
| stmt
{
$$ = node_stmts_new();
node_stmts_add($$, $1);
}
| stmts terms stmt
{
$$ = $1;
node_stmts_add($1, $3);
}위의 코드는
Context Free Grammar의 Action을 바타으로 추상 구문 트리를 추가하는 부분이다.
만약 파싱하려는 구문이
if(3>4){
} else { } 위와 같다면 이를 파싱하는 Context Free Grammar은 아래와 같다.
primary0 : keyword_if condition '{' compstmt '}' opt_else
{
$$ = node_if_new($2, $4, $6);
}라는 Context Free grammar에 따라 node_if_new함수를 호출하고 AST를 만들어 낸다.
아 그리고 중요한것은 bison(yacc)파서는 Bottom-Up Parsing이다.(토큰으로부터 최상위 논터미널로 유도하는 것) 즉, 토큰쪽으로 부터 최상위 논터미널까지의 AST를 만든다. 만들어 낼때는 해당하는 ACtion을 통해 함수를 호출하여 만들어낸다
node* node_if_new(node* cond, node* then, node* opt_else)
{
node_if* nif = malloc(sizeof(node_if));
nif->type = NODE_IF;
nif->cond = cond;
nif->then = then;
nif->opt_else = opt_else;
return (node*)nif;
}
이것은 keyword_if에 대한 action 함수인데 이런식으로 cond와 then을 넣는데 이는 이미 만들어진 노드의 주소이다. 그리고 NODE_IF라는 플래그를 설정하고 해당 노드를 return하는데 이는 나중에 만들어질 더 상위의 노드를 연결하기 위함이다.
이런식으로 만들어진 node들은 exec.c 파일의 exec_expr함수를 통해 tag에 따라 exec_call함수를 호출하여 해당 구문들을 실제로 실행한다.
exec.c exec_expr
case NODE_IF:
{
strm_value v;
node_if* nif = (node_if*)np;
n = exec_expr(ctx, nif->cond, &v);
if (n) return n; //조건부 판단이 실패 한것이다.
if (strm_value_bool(v)) { //contidion에 따른 true or false를 따른다.
return exec_expr(ctx, nif->then, val);
}
else if (nif->opt_else != NULL) { //else if 실행
return exec_expr(ctx, nif->opt_else, val);
}
else {
*val = strm_nil_value();
return 0;
}
}
break;예시로 위에 제시된 if구조의 코드를 실행한다고 했을때 case NODE_IF부분이 실행된다.
if문의 구조는 if condition {} else {} 이기 떄문에 condition이라는 구문을 판단해야한다. 그래서 exec_expr 함수를 재귀적으로 호출하여 다시한번 판단한다. 그리고 판단이 끝난후 &v에는 true and false의 값이 들어가는데 이를 바탕으로 strm_value_bool함수를 호출하여 조건의 참 유무를 판단한다. 그리고 이 결과에 따라 어떤 구문이 실행되게 할지 고른다.
한번더 3+4라는 구문이 있을때는
case NODE_OP:
{
node_op* nop = (node_op*)np;
strm_value args[2];
int i=0;
if (nop->lhs) {
n = exec_expr(ctx, nop->lhs, &args[i++]); //args에 lhs, rhs의 값이 들어감
if (n) return n; //정의 되지 않은값
}
if (nop->rhs) {
n = exec_expr(ctx, nop->rhs, &args[i++]);
if (n) return n; //정의 되지 않은값
}
return exec_call(ctx, nop->op, i, args, val); //args와 val에는 연산의 결과값을 담는다.
}
break;위의 코드가 실행되게 되는데
3 + 4에 대한 노드를 다실행해야하기 떄문에 또한번 재귀적으로 함수를 호출한다.
그럼 3에 해당하는 노드를 인자로 넣고 호출하는데 이는 NODE_VALUE이기 때문에 더이상 함수가 호출되지 않고 return 0한다. 그전에 &args[i++]를 인자로 넣었는데 이는 해당 value를 넣기 위함이다.
그리고 좌변과 마찬가지로 우변도 하고 나선 이 구문을 실행한다. 이 실행할 떄는 exec_call함수를 호출한다.
호출할 떄 args, val를 같은 값을 호출하는 것 처럼 보이지만 val은 해당 구문이 실행하고 나서의 결과값을 담는다.
지금까지 streem lanuage tag 201506 버전의 Core부분을 분석한것이다. 개어렵다. 하지만 어떤식으로 AST를 만들어야하고 Context Free Grammar의 식을 만들어 내야할지는 어느정도 감이 잡힌다.