1.

Transcription

1 3 ( )

2 1.

3 n Tiny C n yacc (bison) lex (flex) n IA n n n

4 n n n (lex ) 50 (yacc ) n n yacc/lex TA

5 Tiny C n C n int n (if, while) int fact(int n) {! if (n == 1) return 1;! else return n * fact(n-1);! }! (for, do-while,...)

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

7 n fact.tc int fact(int n)! {!!if (n == 1) return 1;!!else return n * fact(n-1);! }! n main.c gcc #include <stdio.h>! main()! {!!printf("%d\n", fact(10));! }! n gcc stack layout / calling convention

8 % tcc fact.tc ; fact.asm を生成 % nasm f elf fact.asm ; fact.o を生成 % gcc o fact main.c fact.o! %./fact! ! ソースファイル (*.c) ソースプログラム アセンブリファイル (*.asm) アセンブリプログラム オブジェクトファイル (*.o) オブジェクトプログラム 実行形式プログラム TinyC コンパイラ (tcc) アセンブラ (nasm) リンカ (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 n 8 n 1, 2 n 5 n 7, 8 n n

11 n 3 メールで PDF を提出 n 2 ( 3 6) n ( 7, 8) n n n n n

12 n n n TA n n,, n n web n n TA n le3soft@kuis.kyoto-u.ac.jp

13 2.

14 lex (flex) n (C ) n lex lex n lex C yylex() a = b+c; a, =, b, +, c, ;

15 lex %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 定義セクション ルールセクション C コードセクション

16 n pattern1 action1 pattern2 action2 n pattern: n action: C yacc n lex yylex() n pattern n action

17 n yacc yylex() yylval トークンの値数字からなる1 文字以上の文字列切り出した字句要素 [0-9]+!{!!!!yylval = atoi(yytext);!!!!return INTEGER;!!!}! - + \n!return *yytext;! 字句解析の中断 [ \t]!; /* スペース, タブは無視 & */! - or + or 改行. yyerror("error: invalid トークンの種類を返す character");!

18 lex C #include "calc.tab.h"!! int yylex() {!!!!yylval = atoi(yytext);!!return INTEGER;!!! }! /* C コードセクションのコード */!

19 3.

20 yacc (bison) n (C ) n yacc yacc BNF n yacc C yyparse() yylex

21 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();! }! 定義セクション ルールセクション C コードセクション

22 %token INTEGER! n INTEGER n yacc ASCII n ASCII n a b = < \n

23 n %{ %} n n C %union yacc n yylval %union int n 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 ; n nonterminal: BNF n rule: BNF n action: nonterminal C n yacc yyparse() n LALR(1) n yylex() yylex() (= ) yylval (= )

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

27 lex ファイル %{! #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; }!!;!

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

29 n n yacc expr: INTEGER!!!{ $$ = $1; }! 入力 :7-3! expr '+' INTEGER!{ $$ = $1 + $3; }!! expr '-' INTEGER!{ $$ = $1 - $3; }!!;! yylval: トークンの値 73 yylex() の返値 : INTEGER '-' 7-3 yylvalの値 INTEGER - 3 シフトをpush expr 3 還元 3 expr ' ' 3 シフト pop して push expr ' ' INTEGER シフト 74 expr 還元 トークンの種類 7('-') 値スタック $3! $2! $1!

30 yacc C #define INTEGER 257!! yyparse() {!! }!! int yyerror(char *s) { }! main() {!!yyparse();! }! n C

31 4.

32 make n 1. bison *.tab.c *.tab.h 2. flex lex.yy.c 3. gcc *.tab.c, lex.yy.c yacc ファイルを変更したら,flex を実行しなければならない hoge.tab.c! yacc ファイル! (hoge.y)! bison! lex ファイル! (hoge.l)! hoge.tab.h! flex! lex.yy.c!

33 Makefile タブ文字 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 OBJS bar.tab.h: bar.y!!!$(yacc) $(YFLAGS) bar.y

34 n n Tiny C n else Tiny C + a * b + (c d) + e! * + - e! a! b! c! d!

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

36 n n n #include <stdlib.h>! typedef struct st {! } *st_p;! struct st! st_p p; /*!p->??? = /* st_p p = (st_p)malloc(sizeof(*p));!p->??? = /* OK */! foo() st_p p = (st_p)malloc(sizeof(*p));!!!!!/* free()!/* p foo() */! p

37 struct st1 { };! struct st2 { };! union un { struct st1 s1; struct st2 s2;};! n union un *u = (union un *)!!!!!!malloc(sizeof(union un));!!u->st1.??? = ;! n sizeof(union un) s1 s2 n u st2

38 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 malloc

39 yacc %union n union { int i; char *str; tree n; トークンIdentifierの値は tree yacc 文字列 (char *) 型 n %token <str> Identifier %token <i> Constant %token IF ELSE WHILE! n yylval.i = atoi(yytext); yylval.str = strdup(yytext);! n %type <n> program! 非終端記号 program の値は tree 型

40 n n n a + b + c! (+ (+ a b) c)! n if (e1) if (e2) s1 else s2! = if (e1) { if (e2) s1 else s2 }! (if e1 (if e2 s1 s2))

41 n preorder n ( ) n 6 n + + e! * - a! b! c! d!

42 n n print_statement n print_expression n n

43 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 n empty */

44 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!!;!

45 opt n n conflict n conflict bison -v *.output, conflict

46 5. Misc

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

48 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 その他 : Ruby, OCaml, Haskell,

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