untitled

II 4 Yacc Lex 2005 : 0 1 Yacc 20 Lex 1 20 traverse 1 %% 2 [0-9]+ { yylval.val = atoi((char*)yytext); return NUM; 3 "+" { return + ; 4 "*" { return * ; 5 "-" { return - ; 6 "/" { return / ; 7 [ \t] { /* do nothing */ 8 "\n" { return NL; 9. { return yytext[0]; 3 Yacc 21 Lex 2 a.out int a; int a; a.out int a; a+b; 1: 3 1 (Lex ) int a; a+1; int b; 2 traverse 1 1

1 %% 2 int { return INT; 3 ";" { return SEMI; 4 [_a-za-z][_a-za-z0-9]* { 5 char* tmp2; 6 tmp2=(char*)malloc(strlen(yytext)+1); 7 if (tmp2 == NULL){ 8 perror("memory allocation"); 9 exit(exit_failure); 10 11 strcpy(tmp2, yytext); 12 yylval = tmp2; 13 return IDENTIFIER; 14 15 16 [0-9]+ { return NUM; 17 "+" { return + ; 18 "*" { return * ; 19 "-" { return - ; 20 "/" { return / ; 21 [ \t] { /* do nothing */ 22 "\n" { /* do nothing */ 23. { return yytext[0]; 2: 3 3 (Lex ) 1 C 1.1 C ( ) ( ) C { 1 { { C 3 1 hoge(int* a, int* b){ 2 if (*a<*b){ 3 int c; 4 5 c = *a; 6 *a = *b; 7 *b = c; 8 9 3: 1 3 c hoge 1 { 9 2 { 8 8 printf("%d\n", c); c 2 8 1 ( 4) 8 12 { 4 a 9 a 12 3, 4, 3 2

1 #include <stdio.h> 2 3 main(){ 4 int a = 3; 5 6 printf("out: %d\n", a); 7 8 { 9 int a = 4; 10 11 printf("in: %d\n", a); 12 13 14 printf("out: %d\n", a); 15 4: 1 1.2 (symbol table) 1.2.1 ( ) 4 4 4 main 3 { 1 main 4 a int a 8 { a 12 1 h t 1 1.2.2 1 3

2 2 main{ int a; int b; a = 3; b = 4; { a; b; a; b; 3 4 7 11 7 11 3 4 int a; int b; a = 3+4; b = 5+6; 6: C 1.3 C C 1.3.1 int xxx; a=...; a*b...; { Yacc ( ) 5 C 6 3, 4 7, 11 a, b 7, 11 main a, b 3, 4 1 Yacc C 1.3.2 4

1 %token NUM 2 %token INT 3 %token IDENTIFIER 4 %token SEMI 5 %token MAIN 6 %% 7 8 PROGRAM : MAIN BLOCK 9 ; 10 11 BLOCK : { decl_part use_part 12 ; 13 14 decl_part : decl_list 15 /* empty */ 16 ; 17 18 decl_list : decl_list decl 19 decl 20 ; 21 22 decl : INT IDENTIFIER SEMI 23 ; 24 25 use_part : use_list 26 /* empty */ 27 ; 28 29 use_list : use_list LIST 30 LIST 31 ; 32 33 LIST : E SEMI 34 A SEMI 35 BLOCK 36 ; 37 38 A : IDENTIFIER = E 39 ; 40 41 E : E + T 42 E - T 43 T 44 ; 45 46 T : T * F 47 T / F 48 F 49 ; 50 51 F : NUM 52 IDENTIFIER 53 ( E ) 54 ; 5: C (ex10.y) typedef struct LIST { char *name; int val; int kind; struct LIST *prev; list; 7: enum KIND { ID, BLOCK ; ID 0 BLOCK 1 typedef 1. 2. 3. ( ) 4. (kind) kind list *h, *t, *tmp; 1.3.3 C ( 5 52 ) 5

2 ( ) search_all NULL search_all 5 52 1.3.4 5 38 3 5 38 1.3.5 5 22 { { () 5 11 Yacc BLOCK : { BLOCK_ACTION decl_part use_part ; BLOCK_ACTION : { /* */ ; ε Yacc BLOCK : { { /* action */ decl_part use_part ; 5 11 addlist 2 1 1 { addlist("block", BLOCK); addlist 2 enum BLOCK delete_block 5 11 4 1. addlist (int ) 2. search_block NULL 3. 5 22 4. delete_block 6

1.3.6 main 8 main(){ /* initialize the list */ h = (list*)malloc(sizeof(list)); if (h == NULL){ perror("memory allocation"); exit(exit_failure); t = h; h->prev = NULL; h->name = ""; yyparse(); 8: C Yacc main 5 33 34 Yacc 9 1.4 C 1.4.1 1 %{ #include <stdio.h> #include <stdlib.h> typedef struct LIST { char *name; int val; int kind; struct LIST *prev; list; list *h, *t; list* search_block(char*); list* search_all(char*); void addlist(char*, int); void delete_block(); enum KIND { ID, BLOCK ; % %union { int val; char* name; %type <val> E %type <val> T %type <val> F %type <val> A %token <val> NUM %token INT %token <name> IDENTIFIER %token SEMI %token MAIN %% 9: C Yacc 7

( ) ( ) C ( ) (??) 1 1.4.2 a = f(1,2,3); a = f(g(x, y), h(a, b, c), 4); f 6 expression fname LPAR params RPAR... params : params COMMA expression { $$.val = $1.val + 1; /* */ expression { $$.val = 1; /* */ ; (expression) 1.5 C int double 1 1 1 2 1 ( 8

) ( ) (typedef ) () 6 1 + 2 2 1 2 3 * + 2.2 10 2 Java JVM(Java Virtual Machine) JVM JVM 1 int fact(int n){ 2 if (n>0){ 3 return n*fact(n - 1); 4 5 else { 6 return 1; 7 8 9 10 main(){ 11 int n = 10, res; 12 13 res = fact(n); 14 printf("%d\n", res); 15 2.1 ([2] ) 1+2*3 1 2 3 * + 1 2 3 3 2 1 ( ) * * 2 2 10: 2.2.1 main main main main 10 main int n 2 13 fact 2 9

main main main fact fact fact main fact 2 fact main fact (1) fact (2) ( ) f a b c ( ) c xx(int2 ) c (base) (offset) int 4 c 8 1 [2] 6 2.2.2 ( ) 2.3 PL/0 f int a, b, c; 3 a, b, c PL/0 [1] PL/0 10

if while begin end 3 ( ) read( ) write( ) writeln writeln 2.4 PL/0 PL/0 ([2] ) (1) LOD, l, a l a (2) LIT, 0,a ( )a (3) STO, l, a l a (4) OPR, 0,a a a a a 0. 1. 2. + 3. 4. 5. / 3 C { C PL/0 6. 1 0 7. ( ) 8. = 9. 10. < 11. 12. > 13. (5) INT, 0,a a (a ) (6) JMP, 0,a a ( ) (7) JPC, 0,a 0( ) a (8) CAL, l, a l a (9) CSP, 0,a PL/0 a 4 (10) LAB, 0,a a PL/0 PL/0 (10) RET, 0,a a a pl0i ~nakai/ipp2/pl0i ~nakai/ipp2/pl0i_src 4 11

3 PL/0 3.1 PL/0 3 1 1 1 1 3 1 ( ) tmp tmp->l tmp->o PL/0 (x y ) ( OPR, x, y ) 3.2 ( OPR, 0, 0 ) 3.3 1 ( ) (left value) (right value) 2 PL/0 ( LIT, 0, a ) a 3 ( LIT, 0, 3 ) ( LOD, tmp->l, tmp->o ) 3.4 1+2 1, 2 + 1, 2 LIT + + ( OPR, 0, 2 ) 1+2 PL/0 ( LIT, 0, 1 ) ( LIT, 0, 2 ) ( OPR, 0, 2 ) ( OPR, 0, 0 ) PL/0 12

3.5 a=3 a tmp ( STO, tmp->l, tmp->o ) a=1+2 ( LIT, 0, 1 ) ( LIT, 0, 2 ) ( OPR, 0, 2 ) ( STO, tmp->l, tmp->o ) ( OPR, 0, 0 ) tmp->l tmp->o a 3.6 (if) if if then else then else (JPC) (JMP) JPC ( ) LAB if ( JPC, 0, lab1 ) then ( JMP, 0, lab2 ) ( LAB, 0, lab1 ) else ( LAB, 0, lab2 ) 3.7 (while) while while while (C { ) while while ( LAB, 0, lab1 ) ( JPC, 0, lab2 ) ( JMP, 0, lab1 ) ( LAB, 0, lab2 ) 3.8 PL/0 PL/0 ( CAL, l, a ) l a a ( OPR, 0, 0 ) ( ) PL/0 2 ( ) 13

3 3-1 n i i n 1 (i-n-1 ) ( LOD, l, i-n-1 ) C return return( RET) ret_stmt : RET E SEMI ; E ( RET, 0, a ) a tmp->l 1 2... n ( CAL, tmp->l, lab ) ( LAB, 0, lab )... return ( ) ( RET, 0, a) 3.9 PL/0 ( CSP, 0, 1 ) ( CSP, 0, 2 ) ( CSP, 0, 0 ) PL/0 ( 11) PL/0 ( 12) function f(n) begin if n < 1 then return 1; return n * f(n - 1); end; var x; begin read x; write f(x); writeln; end. 11: ( JMP, 0, 3 ) ( LAB, 0, 1 ) ( INT, 0, 3 ) ( LOD, 0, -1 ) ( LIT, 0, 1 ) ( OPR, 0, 10 ) ( JPC, 0, 2 ) ( LIT, 0, 1 ) ( RET, 0, 1 ) ( LAB, 0, 2 ) ( LOD, 0, -1 ) ( LOD, 0, -1 ) ( LIT, 0, 1 ) ( OPR, 0, 3 ) ( CAL, 1, 1 ) ( OPR, 0, 4 ) ( RET, 0, 1 ) ( OPR, 0, 0 ) ( LAB, 0, 3 ) ( INT, 0, 4 ) ( CSP, 0, 0 ) ( STO, 0, 3 ) ( LOD, 0, 3 ) ( CAL, 0, 1 ) ( CSP, 0, 1 ) ( CSP, 0, 2 ) ( OPR, 0, 0 ) 12: 11 PL/0 14

4 1 2 search_all 13 5 52 14 list *search_all(char* name){ list *tmp; for(tmp=t; tmp!= h; tmp = tmp->prev){ if (strcmp(name, tmp->name)==0){ return tmp; return NULL; IDENTIFIER { list* tmp; 13: search all tmp = search_all($1); if (tmp == NULL){ fprintf(stderr, "this identifier is" " not declared!!\n"); $$ = tmp->val; A : IDENTIFIER = E { list* tmp; tmp = search_all($1); if (tmp == NULL){ fprintf(stderr, "this identifier has not" " been declared!\n"); else { tmp->val = $3; $$ = $3; 15: 5 38 void addlist(char* name, int kind){ list *tmp; tmp = (list*)malloc(sizeof(list)); if (tmp == NULL){ perror("memory allocation"); exit(exit_failure); tmp->name = name; tmp->kind = kind; tmp->prev = t; t = tmp; 16: addlist 2. 17 3. 18 4. 19 14: 5 52 3 15 4 [1] Niklaus Wirth. Algorithms + Data Structure = Programs. Pretice-Hall, 1976. :,, 1980. [2].., 1989. 1. 16 15

1 %{ 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 struct NODE { 6 int nodecode; 7 int val; 8 struct NODE *lc, *rc; 9 ; 10 11 struct NODE *root; 12 13 struct NODE *makenode(struct NODE *l, struct NODE* r, int no, int val); 14 % 15 16 %union { 17 int val; 18 struct NODE* node; 19 20 21 %type <node> E 22 %type <node> T 23 %type <node> F 24 25 %token <val> NUM 26 %token NL 27 %% 28 LIST : E NL { root = $1; 29 ; 30 31 E : E + T { $$ = makenode($1,$3, +, 0); 32 E - T { $$ = makenode($1,$3, -, 0); 33 T { $$ = $1; 34 ; 35 36 T : T * F { $$ = makenode($1,$3, *, 0); 37 T / F { $$ = makenode($1,$3, /, 0); 38 F { $$ = $1; 39 ; 40 41 F : NUM { $$ = makenode(null, NULL, 0, $1); 42 ( E ) { $$ = $2; 43 ; 44 45 %% 46 47 #include "lex.yy.c" 48 49 void traverse(struct NODE *n); 50 51 main(){ 52 yyparse(); 53 54 traverse(root); 55 printf("\n"); 56 57 58 struct NODE *makenode(struct NODE *l, struct NODE* r, int no, int val){ 59 struct NODE *tmp; 60 61 tmp = (struct NODE*) malloc(sizeof(struct NODE)); 62 if (tmp == NULL){ 63 perror("memory allocation error!"); 64 exit(exit_failure); 65 66 67 tmp->nodecode = no; 68 tmp->val = val; 69 tmp->lc = l; 70 tmp->rc = r; 71 72 return tmp; 73 74 75 void traverse(struct NODE *n){ 76 if (n->lc!= NULL){ 77 traverse(n->lc); 78 79 if (n->rc!= NULL){ 80 traverse(n->rc); 81 82 if (n->nodecode == 0){ 83 printf(" %d ", n->val); 84 85 else { 86 printf(" %c ", n->nodecode); 87 88 89 20: 3 1 (Yacc ) 16

1 %{ 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 typedef 6 struct LIST { 7 char *name; 8 struct LIST *next; 9 list; 10 11 list *h, *t, *tmp; 12 13 #define YYSTYPE char* 14 15 list* search(char*); 16 void addlist(char*); 17 18 % 19 20 %token NUM 21 %token INT 22 %token IDENTIFIER 23 %token SEMI 24 %% 25 26 PROGRAM : decl_part use_part ; 27 28 decl_part : decl_list 29 /* empty */ 30 ; 31 32 decl_list : decl_list decl 33 decl 34 ; 35 36 decl : INT IDENTIFIER SEMI { 37 if (search($2) == NULL){ 38 addlist($2); 39 40 else { 41 fprintf(stderr, "this identifier" 42 " has been already declared!\n"); 43 44 45 ; 46 47 use_part : use_list 48 /* empty */ 49 ; 50 51 use_list : use_list LIST 52 LIST 53 ; 54 55 LIST : E SEMI 56 ; 57 58 E : E + T 59 E - T 60 T 61 ; 62 63 T : T * F 64 T / F 65 F 66 ; 67 68 F : NUM 69 IDENTIFIER { 70 if (search($1) == NULL){ 71 fprintf(stderr, "this identifier " 72 "is not declared!!\n"); 73 74 75 ( E ) 76 ; 77 78 %% 79 80 #include "lex.yy.c" 81 82 main(){ 83 /* initialize the list */ 84 h = (list*)malloc(sizeof(list)); 85 if (h == NULL){ 86 perror("memory allocation"); 87 exit(exit_failure); 88 89 90 t = h; 91 h->next = NULL; 92 h->name = NULL; 93 94 yyparse(); 95 96 97 void addlist(char* name){ 98 list *tmp; 99 100 tmp = (list*)malloc(sizeof(list)); 101 if (tmp == NULL){ 102 perror("memory allocation"); 103 exit(exit_failure); 104 105 106 tmp->name = name; 107 108 t->next = tmp; 109 tmp->next = NULL; 110 t = tmp; 111 112 113 list *search(char* name){ 114 list *tmp; 115 116 for(tmp=h->next; 117 tmp!= NULL; 118 tmp = tmp->next){ 119 if (strcmp(name, tmp->name)==0){ 120 break; 121 122 123 return tmp; 124 21: 3 3 (Yacc ) 17

list *search_block(char* name){ list *tmp; for(tmp=t; tmp!= h && tmp->kind!= BLOCK; tmp = tmp->prev){ if (strcmp(name, tmp->name)==0){ return tmp; return NULL; 17: search block decl : INT IDENTIFIER SEMI { if (search_block($2) == NULL){ addlist($2, ID); else { fprintf(stderr, "this identifier has" " been already declared!\n"); 18: 5 22 void delete_block(){ list *tmp; for(tmp=t; tmp!= h && tmp->kind!= BLOCK; tmp = tmp->prev){ free(tmp->name); free(tmp); free(tmp->name); free(tmp); t = tmp->prev; 19: delete block 18