II 3 yacc (2) 2005 : Yacc 0 ~nakai/ipp2 1 C main main 1 NULL NULL for 2 (a) Yacc 2 (b) 2 3 y

Size: px

Start display at page:

Download "II 3 yacc (2) 2005 : Yacc 0 ~nakai/ipp2 1 C main main 1 NULL NULL for 2 (a) Yacc 2 (b) 2 3 y"

いっけいふしはら
4 years ago
Views:

1 II 3 yacc (2) 2005 : Yacc 0 ~nakai/ipp2 1 C main main 1 NULL NULL for 2 (a) Yacc 2 (b) 2 3 yytext tmp2 ("") tmp2->next->word tmp2 yytext tmp2->next->word tmp2 tmp2->next yytext 50 1

2 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MAXSIZE struct LIST { 7 struct LIST * next; 8 char *word; 9 }; main(){ 12 char buf[maxsize]; 13 struct LIST *h, *t, *tmp; /* for making dummy leading node */ 16 h = (struct LIST*) malloc(sizeof(struct LIST)); 17 if (h == NULL){ 18 perror("memory allocation error"); 19 exit(exit_failure); 20 } t = h; 23 h->next = NULL; while(1){ 26 printf("input a word: "); 27 fgets(buf, MAXSIZE, stdin); 28 if (strcmp(buf, "owari\n") == 0){ 29 break; 30 } tmp = (struct LIST*) malloc(sizeof(struct LIST)); 33 if (tmp == NULL){ 34 perror("memory allocation error"); 35 exit(exit_failure); 36 } tmp->word = (char*)malloc(strlen(buf)+1); 39 if (tmp == NULL){ 40 perror("memory allocation error"); 41 exit(exit_failure); 42 } 43 strcpy(tmp->word, buf); t->next = tmp; 46 tmp->next = NULL; 47 t = tmp; 48 } for(tmp = h->next; tmp!= NULL; tmp = tmp->next){ 51 printf("%s", tmp->word); 52 } 53 } 1: tmp2 (for ) for tmp2 yytext 2 (c) 4 3 tmp2 word yytext , (77 96 ) ( ) main

3 1 %{ 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 #define MAXSIZE struct LIST { 8 struct LIST * next; 9 char *word; 10 }; int lineno=1; 13 struct LIST *h, *t, *tmp; 14 %} %% [_A-Za-z][_A-Za-z0-9]* { 51 tmp = (struct LIST*) malloc(sizeof(struct LIST)); 52 if (tmp == NULL){ 53 perror("memory allocation error"); 54 exit(exit_failure); 55 } tmp->word = (char*) malloc(strlen(yytext)+1); 58 if (tmp == NULL){ 59 perror("memory allocation error"); 60 exit(exit_failure); 61 } 62 strcpy(tmp->word, yytext); t->next = tmp; 65 tmp->next = NULL; 66 t = tmp; 67 } 68. { /* do nothing */ } 69 "\n" { lineno++; } %% 72 main(){ /* for making dummy leading node */ 75 h = (struct LIST*) malloc(sizeof(struct LIST)); 76 if (h == NULL){ 77 perror("memory allocation error"); 78 exit(exit_failure); 79 } t = h; 82 h->next = NULL; while(yylex()!=0){ 85 } for(tmp = h->next; tmp!= NULL; tmp = tmp->next){ 88 printf("%s\n", tmp->word); 89 } 90 } 2: 2(a) ( ) 4 Yacc 5 Lex if Pascal-S C Pascal-S TEHN ELSE ELSE if stmt : if_stmt... ; if_stmt : ; else_stmt : ELSE stmt /* empty */ ; IF expr THEN stmt else_stmt expr stmt 1 BEGIN END (C 3

4 if_stmt if_stmt if expr then stmt else_stmt if expr then if_stmt else st2 else_stmt if expr then st1 if expr then st1 else st2 7: if { }) ELSE ELSE ELSE if expr THEN if expr THEN st1 ELSE st2 ELSE if (??) 2 if if_stmt stmt if_stmt if expr THEN st1 stmt ELSE if if 1 ELSE if ELSE if expr THEN st1 stmt ELSE if expr THEN st1 ELSE st2 stmt ( 7) Yacc Shift Reduce Conflict ( ) ELSE ( 7 ) 2 if st1 ( 7 ) ELSE ELSE Yacc ELSE if ELSE IF 1+2*3 2*3 Yacc ( ) 4

5 50 { for(tmp2=h; 51 tmp2->next!= NULL; 52 tmp2 = tmp2->next){ 53 if (strcmp(tmp2->next->word, yytext)>0){ 54 break; 55 } 56 } tmp = (struct LIST*) malloc(sizeof(struct LIST 59 if (tmp == NULL){ 60 perror("memory allocation error"); 61 exit(exit_failure); 62 } tmp->word = (char*)malloc(strlen(yytext)+1); 65 if (tmp == NULL){ 66 perror("memory allocation error"); 67 exit(exit_failure); 68 } 69 strcpy(tmp->word, yytext); tmp->next = tmp2->next; 72 tmp2->next = tmp; 73 } 3: 2(b) ( ) 2 a = 1+2 a 3 2*a a = *3-a { 51 for(tmp2=h; 52 tmp2->next!= NULL; 53 tmp2 = tmp2->next){ 54 if (strcmp(tmp2->next->word, yytext)>0){ 55 break; 56 } 57 } if (strcmp(yytext, tmp2->word)!=0){ 60 tmp = (struct LIST*) malloc(sizeof(struct LIST)); 61 if (tmp == NULL){ 62 perror("memory allocation error"); 63 exit(exit_failure); 64 } tmp->word = (char*) malloc(strlen(yytext)+1); 67 if (tmp == NULL){ 68 perror("memory allocation error"); 69 exit(exit_failure); 70 } 71 strcpy(tmp->word, yytext); tmp->next = tmp2->next; 74 tmp2->next = tmp; 75 } 76 } 4: 2(c) ( ) Lex a = Es E E 9 Es 5

6 1 %token NUM 2 %token NL 3 %% 4 LIST : LIST E NL { printf("%d\n", $2); } 5 /* empty */ 6 ; 7 8 E : E + T { $$ = $1 + $3; } 9 E - T { $$ = $1 - $3; } 10 T { $$ = $1; } 11 ; T : T * F { $$ = $1 * $3; } 14 T / F { $$ = $1 / $3; } 15 F { $$ = $1; } 16 ; F : NUM { $$ = $1; } 19 ( E ) { $$ = $2; } 20 ; %% #include "lex.yy.c" main(){ 27 yyparse(); 28 } 5: 4 (Yacc hw2 4.y) 1 E 1 10 A 1 13 Lex 1 IDENT (3 ) Yacc Lex ( ) a=2*3 a*b 1 asignment 1 %% 2 [0-9]+ { yylval = atoi(yytext); return NUM; } 3 "+" { return + ; } 4 "*" { return * ; } 5 "-" { return - ; } 6 "/" { return / ; } 7 "(" { return ( ; } 8 ")" { return ) ; } 9 [ \t] { /* do nothing */ } 10 "\n" { return NL; } 11. { return yytext[0]; } 6: 4 (Lex hw2 4.l) a=3 b=6 26 (C ) (26 ) ( 10) Yacc Lex [a-z] { yylval = yytext[0]; return IDENT; }

7 1 %{ 2 int ident[26]; 3 %} 4 5 %token NUM 6 %token IDENT 7 %token NL 8 %% 9 LIST : LIST Es NL { printf("%d\n", $2); } 10 /* empty */ 11 ; Es : E { $$ = $1 } 14 A { /* 1 $$=$1 */ } 15 ; A : IDENT = E { 18 $$ = ident[$1 - a ] = $3; 19 } 20 ; E : E + T { $$ = $1 + $3; } 23 E - T { $$ = $1 - $3; } 24 T { $$ = $1; } 25 ; T : T * F { $$ = $1 * $3; } 28 T / F { $$ = $1 / $3; } 29 F { $$ = $1; } 30 ; F : NUM { $$ = $1; } 33 IDENT { $$ = ident[$1 - a ]; } 34 ( E ) { $$ = $2; } 35 ; %% #include "lex.yy.c" main(){ 42 int i = 0; /* the initialization of ident */ 45 for(i=0; i<26; i++){ 46 ident[i] = 0; 47 } yyparse(); 50 } 10: 26 (Yacc ex7.y) 26 int 26 ( 10 2 ) ASCII C a a ASCII ident[0] a ident[1] b ident[25] z a a - a 0 z z - a 25 ident ( ) Lex yylval 1 ASCII Yacc 33 ident 33 $1 yylval $1 - a ident $$ 17 E $3 ident E $$ 2 ex7.y ex7.l a=3 b=a*2 7

8 1 %token NUM 2 %token IDENT 3 %token NL 4 %% 5 LIST : LIST Es NL { printf("%d\n", $2); } 6 /* empty */ 7 ; 8 9 Es : E 10 A 11 ; A : IDENT = E { /* some actions */ } 14 ; E : E + T { $$ = $1 + $3; } 17 E - T { $$ = $1 - $3; } 18 T { $$ = $1; } 19 ; T : T * F { $$ = $1 * $3; } 22 T / F { $$ = $1 / $3; } 23 F { $$ = $1; } 24 ; F : NUM { $$ = $1; } 27 IDENT { /* some actions */ } 28 ( E ) { $$ = $2; } 29 ; %% #include "lex.yy.c" main(){ 36 yyparse(); 37 } 8: (ex6.y) 26 C Lex C [_a-za-z][_a-za-z0-9]* { /* action */ } 1 %% 2 [0-9]+ { yylval = atoi(yytext); return NUM; } 3 [a-z] { return IDENT; } 4 "+" { return + ; } 5 "*" { return * ; } 6 "-" { return - ; } 7 "/" { return / ; } 8 [ \t] { /* do nothing */ } 9 "\n" { return NL; } 10. { return yytext[0]; } 9: 8 Lex (ex6.l) (a) (b) 3. ( ) int (??) yylval 2(a) 2(b) 1 Yacc yylval int yylval Yacc yylval YYSTYPE int double Yacc 8

9 %{ #define YYSTYPE double... %} int char* C int 4 double 8 8 struct ST { }; int val; double dval; union UNI { }; int val; double dval; struct ST union UNI val dval int double yylval Yacc %union { } char *name; int val; C typedef union { char *name; int val; } YYSTYPE; extern YYSTYPE yylval; lex yylval yylval val yylval.val =... 3 yytext yytext yytext yylval.name =... 3 C atoi yytext atoi((char*)yytext) 9

10 0 10 ex8.y Yacc 9 ex8.l Lex stdin freopen man 4 ex8.y main 1 main(int argc, char* argv[]){ 2 extern FILE *yyin; 3 4 if (argc>1){ 5 if((yyin = freopen(argv[argc-1],"r",stdin)) == NULL){ 6 fprintf(stderr, "Can not open file %s\n", argv[argc-1]); 7 exit(1); 8 } 9 } : C Lex yyin 4 C Lex Yacc Lex lex.yy.c Yacc y.tab.c 10

11 1 %{ 2 #include <stdlib.h> 3 4 char *tname; 5 %} 6 7 %% 8 [0-9]+ { yylval.val = atoi((char*)yytext); 9 return NUM; } 10 [_a-za-z][_a-za-z0-9]* { tname = (char*)malloc(strlen(yytext)+1); } 11 if (tname==null){ 12 perror("memory allocation"); 13 exit(exit_failure); 14 } 15 strcpy(tname, yytext); 16 yylval.name = tname; return IDENT; } 17 "+" { return + ; } 18 "*" { return * ; } 19 "-" { return - ; } 20 "/" { return / ; } 21 [ \t] { /* do nothing */ } 22 "\n" { return NL; } 23. { return yytext[0]; } 11: 12 Lex #include 1 12 Yacc 2 %% main 3 main.c #include %token Yacc -d y.tab.h 1. hoge.l 1 %{ #include "y.tab.h"... %} 2. yacc -d hoge.y 3. lex hoge.l 4. cc -c y.tab.c (y.tab.o ) 5. cc -c lex.yy.c (lex.yy.o ) 6. cc main.c y.tab.o lex.yy.o -ly -ll make make Makefile :( ) 14 Yacc Lex Makefile clean make clean 14 make hoge.l hoge.y a.out 11

12 1 %union { 2 char *name; 3 int val; 4 } 5 6 %{ 7 #include <stdio.h> 8 #include <stdlib.h> 9 10 struct VALS { 11 int val; 12 char *name; 13 struct VALS *next; 14 }; struct VALS *h, *t; int getval(char*); 19 int setval(char*, int); 20 %} %token <val> NUM 23 %token <name> IDENT 24 %token NL %type <val> Es 27 %type <val> A 28 %type <val> E 29 %type <val> T 30 %type <val> F %% 33 LIST : LIST Es NL { printf("%d\n", $2); } 34 /* empty */ 35 ; Es : E { $$ = $1; } 38 A { $$ = $1; } 39 ; A : IDENT = E { 42 $$ = setval($1, $3); 43 } 44 ; E : E + T { $$ = $1 + $3; } 47 E - T { $$ = $1 - $3; } 48 T { $$ = $1; } 49 ; T : T * F { $$ = $1 * $3; } 52 T / F { $$ = $1 / $3; } 53 F { $$ = $1; } 54 ; F : NUM { $$ = $1; } 57 IDENT { $$ = getval($1); } 58 ( E ) { $$ = $2; } 59 ; 60 %% #include "lex.yy.c" main(){ 65 int i = 0; 66 struct VALS *tmp; h = t = (struct VALS*) malloc(sizeof(struct VALS)); 69 if (h==null){ 70 perror("memory allocation"); 71 exit(exit_failure); 72 } h->next = NULL; yyparse(); 77 } int getval(char* name){ 80 struct VALS *tmp; for(tmp=h->next; tmp!= NULL; tmp = tmp->next){ 83 if (strcmp(tmp->name, name)==0){ 84 return tmp->val; 85 } 86 } return 0; 89 } int setval(char* name, int val){ 92 struct VALS *tmp; for(tmp=h->next; tmp!= NULL; tmp = tmp->next){ 95 if (strcmp(tmp->name, name)==0){ 96 break; 97 } 98 } if(tmp == NULL){ 01 tmp = (struct VALS*) malloc(sizeof(struct VALS)); 02 if (tmp == NULL){ 03 perror("memory allocation"); 04 exit(exit_failure); 05 } 06 tmp->name = name; 07 tmp->val = val; t->next = tmp; 10 tmp->next = NULL; 11 t = tmp; 12 } 13 else { 14 tmp->val = val; 15 } return val; 18 } 12: Yacc (ex8.y) 12

13 CC a.out = cc : lex.yy.o y.tab.o main.o $(CC) lex.yy.o y.tab.o main.o -ly -ll lex.yy.o : lex.yy.c $(CC) -c lex.yy.c y.tab.o : y.tab.c $(CC) -c y.tab.c lex.yy.c : hoge.l lex hoge.l y.tab.c : hoge.y yacc hoge.y 5 (tree) 5.1 C 1 main.o : main.c $(CC) -c main.c clean : rm -rf *~ *.o y.tab.c lex.yy.c 5 14: Makefile ex8.y ex8.l make hoge ex8 Makefile 2. ex8.l 2 #include "y.tab.h" 3. ex8.y 2 %% #include "lex.yy.c" main.c (ex8.y ) 4. ex8.y %{ %} main.c (ex8.y ) 5. make clean make lex yacc a.out ex8.l 4 make 4 touch 15 E E T + T T * F F F * : 1+2*3 ( ) ( ) 13

14 (traverse) C 2 (subexpression) C struct NODE { int opcode; /* the number of operator */ int val; struct NODE *left_child, *right_child; }; opcode 1 0 val left_child right_child 1 makenode struct NODE* makenode (struct NODE *l, struct NODE *r, int no, int val); ( ) 5.2 Yacc Yacc LIST : E NL ; yylval Yacc 1 yylval 14

15 %union 5 18 $$ 8, 9, 13, 14 ($1 $3 ) 1 Yacc struct NODE *root; root = $2; E () ( 16) 1 void traverse(struct NODE *n){ 2 if (n->lc!= NULL){ 3 traverse(n->lc); 4 } 5 if (n->rc!= NULL){ 6 traverse(n->rc); 7 } 8 if (n->nodecode == 0){ 9 printf(" %d ", n->val); 10 } 11 else { 12 printf(" %c ", n->nodecode); 13 } 14 } 6 ( ) 1 Ctrl-d () 1. ~nakai/ipp2/post 2. ~nakai/ipp2/pre 3. C C 1) int 2) int a; 1 1 3) 4) 5) C 6) 16: 15

16 1 %{ 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 #define MAXSIZE struct LNUM { 8 int lineno; 9 struct LNUM *next; 10 }; struct LIST { 13 struct LIST * next; 14 char *word; struct LNUM *h; 17 struct LNUM *t; 18 }; int lineno=1; 21 struct LIST *h, *t, *tmp, *tmp2; 22 struct LNUM *tmp3; 23 %} %% 59 [_A-Za-z][_A-Za-z0-9]* { 60 for(tmp2=h; 61 tmp2->next!= NULL; 62 tmp2 = tmp2->next){ 63 if (strcmp(tmp2->next->word, yytext)>0){ 64 break; 65 } 66 } tmp3 = (struct LNUM*) malloc(sizeof(struct LNUM)); 69 if (tmp3 == NULL){ 70 perror("memory allocation error"); 71 exit(exit_failure); 72 } tmp3->lineno = lineno; 75 tmp3->next = NULL; if (strcmp(yytext, tmp2->word)!=0){ 78 tmp = (struct LIST*) malloc(sizeof(struct LIST)); 79 if (tmp == NULL){ 80 perror("memory allocation error"); 81 exit(exit_failure); 82 } tmp->word = (char*) malloc(strlen(yytext)+1); 85 if (tmp == NULL){ 86 perror("memory allocation error"); 87 exit(exit_failure); 88 } 89 strcpy(tmp->word, yytext); tmp->h = tmp3; 92 tmp->t = tmp3; tmp->next = tmp2->next; 95 tmp2->next = tmp; 96 } 97 else { 98 tmp2->t->next = tmp3; 99 tmp2->t = tmp3; 100 } 101 } 102. { /* do nothing */ } 103 "\n" { lineno++; } %% main(){ /* for making dummy leading node */ 110 h = (struct LIST*) malloc(sizeof(struct LIST)); 111 if (h == NULL){ 112 perror("memory allocation error"); 113 exit(exit_failure); 114 } t = h; 117 h->next = NULL; 118 h->word == ""; while(yylex()!=0){ 121 } for(tmp = h->next; tmp!= NULL; tmp = tmp->next){ 124 printf("%s : ", tmp->word); 125 for(tmp3 = tmp->h; tmp3!= NULL; tmp3 = tmp3->next){ 126 printf("%5d", tmp3->lineno); 127 } 128 printf("\n"); 129 } 130 } 17: 3 16

untitled

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] { /*