情報科学実験II　コンパイラ作成

第4回

課題4.4の結果を確認する方法

1. 4.4.4節で作成したpicoc2.yのルール部からlineの部分を削除する。4.4.5節、4.4.6節の内容にしたがって書き加えてpicoc.yとして保存する。programから始まる部分をルール部の先頭に書くか、あるいは、定義部の末尾辺りに、

   %start program
   

   を加える。これをしないと大量の警告が出されるだろう。このようにしてできたファイルを

   bison -t -d picoc.y
   

   で処理する。

   picoc.y: 警告: 1 shift/reduce conflict [-Wconflicts-sr]
   

   というエラーが出てもよい。ただし、shift/reduceの前の数が2以上だったら修正が必要である。
2. リスト4.4を補って以下のプログラムを作成し、ast.c, gen.c, printast.cならびにbisonが出力したpicoc.tab.cファイルとともにコンパイルする。ただし、main()関数内でelse genCode()を削除すれば、gen.cは不要。

   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   #include "ast.h"
   /* gen.hはなくてもよいかもしれない(皆さんの書き方に依存する) */
   #include "gen.h"
   /* bison -d -tが出力したヘッダーファイルをインクルードする */
   #include "picoc.tab.h"
   #include "printast.h"
   #if YYDEBUG
   extern int yydebug;
   #endif
   
   extern DefNodePtr sourcedefs;
   FILE  *af;
   
   typedef struct Tokens {
   	int sort;
   	int ival;
   	char *name;
   } Ttokens;
   
   #define T_T(t) { t, 0, NULL }
   #define T_INT(k) { NUM, k, NULL }
   #define T_ID(n) { ID, 0, n }
   #define T_CH(c) { c, 0, NULL }
   
   Ttokens thetokens[]={
   	T_T(TINT),T_ID("in"),T_CH('('),T_CH(')'),T_CH(';'),
   	T_T(TINT),T_ID("out"),T_CH('('),T_T(TINT),T_ID("x"),T_CH(')'),T_CH(';'),
   	T_T(TINT),T_ID("fib"),T_CH('('),T_T(TINT),T_ID("k"),T_CH(')'),T_CH('{'),
   	T_T(IF),T_CH('('),T_ID("k"),T_T(BLT),T_INT(2),T_CH(')'),T_CH('{'),T_T(RETURN),T_INT(1),T_CH(';'),T_CH('}'),
   	T_T(RETURN),T_ID("fib"),T_CH('('),T_ID("k"),T_T(SUB),T_INT(2),T_CH(')'),
   		T_T(ADD),T_ID("fib"),T_CH('('),T_ID("k"),T_T(SUB),T_INT(1),T_CH(')'),T_CH(';'),
   	T_CH('}'),
   	T_T(TINT),T_ID("main"),T_CH('('),T_CH(')'),T_CH('{'),
   	T_T(TINT),T_ID("v"),T_CH(';'),
   	T_ID("v"),T_T(ASSIGN),T_ID("in"),T_CH('('),T_CH(')'),T_CH(';'),
   	T_ID("out"),T_CH('('),T_ID("fib"),T_CH('('),T_ID("v"),T_CH(')'),T_CH(')'),T_CH(';'),
   	T_T(RETURN),T_INT(0),T_CH(';'),
   	T_CH('}'),
   	T_CH(0) };
   
   int yylex() {
   	static int i=0;
   
   	Ttokens *p = thetokens + i;
   	i++;
   	
   	if(p->sort ==NUM)
   		yylval.ival = p->ival;
   	else if(p->sort==ID)
   		yylval.name = p->name;
   	return p->sort;
   }
   /* もし、bisonへの入力ファイル、例えばpicoc.yでyyerror()の中身を定義していれば、
   multiple definition of `yyerror'などのコンパイルエラーが出る。その場合は
   ここでの定義は不要なので、mainの前までを削除する */
   int yyerror( char *msg ){
   	fprintf( stderr, msg );
   	exit( 1 );
   }
   
   int main( int argc, char **argv ){
   #if YYDEBUG
   int i;
   	for( i=1; i<argc; i++ ){
   		if( strcmp( argv[i], "-d" )==0 ) yydebug = 1;
   	}
   #endif
   	af = stdout;
   	/* 構文解析を実行 */
   	if( yyparse() ) return EXIT_FAILURE;
   	/* 結果を出力 */
   	if( argc > 1 ) printASTDef( argc, argv, sourcedefs );
   	else genCode();
   	return EXIT_SUCCESS;
   }
   

3. その結果できたファイル(この例ではkadai44と仮定する)を実行するときに、
   • オプションなしに「./kadai44」のように実行するとコンパイル結果が出力される。このプログラムをMarsで実行すると、入力した数に対するフィボナッチ数が出力されるはず。
   • -tオプションをつけて「./kadai44 -t」のように実行すると構文木をテキストで出力する。

     Prototype Func in
     Prototype Func out
     Func fib
       Stmt: if
         Op: <
           Op: var
             Sym param1 k
           Op: const 2
         Stmt: return
           Op: const 1
       Stmt: return
         Op: +
           Op: func
             Sym func3 fib
             Op: arglist
               Op: -
                 Op: var
                   Sym param1 k
                 Op: const 2
           Op: func
             Sym func3 fib
             Op: arglist
               Op: -
                 Op: var
                   Sym param1 k
                 Op: const 1
     Func main
       Stmt: expr
         Op: =
           Sym local1 v
           Op: func
             Sym func1 in
       Stmt: expr
         Op: func
           Sym func2 out
           Op: arglist
             Op: func
               Sym func3 fib
               Op: arglist
                 Op: var
                   Sym local1 v
       Stmt: return
         Op: const 0
     

   • -sオプションをつけて「./kadai44 -s」のように実行すると記号表をテキストで出力する。

     記号表
     局所変数 no.1 v (関数 main)
     仮引数 no.1 k (関数 fib)
     関数 no.1 in (仮引数 0 個, 局所変数 0 個)
     関数 no.2 out (仮引数 1 個, 局所変数 0 個)
     関数 no.3 fib (仮引数 1 個, 局所変数 0 個)
     関数 no.4 main (仮引数 0 個, 局所変数 1 個)
     

   • 演習室のLinux環境では、-gオプションをつけて次のように実行すると構文木をグラフとして出力する。

     ./kadai44 -g | dot -Tx11
     

     その他の環境でJavaが実行できるのであれば、gv.jarをダウンロードして

     ./kadai44 -g | java -jar gv.jar
     

     のようにグラフを表示されることができる。
     Javaもない場合は、

     ./kadai44 -g > kadai44.dot
     

     のように実行して、ファイルkadai44.dotに出力する。この内容をグラフ表示ページに入力すると、グラフが表示される。
     
   • -pオプションをつけて「./kadai44 -p」のように実行すると構文木に対応するCプログラムが表示される。

     int in();
     int out(int x1);
     int fib(int k){
         if(k<2){
             return 1;
         }
         return fib(k-2)+fib(k-1);
     }
     int main(){
     int v;
         v=in();
         out(fib(v));
         return 0;
     }
     

リスト4.4の構文解析を他のプログラムに対しても実行するには

Ttokens出力