情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤 2017.12.7
前回の演習問題の解答例 1. 四則演算のできる計算機のプログラム ( 括弧も使える ) 2. 実数の扱える四則演算の計算機のプログラム ( 実数 も というより実数 が が正しかったです ) 3. 変数も扱える四則演算の計算機のプログラム ( 変数と実数が扱える )
演習問題 1 で行うべきこと 構文木が演算の順序を反映するように規則を作る 具体的には 同じ演算子が並んだら左側から実行する 加減算より乗除算を優先して実行する 括弧の中が外より先に実行される
算術式の規則 expression : expression + mulexp expression - mulexp mulexp ; mulexp : mulexp * primary mulexp / primary primary ; primary : ( expression ) NUMBER ;
演習問題 1 解答例 (arith.y) %{ #include <stdio.h> #include arith.tab.h" extern int yylex(); extern int yyerror(); %} %token NUMBER statement : expression { prinu("= %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()) { } fprinu(stderr, "Error\n"); return 1; return 0;
演習問題 1 解答例 (arith.l) %{ #include arith.tab.h %} [0-9]+ {yylval = atoi(yytext); return NUMBER;} [\t ] ; /* ignore whitespace */ \n return 0;. return yytext[0];
lex と yacc の連携 (1) 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;} ;
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;} ;
lex と yacc の連携 (3) lex で yylval に入れた値 yacc ではシンボル値として受け取れる lex [0-9]+ {yylval = atoi(yytext); return NUMBER;} [\t ] ; /* ignore whitespace */ \n return 0;. return yytext[0]; yacc primary : ( expression ) {$$ = $2;} NUMBER {$$ = $1;} ;
シンボル シンボル シンボルシンボルシンボル primary : ( expression ) {$$ = $2;} NUMBER {$$ = $1;} ; シンボル
シンボル値 $$ $1 $2 $3 primary : ( expression ) {$$ = $2;} NUMBER {$$ = $1;} ; $1
演習問題 2 で行うべきこと 演習問題 1 のプログラムで整数を実数に変える 1. lex で実数を受け取れるようにする 2. yylval で実数値を yacc に渡す
実数の正規表現の例 [0-9]+ [0-9]*\.[0-9]+ [0-9]+ は 0 から 9 までの数字の 1 個以上の繰り返し. 整数表現に対応例 :14 [0-9]*\.[0-9]+ は 0 から 9 までの数字の 0 個以上の繰り返しの後. が来て, その後 0 から 9 までの数字の 1 個以上の繰り返し.. はそのままではすべての文字にマッチしてしまうので \. にして. だけを表すようにしている. 例 :1.34
yylval を実数に yylval の型は YYSTYPE YYSTYPE はデフォルトでは int YYSTYPE を変えることで yylval とすべてのシンボル値の型が変わる #define YYSTYPE double
演習問題 2 解答例 (arithr.y) %{ #include <stdio.h> #define YYSTYPE double #include arith.tab.h" extern int yylex(); extern int yyerror(); %} %token NUMBER statement : expression { prinu("= %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()) { } fprinu(stderr, "Error\n"); return 1; return 0;
演習問題 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];
演習問題 3 で行うべきこと 1. 演習問題 2 のプログラムで変数を使えるようにする 2. 一行だけで計算が終わるのではなく数式を連続で計算できるようにし,$ が入力されたら終了するようにする
変数を使えるようにする arithr.y を拡張して変数を使えるようにする 変数はアルファベット小文字一文字だけからなるものとする 変数の数はたかだか 26 なので,26 個の要素をもつ配列 vbltable に格納する 配列 vbltable は yacc の宣言部で宣言する
%union どの変数が使われるのかを知るためには lex プログラムから変数名を受け取らなければならない 数字が入力された時は実数を, 変数が入力された時には整数 ( 配列の添え字に使う ) を受け取るように複数種類の型の値を yylval に入れて lex プログラムから yacc プログラムへ値を渡したい そのための %union %union を使うと YYSTYPE の型が共用体になる
共用体とは C のデータ型の一つ 一つの変数を場合によって別の型で使えるようにするための仕組み あまり使われることはない ここでは yylval を double で使ったり int で使ったりするために利用する 詳しくは C の教科書を参照のこと
%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 で宣言する 変数のトークンを NAME として arithrv.l で読み込めるようにする 変数への代入を可能にするために arithrv.y に statement : NAME = expression expression を付け加える NAME を expression の中で使えるようにする statement を複数行読めるようにし,$ が来たら終わるようにする 各トークン, 必要な非終端記号に型を指定すること
演習問題 3 解答例 (arithrv.y) %{ #include <stdio.h> #include arith.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; prinu( %c = %g\n, $1 + a, $3);} expression { prinu("= %g\n", $1);} ( 中略 ) primary : ( expression ) {$$ = $2;} ; NUMBER {$$ = $1;} NAME {$$ = vbltable[$1];} ( 後略 )
演習問題 3 解答例 (arithrv.l) %{ #include arith.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; すると入力終了の意味になる.
演習問題 4 基本言語仕様を構文解析する yacc,lex プログラムを作成する まずは正しいプログラムは何のエラーもなく通るようにする. コード生成はまだしなくてよい. アクション部は何も書かなくてよい. エラーがあれば error と出力するようにする
基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= 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 < 数字 > ::= 0 1 2 3 4 5 6 7 8 9
この言語で書けるプログラムの例 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]; }
この言語でエラーとなるプログラムの例 例 1 例 2 int a; a = 0; define a; array c[3]; a = 0; while (a < 3) { c[a] = a; }
演習問題 4 で行うべきこと 何をトークンとして扱うか 終端記号はすべてトークン 基本言語仕様のうち正規表現で書けるものはトークンとして lex で切り出す
基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= 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 < 数字 > ::= 0 1 2 3 4 5 6 7 8 9
基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= 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 < 数字 > ::= 0 1 2 3 4 5 6 7 8 9
トークン それぞれのトークンごとに種類を分ける例 : 識別子, 数, プラス記号, マイナス記号, define, array. 今はまだ yacc のアクションを書かないので型について考える必要はない lex もトークンの名前を return するだけでよい