II yacc 005 : 1, 1 1 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 %% 14 15 main(){ 16 while(yylex()!=0){ 17 } 18 19 printf("%10d %10d %10d\n", lineno, wordno, charno); 0 }.1 (Context Free Grammar CFG) CFG 1 : ; : 3 4 ; 5 : 6 7 8 ; 1: 1 1. 3: CFG () 1 Lex Lex Yacc 1 1 CFG 1 : ; 1 (production rule) 1 (0 ) 1 1
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 */ } 38 39 [_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
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
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 %% 13 14 #include "lex.yy.c" 15 16 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 4 4 10 4 6 8 10 8 10 8 NUM + 1 8 9 9 ( xpression ) 9 8 +...+...+...+... + 4 6 4 LIST LIST LIST 5 /* empty */ C C 1 LIST NL LIST NL 1 %% Lex C 14 C #include lex.yy.c 16 18 main 4 LALR(1) 4
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 + + 4 5 6 % 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 5 6 ( ) 1++3 abc 5
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 %% 13 14 #include "lex.yy.c" 15 16 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 8 8 9 { } C Lex $ 6
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 + + 8 8 $$=$1+$3 $1 $3 1+ ( 11 ) + 3 6 11 6 4 $ 6 printf("%d\n", $) 6 3.4 + 1 + + 3 3.4.1 11: (1++3) 1++3 11 1 5 * 8 8 8 9 * NUM { $$ = $1 * $3; } 9 3 4 "*" { return * ; } 7
ex3.y ex3.l Yacc Lex 1+*3 3.4. 1+*3 1 ex3.y 1+*3 + * 1 3 1: 1+*3 3 1 1+ 1+ 13 *3 14 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 ; 15 16 %% 17 18 #include "lex.yy.c" 19 0 main(){ 1 yyparse(); } 14: ex3.y (ex4.y) + * 1 3 13: 1+*3 () 1 8 9 + 8 8 * 14 1+*3 15 15 14 1+*3 1 13 T + 9 + 8
T T T 1 + * 3 15: 1+*3 () 3.5 : + NUM : NUM + 1++3 16 13 T 1 8 1 1 + NL 8 * 1 * 3 3 1 T + T 8 T 1. ex4.y 1+*3. ex4.y - / Yacc ex5.y Lex ex5.l 3. ( +3*4*5 ) 1 + + 3 16: : NUM + 16 11 16 11 C a=b=c=3; c=3 (3) b a = - 3 1. C int i, j, k; 9
i,j,k 1 5 i j ID IDLIST COMMA. C 1 + + 3 (a) 1 + + 3 (b) int i; int j; int k; hello, world 1 DCL DCL 1 1 5 LIST DCL DCLS 3.6 Yacc : + NUM ; 1++3 17 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) 5 3 10
(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 : 7 1 1.. 18 1 %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 ; 17 18 %% 19 0 #include "lex.yy.c" 1 main(){ 3 yyparse(); 4 } 3 3. 18: - 11
1. IDLIST : IDLIST COMMA ID ID ; IDLIST : ID COMMA IDLIST ID ;. DCLLIST : DCLLIST DCL /* empty */ ; DCLLIST : DCL DCLLIST /* empty */ ; 4 1. 19. 0 1 #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 } 13 14 void hoge(int *x, int *y){ 15 int tmp; 16 17 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 } 13 14 void hoge(int *x, int *y){ 15 int tmp1, tmp; 16 17 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., 1991. ( ) : lex & yacc, (1994) : ISBN4-7561-097-3600. [] :,, 1995. [3] :,, 1989. [4] : yacc/lex on UNIX,, 1996. : ISBN4-94998-14-1 3400. 1