計算機科学実験及演習3 (ソフトウェア) 大本 義正 馬谷 誠二.

Presentation on theme: "計算機科学実験及演習3 (ソフトウェア) 大本 義正 馬谷 誠二."— Presentation transcript:

1 計算機科学実験及演習3 (ソフトウェア) 大本 義正 馬谷 誠二

2 1. 概要

3 実験内容 Tiny Cコンパイラの作成 一人一つ作成 上位互換であれば言語を拡張してもよい 教科書・資料と異なる設計をしてもよい
yacc (bison) と lex (flex) を用いて作成 ターゲット言語はIAのアセンブリ言語 一人一つ作成 上位互換であれば言語を拡張してもよい 教科書・資料と異なる設計をしてもよい

4 この実験の目的・意義 プログラミングスキルの向上 コンパイラ作成を通してプログラムに対する 理解を深める
これまで学んだプログラミング技術の応用 ある程度大きいプログラムの作成 字句解析 (lexファイル)：50行 構文解析・構文木生成(yaccファイル)：400行 意味解析・識別子操作：200行 コード生成：550行 コンパイラ作成を通してプログラムに対する 理解を深める yacc/lexをマスターすることは重要でない 解らないことはTA・教員にどんどん訊く

5 Tiny C C言語のサブセット 型はint型のみ 制御構造は最低限のもの(if, while)だけ int fact(int n) {
追加してもかまわない(for, do-while, ...) int fact(int n) { if (n == 1) return 1; else return n * fact(n-1); }

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

7 コンパイル例 fact.tc main.c （このファイルはgccでコンパイル）
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)); }

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

9 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

10 実験の進め方 実験資料の課題1～8を順に解く 課題1, 2はレポートに書く必要なし 課題5は選択自由 課題7, 8が本実験の主要部分
費やす時間もこの部分が大きい 資料のコンパイラは教科書に沿った設計 教科書もよく読むこと 各課題の解答となるソースは残しておく 上書きすると元に戻せない

11 成績評価 レポート3回 報告会 成績 中間レポート2回 (課題3〜6) 最終レポート (課題7, 8) サンプルプログラムのコンパイルと実行
課題毎にソースを残し，パス名をレポートに明記 プログラムの解説 感想・要望 報告会 サンプルプログラムのコンパイルと実行 成績 コンパイラの完成度 レポートの出来（分かりやすい説明） メールでPDFを提出

12 その他の注意 出席を重視する 積極的にTA・教員に訊く 予習をしっかりと webページ 教員・TA宛メールアドレス
止むを得ない場合はできるだけ事前に連絡する 積極的にTA・教員に訊く 予習をしっかりと 予め資料を読み, 理解し, 方針を立てておく 演習時間は「実装・デバッグの時間」 webページ 教員・TA宛メールアドレス

13 2. 字句解析部の作成

14 lex (flex) 字句解析部 (Cのプログラム)を作成 lexへの入力：lexファイル lexの出力：Cファイル
字句構造を正規表現で定義 lexの出力：Cファイル 関数 yylex() を定義 生成される字句解析プログラムの本体 入力文字列から字句要素を切り出す “a = b+c;” → “ a”, “=”, “b”, “+”, “c”, “;” 字句要素はトークンとして構文解析部に渡される

15 lexファイルの例 Ｃのコード．字句解析プログラムの先頭にそのまま挿入される 定義 セクション 数字を表すマクロ digitの定義
%option noyywrap %{ #include "calc.tab.h" %} digit [0-9] %% {digit}+ { yylval = atoi(yytext); return INTEGER; } "-"|"+"|\n return *yytext; [ \t] ; /* スペース，タブは無視 */ . yyerror("Error: invalid character"); 定義 セクション ルール Cコード 数字を表すマクロ digitの定義 cf. #define noyywrapはおまじないと思え．

16 ルールセクションの基本構造 lexはルールから関数yylex()を生成 pattern1 action1
普通はトークンをyaccに渡すコードを記述 字句要素：切り出した文字列 トークン：字句要素を構文解析に適した形に変換したデータ lexはルールから関数yylex()を生成 入力からpatternに一致する最長の文字列を探す 見つかれば，対応するactionを実行

17 ルールセクション例 yaccにおけるトークン トークンの種類：識別子，整数定数… yylex()の返値
トークンの値：識別子の名前，整数値… 大域変数yylvalの値 トークンの値 字句解析の中断 ＆ トークンの種類を返す 切り出した字句要素 数字からなる１文字以上の文字列 - or + or 改行 [0-9]+ { yylval = atoi(yytext); return INTEGER; } “-”|“+”|”\n”　 return *yytext; [ \t] ;　/* スペース，タブは無視 */ . yyerror("Error: invalid character"); "while"など文字列でも可．パターンの順序に注意．

18 lexが出力するCファイルの内容 #include "calc.tab.h" … int yylex() {
yylval = atoi(yytext); return INTEGER; } /* Cコードセクションのコード */

19 3. 構文解析部の作成

20 yacc (bison) 構文解析部(Cプログラム)を生成 yaccへの入力：yaccファイル yaccの出力：Cファイルとヘッダファイル
BNFに似た記法で生成規則を記述 yaccの出力：Cファイルとヘッダファイル 関数yyparse() の定義 生成される構文解析プログラムの本体 yylexを用いてトークンを取得し，構文をチェック 抽象構文木を生成

21 yaccファイルの例 定義 %token INTEGER セクション %% program: /* empty */
ルール %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(); }

22 定義セクション 終端記号 INTEGER の定義 ASCII文字はそのまま終端記号になる 自動的に適当な整数値が割り振られる
%token INTEGER 終端記号 INTEGER の定義 自動的に適当な整数値が割り振られる yaccが出力するヘッダファイルで定義 ASCIIコードは避けられる ASCII文字はそのまま終端記号になる ’a’ ’b’ ’=’ ’<’ ’\n’ などなど

23 定義セクション（続き） Cコードを記述可能 yylval，終端記号，非終端記号の型として複数の型を許す 型を指定する方法 %{ … %}
yaccの出力ファイルの先頭にそのまま貼られる %union yylval，終端記号，非終端記号の型として複数の型を許す %union宣言しなければ，int型 型を指定する方法 yylval： yylval.(%unionのメンバ名) 非終端記号： %type <(メンバ名)> (記号) 終端記号： %token <(メンバ名)> (記号)

24 yaccファイルの例 %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(); } ルール セクション

25 ルールセクション nonterminal: rule1 action1 | rule2 action2 … ;
nonterminal: BNFの左辺に相当 rule: BNFの右辺に相当，構文規則を規定 action: nonterminalを還元するときに実行されるCコード 構文木生成コード インタプリタのコード など yaccはルールから関数 yyparse() を生成 LALR(1)構文解析 トークンを一つ得るために yylex() を一回呼出す yylex()の返値 (=トークンの種類) yylvalの値 (=トークンの値)

26 ルールセクション：rule トークンの種類 = 終端記号 ε program: /* empty */ 終端記号
| program expr '\n' { printf("%d\n", $2); } ; expr: INTEGER { $$ = $1; } | expr '+' INTEGER { $$ = $1 + $3; } | expr '-' INTEGER { $$ = $1 - $3; } 終端記号 非終端記号

27 lexファイル yaccファイル %{ #include "calc.tab.h" %} %% {digit}+ {
yylval = atoi(yytext); return INTEGER; } "-"|"+"|\n return *yytext; yaccファイル %token INTEGER %% program: /* empty */ | program expr '\n' { printf("%d\n", $2); } ; expr: INTEGER { $$ = $1; } | expr '+' INTEGER { $$ = $1 + $3; } | expr '-' INTEGER { $$ = $1 - $3; } 字句解析のアクションが返すトークンの種類が，構文解析では終端記号となる． 字句解析で calc.tab.hをインクルードすることでINTEGERが使える．

28 ルールセクション：action 終端記号・非終端記号は値を持つ 終端記号の値 = トークンの値 $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; } 還元されたexprの値 INTEGERの値 = yylvalの値 exprの値

29 値スタックと$$，$n yaccが持つ値スタックの要素へのアクセス 入力：7 - 3 yylval: yylex()の返値： 7 3
expr: INTEGER { $$ = $1; } | expr '+' INTEGER { $$ = $1 + $3; } | expr '-' INTEGER { $$ = $1 - $3; } ; トークンの値 トークンの種類 入力：7 - 3 yylval: yylex()の返値： 7 3 INTEGER '-' INTEGER ・7 - 3 yylvalの値 をpush INTEGER ・- 3 シフト expr ・– 3 還元 3 $1 $2 $3 pop してpush expr '–' ・3 シフト 7('-') expr '–' INTEGER ・ シフト 4 7 expr ・ 還元 値スタック

30 yaccが出力するCファイル Cコードセクションのコードは別ファイルに記述しても構わない #define INTEGER 257 …
yyparse() { } int yyerror(char *s) { … } main() { yyparse(); Cコードセクションのコードは別ファイルに記述しても構わない

31 4. 補足事項

32 makeのススメ 実行ファイル作成手順 bisonにより *.tab.c と *.tab.h を生成 flexにより lex.yy.c
gccにより*.tab.c, lex.yy.c 他必要なソースをコンパイル・リンク yaccファイルを変更したら，flexを実行しなければならない hoge.tab.c bison lexファイル (hoge.l) yaccファイル (hoge.y) flex lex.yy.c hoge.tab.h

33 Makefileの例 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) タブ文字

34 構文木 抽象構文木 Tiny Cプログラムの別の表現 優先順位，結合性，elseの結びつきが容易に読み取れる
+ * a b - c d e a * b + (c – d) + e

35 構文木の型 木のノードの型 nd tree型 = ndへのポインタ型 (nd *) typedef union nd { struct {
int op; } n; struct tp tp; struct tk tk; struct c c; } ノードの種類を示す （tp, tk, cに共通のメンバ） タプル＝子要素を持つノード 識別子ノード 整数定数ノード

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

37 共用体 u は st2 として再利用可 struct st1 { … }; struct st2 { … };
union un { struct st1 s1; struct st2 s2;}; union un *u = (union un *) malloc(sizeof(union un)); u->st1.??? = …; sizeof(union un)：s1 または s2 を格納するのに十分なサイズ u は st2 として再利用可

38 共用体（続き） struct st1 *s = (struct st1 *) malloc(sizeof(struct st1));
union un *u = (union un *)s; u->st1.??? = …; sizeof(struct st1) ≧ sizeof(struct st2) ? u は struct st2 型として再利用できるとは 限らない どちらの方法が望ましいか？ 用途・要求による メモリの使用量 vs. メモリの管理効率 malloc の実装法

39 yaccファイルでの%union指定 %union { int i; char *str; tree n; }
型treeの宣言を持つヘッダファイルを用意してyaccファイルの先頭でインクルード %token <str> Identifier %token <i> Constant %token IF ELSE WHILE… yylval.i = atoi(yytext); yylval.str = strdup(yytext); %type <n> program … トークンIdentifierの値は 文字列(char *)型 非終端記号programの値は tree型

40 構文木の表示 括弧で括った表示 木構造の形を忠実に反映した表示が可能 a + b + c
if (e1) if (e2) s1 else s2 = if (e1) { if (e2) s1 else s2 } (if e1 (if e2 s1 s2))

41 構文木の表示（続き） preorderの木の走査 課題6（構文木の表示） 葉でないノードの表示 表示の仕様は自由 ‘(’を表示 節の値を表示
子の値を再帰的に表示 ‘)’を表示 課題6（構文木の表示） 表示の仕様は自由 インデントなどはしなくても構わない + * a b - c d e

42 構文木の表示（続き） 構文の要素毎に表示ルーチンを用意 演算子の結合の優先順位 print_statement … 文の表示
print_expression … 式の表示 などなど 演算子の結合の優先順位 構文解析時に構文木に反映しているはずなので，表示側で考慮する必要はない

43 opt の扱い 1 a: bopt c d （b c d または c d にマッチ） ↓ a: b_opt c d ; b_opt:
　↓ a: b_opt c d ; b_opt: /* empty */ { $$ = NULL; } | b yaccのエラー「empty rule for typed nonterminal, and no action」が出る場合 /* empty */　に対するアクションを明示的に書く

44 opt の扱い 2 a: bopt c d ↓ a: bopt c d x: a | y ↓ a_aux: c d ; a: c d
　↓ a_aux: c d ; x: a_aux | b a_aux a: bopt c d 　↓ a: c d | b c d ;

45 opt の扱い まとめ どの方法が優れているかは一概には言えない（状況によって異なる） 可読性・記述性
アクションの可読性・記述性 conflictの問題 conflictが生じたら他の方法を試す bisonの-vオプションにより生成される*.outputファイルにより, conflictの原因を探る

46 5. Misc

47 ミニ補講 課題が難しくて困っている プログラミングスキル不足を感じている 人達を対象にTAが実施 週に1回， 1時間程度
対象人数： 10名前後 (x 2 or x 3?) 詳細は後日改めてお知らせします

48 C言語以外で演習するには その他： Ruby, OCaml, Haskell, … 演習資料の読み替えは自己責任 C++
flex, bisonがそのまま使えます Scheme, Common Lisp 課題6の結果を渡せばOK Java JFlex, Cupというツールがあります サンプル入力を用意してあるので参考に JRuby, Jython, Scala, Clojure, ... その他： Ruby, OCaml, Haskell, …

49 グループ分け 座席 実装言語の選択 入口 TA ミニ補講用モニタ