情報工学実験 C コンパイラ第 2 回説明資料 (2016 年度 ) 担当 : 笹倉 佐藤
変数を使えるようにする arithr.y を拡張して変数を使えるようにする 変数はアルファベット小文字一文字だけからなるものとする 変数の数はたかだか 26 なので,26 個の要素をもつ配列 vbltable に格納する 一行だけで計算が終わるのではなく数式を連続で計算できるようにし,$ が入力されたら終了するようにする
%union どの変数が使われるのかを知るためには lex プログラムから変数名を受け取らなければならない 数字が入力された時は実数を, 変数が入力された時には整数 ( 配列の添え字に使う ) を受け取るように複数種類の型の値を yylval に入れて lex プログラムから yacc プログラムへ値を渡したい そのための %union
%union 宣言の使い方例 yacc プログラムの宣言部にシンボルの型を定義する %union { double dval; int vblno; } C の共用体として実現される yacc プログラムの各シンボルにどの型を取るかを教えてあげなければならない トークンの場合 %token <dval> NUMBER %token <vblno> NAME 非終端記号のシンボルの場合 %type <dval> expression
演習 : 変数も使える計算機 (arithrv.[ly]) arithr.[ly] を拡張する %union 行を arithrv.y に加える 変数の値を格納する配列 vbltable[26] を arithrv.y で宣言し, arithrv.l では extern 宣言する 変数のトークンを NAME として arithrv.l で読み込めるようにする arithrv.y に statement : NAME = expression expression を付け加える ( アクション部も各自考えて追加すること ) NAME を expression の中で使えるようにする statement を複数行読めるようにし,$ が来たら終わるようにする 各トークン, 必要な非終端記号に型を指定すること
arithrv.l %{ #include "arithrv.tab.h" #include <math.h> extern double vbltable[26]; %} %% [0-9]+ [0-9]*\.[0-9]+ {yylval.dval = atof(yytext) ; return NUMBER; } [\t ] ; /* ignore whitespace */ [a- z] {yylval.vblno = yytext[0] - 'a'; return NAME; } "$" {return 0; /* end of input */} \n. return yytext[0]; %%
arithrv.y %{ #include <stdio.h> #include "arithrv.tab.h" extern int yylex(); extern int yyerror(); double vbltable[26]; %} %union{ double dval; int vblno; } %token <vblno> NAME %token <dval> NUMBER %type <dval> expression mulexp primary %% statement_list : statement '\n' statement_list statement '\n' ; statement : NAME '=' expression {vbltable[$1] = $3; prin`("%c = %g\n", $1+'a', $3); } expression {prin`("= %g\n", $1);} ; expression : expression '+' mulexp {$$ = $1 + $3; } expression '- ' mulexp {$$ = $1 - $3; } mulexp {$$ = $1;} ; mulexp : mulexp '*' primary {$$ = $1 * $3; } mulexp '/' primary {if($3 == 0) {/* prin`("divide by zero\n"); or */ yyerror("divide by zero"); return 0;} else $$ = $1 / $3; } primary {$$ = $1;} ; primary : '(' expression ')' {$$ = $2; } NUMBER {$$ = $1;} NAME {$$ = vbltable[$1];} ; %% int main(void) { if (yyparse()) { fprin`(stderr, "Error\n"); return 1; } }
make の利用 毎回以下の用なコマンドを手で打つのは面倒 flex arithrv.l bison d arithrv.y gcc lex.yy.c arithrv.tab.c o arithrv lfl - ly make (GNU make) を使って楽をしよう
make とは ファイルの更新時間をみて処理を行うためのツール 主に分割コンパイルの支援のために使われる Unix で標準でついてくるツール
make の基本 デフォルトでは Makefile に処理の規則を書く (makefile でもいいが Makefile が推奨 ) 処理の規則の書き方 FileB : FileA1 FileA2. <tab> 指定するコマンド FileA1, FileA2, のファイルのうちどれか一つでも更新時間が FileB よりも新しければ指定するコマンドを実行する ここは必ず タブ でなければならない
Makefile の例 以下の内容の Makefile をソースファイルのおいてあるディレクトリで作成する arithrv : lex.yy.c arithrv.tab.c gcc o arithrv arithrv.tab.o lex.yy.o lfl -ly lex.yy.c : arithrv.l flex arithrv.l arithrv.tab.c : arithrv.y bison d arithrv.y make とすると, 更新されたものだけコンパイルされる
賢い make の使い方 マクロの利用 長いものに別名をつけて何度も書かなくていいように 変更も容易 暗黙のルールの利用 よく使うルールはあらかじめ make が知っている. 例えば.c ファイルからは.o ファイルを作る.
Makefile の例 2 CC = gcc CFLAGS = -O -Wall LEX = flex YACC = bison -d HDRS = parse.tab.h LDFLAGS = -lfl -ly LIBS = OBJS = lex.yy.o parse.tab.o PROGRAM = mycompiler all: $(PROGRAM) $(PROGRAM): $(OBJS) $(HDRS) $(CC) $(OBJS) $(LDFLAGS) $(LIBS) -o $(PROGRAM) lex.yy.c: lex.l $(LEX) lex.l parse.tab.c: parse.y ast.h $(YACC) parse.y clean:; rm -f *.o *~ make についてもっと知りたい人は http://www.ecoop.net/coop/translated/gnumake3.77/make_toc.jp.html などを参照のこと
基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= define < 識別子 >; < 文集合 > ::= < 文 > < 文集合 > < 文 > < 文 > ::= < 代入文 > < ループ文 > < 条件分岐文 > < 代入文 > ::= < 識別子 > = < 算術式 >; < 算術式 > ::= < 算術式 > < 加減演算子 > < 項 > < 項 > < 項 > ::= < 項 > < 乗除演算子 > < 因子 > < 因子 > < 因子 > ::= < 変数 > (< 算術式 >) < 加減演算子 > ::= + - < 乗除演算子 > ::= * / < 変数 > ::= < 識別子 > < 数 > < ループ文 > ::= while (< 条件式 >) { < 文集合 > } < 条件分岐文 > ::= if (< 条件式 >) { < 文集合 > } if (< 条件式 >) { < 文集合 > } else { < 文集合 > } < 条件式 > ::= < 算術式 > < 比較演算子 > < 算術式 > < 比較演算子 > ::= == '<' '>' < 識別子 > ::= < 英字 > < 英数字列 > < 英字 > < 英数字列 > ::= < 英数字 > < 英数字列 > < 英数字 > < 英数字 > ::= < 英字 > < 数字 > < 数 > ::= < 数字 > < 数 > < 数字 > < 英字 > ::= a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z < 数字 > ::= 0 1 2 3 4 5 6 7 8 9
この言語で書けるプログラムの例 define a; define a1; define b; a = 2800; b = (a + 5) *3; if (b> 3000) { b = 3000; } a1 = 0; while(a1 < 2){ b = b / 2; a1 = a1 + 1; }
本日の作業内容 ( 目安 :4 限まで ) 作業目標 基本言語仕様を構文解析する yacc,lex プログラムを作成する まずは正しいプログラムは何のエラーもなく通るようにする. コード生成はまだしなくてよい. アクション部は何も書かなくてよい. エラーがあれば error と出力するようにする 時間が余れば途中で適宜メッセージを出して正しく解析されているかどうかを確認する 例えば,while 文の解析のところで while_loop, 算術式の解析のところで expression と出す, など. グループで相談しながら作業すること. 可能ならば分担して作業すること.
抽象構文木 構文木からコードに必要な部分のみを残したもの < 算術式 > < 算術式 > < 演算子 > < 数 > < 算術式 > < 演算子 > < 数 > 1 + 2 ー 3 < 数 > 1 + 2 ー 3 構文木 ( ちょっと省略しているけど ) 抽象構文木
構文木と抽象構文木 < 算術式 > < 項 > < 項 > < 因子 > < 乗算演算子 > < 数 > * 3 < 左括弧 > < 算術式 > < 右括弧 > < 数 > < 加算演算子 > < 数 > 1 + 2 ( 1 + 2 ) * 3 構文木 抽象構文木
抽象構文木の決定 その言語に合うように決めれば良い 言語の基本的な要素について木の形を決めていく例 : 算術式ならば通常はこどもを三つもつ 代入文ならば通常こどもは二つ ( 左辺と右辺 ) while 文ならば通常こどもは二つ ( 条件式と文集合 ) for 文ならば通常こどもは四つ If 文ならば通常こどもは三つ ( 条件式, 真の場合の文集合, 偽の場合の文集合 ) 変数宣言文ならば? ( 基本仕様なら一つでいいだろう ) 文集合の場合は? ( 普通は二つ. 文と残りの文集合 ) 条件式の場合は?
抽象構文木のデータ構造 構造体 (struct) を使ってもいいが 要素によってこどもの数が違う 要素によってこどもの型が違う例えば, 算術式では数がこどもになるが,while 文などでは文がこどもになったりする 構造体を使おうとすると, 有り得る場合の全てに対応したメンバを定義しておいて実際にはその一部しか使わないという実装しかできずメモリを効率的に使えない
共用体 (union) 異なる型とサイズのオブジェクトを ( 異なる時に ) 保持するための変数 union u_tag{ int ival; float fval; char *sval; } u; (u_tag という共用体を定義しその変数として u を宣言した.)
共用体 (union) 続き この場合, 三つのメンバを取るのではなく, 一つのメンバしかメモリ上では取られない. プログラム内では u.ival でアクセスすると整数と, u.fval でアクセスすると実数と,u.sval でアクセスすると文字列とみなされる. u.sval に文字列を入れた後,u.fval で参照したらその文字列を実数と思ってプログラムは参照する 共用体は通常あまり使われないが, コンパイラの抽象構文木を表現するのに便利
共用体使用上の注意 共用体に今どの型の値が入っているかはプログラマが管理しないといけない 通常はどの型が入っているかを示す変数を一つ用意して管理するウェブ : 言語定義共用体例 2 を参照
応用 : 型を示す変数を共用体のメンバ にする方法 共用体のメンバの型を示すための変数が独立しているとどの共用体とどの変数が関係しているのかがわかりにくい 共用体の中に型を示す変数を入れることはできないか? ウェブ : 言語定義共用体例 3 を参照
抽象構文木実装のヒント まず, 言語の各要素を表現するための型を定義する それらの型を使える共用体を定義する yacc プログラムの各要素のアクションとしてこの共用体を作成する C プログラムを書く 入力されたプログラムは定義した共用体が形作る木 ( これが抽象構文木 ) で表現されることになる ウェブページに追加解説あり
抽象構文木の確認 抽象構文木が正しくできているか確認をする 基本的には適宜 prin` 文を入れて確認する 算術式については算術式を逆ポーランド記法で表示させて確認する
逆ポーランド記法による表現 日本語の語順と同じ A + B A B + B * C + D / E B C * D E / + B に C をかけたものと D を E で割ったものを加えたもの
AST の作成を含めた Makefile の例 CC = gcc CFLAGS = -O -Wall LEX = flex YACC = bison -d HDRS = parse.tab.h ast.h LDFLAGS = -lfl -ly LIBS = OBJS = lex.yy.o parse.tab.o ast.o PROGRAM = mycompiler all: $(PROGRAM) $(PROGRAM): $(OBJS) $(HDRS) $(CC) $(OBJS) $(LDFLAGS) $(LIBS) -o $(PROGRAM) lex.yy.c: lex.l $(LEX) lex.l parse.tab.c: parse.y ast.h $(YACC) parse.y clean:; rm -f *.o *~ ### ast.o: ast.c ast.h 注 :ast.c と ast.h いうファイルを新しく作った場合の例
本日の作業内容 ( 残り ) 作業目標 基本言語仕様で抽象構文木の図を書いてグループで確認する その抽象構文木を表現するために必要なデータ型等をグループで決める 基本言語仕様を構文解析する yacc,lex プログラムのアクションとして抽象構文木を作成するようにプログラムを改造する 抽象構文木を出力して正しく構文解析されているか確かめる グループで相談しながら作業すること. 可能ならば分担して作業すること.
ヒント まずは算術式の部分だけの AST を作ってみよう 数字は整数だけ 変数あり 共用体ではなく構造体で作ってみる 代入文で < 変数 > = < 算術式 > のアクションで算術式を逆ポーランド記法で出力する関数 print_tree を呼び出しそこで算術式を表示させる.