情報工学実験 C コンパイラ第 2 回説明資料 (2018 年度 ) 担当 : 笹倉 佐藤

Transcription

1 情報工学実験 C コンパイラ第 2 回説明資料 (2018 年度 ) 担当 : 笹倉 佐藤

2 コンパイラ作成実験 非常に難しい. まず コンパイラを実装すること自体が難しい. コンパイラを指して 人工知能 と呼んだ時代もあった. 難しさは 抽象的なアイデアを元に具体的な実装を行うことにある. クヌースはこれを 計算機科学的な考え方 と呼び できる人の存在比率は 1/50 だと述べている. つまりこれが まさに計算機科学の難しさである.

3 抽象的なことを具体的に そもそもコンパイラ自体が抽象的なことを具体的に変換するもの高級プログラミング言語 アセンブラコード コンパイラの各フェーズを実装するのも抽象的なことを具体的にしないと実装できてない例 : 入力のソースを抽象構文木に変換 抽象構文木のデータ構造はどうする? どうやって抽象構文木を作る?

4 実験を実施するにあたって 手順を示して その通りにしてもらうことは簡単. しかし, そうではなくて, 悩んで, 理解して, 腑に落ちてほしい. わからないことは相談してください. グループ内 教員 TA 答えを聞く のではなくて 理解する手助けを求めてほしい.

5 大学で学ぶべきこととは わからないことはストレスだけど, 耐えてほしい. 新しいこと は常に わからないこと わからないことがわかるようになる活動が非常に重要 わかる とはどういうことか. むしろ わかることはやらなくてもよい

6 前回の演習問題 ( 復習 ) 1. 四則演算のできる計算機のプログラム ( 括弧も使える ) 2. 実数の扱える四則演算の計算機のプログラム ( 実数 も というより実数 が が正しかったです ) 3. 変数も扱える四則演算の計算機のプログラム ( 変数と実数が扱える )

7 演習問題 1 で行うべきこと 構文木が演算の順序を反映するように規則を作る 具体的には 同じ演算子が並んだら左側から実行する 加減算より乗除算を優先して実行する 括弧の中が外より先に実行される

8 算術式の規則 expression : expression + mulexp expression - mulexp mulexp ; mulexp : mulexp * primary mulexp / primary primary ; primary : ( expression ) NUMBER ;

9 演習問題 1 解答例 (arith.y) %{ #include <stdio.h> #include arith.tab.h" extern int yylex(); extern int yyerror(); %} %token NUMBER statement : expression { priny("= %d\n", $1);} ; expression : expression '+ mulexp {$$ = $1 + $3;} expression '- mulexp {$$ = $1 - $3;} ; mulexp {$$ = $1;} mulexp : mulexp * primary {$$ = $1 * $3;} ; mulexp / primary {if ($3 == 0) { yyerror( divide by zero ); return 0;} else $$ = $1 / $3;} primary {$$ = $1;} primary : ( expression ) {$$ = $2;} ; NUMBER {$$ = $1;} int main(void) { } if(yyparse()) { } fpriny(stderr, "Error\n"); return 1; return 0;

10 演習問題 1 解答例 (arith.l) %{ #include arith.tab.h %} [0-9]+ {yylval = atoi(yytext); return NUMBER;} [\t ] ; /* ignore whitespace */ \n return 0;. return yytext[0];

11 lex と yacc の連携 (1) lex のアクションで return した値 yacc ではトークンの種類として受け取る lex [0-9]+ {yylval = atoi(yytext); return NUMBER;} [\t ] ; /* ignore whitespace */ \n return 0;. return yytext[0]; yacc %token NUMBER ( 中略 ) primary : ( expression ) {$$ = $2;} NUMBER {$$ = $1;} ;

12 lex と yacc の連携 (2) lex のアクションで return した値 yacc で で囲まれたものは文字そのものとして受け取る lex [0-9]+ {yylval = atoi(yytext); return NUMBER;} [\t ] ; /* ignore whitespace */ \n return 0;. return yytext[0]; yacc primary : ( expression ) {$$ = $2;} NUMBER {$$ = $1;} ;

13 lex と yacc の連携 (3) lex で yylval に入れた値 yacc ではシンボル値として受け取れるシンボル値のデフォルトの型は int lex [0-9]+ {yylval = atoi(yytext); return NUMBER;} [\t ] ; /* ignore whitespace */ \n return 0;. return yytext[0]; yacc primary : ( expression ) {$$ = $2;} NUMBER {$$ = $1;} ;

14 シンボル ( 例 ) シンボル シンボルシンボルシンボル primary : ( expression ) {$$ = $2;} ; NUMBER {$$ = $1;} シンボル $$ は規則の左辺のシンボル値 ( この例では primary のシンボル値 ) $1 は規則の右辺の一つ目のシンボル値 $2 は規則の右辺の二つ目のシンボル値

15 シンボル値 ( 例 ) $$ $1 $2 $3 primary : ( expression ) {$$ = $2;} NUMBER {$$ = $1;} ; $1

16 演習問題 2 で行うべきこと 演習問題 1 のプログラムで整数を実数に変える 1. lex で実数を受け取れるようにする 2. yylval で実数値を yacc に渡す

17 実数の正規表現の例 [0-9]+ [0-9]*\.[0-9]+ [0-9]+ は 0 から 9 までの数字の 1 個以上の繰り返し. 整数表現に対応例 :14 [0-9]*\.[0-9]+ は 0 から 9 までの数字の 0 個以上の繰り返しの後. が来て, その後 0 から 9 までの数字の 1 個以上の繰り返し.. はそのままではすべての文字にマッチしてしまうので \. にして. だけを表すようにしている. 例 :1.34

18 yylval を実数に yylval の型は YYSTYPE で指定 YYSTYPE はデフォルトでは int YYSTYPE を変えることで yylval とすべてのシンボル値の型が変わる #define YYSTYPE double

19 演習問題 2 解答例 (arithr.y) %{ #include <stdio.h> #define YYSTYPE double #include arith.tab.h" extern int yylex(); extern int yyerror(); %} %token NUMBER statement : expression { priny("= %g\n", $1);} ; expression : expression '+ mulexp {$$ = $1 + $3;} expression '- mulexp {$$ = $1 - $3;} ; mulexp {$$ = $1;} mulexp : mulexp * primary {$$ = $1 * $3;} ; mulexp / primary {if ($3 == 0) { yyerror( divide by zero ); return 0;} else $$ = $1 / $3;} primary {$$ = $1;} primary : ( expression ) {$$ = $2;} ; NUMBER {$$ = $1;} int main(void) { } if(yyparse()) { } fpriny(stderr, "Error\n"); return 1; return 0;

20 演習問題 2 解答例 (arithr.l) %{ #define YYSTYPE double #include arith.tab.h %} [0-9]+ [0-9]*\.[0-9]+ {yylval = atof(yytext); return NUMBER;} [\t ] ; /* ignore whitespace */ \n return 0;. return yytext[0];

21 演習問題 3 で行うべきこと 1. 演習問題 2 のプログラムで変数を使えるようにする 2. 一行だけで計算が終わるのではなく数式を連続で計算できるようにし,$ が入力されたら終了するようにする

22 変数を使えるようにする arithr.y を拡張して変数を使えるようにする 変数はアルファベット小文字一文字だけからなるものとする 変数の数はたかだか 26 なので,26 個の要素をもつ配列 vbltable に格納する 配列 vbltable は yacc の宣言部で宣言する

23 %union どの変数が使われるのかを知るためには lex プログラムから変数名を受け取らなければならない 数字が入力された時は実数を, 変数が入力された時には整数 ( 配列の添え字に使う ) を受け取るように複数種類の型の値を yylval に入れて lex プログラムから yacc プログラムへ値を渡したい そのための %union %union を使うと YYSTYPE の型が共用体になる

24 共用体とは C のデータ型の一つ 一つの変数を場合によって異なる型で使えるようにするための仕組み あまり使われることはないでもコンパイラで使うと便利 ここでは yylval を double で使ったり int で使ったりするために利用する

25 C の共用体とは 宣言の形は構造体と似ているが, 構造体とは別物例 : union u_tag{ int ival; float fval; char *sval; } u; u には整数も実数も文字列へのポインタも入れることができる整数を入れる例 u.ival = 3; 実数を入れる例 u.fval = 整数へのポインタを入れる例 u.sval = 文字列へのポインタ 構造体とは違い, 型が異なる場合別々の場所に値が格納されるのではなく, 同じ場所に格納される. だから異なる型のうち一番格納場所をたくさん必要とするサイズに合わせて格納場所が確保される. 実際に使うときには, そのときどの型の値が入っているかをプログラマの側で管理しないといけない 詳しくは C の教科書を参照のこと

26 %union 宣言の使い方例 yacc プログラムの宣言部にシンボルの型を定義する %union { double dval; int vblno; } yacc を通すと *.tab.h, *.tab.c の中で C の共用体として実現される yacc プログラムの各シンボルにどの型を取るかを教えてあげなければならない トークンの場合 %token <dval> NUMBER %token <vblno> NAME 非終端記号のシンボルの場合 %type <dval> expression

27 演習 : 変数も使える計算機 (arithrv.[ly]) arithr.[ly] を拡張する %union 行を arithrv.y に加える 変数の値を格納する配列 vbltable[26] を arithrv.y で宣言する 変数のトークンを NAME として arithrv.l で読み込めるようにする 変数への代入を可能にするために arithrv.y に statement : NAME = expression expression を付け加える NAME を expression の中で使えるようにする statement を複数行読めるようにし,$ が来たら終わるようにする 各トークン, 必要な非終端記号に型を指定すること

28 演習問題 3 解答例 (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; priny( %c = %g\n, $1 + a, $3);} expression { priny("= %g\n", $1);} ( 中略 ) primary : ( expression ) {$$ = $2;} ; NUMBER {$$ = $1;} NAME {$$ = vbltable[$1];} ( 後略 )

29 演習問題 3 解答例 (arithrv.l) %{ #include arithrv.tab.h %} [0-9]+ [0-9]*\.[0-9]+ {yylval = 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]; 注 ) lex が return 0; すると入力終了の意味になる.

30 演習問題 4 基本言語仕様を構文解析する yacc,lex プログラムを作成する まずは正しいプログラムは何のエラーもなく通るようにする. コード生成はまだしなくてよい. アクション部は何も書かなくてよい. エラーがあれば error と出力するようにする

31 基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= define < 識別子 >; array < 識別子 > [< 数 >]; < 文集合 > ::= < 文 > < 文集合 > < 文 > < 文 > ::= < 代入文 > < ループ文 > < 条件分岐文 > < 代入文 > ::= < 識別子 > = < 算術式 >; < 識別子 > [ < 数 > ] = < 算術式 >; ß 追加 < 算術式 > ::= < 算術式 > < 加減演算子 > < 項 > < 項 > < 項 > ::= < 項 > < 乗除演算子 > < 因子 > < 因子 > < 因子 > ::= < 変数 > (< 算術式 >) < 加減演算子 > ::= + - < 乗除演算子 > ::= * / < 変数 > ::= < 識別子 > < 数 > < 識別子 >[< 数 >] < ループ文 > ::= 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 < 数字 > ::=

32 この言語で書けるプログラムの例 define a; define a1; define b; array c[3]; a = 2800; b = (a + 5) *3; c[0] = 0; c[1] = 1; c[2] = 2; if (b> 3000) { b = 3000; } a1 = c[0]; while(a1 < c[2]){ b = b / 2; a1 = a1 + c[1]; }

33 この言語でエラーとなるプログラムの例 例 1 例 2 int a; a = 0; define a; array c[3]; a = 0; while (a < 3) { c[a] = a; } int という型名は定義されていない 配列の添え字に変数を用いることは定義されていない

34 演習問題 4 で行うべきこと 何をトークンとして扱うか 終端記号はすべてトークン 基本言語仕様のうち正規表現で書けるものはトークンとして lex で切り出す

35 基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= define < 識別子 >; array < 識別子 > [< 数 >]; < 文集合 > ::= < 文 > < 文集合 > < 文 > < 文 > ::= < 代入文 > < ループ文 > < 条件分岐文 > < 代入文 > ::= < 識別子 > = < 算術式 >; < 識別子 > [ < 数 > ] = < 算術式 >; < 算術式 > ::= < 算術式 > < 加減演算子 > < 項 > < 項 > < 項 > ::= < 項 > < 乗除演算子 > < 因子 > < 因子 > < 因子 > ::= < 変数 > (< 算術式 >) < 加減演算子 > ::= + - < 乗除演算子 > ::= * / < 変数 > ::= < 識別子 > < 数 > < 識別子 >[< 数 >] < ループ文 > ::= while (< 条件式 >) { < 文集合 > } < 条件分岐文 > ::= if (< 条件式 >) { < 文集合 > } if (< 条件式 >) { < 文集合 > } else { < 文集合 > } < 条件式 > ::= < 算術式 > < 比較演算子 > < 算術式 > < 比較演算子 > ::= == '<' '>' < 識別子 > ::= < 英字 > < 英数字列 > < 英字 > この線から下はlexで < 英数字列 > ::= < 英数字 > < 英数字列 > < 英数字 > < 英数字 > ::= < 英字 > < 数字 > < 数 > ::= < 数字 > < 数 > < 数字 > < 英字 > ::= 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 < 数字 > ::=

36 基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= define < 識別子 >; array < 識別子 > [< 数 >]; < 文集合 > ::= < 文 > < 文集合 > < 文 > < 文 > ::= < 代入文 > < ループ文 > < 条件分岐文 > < 代入文 > ::= < 識別子 > = < 算術式 >; < 識別子 > [ < 数 > ] = < 算術式 >; < 算術式 > ::= < 算術式 > < 加減演算子 > < 項 > < 項 > < 項 > ::= < 項 > < 乗除演算子 > < 因子 > < 因子 > < 因子 > ::= < 変数 > (< 算術式 >) < 加減演算子 > ::= + - < 乗除演算子 > ::= * / < 変数 > ::= < 識別子 > < 数 > < 識別子 >[< 数 >] < ループ文 > ::= 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 < 数字 > ::=

37 トークン それぞれのトークンごとに種類を分ける例 : 識別子, 数, プラス記号, マイナス記号, define, array. 今はまだ yacc のアクションを書かないので型について考える必要はない lex もトークンの名前を return するだけでよい

38 非終端記号の名前 ( 本来なんでもいいのだが, 時間がないので例を示す ) < プログラム > program < 変数宣言部 > declarations < 宣言文 > decl_statement < 文集合 > statements < 文 > statement < 代入文 > assignment_stmt < 算術式 > expression < 項 > term < 因子 > factor < 加減演算子 > add_op < 乗除演算子 > mul_op < 変数 > var < ループ文 > loop_stmt < 条件分岐文 > cond_stmt < 条件式 > condition < 比較演算子 > cond_op これらの名前を yacc ファイルで使う 基本言語仕様にあるそれ以外の非終端記号は lex で処理してトークンになってしまうので yacc ファイルでの非終端記号としては扱わない 言語仕様を拡張してこれ以外の非終端記号を導入するときはその名前は自分たちで考えること

39 トークン名 ( 普通は大文字を使う ) ( 本来なんでもいいのだが, 時間がないので例を示す.) define DEFINE array ARRAY while WHILE if IF else ELSE ; SEMIC [ L_BRACKET ] R_BRACKET ( L_PARAN ) R_PARAN { L_BRACE } R_BRACE = ASSIGN + ADD - SUB * MUL / DIV == EQ < LT > GT < 識別子 > IDENT < 数 > NUMBER これらが lex からの return 値になる 言語仕様を拡張してこれ以外のトークンを導入するときはその名前は自分たちで考えること

40 lex ファイル ( ひながた ) ( 定義部省略 ) "define" return DEFINE; "array" return ARRAY; ( 中略 ) 整数の正規表現 return NUMBER; 識別子の正規表現 return IDENT; 空白タブ改行 ; 省略されている定義部と規則部の部分を書くこと 赤字のところを正規表現に直すこと

41 yacc ファイル ( ひながた ) ( 略 ) %token DEFINE ARRAY WHILE IF ELSE 以下トークンを全て %token で定義 program : declaraxons statements ; declaraxons : decl_statement declaraxons decl_statement ; decl_statement : DEFINE IDENT SEMIC ARRAY IDENT L_BRACKET NUMBER R_BRACKET SEMIC ; 以下規則をすべて定義 int main(void) { if (yyparse()){ fpriny(stderr, Error\n ); return 1; } retrurn 0; }