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

(1)

情報工学実験

C

コンパイラ

第

2回説明資料

（

2018年度）

担当：笹倉・佐藤

2018.12.13

(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 ではトークンの種類として受け取る

%%

[0-‐9]+ {yylval = atoi(yytext);

return NUMBER;

}

[\t ] ; /* ignore whitespace

*/

\n return 0;

. return yytext[0];

%%

lex

%token NUMBER

%%

　

…(中略) …

primary : ‘(‘ expression ‘)’ {$$ = $2;}

|

NUMBER

{$$ = $1;}

;

%%

yacc

(12)

lex とyaccの連携(2)

• lex のアクションでreturn した値

→　yacc で’’で囲まれたものは文字そのものとし

て受け取る

%%

[0-‐9]+ {yylval = atoi(yytext);

return NUMBER;}

[\t ] ; /* ignore whitespace

*/

\n return 0;

.

return yytext[0];

%%

lex

primary :

‘(‘

expression

‘)’

{$$ = $2;}

| NUMBER {$$ = $1;}

;

%%

yacc

(13)

lex とyaccの連携(3)

• lex で yylval に入れた値

→　yacc ではシンボル値として受け取れる

　　シンボル値のデフォルトの型は　

int

%%

[0-‐9]+ {

yylval = atoi(yytext);

return NUMBER;}

[\t ] ; /* ignore whitespace

*/

\n return 0;

. return yytext[0];

%%

lex

primary : ‘(‘ expression ‘)’ {$$ = $2;}

| NUMBER {$$ =

$1

;}

;

%%

yacc

(14)

シンボル

(例)

primary : ‘(‘ expression ‘)’ {$$ = $2;}

| NUMBER {$$ = $1;}

;

シンボル

$$ は規則の左辺のシンボル値（この例ではprimaryのシンボル値)

$1は規則の右辺の一つ目のシンボル値

$2は規則の右辺の二つ目のシンボル値

…

(15)

シンボル値

(例）

primary : ‘(‘ expression ‘)’ {$$ = $2;}

| NUMBER {$$ = $1;}

;

$$

$1

$2

$3

(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 とすべてのシン

ボル値の型が変わる

(19)

演習問題

2解答例(arithr.y)

%{

#include <stdio.h>

#deﬁne 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)

%{

#deﬁne 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;

ﬂoat fval;

char *sval;

} u;

• u には整数も実数も文字列へのポインタも入れることができる

　　整数を入れる例　

_{u.ival
=
3;}

　　実数を入れる例　

_{u.fval
=
5.789}

　　整数へのポインタを入れる例　

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];

%%

(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 <数字> ::= 0|1|2|3|4|5|6|7|8|9

(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)

この言語でエラーとなるプログラムの例

int a;

a = 0;

define a;

array c[3];

a = 0;

while (a < 3) {

c[a] = a;

}

例

1 例

2 int という型名は定義されていない

配列の添え字に変数を用いることは

定義されていない

(34)

演習問題

4で行うべきこと

•  何をトークンとして扱うか

– 終端記号はすべてトークン

– 基本言語仕様のうち

正規表現で書けるもの

は

トークンとして

lexで切り出す

(35)

基本言語仕様

<プログラム> ::= <変数宣言部> <文集合> <変数宣言部> ::= <宣言文> <変数宣言部> | <宣言文> <宣言文> ::= 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

この線から下は

_lexで

(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 <数字> ::= 0|1|2|3|4|5|6|7|8|9

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