untitled

Transcription

1 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

2 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); strcpy(tmp2, yytext); 12 yylval = tmp2; 13 return IDENTIFIER; [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 ( 4) 8 12 { 4 a 9 a 12 3, 4, 3 2

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

4 2 2 main{ int a; int b; a = 3; b = 4; { a; b; a; b; int a; int b; a = 3+4; b = 5+6; 6: C 1.3 C C 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

5 1 %token NUM 2 %token INT 3 %token IDENTIFIER 4 %token SEMI 5 %token MAIN 6 %% 7 8 PROGRAM : MAIN BLOCK 9 ; BLOCK : { decl_part use_part 12 ; decl_part : decl_list 15 /* empty */ 16 ; decl_list : decl_list decl 19 decl 20 ; decl : INT IDENTIFIER SEMI 23 ; use_part : use_list 26 /* empty */ 27 ; use_list : use_list LIST 30 LIST 31 ; LIST : E SEMI 34 A SEMI 35 BLOCK 36 ; A : IDENTIFIER = E 39 ; E : E + T 42 E - T 43 T 44 ; T : T * F 47 T / F 48 F 49 ; 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 ( ) 4. (kind) kind list *h, *t, *tmp; C ( 5 52 ) 5

6 2 ( ) search_all NULL search_all { { () 5 11 Yacc BLOCK : { BLOCK_ACTION decl_part use_part ; BLOCK_ACTION : { /* */ ; ε Yacc BLOCK : { { /* action */ decl_part use_part ; 5 11 addlist { addlist("block", BLOCK); addlist 2 enum BLOCK delete_block addlist (int ) 2. search_block NULL delete_block 6

7 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 Yacc C %{ #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

8 ( ) ( ) C ( ) (??) 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 ( 8

9 ) ( ) (typedef ) () * 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; main(){ 11 int n = 10, res; res = fact(n); 14 printf("%d\n", res); ([2] ) 1+2* * ( ) * * : main main main main 10 main int n 2 13 fact 2 9

10 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] ( ) 2.3 PL/0 f int a, b, c; 3 a, b, c PL/0 [1] PL/0 10

11 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 / 3 C { C PL/ ( ) 8. = < > 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

12 3 PL/0 3.1 PL/ ( ) tmp tmp->l tmp->o PL/0 (x y ) ( OPR, x, y ) 3.2 ( OPR, 0, 0 ) ( ) (left value) (right value) 2 PL/0 ( LIT, 0, a ) a 3 ( LIT, 0, 3 ) ( LOD, tmp->l, tmp->o ) , 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

13 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

14 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 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

15 4 1 2 search_all 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 : [1] Niklaus Wirth. Algorithms + Data Structure = Programs. Pretice-Hall, :,, [2]..,

16 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 ; struct NODE *root; struct NODE *makenode(struct NODE *l, struct NODE* r, int no, int val); 14 % %union { 17 int val; 18 struct NODE* node; %type <node> E 22 %type <node> T 23 %type <node> F %token <val> NUM 26 %token NL 27 %% 28 LIST : E NL { root = $1; 29 ; E : E + T { $$ = makenode($1,$3, +, 0); 32 E - T { $$ = makenode($1,$3, -, 0); 33 T { $$ = $1; 34 ; T : T * F { $$ = makenode($1,$3, *, 0); 37 T / F { $$ = makenode($1,$3, /, 0); 38 F { $$ = $1; 39 ; F : NUM { $$ = makenode(null, NULL, 0, $1); 42 ( E ) { $$ = $2; 43 ; %% #include "lex.yy.c" void traverse(struct NODE *n); main(){ 52 yyparse(); traverse(root); 55 printf("\n"); struct NODE *makenode(struct NODE *l, struct NODE* r, int no, int val){ 59 struct NODE *tmp; tmp = (struct NODE*) malloc(sizeof(struct NODE)); 62 if (tmp == NULL){ 63 perror("memory allocation error!"); 64 exit(exit_failure); tmp->nodecode = no; 68 tmp->val = val; 69 tmp->lc = l; 70 tmp->rc = r; return tmp; void traverse(struct NODE *n){ 76 if (n->lc!= NULL){ 77 traverse(n->lc); if (n->rc!= NULL){ 80 traverse(n->rc); if (n->nodecode == 0){ 83 printf(" %d ", n->val); else { 86 printf(" %c ", n->nodecode); : 3 1 (Yacc ) 16

17 1 %{ 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 typedef 6 struct LIST { 7 char *name; 8 struct LIST *next; 9 list; list *h, *t, *tmp; #define YYSTYPE char* list* search(char*); 16 void addlist(char*); % %token NUM 21 %token INT 22 %token IDENTIFIER 23 %token SEMI 24 %% PROGRAM : decl_part use_part ; decl_part : decl_list 29 /* empty */ 30 ; decl_list : decl_list decl 33 decl 34 ; decl : INT IDENTIFIER SEMI { 37 if (search($2) == NULL){ 38 addlist($2); else { 41 fprintf(stderr, "this identifier" 42 " has been already declared!\n"); ; use_part : use_list 48 /* empty */ 49 ; use_list : use_list LIST 52 LIST 53 ; LIST : E SEMI 56 ; E : E + T 59 E - T 60 T 61 ; T : T * F 64 T / F 65 F 66 ; F : NUM 69 IDENTIFIER { 70 if (search($1) == NULL){ 71 fprintf(stderr, "this identifier " 72 "is not declared!!\n"); ( E ) 76 ; %% #include "lex.yy.c" main(){ 83 /* initialize the list */ 84 h = (list*)malloc(sizeof(list)); 85 if (h == NULL){ 86 perror("memory allocation"); 87 exit(exit_failure); t = h; 91 h->next = NULL; 92 h->name = NULL; yyparse(); void addlist(char* name){ 98 list *tmp; tmp = (list*)malloc(sizeof(list)); 101 if (tmp == NULL){ 102 perror("memory allocation"); 103 exit(exit_failure); tmp->name = name; t->next = tmp; 109 tmp->next = NULL; 110 t = tmp; list *search(char* name){ 114 list *tmp; for(tmp=h->next; 117 tmp!= NULL; 118 tmp = tmp->next){ 119 if (strcmp(name, tmp->name)==0){ 120 break; return tmp; : 3 3 (Yacc ) 17

18 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