1.

計算機科学実験及演習

3

(ソフトウェア)

大本 義正

馬谷 誠二

実験内容

n

 

Tiny C

コンパイラ

の作成

n 

yacc (bison) と lex (flex) を用いて作成

n 

ターゲット言語は

IAのアセンブリ言語

n

 

一人一つ作成

n

 

上位互換であれば言語を拡張してもよい

この実験の目的・意義

n 

プログラミングスキルの向上

n 

これまで学んだプログラミング技術の応用

n 

ある程度大きいプログラムの作成

•  字句解析 (lexファイル)：50行 •  構文解析・構文木生成(yaccファイル)：400行 •  意味解析・識別子操作：200行 •  コード生成：550行 n 

コンパイラ作成を通してプログラムに対する

理解を深める

n 

yacc/lexをマスターすることは重要でない

•  解らないことはTA・教員にどんどん訊く

Tiny C

n

 

C言語のサブセット

n 

型は

int型のみ

n 

制御構造は最低限のもの

(if, while)だけ

•

 

追加してもかまわない

(for, do-while, ...)

int fact(int n) {!

if (n == 1) return 1;!

else return n * fact(n-1);!

}!

Tiny Cプログラムのコンパイル

ソースプログラム ソースファイル(*.tc) アセンブリファイル(*.asm) アセンブリ プログラム オブジェクトファイル(*.o) TinyCコンパイラ アセンブラ (nasm) リンカ (ld, gcc) オブジェクト プログラム 実行形式 プログラム 他の オブジェクトファイル ライブラリファイル

コンパイル例

n 

fact.tc

n 

main.c （このファイルはgccでコンパイル）

n 

gccと同一の stack layout / calling convention

int fact(int n)! {!

!if (n == 1) return 1;!

!else return n * fact(n-1);! }! #include <stdio.h>! main()! {! !printf("%d\n", fact(10));! }!

コンパイル例（続き）

ソースファイル(*.c) ソースプログラム アセンブリファイル(*.asm) アセンブリ プログラム オブジェクトファイル(*.o) TinyCコンパイラ (tcc) アセンブラ (nasm) リンカ (ld, gcc) オブジェクト プログラム 実行形式 プログラム 他のオブジェクトファイル ライブラリファイル % tcc fact.tc ; fact.asm を生成 % nasm –f elf fact.asm ; fact.o を生成

% gcc –o fact main.c fact.o! % ./fact!

Tiny Cコンパイラの出力

（テキストファイル）

fact.asm:� GLOBAL fact!

fact!push!ebp!

!mov !ebp, esp!

!cmp !dword [8+ebp], 1! !jne !L2!

!mov !eax, 1! !jmp !L1!

L2 !mov !eax, [8+ebp]! !sub !eax, 1! !push!eax! !call!fact! !add !esp, 4! !imul!eax, [8+ebp]! L1 !pop !ebp! !ret!

実験の進め方

n 

実験資料の課題1∼

8を順に解く

n 

課題

1, 2はレポートに書く必要なし

n 

課題

5は選択自由

n 

課題

7, 8

が本実験の主要部分

•  費やす時間もこの部分が大きい n 

資料のコンパイラは教科書に沿った設計

•  教科書もよく読むこと n 

各課題の解答となるソースは残しておく

•  上書きすると元に戻せない

成績評価

n 

レポート

3回

n 

中間レポート

2回 (課題3∼6)

n 

最終レポート

(課題7, 8)

•  課題毎にソースを残し，パス名をレポートに明記 •  プログラムの解説 •  感想・要望 n 

報告会

n 

サンプルプログラムのコンパイルと実行

n 

成績

n 

コンパイラの完成度

n 

レポートの出来（分かりやすい説明）

メールで_PDFを提出

その他の注意

n 

出席を重視する

n 

止むを得ない場合はできるだけ事前に連絡する

n 

積極的に

TA・教員に訊く

n 

予習をしっかりと

n 

予め資料を読み

, 理解し, 方針を立てておく

n 

演習時間は「実装・デバッグの時間」

n 

webページ

n 

http://ecs.kuis.kyoto-u.ac.jp/isle/le3b/

n 

教員・

TA宛メールアドレス

n 

[email protected]

lex (flex)

n

 

字句解析部

(Cのプログラム)を作成

n 

lexへの入力：lexファイル

•

 

字句構造を正規表現で定義

n 

lexの出力：Cファイル

•

 

関数

yylex()

を定義

•  生成される字句解析プログラムの本体 •  入力文字列から字句要素を切り出す “a = b+c;” → “ a”, “=”, “b”, “+”, “c”, “;” •  字句要素はトークンとして構文解析部に渡される

%option noyywrap! %{! #include "calc.tab.h"! %}! digit! ![0-9]! %%! {digit}+ !{! ! ! !yylval = atoi(yytext);! ! ! !return INTEGER;! ! !}! "-"|"+"|\n !return *yytext;! [ \t] !; /* スペース，タブは無視 */

. _{yyerror("Error: invalid character");!}

%%!

lexファイルの例

定義 セクション ルール セクション Cコード セクション Ｃのコード．字句解析プログラムの 先頭にそのまま挿入される 数字を表すマクロ digitの定義 cf. #define

ルールセクションの基本構造

n 

pattern1 action1

pattern2 action2 …

n  pattern: 字句構造の正規表現 n  action: 字句要素を切り出したときに実行されるコード •  Cで記述 •  普通はトークンをyaccに渡すコードを記述 •  字句要素：切り出した文字列 •  トークン：字句要素を構文解析に適した形に変換したデータ n 

lexはルールから関数yylex()を生成

n  入力からpatternに一致する最長の文字列を探す n  見つかれば，対応するactionを実行

n 

yaccにおけるトークン

•

 

トークンの

種類

：識別子，整数定数

…

yylex()の返値

•

 

トークンの

値

：識別子の名前，整数値

…

大域変数

yylvalの値

[0-9]+ !{! ! ! !yylval = atoi(yytext);! ! ! !return INTEGER;! ! !}! “-”|“+”|”\n”　 !return *yytext;! [ \t] !;　/* スペース，タブは無視 */!

. yyerror("Error: invalid character");!

数字からなる１文字以上の文字列 - or + or 改行

ルールセクション例

トークンの値 字句解析の中断 ＆ トークンの種類を返す 切り出した字句要素

lexが出力するCファイルの内容

#include "calc.tab.h"!

…!

int

yylex()

{!

!…!

!yylval = atoi(yytext);!

!return INTEGER;!

!…!

}!

/* Cコードセクションのコード */!

…

yacc (bison)

n

 

構文解析部

(Cプログラム)を生成

n 

yaccへの入力：yaccファイル

•

 

BNFに似た記法で生成規則を記述

n 

yaccの出力：Cファイルとヘッダファイル

•

 

関数

yyparse()

の定義

•  生成される構文解析プログラムの本体 •  yylexを用いてトークンを取得し，構文をチェック •  抽象構文木を生成

定義 セクション Cコード セクション ルール セクション %token INTEGER! %%! program:! !/* empty */!

!| program expr '\n' !{ printf("%d\n", $2); }!

!;! expr:! !INTEGER ! ! !{ $$ = $1; }! !| expr '+' INTEGER !{ $$ = $1 + $3; }! !| expr '-' INTEGER !{ $$ = $1 - $3; }! !;! %%! int yyerror(char *s) { … }! main() {! !yyparse();! }!

yaccファイルの例

定義セクション

n

 

終端記号 INTEGER の定義

n 

自動的に適当な整数値が割り振られる

•

 

yaccが出力するヘッダファイルで定義

•

 

ASCIIコードは避けられる

n

 

ASCII文字はそのまま終端記号になる

n 

’a’ ’b’ ’=’ ’<’ ’\n’ などなど

%token INTEGER!

定義セクション（続き）

n  %{ … %} n 

Cコードを記述可能

•  yaccの出力ファイルの先頭にそのまま貼られる n  %union n 

yylval，終端記号，非終端記号の型として複数の型

を許す

•  %union宣言しなければ，int型 n 

型を指定する方法

•  yylval： yylval.(%unionのメンバ名) •  非終端記号： %type <(メンバ名)> (記号) •  終端記号： %token <(メンバ名)> (記号)

%token INTEGER!

%%!

program:!

!/* empty */!

!| program expr '\n' !{ printf("%d\n", $2); }!

!;! expr:! !INTEGER ! ! !{ $$ = $1; }! !| expr '+' INTEGER !{ $$ = $1 + $3; }! !| expr '-' INTEGER !{ $$ = $1 - $3; }! !;! %%! int yyerror(char *s) { … }! main() {! !yyparse();! }! ルール セクション

yaccファイルの例

ルールセクション

nonterminal: rule1 action1

| rule2 action2

…

;

n  nonterminal: BNFの左辺に相当 n  rule: BNFの右辺に相当，構文規則を規定 n  action: nonterminalを還元するときに実行されるCコード •  構文木生成コード •  インタプリタのコード など n 

yaccはルールから関数

yyparse()

を生成

n  LALR(1)構文解析 n  トークンを一つ得るために yylex() を一回呼出す •  yylex()の返値 (=トークンの種類) •  yylvalの値 (=トークンの値)

ルールセクション：

rule

n

 

トークンの種類

= 終端記号

program:!

!/* empty */!

!| program expr '\n'! !{ printf("%d\n", $2); }! !;! expr:! !INTEGER ! ! ! !{ $$ = $1; }! !| expr '+' INTEGER ! !{ $$ = $1 + $3; }! !| expr '-' INTEGER ! !{ $$ = $1 - $3; }! !;! 終端記号 終端記号 ε 非終端記号

%{! #include "calc.tab.h"! %}! %%! {digit}+ ! !{! ! ! ! yylval = atoi(yytext);! ! ! ! return INTEGER;! ! ! !}! "-"|"+"|\n ! !return *yytext;! %token INTEGER! %%! program:! !/* empty */!

!| program expr '\n' !{ printf("%d\n", $2); }!

!;! expr:! !INTEGER ! ! !{ $$ = $1; }! !| expr '+' INTEGER !{ $$ = $1 + $3; }! !| expr '-' INTEGER !{ $$ = $1 - $3; }! !;! lexファイル� yaccファイル�

ルールセクション：

action

n

 

終端記号・非終端記号は値を持つ

•

 

終端記号の値

= トークンの値

•

 

$n (n=1,2,3…) でアクセス可能

program:! !/* empty */!

!| program expr '\n'! !{ printf("%d\n", $2); }! !;! expr:! !INTEGER ! ! ! !{ $$ = $1; }! !| expr '+' INTEGER ! !{ $$ = $1 + $3; }! !| expr '-' INTEGER ! !{ $$ = $1 - $3; }! !;! INTEGERの値� = yylvalの値 exprの値� 還元された exprの値�

7('-') n 

yaccが持つ値スタックの要素へのアクセス

値スタックと$$

，

$

_n

expr ・ 還元 3 入力：7 - 3 ・7 - 3 INTEGER ・- 3 シフト expr ・– 3 還元 expr '_–' ・3 シフト expr '–' INTEGER ・ シフト _{7 4} yylvalの値 をpush 値スタック yylex()の返値：

yylval: _{7 3} INTEGER INTEGER '-'

pop して push トークンの値 トークンの種類 $1! $2! $3! expr: INTEGER ! ! !{ $$ = $1; }! !| expr '+' INTEGER !{ $$ = $1 + $3; }! !| expr '-' INTEGER !{ $$ = $1 - $3; }! !;!

#define INTEGER 257! …! yyparse() {! …! }! ! int yyerror(char *s) { … }! main() {! !yyparse();! }!

yaccが出力するCファイル

n 

Cコードセクションのコードは別ファイルに記

述しても構わない

makeのススメ

n 

実行ファイル作成手順

1. 

bisonにより *.tab.c と *.tab.h を生成

2. 

flexにより lex.yy.c

3. 

gccにより*.tab.c, lex.yy.c 他必要なソースをコン

パイル・リンク

bison! flex! hoge.tab.h! hoge.tab.c! lex.yy.c! lexファイル! (hoge.l)! yaccファイル! (hoge.y)! yaccファイルを変更したら，flexを実行しなければならない�

Makefileの例

n 

OBJS

のリストの並び順によっては以下も必要

bar.tab.h: bar.y!

! !$(YACC) $(YFLAGS) bar.y YACC=bison!

YFLAGS= -d! LEX=flex! LFLAGS=!

OBJS = bar.tab.o lex.yy.o! all: a.out!

bar.tab.c: bar.y!

!$(YACC) $(YFLAGS) bar.y! lex.yy.c: foo.l bar.tab.h!

!$(LEX) $(LFLAGS) foo.l! a.out: $(OBJS)!

!$(CC) –o $@ $(OBJS)! タブ文字

構文木

n

 

抽象構文木

n 

Tiny Cプログラムの別の表現

n 

優先順位，結合性，

elseの結びつきが容易に

読み取れる

•

 

元の

Tiny Cプログラムの場合，（複雑な）生成規

則と（複雑な）構文解析が必要

+ + * a! b! - c! d! e! a * b + (c – d) + e!

構文木の型

n 

木のノードの型

nd

n 

tree型 = ndへのポインタ型 (nd *)

typedef union nd {! !struct {! ! !int op;! !} n;! !struct tp tp;! !struct tk tk;! !struct c c;
 }� ノードの種類を示す （tp, tk, cに共通のメンバ）! タプル＝子要素を持つノード! 識別子ノード! 整数定数ノード!

構造体のメモリ割当て

n  st_p p; /* ポインタ変数のメモリ割り当て */ !p->??? = … /* 不可 */ n  st_p p = (st_p)malloc(sizeof(*p)); !p->??? = … /* OK */! n  foo() { st_p p = (st_p)malloc(sizeof(*p));! ! ! ! !/* free()するまで有効 */ … _{!/* ただし，pはfoo()内でのみ有効 */!} } ! #include <stdlib.h>! typedef struct st {
 …! } *st_p;! � struct st! p�

共用体

n  union un *u = (union un *)! ! ! ! ! !malloc(sizeof(union un));! !u->st1.??? = …;! n  sizeof(union un)

：s1 または s2 を格納するの

に十分なサイズ

n 

u は st2 として再利用可

struct st1 { … };! struct st2 { … };!

共用体（続き）

n  struct st1 *s = (struct st1 *)! ! ! ! !malloc(sizeof(struct st1));! !union un *u = (union un *)s;! !u->st1.??? = …;! n  sizeof(struct st1) sizeof(struct st2)

?

n  u

は

struct st2

型として再利用できるとは

限らない

n 

どちらの方法が望ましいか？

n  用途・要求による n  メモリの使用量 vs. メモリの管理効率 • malloc の実装法

yaccファイルでの%union指定

n  %union {
 int i;
 char *str; tree n; } •  型treeの宣言を持つヘッダファイルを用意してyaccファイルの先 頭でインクルード n  %token <str> Identifier


%token <i> Constant


%token IF ELSE WHILE…!

n  yylval.i = atoi(yytext);
 yylval.str = strdup(yytext);! n  %type <n> program …! トークンIdentifierの値は 文字列_{(char *)型} 非終端記号programの値は tree型

構文木の表示

n

 

括弧で括った表示

n 

木構造の形を忠実に反映した表示が可能

n 

a + b + c!

•

 (+ (+ a b) c)!

n 

if (e1) if (e2) s1 else s2!

= if (e1) { if (e2) s1 else s2 }!

構文木の表示（続き）

n

 

preorderの木の走査

n 

葉でないノードの表示

•

 

‘(’を表示

•

 

節の値を表示

•

 

子の値を再帰的に表示

•

 

‘)’を表示

n

 

課題

6（構文木の表示）

n 

表示の仕様は自由

•

 

インデントなどはしなくても構わない

+ + * a! b! - c! d! e!

構文木の表示（続き）

n

 

構文の要素毎に表示ルーチンを用意

n 

print_statement … 文の表示

n 

print_expression … 式の表示 などなど

n

 

演算子の結合の優先順位

n 

構文解析時に構文木に反映しているはずなの

で，表示側で考慮する必要はない

opt

の扱い

1

a: b_opt c d （b c d または c d にマッチ）  ↓ a:! !b_opt c d! !;! b_opt:! !/* empty */ !{ $$ = NULL; }! |!b! !;!

n  yaccのエラー「empty rule for typed nonterminal, and no

action」が出る場合

opt

の扱い

2

a: b

_opt

c d

 ↓

!

a: c d!

!| b c d!

!;!

a: b

_opt

c d

x: a

| y

�↓�

a_aux: c d!

!

! ;!

x: a_aux!

!| b a_aux!

!| y!

!;!

opt

の扱い まとめ

n

 

どの方法が優れているかは一概には言え

ない（状況によって異なる）

n 

可読性・記述性

•

 

アクションの可読性・記述性

•

 

conflictの問題

n 

conflictが生じたら他の方法を試す

•

 

bisonの-vオプションにより生成される*.outputフ

ァイルにより

_{, conflictの原因を探る}

ミニ補講�

n

 

課題が難しくて困っている

n

 

プログラミングスキル不足を感じている

人達を対象にTAが実施

n

 

週に1回， 1時間程度

n

 

対象人数： 10名前後 (x 2 or x 3?)

n

 

詳細は後日改めてお知らせします

C

言語以外で演習するには�

n 

演習資料の読み替えは自己責任

n 

C++

n  flex, bisonがそのまま使えます

n 

Scheme, Common Lisp

n  課題6の結果を渡せばOK�

n 

Java

n  JFlex, Cupというツールがあります

•  サンプル入力を用意してあるので参考に

n  JRuby, Jython, Scala, Clojure, ...

グループ分け�

n

 

座席

n

 

実装言語の選択�

TA ミニ補講用モニタ 入口