情報工学実験
C
コンパイラ
（
2016年度）
担当：笹倉・佐藤
2016.12.7version
コンパイラとは
• プログラミング言語（高級言語）で書かれたプ
ログラムを入力し，コンピュータが実行できる
言語（機械語など）に変換するプログラムのこ
と
例：
gcc
• コンパイラは対応する言語によって複雑であ
る場合もあるし単純である場合もある
• 本実験では簡単な言語のコンパイラを作成す
る
本実験の目的
•
3年間の総仕上げとしてある程度大きなプロ
グラムを作成する
• グループでシステム（プログラム）を仕上げる
経験をする
• 自分でスケジュールを立てシステムを構築す
る経験をする
スケジュール
12/6(
火
)
概要説明
yacc, lex
演習
12/13(火) yacc, lex を用いた構文解析1
12/15(木) yacc, lex を用いた構文解析2
12/20(火) yacc, lex を用いた構文解析3
1/10(火) コード生成説明
1/18(水)
コード生成
1
1/24(火) コード生成2
1/26(木) コード生成3
1/31(火) コード生成4
2/2(木) コード生成5
2/7(火) 最終面接
実験概要
• 手続き型言語のコンパイラの作成
• 目的コードはハードウェア実験で作成したプ
ロセッサのアセンブラ
• 基本言語仕様を与えるので，それを適宜拡張
する
•
yacc, lex を使う
• 時間があればコード最適化を行う
実施上の注意
•
Webページ
hAp://150.46.1.165/~sasakura/jikken/
• グループで行う
– グループで共通の言語仕様を決めてプログラムを作成す る – できるだけ分担してプログラムを書く – わからないことはまずグループで相談する – 遅刻・欠席する場合は必ずグループの他のメンバーにも 連絡のこと• 作業報告書を毎回出す
• 最終面接で評価する
（最終課題のプログラムが動くかどうか，内容をきちん
と理解しているか，レポートがきちんと書けているか）
グループ自己紹介（
5分間）
• 名前
• 今朝の朝ごはんは何を食べたか
• 好きな食べもの
• 好きな色
• 特技
• 好きな科目
• 苦手な科目
• プログラミングの経験
• プログラミングがどれくらい好きか
下記のことをすべて述べること
手続き型言語とは
• プログラムに書いてある順番通りにコン
ピュータが実行すればよいようになっている
言語
例：
C言語
• その他の言語とは
– 関数型言語
例：
ML, Haskell
– オブジェクト指向言語
例：
Java
手続き型言語の利点
• 「手続き」を考えてプログラムを書けばよいの
で比較的わかりやすい
•
コンパイラを作りやすい
– 基本的には入力プログラムの1行1行を順番に実
行コード（アセンブラ）に変換していけばよい
– ただしそうすると効率の悪いプログラムになる場
合があるので，
コード最適化
を行う場合が多い．
コンパイラの概要
• 字句解析
入力プログラムを字句（トークン）に分ける
• 構文解析
入力プログラムが文法に合っているかどうか
をチェックする．抽象構文木
(AST)を作る．
•
ASTレベルでの最適化
• コード生成
実行コード（アセンブラ）に変換する
• コードレベルでの最適化
字句解析
• 入力プログラムを字句（トークン）に分ける
• 自作するならオートマトンを用いる
表駆動型（参考：
2015年度コンパイラ実験）
• 今回は
(今年度から) lex を使う
•
lexについては後述
字句解析オートマトン
初期状態 終了状態 整数 実数 識別子 英数字 0 〜 9 0 〜 9 0 〜 9 0 〜 9 以外 0 〜 9 . 以外 . 英字 英数字以外整数・実数・識別子の場合の例
構文解析
• 入力プログラムが文法に合っているかどうか
をチェックする
→ 合っていなければコンパイラがエラーを出
す
• 自作するなら，再帰下降型構文解析や演算
子順位法を使う
• 今回は
yacc を利用．
•
yaccについては後述
構文木
<簡単な算術式> ::= <簡単な算術式> <演算子> <数> | <数> <演算子> ::= + | - <数> ::= <数字><数> | <数字> <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <簡単な算術式> <簡単な算術式> <簡単な算術式> <数> <数> <数> <演算子> <演算子> １ ＋ ２ ー ３抽象構文木
(AST)
• 構文解析の結果，プログラムを木の形で記憶
する
• 構文木から非終端記号を取り除き，コード生
成に必要なものだけを残して作った木
• この木をたどりながらコード生成をする
•
ASTを意味を変えないように違う形にすること
でより速いコードにすることができる（コード最
適化）
コード生成
•
ASTをたどりながら実行コード（アセンブラ）に
変換していく
•
ASTの形によってどういうコードを生成するか
が決まる
• 一度生成したコードを見直して意味を変えな
いように変換することでより速いコードにする
こともできる（コード最適化）
yacc, lex
•
UNIXで標準で装備されている字句解析・構文
解析ルーチン
•
lex （lexical analyzer)
字句解析ルーチン
単独で使うこともできる
•
yacc (Yet Another Compiler Compiler)
構文解析ルーチン
字句解析の結果を使うので基本的に
lex と一
yacc と lex
字句解析
構文解析
AST
概念的：
入力プログラム
字句解析
lex
構文解析
yacc
AST
入力プログラム
実装：
yacc と lex の出力
•
yacc も lex も C プログラムを自動生成する
• そのCプログラムをコンパイルすることで実行可能な
ファイルができる
lex
lex.yy.c
yacc
*.tab.h
*.tab.c
lexの構造
定義部
%%
定義部の終了
規則部
%%
規則部の終了
ユーザ定義サブルーチン部
：
Cのプログラムを書く
lex 定義部
• 初期設定を行う
•
%{
と
%}
で囲まれた部分はそのまま
lex.yy.c
lex 規則部
パタン 空白 アクション
の繰り返し
• パタンは正規表現で書く
• アクションは
C言語で書く
例：
%%
\n ++num_lines; ++num_chars;
. ++num_chars;
%%
正規表現で使える文字
ユーザ定義サブルーチン部
• ここで書いたものはすべて
C言語だと解釈さ
れ
lex.yy.cにそのままコピーされる
•
yylex() を呼び出さないと字句解析が実行され
ない
ので
lex単独でプログラムを書く場合はこ
の中で必ず
yylex() を呼び出さなければなら
ない
例：文字数を数えるプログラム
(count.l)
%{int num_lines = 0, num_chars = 0; %} %% \n ++num_lines; ++num_chars; . ++num_chars; %% Int main(void) { yylex();
prinb("# of lines = %d, # of chars = %d\n", num_lines, num_chars);
return 0; }
lex のコンパイルの仕方
> flex ファイル名
> gcc lex.yy.c –o 実行ファイル名 -‐lfl
UNIXの標準は lex だが，GNUの lex相当である
flex
を
本実験では使う．
lex(flex) の関数（例えばyylex)を使うためには，lex のラ
イブラリである
libfl.a をリンクする必要がある．-‐lfl はそ
れを指定している．
count.l をコンパイルして実行してみよう
> flex count.l
ライブラリがないと言われたら
1. ~/.bashrc に以下を追記
export LD_LIBRARY_PATH=/home/users/ecs/
sato/local/lib:$LD_LIBRARY_PATH
export LIBRARY_PATH=/home/users/ecs/
sato/local/lib:$LIBRARY_PATH
2. bashrcを再読み込みして環境変数を再設定
source ./bashrc
例
2：単語数を数えるプログラム(word.l)
%{int charCount = 0; int wordCount = 0; int lineCount = 0; %}
%%
[^ \t\n]+ {wordCount++; charCount += yyleng; } \n {charCount++; lineCount++;}
. {charCount++;} %%
int main(void ) { yylex();
prinb("# of lines = %d, # of words = %d, # of chars = %d\n", lineCount, wordCount, charCount);
return 0; }
lex の主要な変数・関数
•
yyleng
(最後に)マッチしたトークンの長さ
•
yytext
(最後に)マッチしたトークン文字列
•
yylex()
字句解析の開始．アクションの中で
return を使うか，もしくは入力がなくなるまで
字句解析をする．
return を用いたとき，再度
yylex()を呼ぶと前回の続きから字句解析を再
開する
例
3：単語の認識(verb.l)
%{
/* Simple verb recogniton. */ %}
%%
[\t ]+ /* ignore whitespace */ is|am|are|were |
was {prinb("%s: is a verb\n", yytext); }
[a-‐zA-‐Z]+ {prinb("%s: is not a verb\n", yytext); } . | \n {ECHO; } %% int main(void){ yylex(); return 0; }
lex 知っておいた方がよいこと
•
lex のパタンは
一度だけしかマッチしない
• 合致するパタンが複数あるときは
マッチする長さ
がもっとも長いパタンのアクション
を実行する
例：
This is an island. を入力してみる．
•
｜
：特別なアクション．次のパタンと同じアクショ
ンを使用することを示す．
•
ECHO
: トークンの内容をそのまま出力する．ど
のパタンにもマッチしない入力に対するデフォル
トアクションとして使われる．
応用問題
(word-‐ext.l)
•
word.l を次のように拡張しよう
1. アルファベットのみをcharCountで数える．
2. 数字のみを数える変数を付け加える．
yaccの構造
定義部
%%
定義部の終了
規則部
%%
規則部の終了
ユーザ定義サブルーチン部
：
Cのプログラムを書く
形は
lexと同じ
yacc 注意点
•
yacc は
字句解析をされた後のトークン
を入力
とするので必ず字句解析ルーチンが必要．単
独では使えない
• 字句解析ルーチンを使うには
yaccの中から
yylex()関数を呼び出す（実際にはyyparse()関
数を呼ぶとその中で自動的に
yylex()を呼んで
くれる）
• 字句解析ルーチンは自作することも可能だが
普通は
lexを使う
yacc 定義部
• 初期設定を行う
• 使用するトークン名を
%token
の後に続けて書く
→ そうするとそれに対応したCのマクロ宣言が
作成され
*.tab.h が自動的に作成される
→ それをlexプログラムでもyaccプログラムでも
includeすることでトークンの受け渡しが可能にな
る．
•
%{
と
%}
で囲まれた部分はそのまま
*.tab.c にコ
ピーされる．必要なヘッダファイルの
includeなど
を行ったりする
yacc 規則部
• 文法規則を書く • 左辺 : 右辺; • 文法としては左辺が右辺に変換される（基本的に書き換え るだけ）．ただしそれに加えて右辺にアクションが書ける． • 左辺は非終端記号 • 左辺と右辺の区切りは : • 各ルールの区切りは; • lexと同様に | が使える • 右辺のアクションはその時点で実行される．Cのプログラム も書ける • 最初の規則の左辺がスタートシンボルとみなされるyacc ユーザ定義サブルーチン部
• ここで書いたものはすべて
C言語だと解釈さ
れ
*.tab.cにそのままコピーされる
•
yyparse() を呼び出さないと字句解析が実行さ
れない
ので
yaccがmainとなるプログラムを書
く場合はこの中で必ず
yyparse() を呼び出さ
なければならない
•
yyparse()の中でyylex()が呼ばれている.
例：「
I am」だけを受理する(sample.y)
%{
#include <stdio.h>
#include "sample.tab.h" extern int yylex();
extern int yyerror(); %}
%token SUBJECT PRED SPACE %%
statement
: SUBJECT SPACE PRED { prinb("OK!\n");} ;
%%
int main(void){ if (yyparse()) {
fprinb(stderr, "Error ! Error ! Error !\n"); return 1;
} }
例：「
I am」だけを受理する(sample.l)
%{
#include "sample.tab.h" /* lex for sample.y */ %}
%%
I {return SUBJECT;} am {return PRED;} [\t ]+ {return SPACE;} \n return 0;
. return yytext[0]; %%
yacc のコンパイルの仕方
> flex ファイル名
> bison -‐d ファイル名
> gcc *.tab.c lex.yy.c –o 実行ファイル名 –lfl -‐ly
• UNIXの標準は yacc だが，GNUの yacc相当であるbison を本 実験では使う．-‐d はヘッダファイルを出すためのオプション． ヘッダファイルに変更がなければつけなくていい．
sample.y をコンパイルして実行してみよう
> flex sample.l
> bison –d sample.y
yacc が対応できない規則1
• 二つ以上のトークンを先読みしないといけな
いような文法
例：
phrase : cart_animal AND CART
| work_animal AND PLOW ;
cart_animal : HORSE | GOAT;
work_animal : HORSE | OX;
(注：大文字はトークン） この例では例えば HORSE AND CART の HORSE が cart_animal から導出されたHORSEなのかwork_animalから導出された
HORSEなのかはHORSEの2トークン先のCARTを見ないと決定で きない
yacc が対応できない規則2
• 曖昧な文法
– 複数の構文木を作れるような文法を曖昧な文法
という
– 曖昧な文法に対して yacc はreduce/reduce
曖昧な文法の例
1
start : x
| y;
x : A;
y : A;
この時，
Aという入力に対して，これがx から導
出される
Aなのかyから導出されるAなのかはっ
きりしない．どちらも有りうる．
これが還元
/還元衝突 (reduce/reduce conflict)
曖昧な文法の例
2
start : x
| y R;
x : A R;
y : A;
ARという入力に対して，x から A R が導出され
るし，
yをAを考えてstartの規則に戻ってRとも考
えられる．どちらも有りうる．
これがシフト
/還元衝突 (shi|/reduce conflict)
lex から yacc に値を渡す方法
•
lex プログラムから yacc プログラムに値を渡すには
– lex プログラムのアクション部で return 値； とする．この 場合，型はデフォルトではint – lex プログラムで渡したい値をyylval変数に入れておく．こ の場合の型はデフォルトではint – yylvalの型は変更することができる（後述）．•
yacc プログラムで値を受け取るには
– 規則部のシンボルの値として受け取れる． $$ : 左辺のシンボルの値 $1 : 右辺一番左のシンボルの値 $2 : 右辺二番目のシンボルの値 …yylval の型
•
yylval のデフォルトの型は int
int の値が欲しければ何もしなくてよい
•
yylval はライブラリの中で宣言されているので，
これを使う
lexプログラムの宣言部にC言語と
して
extern int yylval;
加減算を行う計算機
(p-‐m.y)
%{
#include <stdio.h> #include "p-‐m.tab.h" extern int yylex(); extern int yyerror(); %} %token NUMBER %% statement : expression {prinb("= %d\n", $1);}; expression : expression '+' NUMBER {$$ = $1 + $3; } | expression '-‐' NUMBER {$$ = $1 -‐ $3; } | NUMBER {$$ = $1;}; %% int main(void) { if (yyparse()) { fprinb(stderr, "Error\n"); return 1; } }
加減算を行う計算機
(p-‐m.l)
%{
#include "p-‐m.tab.h" extern int yylval;
%} %%
[0-‐9]+ {yylval = atoi(yytext); return NUMBER; } [\t ] ; /* ignore whitespace */
\n return 0;
. return yytext[0]; %%
演習：四則演算
(arith.y)
•
p-‐m.y を拡張して乗除算と括弧も扱えるように
しよう
• 乗除算は加減算より優先される（先に実行さ
れる）ことに注意
• 括弧があると括弧の中を先に計算することに
注意
• 最初に文法を考える
演習：文法
• 数字と四則演算とかっこからなる算術式の文
法を書いてみよ
<算術式> ::= <算術式> <演算子> <因子> | <因子> <演算子> ::= + | - | * | / <因子> ::= <数> | (<算術式>)よくない例
(BNF
表記
)
：
算術式において乗除算は加減算より優先されることがこの 文法では実現できていない演習：文法
• 数字と四則演算とかっこからなる算術式の文
法を書いてみよ
<算術式> ::= <算術式> + <項> | <算術式> - <項> | <項> <項> ::= <項> * <因子> | <項> / <因子> | <因子 > <因子> ::= <数> | (<算術式>)正しい例
(BNF
表記
)
：
演習：四則演算
(arith.y)
• 文法の正しい例になるように
p-‐m.y を変更し四
則演算と括弧が使えるようにしよう
(lexプログラムはp-‐m.yと同じでよい）
• 応用：除算の時に
0で割っている場合にはエラー
メッセージをだして計算を行わないようにする
– ヒント：エラーが起こったことを知らせるには関数
yyerror()を使うのがよい
– 関数
yyerror()はデフォルトでは引数で与えた文字列
を
stderrに表示する
（独自に実装することも可能）
演習：実数
(arithr.l, arithr.y)
• これまで整数の四則演算を行っていたarith.yを実数
の四則演算を行うように変更しよう
•
lexプログラムを実数をトークンとするように変更する
•
lexプログラムからyaccプログラムへ渡す値も実数にな
る
– ヒント：lex プログラム yaccプログラムのどちらにも宣言部 でarithr.tab.hをincludeする前に
#define YYSTYPE double
を入れる（注：YYSTYPE はyylval の型） – arithr.tab.hを見て理解すること
変数を使えるようにする
•
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 を複数行読めるようにし，$が来たら終わるようにする • 各トークン，必要な非終端記号に型を指定すること
基本言語仕様
<プログラム> ::= <変数宣言部> <文集合> <変数宣言部> ::= <宣言文> <変数宣言部> | <宣言文> <宣言文> ::= 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; }
