untitled

Size: px

Start display at page:

Download "untitled"

みいかちとく
7 years ago
Views:

1 II yacc 005 : 1, %{ int lineno=0; 3 int wordno=0; 4 int charno=0; 5 6 %} 7 8 %% 9 [ \t]+ { charno+=strlen(yytext); } 10 "\n" { lineno++; charno++; } 11 [^ \t\n]+ { wordno++; charno+=strlen(yytext);} 1 13 %% main(){ 16 while(yylex()!=0){ 17 } printf("%10d %10d %10d\n", lineno, wordno, charno); 0 }.1 (Context Free Grammar CFG) CFG 1 : ; : 3 4 ; 5 : ; 1: : CFG () 1 Lex Lex Yacc 1 1 CFG 1 : ; 1 (production rule) 1 (0 ) 1 1

2 1 %{ int lineno=1; 3 %} 4 5 %% 6 "auto" { /* do nothing */ } 7 "break" { /* do nothing */ } 8 "case" { /* do nothing */ } 9 "char" { /* do nothing */ } 10 "const" { /* do nothing */ } 11 "continue" { /* do nothing */ } 1 "default" { /* do nothing */ } 13 "do" { /* do nothing */ } 14 "double" { /* do nothing */ } 15 "else" { /* do nothing */ } 16 "enum" { /* do nothing */ } 17 "extern" { /* do nothing */ } 18 "float" { /* do nothing */ } 19 "for" { /* do nothing */ } 0 "goto" { /* do nothing */ } 1 "if" { /* do nothing */ } "int" { /* do nothing */ } 3 "long" { /* do nothing */ } 4 "register" { /* do nothing */ } 5 "return" { /* do nothing */ } 6 "short" { /* do nothing */ } 7 "signed" { /* do nothing */ } 8 "sizeof" { /* do nothing */ } 9 "static" { /* do nothing */ } 30 "struct" { /* do nothing */ } 31 "switch" { /* do nothing */ } 3 "typedef" { /* do nothing */ } 33 "union" { /* do nothing */ } 34 "unsigned" { /* do nothing */ } 35 "void" { /* do nothing */ } 36 "volatile" { /* do nothing */ } 37 "while" { /* do nothing */ } [_A-Za-z][_A-Za-z0-9]* { printf("%4d: %s\n", lineno, yytext); } 40. { /* do nothing */ } 41 "\n" { lineno++; } 4 43 %% 44 main(){ 45 while(yylex()!=0){ 46 } 47 } : 1. 3 (terminal symbol) (non-terminal symbol) (start symbol) 1 S S : S (augmented grammar). (A, B, C, ) (a, b, c, ) (α, β,γ, ) (X, Y, Z ) () (x, y, z ) ( 0 ) ( a a ) Yacc.3 3 I love you

3 1 6 I love you 4: I love you 4 4 (leaf) (root) (??).4 () (derivation) (reduction).5 3 ( ) 3 3 The car that I used is my father s. 3 I used (recursively).6 (syntax analysis parsing) Yacc [3] 3 Yacc (parser) (arithmetic expression) 3 3

4 3.1 Yacc Yacc ( Yacc ) 5 1 %token NUM %token NL 3 %% 4 LIST : LIST NL 5 /* empty */ 6 ; 7 8 : + NUM 9 NUM 10 ; 11 1 %% #include "lex.yy.c" main(){ 17 yyparse(); 18 } 5: yacc (ex1.y) 5 Lex 6 1 %% [0-9]+ { return NUM; } 3 "+" { return + ; } 4 [ \t] { /* do nothing */ } 5 "\n" { return NL; } 6. { return yytext[0]; } 6: 5 lex (ex1.l) 5 1 %token NUM NUM NL new line NL NWLIN C 3 %% Lex NUM ( xpression ) LIST LIST LIST 5 /* empty */ C C 1 LIST NL LIST NL 1 %% Lex C 14 C #include lex.yy.c main 4 LALR(1) 4

5 yytext LIST yytext yytext[0] LIST 3. Yacc Lex LIST Yacc Yacc y.tab.c ε NL NL 7: 5 yyparse 6 5 Lex return NUM NUM Yacc %token %token NUM Yacc #define NUM 57 Lex NUM Yacc return yyparse 3 + Yacc ( 5) + return % yacc ex1.y % lex ex1.l % cc y.tab.c -ly -ll Yacc #include "lex.yy.c" Lex lex.yy.c Yacc y.tab.c main C 1 #include #include C (preprocessor ) y.tab.c -ly Yacc Lex -ly -ll ( ) 1++3 abc 5

6 3.3 Yacc Yacc 1 8 Yacc 9 Yacc Lex 1 %token NUM %token NL 3 %% 4 LIST : LIST NL { printf("%d\n", $); } 5 /* empty */ 6 ; 7 8 : + NUM { $$ = $1 + $3; } 9 NUM { $$ = $1; } 10 ; 11 1 %% #include "lex.yy.c" main(){ 17 yyparse(); 18 } 8: Yacc (ex.y) 1 #include <stdio.h> 3 main(){ 4 char a[100]; 5 int x, y; 6 7 fgets(a, 100, stdin); 8 x = atoi(a); 9 10 fgets(a, 100, stdin); 11 y = atoi(a); 1 13 printf("%d\n", x+y); 14 } 10: atoi 6 NUM Yacc (value) Yacc atoi Lex 1 %% [0-9]+ { yylval = atoi(yytext); return NUM; } 3 "+" { return + ; } 4 [ \t] { /* do nothing */ } 5 "\n" { return NL; } 6. { return yytext[0]; } 10 fgets 13 9: ex.y Lex (ex.l) Lex 9 yylval Lex Yacc Yacc { } C Lex $ 6

7 9 NUM () n $n 9 $1 1 NUM NUM Lex yylval Lex yylval Yacc 5 Lex yylval Yacc $n( n ) $$ 9 1 atoi yylval 9 $$=$ $$=$1+$3 $1 $3 1+ ( 11 ) $ 6 printf("%d\n", $) : (1++3) * * NUM { $$ = $1 * $3; } "*" { return * ; } 7

8 ex3.y ex3.l Yacc Lex 1+* *3 1 ex3.y 1+*3 + * 1 3 1: 1+* * %token NUM %token NL 3 %% 4 LIST : LIST NL { printf("%d\n", $); } 5 /* empty */ 6 ; 7 8 : + T { $$ = $1 + $3; } 9 T { $$ = $1; } 10 ; 11 1 T : T * NUM { $$ = $1 * $3; } 13 NUM { $$ = $1; } 14 ; %% #include "lex.yy.c" 19 0 main(){ 1 yyparse(); } 14: ex3.y (ex4.y) + * : 1+*3 () * 14 1+* * T

9 T T T 1 + * 3 15: 1+*3 () 3.5 : + NUM : NUM T NL 8 * 1 * T + T 8 T 1. ex4.y 1+*3. ex4.y - / Yacc ex5.y Lex ex5.l 3. ( +3*4*5 ) : : NUM C a=b=c=3; c=3 (3) b a = C int i, j, k; 9

10 i,j,k 1 5 i j ID IDLIST COMMA. C (a) (b) int i; int j; int k; hello, world 1 DCL DCL LIST DCL DCLS 3.6 Yacc : + NUM ; Yacc 17 (a) (b) Yacc 17: 1++3 Yacc Yacc 4 C (linked list) (tree) 4 1. (a) main a b (b) 1 (c) hoge ( main a b ) (d) main hoge a b.(a) main a b (b)

11 (c) hoge a+b a a-b b ( a b main ) (d) main hoge a b 4. - ( ) 6 5 Lex Yacc [ ] dream% a.out < file 1. owari 1 1. C (a) (b) 6 (c) 3. C 7 6 : 7 : %token NUM %token NL 3 %% 4 LIST : LIST NL { printf("%d\n", $); } 5 /* empty */ 6 ; 7 8 : + T { $$ = $1 + $3; } 9 - T { $$ = $1 - $3; } 10 T { $$ = $1; } 11 ; 1 13 T : T * NUM { $$ = $1 * $3; } 14 T / NUM { $$ = $1 / $3; } 15 NUM { $$ = $1; } 16 ; %% 19 0 #include "lex.yy.c" 1 main(){ 3 yyparse(); 4 } : - 11

12 1. IDLIST : IDLIST COMMA ID ID ; IDLIST : ID COMMA IDLIST ID ;. DCLLIST : DCLLIST DCL /* empty */ ; DCLLIST : DCL DCLLIST /* empty */ ; #include <stdio.h> 3 void hoge(int*, int*); 4 5 main(){ 6 int a=1; 7 int b=; 8 9 printf("a = %d\nb = %d\n", a, b); 10 hoge(&a, &b); 11 printf("a = %d\nb = %d\n", a, b); 1 } void hoge(int *x, int *y){ 15 int tmp; tmp = *x; 18 *x = *y; 19 *y = tmp; 0 } 1 #include <stdio.h> 3 void hoge(int*, int*); 4 5 main(){ 6 int a=5; 7 int b=3; 8 9 printf("a = %d\nb = %d\n", a, b); 10 hoge(&a, &b); 11 printf("a = %d\nb = %d\n", a, b); 1 } void hoge(int *x, int *y){ 15 int tmp1, tmp; tmp1 = *x + *y; 18 tmp = *x - *y; 19 *x = tmp1; 0 *y = tmp; 1 } 19: 4 1 0: 4 [1] Levine, J. R., Mason, T., and Brown, D.: lex & yacc, O Reilly & Associates, Inc., ( ) : lex & yacc, (1994) : ISBN [] :,, [3] :,, [4] : yacc/lex on UNIX,, : ISBN

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