情報工学実験
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 とは
• ファイルの更新時間をみて処理を行うための
ツール
• 主に分割コンパイルの支援のために使われ
る
• Unix で標準でついてくるツール
make の基本
• デフォルトでは Makefile に処理の規則を
書く
(makefile でもいいが Makefile が推
奨）
• 処理の規則の書き方
FileB : FileA1 FileA2 ….
<tab>指定するコマンド
FileA1, FileA2, …のファイルのうちどれか
一つでも更新時間が
FileBよりも新しけれ
ば指定するコマンドを実行する
Makefile の例
• 以下の内容の Makefile をソースファイルのおい
てあるディレクトリで作成する
• make とすると，更新されたものだけコンパイルさ
れる
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 が知ってい
る．例えば
.c ファイルからは .o ファイルを作る．
Makefile の例２
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”と出す，など．
• グループで相談しながら作業すること．可能なら
ば分担して作業すること．
抽象構文木
• 構文木からコードに必要な部分のみを残した
もの
<算術式>
<算術式>
<算術式>
<数>
<数>
<数>
<演算子>
<演算子>
１
＋
２
ー
３
１
＋
２
ー
３
構文木（ちょっと省略しているけど）
抽象構文木
構文木と抽象構文木
<算術式>
<因子>
<算術式>
<数>
<乗算演算子>
(
＋
２
*
３
<項>
<項>
<左括弧>
<右括弧>
<数> <加算演算子> <数>
１
)
＋
２
*
３
１
構文木
抽象構文木
抽象構文木の決定
• その言語に合うように決めれば良い
• 言語の基本的な要素について木の形を決めていく
例：
– 算術式ならば通常はこどもを三つもつ
– 代入文ならば通常こどもは二つ（左辺と右辺）
–
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
