(ver. 1.3 (2018) ) yacc 1 1 yacc yacc (Yet Another Compiler Compiler) UNIX yacc yacc y .y yacc ) yacc .tab.h *.tab.c C C yacc yacc UNIX yacc bison 2

Size: px

Start display at page:

Download "(ver. 1.3 (2018) ) yacc 1 1 yacc yacc (Yet Another Compiler Compiler) UNIX yacc yacc y *.y yacc ) yacc *.tab.h *.tab.c C C yacc yacc UNIX yacc bison 2"

つかさうるしはた
4 years ago
Views:

1 (ver. 1.3 (2018) ) yacc 1 1 yacc yacc (Yet Another Compiler Compiler) UNIX yacc yacc y *.y yacc ) yacc *.tab.h *.tab.c C C yacc yacc UNIX yacc bison 2 yacc yacc lex %token yacc yacc token *.tab.h #define *.tab.c *.tab.h include %token <typename> typename 8 %type <typename> 8 %{ %} *.tab.c C include : BNF 3 1 [1] 1

2 *.tab.c yyparse() yacc main yyparse() yylex() yyparse() yyparse() yylex() I am I am 1-1 sample.y %{ #include <stdio.h> #include "sample.tab.h" extern int yylex() extern int yyerror() %} %token SUBJECT PRED SPACE statement : SUBJECT SPACE PRED { printf("ok!\n")} int main(void){ if (yyparse()) { fprintf(stderr, "Error! Error! Error!\n") return 1 } } 1-2 sample.l %{ #include "sample.tab.h" /* lex for sample.y */ %} I {return SUBJECT} am {return PRED} [\t ]+ {return SPACE} \n return 0. return yytext[0] 1 1 sample.y yacc %{ %} C %token %{ %} C stdio.h include sample.y 2

3 printf include sample.tab.h include 10 yylex(), yyerror() extern yyparse() yylex(), yyerror() yyparse() %token SUBJECT, PRED, SPACE SUBJECT SPACE PRED OK! main() yyparse() yyparse() yyparse() syntax error Error! Error! Error! 1 2 sample.l sample.y lex yacc sample.tab.h include SUBJECT, PRED, SPACE 3 lex return I SUBJECT yylex() return sample.tab.h #define. return yytext[0] lex yytext I SUBJECT, am PRED, SPACE, 0, 0 yyparse yacc lex yacc BNF 1 printf yacc 1 yacc yyerror() syntax error yacc 3

4 1: yacc : C : lex (OR 3.2 yacc %token HOARSE AND CART PLOW GOAT OX phrase : cart_animal AND CART work_animal AND PLOW cart_animal : HORSE GOAT work_animal : HORSE OX HORSE AND CART HORSE AND PLOW HORSE cart animal work animal HORSE CART PLOW %token HOARSE AND CART PLOW GOAT OX phrase : HORSE AND work_doing work_doing : GOAT AND CART OX AND PLOW CART PLOW yacc 4

5 bison 2 1 yacc bison warning: rule useless in parser due to conflist: work animal: HORSE 3.3 yacc / (reduce/reduce conflict) / (shift/reduce conflict) 2 (reduce) (shift) / / 3 1 / 3 1 / %token IDENT PLUS MINUS target : IDENT MINUS IDENT IDENT kigou IDENT kigou : PLUS MINUS IDENT MINUS IDENT target MINUS kigou MINUS / warning: rule useless in parser due to conflist: kigou: MINUS bison 3 2 / 3 2 / %token IDENT NUM PLUS MINUS arith : var kigou var var : IDENT NUM arith kigou : PLUS MINUS IDENT PLUS IDENT PLUS IDENT IDENT PLUS PLUS var arith kigou, var IDENT arith kihou / / conflicts: 1 shift/reduce 3 2 bison conflicts: 2 shift/reduce 5

6 4 1 yacc ( ) bison 5 yacc yacc %token NUMBER statement : expression expression : expression + NUMBER expression - NUMBER NUMBER %token expression expression + NUMBER expression NUMBER expression - NUMBER expression NUMBER NUMBER statement expression printf $1, $2,... $$ 4 2 6

7 (p-m.y) %{ #include <stdio.h> #include "p-m.tab.h" %} %token NUMBER statement : expression { printf("= %d\n", $1)} expression : expression + NUMBER {$$ = $1 + $3} expression - NUMBER {$$ = $1 - $3} NUMBER {$$ = $1} printf include C NUMBER p m.tab.h include C bison 6 lex 1. lex ) 2. C main lex NUMBER 0 yacc + - yacc yacc PLUS, MINUS 7

8 lex lex 1 [0-9]+ {return NUMBER} [\t ] /* ignore whitespace */ \n return 0. return yytext[0] lex lex 4 2 yacc 1. NUMBER 2. lex yacc yacc NUMBER NUMBER yacc %token yacc.tab.h define.tab.h lex include yacc yacc lex return.tab.h 4 2 p-m.y + lex yytext[0] yacc $1, $2 lex yylval yacc $1, $2 return NUMBER yylval yacc 4 2 yacc lex lex (p-m.l) #include "p-m.tab.h" extern yylval [0-9]+ {yylval = atoi(yytext) return NUMBER} [\t ] /* ignore whitespace */ \n return 0. return yytext[0] 8

9 6.2 C p-m.y( 4 2 p-m.l( 5 2) yacc lex C main 4 3 p-m.y 4 3 yacc (p-m.y) %{ #include <stdio.h> #include "p-m.tab.h" extern int yylex() extern int yerror() %} %token NUMBER statement : expression { printf("= %d\n", $1)} expression : expression + NUMBER {$$ = $1 + $3} expression - NUMBER {$$ = $1 - $3} NUMBER {$$ = $1} int main(void) { } if(yyparse()) { } fprintf(stderr, "Error\n") return 1 return 0 main yyparse() yyparse 1 0 yyparse 1 Error yyparse syntax error syntac error Error extern int yylex() extern int yerror() yyparse 6.3 C C p-m.y yacc p-m.l lex 9

10 % bison -d p-m.y % flex p-m.l % gcc -o p-m p-m.tab.c lex.yy.c -lfl -ll yacc yacc int int yacc yacc %token < > %union yacc $$ = $1 %type

11 vbltable $ arithv yacc lex arithv.y, arithv.l aruthv arithv %./arithv > a = 100 a = 100 > b = 35 b = 35 > a * b = 3850 > $ % > arithv yacc 11

12 6 1 yacc %union{ int dval int vblno } %token <vblno> NAME %token <dval> NUMBER statement_list : statement \n statement_list statement \n statement : NAME = expression expression expression : expression + mulexp expression - mulexp mulexp mulexp : mulexp * primary mulexp / primary primary primary : ( expression ) NUMBER NAME statement list n statement NAME expression mulexp primary NAME NAME NUMBER NAME NUM- BER NAME NUMBER NAME 12

13 NUMBER %union int dval int vblno %union YYSTYPE dval NUMBER vblno NAME %token <vblno> NAME NAME vblno %token <dval> NUMBER lex 13

14 yacc (arithv.y) %{ #include <stdio.h> #include "arithv.tab.h" extern int yylex() extern int yyerror() int vbltable[26] %} %union{ } int dval int vblno %token <vblno> NAME %token <dval> NUMBER %type <dval> expression mulexp primary statement_list : statement \n statement_list statement \n statement : NAME = expression {vbltable[$1] = $3 printf("%c = %d\n> ", $1+ a, $3) } expression {printf("= %d\n> ", $1)} expression : expression + mulexp {$$ = $1 + $3 } expression - mulexp {$$ = $1 - $3 } mulexp {$$ = $1} mulexp : mulexp * primary {$$ = $1 * $3 } mulexp / primary {if($3 == 0) {yyerror("divide by zero") return 0} else $$ = $1 / $3 } primary {$$ = $1} primary : ( expression ) {$$ = $2 } NUMBER {$$ = $1} NAME {$$ = vbltable[$1]} int main(void) { } printf ("> ") if (yyparse()) { } fprintf(stderr, "Error\n") return 1 return 0 14

15 primary arithv.y: : $$ of primary has no declared type yacc %type vbltable a 0 z 25 lex lex lex (arithv.l) %{ #include "arithv.tab.h" #include <math.h> extern int vbltable[26] %} [0-9]+ {yylval.dval = atoi(yytext) return NUMBER } [\t ] /* ignore whitespace */ [a-z] {yylval.vblno = yytext[0] - a return NAME } "$" {return 0 /* end of input */} \n. return yytext[0] yylval yylval. atoi yytext yytext[0] a a 0 z 25 9 (arithv.y, arithv.l) 10 yacc lex yacc lex lex yacc %token %token NUMBER yacc expression : expression + NUMBER 15

16 lex return [0-9]+ {return NUMBER} lex return yacc 4-1 expression : expression + NUMBER yacc lex return return yytext[0] lex yylval yacc $1, $2, lex yylval [0-9]+ {yylval = atoi(yytext) return NUMBER} yacc expression : expression + NUMBER {$$ = $1 + $3} yylval YYSTYPE int #define %union #define #define %union AST %union lex yytext yacc yytext lex yacc lex yytext yytext [1] John R. Levine, Tony Mason, Doug Brown lex & yacc, [2] John R. Levine, Flex & Bison, Oreilly & Associates Inc, ( 16

18/12/06 情報工学実験 C コンパイラ (2018 年度 ) 担当 : 笹倉佐藤その 3 yacc の構造定義部 %% 定義部の終了規則部 %% 規則部の終了ユーザ定義サブルーチン部 :C のプログラムを書く形は lex と同じ 1

18/12/06 情報工学実験 C コンパイラ (2018 年度 ) 担当 : 笹倉佐藤その 3 yacc の構造定義部 %% 定義部の終了規則部 %% 規則部の終了ユーザ定義サブルーチン部 :C のプログラムを書く形は lex と同じ 1 情報工学実験 C コンパイラ (2018 年度 ) 担当 : 笹倉佐藤 2018.12.6 その 3 yacc の構造定義部定義部の終了規則部規則部の終了ユーザ定義サブルーチン部 :C のプログラムを書く形は lex と同じ 1 yacc yacc のキモは規則部規則部には文法規則を書く左辺 : 右辺 yacc は入力されたプログラムを右辺から左辺に還元していくこの規則にアクションが書かれていたら還元するときにアクションも実行する.