gcc C C tcc lex yacc flex bison [ ] Tiny C 2 Lex [ 2.6 ] 2.1 lex yacc [ ] lex flex yacc bison yacc yyparse() C yyparse() yylex() yylex() yylex() flex

3 1 C Tiny C Tiny C int if while Tiny C 4 C Tiny C % cat test.tc int f(int x) while(x > 1) x = x - 2; return x; Tiny C NASM [3] tcc C % tcc < test.tc GLOBAL f f push ebp mov ebp, esp L1 mov eax, [ebp+8] cmp eax, 1 setg al movzx eax, al cmp eax, 0 je L2 mov eax, [ebp+8] sub eax, 2 mov [ebp+8], eax jmp L1 L2 mov eax, [ebp+8] mov esp, ebp pop ebp ret 1

gcc C C tcc lex yacc flex bison [ ] Tiny C 2 Lex [ 2.6 ] 2.1 lex yacc [ ] lex flex yacc bison yacc yyparse() C yyparse() yylex() yylex() yylex() flex *1 2.2 lex calc.l %option noyywrap % int yylval; % digit [0-9] %% digit+ yylval = atoi(yytext); printf("int = %d\n", yylval); "+" "*" printf("opr = %s\n", yytext); [ \t\n] ; /* */. ; %% main() *1 yacc C yylex() 2

yylex(); lex flex yylex() lex.yy.c % flex calc.l % gcc -o calc lex.yy.c % cat sample 1*23+456 %./calc < sample INT = 1 OPR = * INT = 23 OPR = + INT = 456 2.3 lex lex calc.l 3 %% 2.3.1 % % lex.yy.c name definition name calc.l digit digit ([0-9]) 2.3.2 2 pattern action pattern 1 action pattern C yylex() pattern lex action yytext yytext action yylex() pattern yylex() 3

1 pattern pattern abc abc abc* ab, abc, abcc, abccc,... abc+ abc, abcc, abccc,... a(bc)+ abc, abcbc, abcbcbc,... a(bc)? a, abc [abc] a, b, c [a-z] a, b, c,..., x, y, z [a\-z] a, -, z [-az] -, a, z [A-Za-z0-9]+ 1 [ \t\n]+ 1 whitespace [ˆab] a b [aˆb] a, ˆ, b [a b] a,, b a b a b "[a-z]+" [a-z]+. newline 2.3.3 C lex.yy.c 2.4 calc.l yacc etc. yacc yylval yylex() yacc ASCII char yacc yacc lex yylex() yacc yylval return return yylex() yylex() yylex() 4

int calc.l yacc Integer calc.tab.h yylex() lex %option noyywrap % #include "calc.tab.h" % digit [0-9] %% digit+ yylval = atoi(yytext); return Integer; "+" "*" return *yytext; [ \t\n] ; /* */. yyerror("error: invalid character"); %% yylval Integer +, * yylval yyerror() yylex() C 3 Yacc [ 4.4 4.5.3 4.6.3 ] 3.1 2 calc.l yacc program: expression expression: multiplicative-expr multiplicative-expr + expression multiplicative-expr: constant constant * multiplicative-expr program yacc calc.y 5

*2 % #include <stdio.h> % %token Integer %% program: expr printf("%d\n", $1); ; expr: mult_expr $$ = $1; mult_expr + expr $$ = $1 + $3; ; mult_expr: Integer $$ = $1; Integer * mult_expr $$ = $1 * $3; ; %% int yyerror(char *s) fprintf(stderr, "%s\n", s); return 0; main() yyparse(); bison calc.tab.h C calc.tab.c calc.tab.h lex calc.l bison -d % bison -d calc.y % flex calc.l % gcc -o calc lex.yy.c calc.tab.c % cat sample 1+2*3+4 %./calc < sample 11 [ ] 1+2*3+4 3.2 yacc yacc yacc lex %% 3 *2 yacc mult-expr - 6

3.2.1 lex % % C calc.y %token Integer Integer %token yacc ASCII int yacc calc.tab.h lex Integer lex [ ] Integer yacc yylex() yacc c c c %token yacc ASCII 2 "+" "*" return *yytext; yacc + * 3.2.2 2 nonterminal: rule 1 action 1 rule 2 action 2 ; nonterminal BNF ε rule i rule i c action i nonterminal C / rule i A: B... $1... C... $3... A: B X C... $3... X:... $0... $n X rule yacc LALR(1) 1-2+3 2 lex expr: 7

Integer $$ = $1; expr + Integer $$ = $1 + $3; expr - Integer $$ = $1 - $3; ; 1-2+3 Integer -2+3 expr -2+3 expr- 2+3 expr-integer +3 expr +3 expr+ 3 expr+integer expr $$ $n rule i n n $n yylval expr: expr + Integer $$ = $1 + $3; ; expr $1 Integer $3 expr expr $3 Integer yylval 2 yylex() yylval 3.2.3 C yacc C yacc C yyerror() 1 calc.l calc.y % bison -d calc.y % flex calc.l % gcc -o calc calc.tab.c lex.yy.c % cat sample 1+2*3+4 %./calc < sample 11 2 1 yacc expr expr: mult_expr $$ = $1; mult_expr + expr $$ = $1 + $3; mult_expr - expr $$ = $1 - $3; 8

; 1-2-3 [ ] (1-2)-3 3 Tiny C else C if identifier _ constant lex yylval program: external-declaration program external-declaration external-declaration: declaration function-definition declaration: int declarator-list ; declarator-list: declarator declarator-list, declarator declarator: identifier function-definition: int declarator ( parameter-type-list opt ) compound-statement parameter-type-list: parameter-declaration parameter-type-list, parameter-declaration parameter-declaration: int declarator statement: ; expression ; compound-statement if ( expression ) statement if ( expression ) statement else statement while ( expression ) statement return expression opt ; compound-statement: declaration-list opt statement-list opt declaration-list: declaration 9

declaration-list declaration statement-list: statement statement-list statement expression: assign-expr expression, assign-expr assign-expr: logical-or-expr identifier = assign-expr logical-or-expr: logical-and-expr logical-or-expr logical-and-expr logical-and-expr: equality-expr logical-and-expr && equality-expr equality-expr: relational-expr equality-expr == relational-expr equality-expr!= relational-expr relational-expr: add-expr relational-expr < add-expr relational-expr > add-expr relational-expr <= add-expr relational-expr >= add-expr add-expr: mult-expr add-expr + mult-expr add-expr - mult-expr mult-expr: unary-expr mult-expr * unary-expr mult-expr / unary-expr unary-expr: postfix-expr - unary-expr postfix-expr: primary-expr identifier ( argument-expression-list opt ) primary-expr: identifier constant ( expression ) argument-expression-list: assign-expr argument-expression-list, assign-expr 10

lex : %option noyywrap %option yylineno % #include "filename.tab.h" % %% %% yacc : % % %error_verbose %token Integer Identifer... %% program: %% extern int yylineno; int yyerror(char *s) fprintf(stderr, "%d: %s\n", yylineno, s); return 0; main() yyparse(); conflict yacc % bison -d calc.y calc.y contains 1 shift/reduce conflict. shift/reduce conflict reduce/reduce conflict 2 yacc shift/reduce conflict 3 else if-else else else if 2 C if else if conflict reduce/reduce conflict yacc reduce/reduce conflict conflict yacc (bison) -v filename.output 4 3 11

: % cat test.tc int fact(int x) int z; z = 1; while (x >= 1) z = z * x; x = x - 1; return z; %./tcc < test.tc % 5 [ ] yacc error 3 4 error shift/reduce conflict reduce/reduce conflict 4 (Syntax tree) [ 4.1 ] (syntax tree) 4.1 N (N-tuple) [ ] yacc lex yacc lex : typedef struct c /* constant node */ int op; int v; *constant; 12

typedef struct tk /* token node */ int op; char *name; *token; typedef struct tp /* n-tuple (n=4) */ int op; union nd *a[4]; *tuple; typedef union nd /* tree */ struct int op; n; struct tp tp; struct tk tk; struct c c; *tree; : tree make_tuple(int, tree, tree, tree, tree); tree make_token_node(char *); tree make_constant_node(int); struct tp a op int union nd op C op n op t tree switch(t->n.op) case Integer:...... case Identifier:......... op Integer + op CONS yacc %token [ ] filename.tab.h N int f(int x, int y) int a, b, c; statement-list statement 13

FUNDEF INT CONS CMPD_STM Identifier INT INT INT CONS "f" Identifier Identifier CONS statement_list statement "x" "y" CONS Identifier Identifier Identifier "c" "a" "b" 1 1 N op a[n] N 4 NULL CONS 2 Tiny C external-declaration program CONS CONS 2 program program external-declaration CONS program CONS statement statement-list CONS 4.2 3 add-expr add_expr: mult_expr $$ = $1; add_expr + mult_expr $$ = make_tuple( +, $1, $3, NULL, NULL); add_expr - mult_expr $$ = make_tuple( -, $1, $3, NULL, NULL); ; yylval yacc $$ $n int YYSTYPE #define YYSTYPE int YYSTYPE yacc % % add_expr tree tree 14

% #define YYSTYPE tree % tree Identifier Integer $1 char * int primary_expr: Identifier $$ = make_token_node($1); Integer $$ = make_constant_node($1); ( expression ) $$ = $2; ; add_expr YYSTYPE %union %union YYSTYPE %union yylval %union int i; char *str; tree n; %union yacc yacc /* add_expr mult_expr tree */ %type <n> add_expr mult_expr yacc /* Identifier char * */ %token <str> Identifier lex yylval yylval.i = atoi(yytext); /* yylval int */ yylval.str = strdup(yytext); /* yylval char * */ [ ] identifier yylval.str yytext yylval.str yytext char *strdup(char *) *3 *3 string.h 15

4.3 program main: program ; if (yynerrs == 0) print_program($1); yynerrs yacc print_program() void print_program(tree p) if (p->n.op!= CONS) print_external_declaration(p); printf("\n"); else print_program(p->tp.a[0]); print_external_declaration(p->tp.a[1]); printf("\n"); 6 3 5 3 expression % cat test1.tc int gcd(int a, int b) if (a == b) return a; else if (a > b) return gcd(a-b, b); else return gcd(a, b-a); %./tcc < test1.tc ((int gcd) ((int a)(int b)) ( (IF (== a b) (RETURN a) (IF (> a b) (RETURN (FCALL gcd (- a b) b)) (RETURN (FCALL gcd a (- b a))) ) ) )) 16

[ ] 5 [ 5 ] 6... Tiny C int yacc 5.1 Tiny C [1] 5.4 struct tk token typedef struct tk int op; struct tk *next; char *name; int lev; enum FRESH, VAR, FUN, PARM, UNDEFFUN kind; int offset; *token; 5.1.1 lev lev 0 1 2 17

3 int cur_lev make_token_node() cur_lev lev cur_lev (compound-statement) 1 1 compound_statement: cur_lev++; declaration_list statement_list cur_lev--; ; [ ] $n n declaration_list $3 5.1.2 kind kind FRESH: make_token_node() VAR: FUN: PARM: UNDEFFUN: VAR C Tiny C Tiny C kind FUN 5.1.3 offset offset ; ebp 6.5 5.2 token 5.4(c) 2 symtab token token make_token_node() 3 1 cur_lev-- 18

symtab Identifier Identifier Identifier Identifier Identifier y x foo 2 1 0 0 0 VAR PARM FUN -4 8 1 2 5.4(c) symtab Identifier Identifier Identifier Identifier x foo 1 0 0 0 Identifier PARM FUN 8 1 y 2 FRESH symtab Identifier Identifier Identifier Identifier Identifier y x foo 2 1 0 0 0 FRESH PARM FUN 8 1 3 2 symtab / tree lookup_sym(char *) tree NULL lookup_sym() if (!(yylval.n = lookup_sym(yytext))) yylval.n = make_token_node(yytext); return Identifier; lookup_sym() tree Identifier char * 19

5.3 *4 lookup_sym 5.3.1 kind FRESH kind VAR 0 kind VAR kind VAR *5 kind VAR make_decl() declarator-list make_decl() : tree make_decl(tree n) switch (n->tk.kind) case VAR: /* */ if (n->tk.lev == cur_lev) /* */ error("redeclaration of %s ", n->tk.name); n = make_token_node(n->tk.name); break; case FUN: /* */ case UNDEFFUN: /* */ if (n->tk.lev == cur_lev) /* */ error(" %s redeclared as different kind of symbol", n->tk.name); n = make_token_node(n->tk.name); break; *4 *5 20

case PARM: /* */ warn("declaration of %s shadows a parameter", n->tk.name); n = make_token_node(n->tk.name); break; case FRESH: break; n->tk.kind = VAR; return n; make_decl() : declarator_list: declarator $$ = make_decl($1); /* $1 yylval.n */ error() warn() #include <stdio.h> #include <stdarg.h> int semnerrs; extern int yylineno; void error(char *fmt,...) va_list argp; va_start(argp, fmt); semnerrs++; fprintf(stderr, "%d: ", yylineno); vfprintf(stderr, fmt, argp); fprintf(stderr, "\n"); va_end(argp); void warn(char *fmt,...) va_list argp; va_start(argp, fmt); fprintf(stderr, "%d: warning: ", yylineno); vfprintf(stderr, fmt, argp); fprintf(stderr, "\n"); va_end(argp); error() warn() semnerrs semnerrs 1 error() warn() warn() make_decl() make_token_node() 21

5.3.2 1 tree make_parm_decl(tree n) switch (n->tk.kind) case VAR: case FUN: case UNDEFFUN: n = make_token_node(n->tk.name); break; case PARM: error("redeclaration of %s ", n->tk.name); return n; case FRESH: break; n->tk.kind = PARM; return n; 5.3.3 0 tree make_fun_def(tree n) switch (n->tk.kind) case VAR: error(" %s redeclared as different kind of symbol", n->tk.name); break; case FUN: error("redefinition of %s ", n->tk.name); break; case UNDEFFUN: case FRESH: n->tk.kind = FUN; break; return n; 5.3.4 lookup_sym() 22

kind FRESH kind VAR ref_var() ref_var() : tree ref_var(tree n) switch (n->tk.kind) case VAR: case PARM: break; case FUN: case UNDEFFUN: error("function %s is used as variable", n->tk.name); break; case FRESH: error(" %s undeclared variable", n->tk.name); n->tk.kind = VAR; /* */ break; return n; ref_var() : primary_expr: Identifier $$ = ref_var($1); 5.3.5 0 globalize_sym() 4 ref_fun() : tree ref_fun(tree n) switch (n->tk.kind) casevar: case PARM: error("variable %s is used as function", n->tk.name); break; case FUN: 23

symtab Identifier Identifier Identifier Identifier Identifier Identifier z 3 VAR -8 f 2 UNDEFFUN -1 y x foo 2 1 0 0 VAR -4 PARM 8 FUN 1 symtab Identifier Identifier Identifier Identifier Identifier Identifier z 3 VAR -8 y x foo 2 1 0 0 VAR -4 PARM 8 FUN 1 f 0 UNDEFFUN -1 4 case UNDEFFUN: break; case FRESH: warn(" %s undeclared function", n->tk.name); n->tk.kind = UNDEFFUN; if (n->tk.lev > 0) globalize_sym(n); break; return n; ref_fun() : postfix_expr Identifier ( opt_argument_expression_list ) ref_fun($1) 7 6 Tiny C 6.3 6.4.1 [ ] 24

: main: program ; symtab = NULL; cur_lev = 0; if (yynerrs == 0 && semnerrs == 0) print_program($2); % cat test.c int x; int f(int x, int y) int x; int x, y; x+y; int x, z; x+y+z; int w; x+y+w; x+y; int g(int y) int z; f(x, y); g(z); %./tcc < test.c 4: warning: declaration of x shadows a parameter 6: warning: declaration of y shadows a parameter (int x:0) ((int f:0) ((int x:1:8)(int y:1:12)) ( (int x:2:-4) ( (int x:3:-8 y:3:-12) (+ x:3 y:3) ( (int x:4:-16 z:4:-20) (+ (+ x:4 y:3) z:4) ) ) ( (int w:3:-8) (+ (+ x:2 y:1) w:3) ) (+ x:2 y:1) )) 25

((int g:0) ((int y:1:8)) ( (int z:2:-4) (FCALL f:0 x:0 y:1) (FCALL g:0 z:2) )) [ ] 6 6 NASM [ 6 ] Pentium NASM (Netwide Assembler)[3] NASM [1] p. 160 foo NASM GLOBAL foo foo push ebp mov ebp, esp sub esp, 4 mov eax, [ebp+8] imul eax, [ebp+8] mov [ebp-4], eax mov eax, [ebp-4] add eax, 2 mov esp, ebp pop ebp ret NASM GLOBAL GLOBAL GLOBAL EXTERN Tiny C EXTERN abs abs EXTERN abs call abs 2 EXTERN 2 R n [R+n] [R-n] [n+r] / x x (_) COMMON 26

COMMON label n n label COMMON n Tiny C COMMON label [label] imul ebx, [x] push dword loc(v) mov dword loc(v), c cmp dword loc(v), c dword 32 (:) ; NASM % cat a.asm foo % cat main.c #include <stdio.h> main() printf("%d\n", foo(3)); % nasm -f elf a.asm % gcc main.c a.o %./a.out 11 foo() NASM main() gcc a.out [ ] int n n 2 foo NASM main.c 7 [ 6 ] NASM 4 27

eax *6 7.1 Nlocal p. 166 Nlocal struct code char *cd; struct code *next; ; 1 1 1 #include <stdio.h> #include <stdlib.h> #include <string.h> struct code *emit(char *inst, char *op1, char *op2) char buf[80]; struct code *c = (struct code *)malloc(sizeof(struct code)); if (inst == NULL) buf[0] = \0 ; else if (op1 == NULL) sprintf(buf, "\t%s\n", inst); else if (op2 == NULL) sprintf(buf, "\t%s\t%s\n", inst, op1); else sprintf(buf, "\t%s\t%s, %s\n", inst, op1, op2); c->cd = strdup(buf); c->next = NULL; c ; return c; [ ] emit() emit() p. 186 emit() emit("mov", "eax", "1") *7 "\tmov\teax, 1\n" emit() ret *6 edx *7 emit() eax 1 emit() 28

emit("ret", NULL, NULL) C emit() struct code * main: program ; symtab = NULL; cur_lev = 0; if (yynerrs == 0 && semnerrs == 0) emit_program($2); print_code(); Lret n Ln char *make_label() [ ] 7.2 GLOBAL f f push ebp mov ebp, esp sub esp, Nlocal (*) top_alloc Lret mov esp, ebp pop ebp ret Nlocal (*) sub esp, Nlocal struct code *c = emit(null, NULL, NULL); top_alloc 0 Nlocal 0 ; if (top_alloc) char buf[80]; sprintf(buf, "\tsub\tesp, %d\n", -top_alloc); c->cd = strdup(buf); 29

emit("mov", "esp", "ebp"); /* */ top_alloc 0 7.3 while case WHILE: ; ; ; emit("cmp", "eax", "0"); emit("je",, NULL); ; emit("jmp",, NULL); ; break; 7.4 eax 7.4.1 RSL 6.5.2 RSL RSL ; ; emit("mov",, "eax"); ; emit(, "eax", ); ; eax [ ] 30

RSL Nlocal allocate_loc release_loc idiv idiv edx eax 64 edx eax eax edx e 1 eax edx RSL e 2 eax mov temp, eax e 1 eax cdq idiv dword temp / e 2 L e 2 v e 1 eax cdq idiv dword loc(v) L e 2 c e 1 eax cdq mov dword temp, c idiv dword temp cdq eax 32 edx 32 eax 7.4.2 ==,!=, >, etc. cmp setc al movzx eax, al ; al 32 eax setc c g, ge, e 1 0 al al eax 8 8 e 1 >= e 2 RSL e 2 eax mov temp, eax e 1 eax cmp eax, temp setge al movzx eax, al 31

7.4.3 &&, e 1 && e 2 L: mov dword temp, 0 e 1 L e 2 L mov dword temp, 1 mov eax, temp 7.4.4 push call f(e1, e2,..., en) en push kind UNDEFFUN EXTERN [ ] EXTERN UNDEFFUN call EXTERN 8 Tiny C for, continue, break [ ] continue, break / / [ ] & ˆ and, or xor char [ ] CISC [4] 32

8 flex, bison, nasm UNIX man Flex Bison NASM emacs info URL[2] info emacs M-x info NASM URL[3] [1] [2] http://ecs.kuis.kyoto-u.ac.jp/isle/le3b/index.html [3] NASM http://nasm.sourceforge.net/doc/nasmdoc0.html [4] (R) 64 IA-32 http://download.intel.com/jp/developer/jpdoc/248966-017ja.pdf 33