tiny C の構文解析

前に解説したデータ構造を使って、parserを作る。 構文解析に関連するのは、以下の２つのファイルである。

• clex.c: 字句解析部分
• cparser.y : parserのyaccプログラム

字句解析のプログラム： yylex (clex.c)

int yylex() { int c,n; char *p; again: c = getChar(); if(isspace(c)) goto again; switch(c){ case '+': case '-': case '*': case '>': case '<': case '(': case ')': case '{': case '}': case ']': case '[': case ';': case ',': case '=': case EOF: return c; case '"': p = yytext; while((c = getChar()) != '"'){ *p++ = c; } *p = '\0'; yylval.val = makeNum((int)strdup(yytext)); return STRING; } if(isdigit(c)){ n = 0; do { n = n*10 + c - '0'; c = getChar(); } while(isdigit(c)); ungetChar(c); yylval.val = makeNum(n); return NUMBER; } if(isalpha(c)){ p = yytext; do { *p++ = c; c = getChar(); } while(isalpha(c)); *p = '\0'; ungetChar(c); if(strcmp(yytext,"var") == 0) return VAR; else if(strcmp(yytext,"if") == 0) return IF; else if(strcmp(yytext,"else") == 0) return ELSE; else if(strcmp(yytext,"return") == 0) return RETURN; else if(strcmp(yytext,"while") == 0) return WHILE; else if(strcmp(yytext,"for") == 0) return FOR; else if(strcmp(yytext,"println") == 0) return PRINTLN; else { yylval.val = makeSymbol(yytext); return SYMBOL; } } fprintf(stderr,"bad char '%c'\n",c); exit(1); }

• 入力から、文字を読み込み、空白(isspace)ならば、読み飛ばす。
• 次のswitch文では、１文字の終端記号を読み込む。
• もしも、'"'ならば、 文字列定数を読み込み、STRINGを返す。意味値としては、読み込んだ文字列を セーブして(strdup)、そのアドレスをNUMのASTノードとして返す。
• もしも、数字ならばそれに続く数を読み込み、NUMBERを返す。読み込ん だ数を十進数として解釈し、NUMのASTノードを意味値とする。
• もしも、英文字ならば、まず英文字の列を読み込み、それをyytextにい れる。次に、それがキーワードならばキーワードに対応する終端記号を返す。 キーワードでなかったら、SYMを返し、意味値としてSYMのASTを作る。
• なお、このルーチンはcparser.yにincludeされて、コンパイルされる。 終端記号に使われる名前はcparser.yで自動的に生成されていることに注意。 getCharとungetCharは、デバック用のもので、getcとungetcに変えてもよい。

構文解析のプログラム : cparser.y

parserは、yaccで記述されている。部分部分に分けて解説する。

まずは、終端記号のtokenの定義を行う。1文字で表されるtokenはその文字自 体をつかってよい。例えば、+などの記号は、'+'と記述する。 tokenの定義は、%tokenで行う。

%token NUMBER %token SYMBOL %token STRING %token VAR %token IF %token ELSE %token RETURN %token WHILE %token FOR %token PRINTLN

次に、生成されたCプログラムの中で必要となるファイルのincludeを行う。 ここでは、stdio.hとAST.hをincludeする。

%{ #include <stdio.h> #include "AST.h" %}

意味値として返される値のデータ型を定義する。このプログラムでは、ASTを 意味値として返すために、ASTへのポインタを意味値の値としている。

%union { AST *val; }

%right '=' %left '<' '>' %left '+' '-' %left '*' %type <val> parameter_list block local_vars symbol_list %type <val> statements statement expr primary_expr arg_list %type <val> SYMBOL NUMBER STRING

%start program

構文の定義は%%で始める。どのような順番でもいいが、通常、top-downに 定義していく。programは空であるか(入力がなし)、もしくは外部定義の列 external_definitionsである。

%% program: /* empty */ | external_definitions ;

列の定義は以下のように定義する。left recursionに定義することに注意。

external_definitions: external_definition | external_definitions external_definition ;

外部定義external_definitionは、関数定義、大域変数の定義、もしくは配列 の定義である。

external_definition: SYMBOL parameter_list block /* fucntion definition */ { defineFunction(getSymbol($1),$2,$3); } | VAR SYMBOL ';' { declareVariable(getSymbol($2),NULL); } | VAR SYMBOL '=' expr ';' { declareVariable(getSymbol($2),$4); } | VAR SYMBOL '[' expr ']' ';' { declareArray(getSymbol($2),$4); } ;

• 関数定義の場合は

  void defineFunction(Symbol *fsym,AST *params,AST *body)

  fsymに関数名のシンボル、paramsにパラメータのAST、bodyに関数本体のASTを 与える。
• 大域変数の定義の場合

  void declareVariable(Symbol *vsym,AST *init_value);

  vsymに変数名のシンボル、init_valueに初期値のASTを与える。初期値がない 場合は、NULL
• 大域配列の定義の場合

  void declareArray(Symbol *asym,AST *size);

  asymに配列名のシンボル、sizeにサイズのASTを与える。

パラメータの並びの定義。パラメータは、シンボルの並びを'('と')'ではさん だもの。

parameter_list: '(' ')' { $$ = NULL; } | '(' symbol_list ')' { $$ = $2; } ; symbol_list: SYMBOL { $$ = makeList1($1); } | symbol_list ',' SYMBOL { $$ = addLast($1,$3); } ;

blockすなわち複文は、'{'ではじまり、'}'で終る。最初に局所変数の定義 local_varsがあり、文の並びが続くもの。複文を表すASTは、左に局所変数の リスト、右に文のリストをいれたものである。

block: '{' local_vars statements '}' { $$ = makeAST(BLOCK_STATEMENT,$2,$3); } ; statements: statement { $$ = makeList1($1); } | statements statement { $$ = addLast($1,$2); } ; local_vars: /* NULL */ { $$ = NULL; } | VAR symbol_list ';' { $$ = $2; } ;

以下が、文の定義である。それぞれの文に対応したASTを作り返す。

statement: expr ';' { $$ = $1; } | block { $$ = $1; } | IF '(' expr ')' statement { $$ = makeAST(IF_STATEMENT,$3,makeList2($5,NULL)); } | IF '(' expr ')' statement ELSE statement { $$ = makeAST(IF_STATEMENT,$3,makeList2($5,$7)); } | RETURN expr ';' { $$ = makeAST(RETURN_STATEMENT,$2,NULL); } | RETURN ';' { $$ = makeAST(RETURN_STATEMENT,NULL,NULL); } | WHILE '(' expr ')' statement { $$ = makeAST(WHILE_STATEMENT,$3,$5); } | FOR '(' expr ';' expr ';' expr ')' statement { $$ = makeAST(FOR_STATEMENT,makeList3($3,$5,$7),$9); } ;

• まず、式はそれ自身で文になる。だだし、文の終りを表す';'が必要
• もちろん、複文は文である。
• if文のASTは、左に条件式、右にthen部とelse部の2つのASTを持つリス トを持つASTである。elseがない場合にはNULLとする。
• RETURN文のASTは、右にリターン値の式をいれたASTである。ない場合は NULLとする。
• WHILE文のASTは、右に条件式、左の本体をいれたもの。
• FOR文のASTは、左に初期式、繰り返し条件式、繰り返し式の3つの要素を 持つAST、右に本体をいれたもの。

以下が、式の定義である。

expr: primary_expr | SYMBOL '=' expr { $$ = makeAST(EQ_OP,$1,$3); } | SYMBOL '[' expr ']' '=' expr { $$ = makeAST(SET_ARRAY_OP,makeList2($1,$3),$6); } | expr '+' expr { $$ = makeAST(PLUS_OP,$1,$3); } | expr '-' expr { $$ = makeAST(MINUS_OP,$1,$3); } | expr '*' expr { $$ = makeAST(MUL_OP,$1,$3); } | expr '<' expr { $$ = makeAST(LT_OP,$1,$3); } | expr '>' expr { $$ = makeAST(GT_OP,$1,$3); } ;

• primary_exprとは、以下に示すように変数や配列参照など。
• 2項演算の式については、左には左辺の式のAST、右には右辺の式のASTを いれたASTを作る。
• 代入については左には変数、右には代入する式のASTをいれたEQ_OPのAST を作る。
配列の代入の場合は、左に配列のシンボルとインデックスの式のリスト をいれたSET_ARRAY_OPのASTを作る。 なお、２項演算子の優先度については、最初に%right,%leftなどを使っ て定義してある。

次の定義が、primary_exprである。変数や定数の他に、配列要素の参照、関数 呼び出しが定義してある。関数呼び出しでは、左に関数名、右に引数のならび のリストを持つCALL_OPのASTノードを作る。唯一のシステム関数である printlnはここで定義してある。

primary_expr: SYMBOL | NUMBER | STRING | SYMBOL '[' expr ']' { $$ = makeAST(GET_ARRAY_OP,$1,$3); } | SYMBOL '(' arg_list ')' { $$ = makeAST(CALL_OP,$1,$3); } | PRINTLN '(' arg_list ')' { $$ = makeAST(PRINTLN_OP,$3,NULL); } ; arg_list: expr { $$ = makeList1($1); } | arg_list ',' expr { $$ = addLast($1,$3); } ;

最後に、%%で終る。そのあとは、任意のCのプログラムが書けるので、ここに lex.cをincludeする。このようにすることのメリットは、clex.cのなかで、 tokenの名前をマクロで定義されているものとして、使うことができる点であ る。

%% #include "clex.c"

yyerror

yaccで生成される構文解析ルーチンでは、エラーを起こした時に、つまり間違っ た構文が入力されたときに、yyerrorという関数が呼び出されるようになって いる。このプログラムでは、yyerrorは以下のように、メッセージをプリント してプログラムを停止する、簡単なものにしている。

void yyerror() { printf("syntax error!\n"); exit(1); }

構文解析のプログラムのコンパイル

cparser.yから、yaccを使ってparserを生成する。

% yacc cparser.y

% mv y.tab.c cparser.c % cc -c cparser.c