2017 c 8 Yacc Mini-C C/C++, yacc, Mini-C, run,, Mini-C 81 Yacc Yacc, 1, 2 ( ), while ::= "while" "(" ")" while yacc 1: st while : lex KW WHILE lex LPAREN expression lex RPAREN statement 2: 3: $$ = new St while($3, $5); 4: 1, st while, while lex KW WHILE, while lex LPAREN, (() expression, lex RPAREN, ()) statement, while 2 4, $1 while $2 $3 $4 $5 cond St while body "while" "(" ")" expression statement Yacc, while 5, $1, $2,, $5, $3, $5, while, $3 $5, 3 $$ St while, while 8 1
, run, 82 Yacc 1 Makefile parseyy yacc t822bmc, factormc 2 parseyy yacc 7 ( Part-1 Part-7 ) Part-1 ( % % ), yacc C/C++ #include "asth" #include <cstdio> C++ C stdioh // lex extern int linenum; extern std::file* yyin; int yylex(void); 1 void yyerror(const char*); Part-2 (%union ) lex, INT lex CHAR int yylvalval, lex ID char* string, 2 while, Part-3 (%token ) %token <val> lex INT lex CHAR %token <string> lex ID, (val string Part-2 ) (, ), Part-4 (%type ) Part-3 ( ), Part-4 ( ) ( ) Part-5 (%start ) %start program program Part-6 ( ) 8 2
, Part-7 ( ),, / main main, (argv[1]) Mini-C, 7 yyparse(); int main(int argc, char *argv[]) if(std::file* fp = std::fopen(argv[1], "r")) linenum = 1; // lex 1 yyin = fp; yyparse(); else // lex // printf(" %s \n", argv[1]); 3 yacc yacc bison --debug -d parseyy -o parsecpp, parsecpp parsecpph (linux)/parsehpp (Cygwin) lex 4 lexll lexll A #include "lexh", lex yacc, yacc, lexh,, yacc, asth Cygwin #include "asth" #include "parsehpp" Linux #include "asth" #include "parsecpph" 5 Makefile 8 3
make mci mci 1, Mini-C /mci factormc,, 83 Yacc 81 20 ::= "(" ")",, 20 ::= 1 parseyy Part-2 expression %union char* string; int val; Expression* expression; 2 Part-4, expression4 // -------------------------------------------------------------------- // [Part-4] // -------------------------------------------------------------------- %type <expression> expression4 3 Part-6 expression4 // -------------------------------------------------------------------- // [Part-6] // -------------------------------------------------------------------- program : expression4 : lex INT $$ = new Exp constant(type INT, $1); 1 Mini-C Interpreter 8 4
::= $1 lex INT 2 Exp constant, $$, 4, program // -------------------------------------------------------------------- // [Part-6] // -------------------------------------------------------------------- program : expression4 $1->print(std::cout); std::cout<<std::endl; expression4 : lex INT $$ = new Exp constant(type INT, $1);, 1 ::= 20 ::= program, $1, expression4 print 5 6 make mci t801mc (lex ) 2004 /mci t801mc, ( 2004) 82 20 ::= 8 5
1 expression4, expression4 : lex INT $$ = new Exp constant(type INT, $1); lex CHAR 2 $$ = new Exp constant(type CHAR, $1); 6 t802mc x, x OK /mci t802mc 83 20 ::= 1 expression4 expression4 : lex INT $$ = new Exp constant(type INT, $1); lex CHAR $$ = new Exp constant(type CHAR, $1); exp variable $$ = $1; exp variable, 11 ::=, Part-6 8 6
exp variable : lex ID $$ = new Exp variable($1); $1 lex ID, Exp variable 2 exp variable Part-2 %union exp variale exp variable %union char* string; int val; Expression* expression; Exp variable* exp variable; Part-4 exp variale %union exp variale // -------------------------------------------------------------------- // [Part-4] // -------------------------------------------------------------------- %type <expression> expression4 %type <exp variable> exp variable 3 t803mc (lex ) xyz OK t801mc, t802mc 84, 19 ::= ( "*" "/" "%" ) 19 ::= "*",, "*", "*" "*",, 1 expression3 8 7
expression3 : expression4 $$ = $1; expression3 lex STAR expression4 $$ = new Exp operation2(operator MUL, $1, $3); 2, program program : expression3 $1->print(std::cout); std::cout<<std::endl; 3 Part-4 expression3 4 %type <expression> expression4 %type <exp variable> exp variable %type <expression> expression3 t804mc 123 * x *2 mci ((123 * x) * 2) OK t801mc t803mc 85 1 expression3,, yacc,, 19 ::= ( "*" "/" "%" ) 19 ::= "*" "/" "%" 2,, t805mc, mci 23 * x / 45 % c 8 8
(((23 * x) / 45) % c) OK 86 +, 18 ::= ( "+" "-" ) ( "+" "-" ) 18 ::= ( "+" ), (+ -) 1 expression2 expression2 : expression3 $$ = $1; lex PLUS expression3 $$ = new Exp operation1(operator PLUS, $2); 2, program program : expression2 $1->print(std::cout); std::cout<<std::endl; 3 Part-4 expression2 4 %type <expression> expression4 %type <exp variable> exp variable %type <expression> expression3 %type <expression> expression2 + t806mc, mci + 81 / a * 23 (+((81 / a) * 23)) OK 87 8 9
18 ::= ( "+" "-" ) 1 t807mc, mci -123*x (-(123 * x)) OK t805mc, t806mc 88 18 ::= ( "+" "-" ) ( "+" "-" ), 1 t808mc, mci -123 + a*48-9/xy (((-123) + (a * 48)) - (9 / xy)) OK 89 expression, 17 ::= ( "<" ">" "<=" ">=" "==" "!=" ) program Part-4 86 1 t809mc, mci -23*a == b!= 2+9 < x > y <= z >= -2 (((((((-(23 * a)) == b)!= (2 + 9)) < x) > y) <= z) >= (-2)) OK 810,, 20 ::= "(" ")" 1 expression4??? 8 10
??? expression??? 2 $$ = $2; t810mc, mci (10-(x+y)*8) > a/(-2) ((10 - ((x + y) * 8)) > (a / (-2))) OK 811, 20 ::= "(" ")" 1 expression4, exp function $$ = $1; 2 exp function, 21 ::= "(" ")",??? exp function :?????? explist??? $$ = new Exp function($1, *$3); delete $3; explist, expression list 4 $3 * $3, Exp function list 2,, delete 3 explist, 16 ::= ",", 2 C,, 8 11
explist : $$ = new std::list<expression*>; // expression $$ = new std::list<expression*>; $$->push back($1); explist lex COMMA expression $1->push back($3); $$ = $1;, 4 Part-2 Part-4, exp function explist Part-2 1 std::list<expression*>* explist; Part-4 2 5 %type <expression> exp function %type <explist> explist t811mc, mci asum(15,a+3)*9==5 ((asum(15,(a + 3)) * 9) == 5) OK, t801mc t810mc 812, 9 ::= "" "" if while return statement, Statement 1 Part-6 8 12
statement : st assign $$ = $1; lex LBRACE st list lex RBRACE $$ = $2; st if $$ = $1; st while $$ = $1; st return $$ = $1; st function $$ = $1; st assign, st assign : st list : st if : st while : st return : st function :,, program : statement $1->print(std::cout); std::cout<<std::endl; 2 Part-4 %type <statement> statement %type <statement> st assign %type <statement> st if %type <statement> st while %type <statement> st return %type <statement> st function %type <statement> st list 3 Part-2 Statement* statement; 4 make mci Statement* statement; parseyy contains 7 useless nonterminals and 26 useless rules parseyy contains 1 reduce/reduce conflict,,, Segmentation fault 813 1 Part-6 10 ::= "=" ";" st assign??? 8 13
st assign : exp variable????????? 2 $$ = new St assign($1, $3); t813mc, mci x = (a*b+c)/d ; x = (((a * b) + c) / d); OK 814 ( ) 8 :: = 1 Part-6 st list stlist (stlist Part-2, 4 ) stlist st list, stlist (list<statement*>, st list (St list) st list : stlist $$ = new St list(*$1); delete $1; stlist : $$ = new std::list<statement*>; stlist statement $1->push back($2); $$ = $1; 2 t814mc, mci x = a+2; y = b*c; z = x+y; 8 14
, 815 if x = (a + 2); y = (b * c); z = (x + y); OK if 12 if ::= "if" "(" ")" "if" "(" ")" "else" 1 Part-6????????? st if : lex KW IF lex LPAREN expression lex RPAREN statement $$ = new St if($3, $5, NULL);????????? 2 $$ =?????????; t815amc, mci, if (a>0) b = a; else b = -a; if ((a > 0)) b = a; else b = (-a); OK t815bmc, mci, if (a>0) b = a; if ((a > 0)) b = a; else OK 8 15
816 while 1 while 2 13 while ::= "while" "(" ")" t816mc, mci, while (i<n) s = s * i; i = i + 1; while ((i < n)) s = (s * i); i = (i + 1); OK 817 return 1 return 2 14 return ::= "return" ";" t817mc, mci return 9; OK 818 1 15 ::= "(" ")" ";" 811 explist, 2 t818mc, mci gcd(25,b);, gcd(25,b); OK 819 3 ::= 4 ::= "int" "char" 8 16
1 Part-6 variable dcl, type variable dcl : type lex ID $$ = new Variable($1, $2); type : lex KW INT $$ = Type INT; lex KW CHAR $$ = Type CHAR; 2 Part-2 Part-4, variable type Part-2 1 Variable* variable; Type type; Part-4 2 %type <variable> variable dcl %type <type> type 3 Part-6 program program : variable dcl 4 $1->print(std::cout); std::cout<<std::endl; t819mc, mci int x OK 820 ( ) 1, 5 ::= "(" ")" "" "" 6 :: = "," 7 :: = ";" 5 ::= "(" ")" "" "" 8 17
Part-6 function dcl, argument dcllist, variable dcllist, st list??? function dcl :????????? argument dcllist?????? variable dcllist st list??? $$ = new Function($1, $2, *$4, *$7, $8); delete $4; delete $7; 2, 6 :: = ",",, 6 :: =, Part-6 3 argument dcllist : $$ = new std::list<variable*>; 7 :: = ";", 7 :: =, Part-6 variable dcllist : $$ = new std::list<variable*>; 4 Part-2 Part-4, function dcl, argument dcllist, variable dcllist Part-2 Function* function; std::list<variable*>* varlist; Part-4 %type <function> function dcl %type <varlist> argument dcllist %type <varlist> variable dcllist 5 Part-6 program 8 18
program : function dcl 6 $1->print(std::cout); std::cout<<std::endl; t820mc, mci int kansuu() a = 10; return x + y; int kansuu() a = 10; return (x + y); OK 821 ( ) 1 Part-6 argument dcllist 6 :: = ","??? argument dcllist : $$ = new std::list<variable*>;??? $$ = new std::list<variable*>; $$->push back($1);????????? 2 $1->push back($3); $$ = $1; t821amc, mci 8 19
int kansuu(int n) OK t821bmc, mci int kansuu(int n, char c, int x) OK 822 ( ) 1 Part-6 variable dcllist 7 :: = ";" 2 t822amc mci int kansuu(int n, char c, int x) int i; int j; int k; return x; OK t822bmc mci int asum(int n) int s; int i; s = 0; i = -n; while(i<=n) if (i<0) s = s - i; else s = s + i; i = i + 1; return s; 8 20
(, ) OK 823, 1 ::= 2 ::= ( ";" ) 1 Part-6 program program : function dcl $1->print(std::cout); std::cout<<std::endl; program : dcllist ast = build program($1); (program) (dcllist) program, yacc, ( ) $$, ast,,, build program ( ) 2 Part-6 (dcllist) 2 ::= ( ";" ), (variable dcl) (function dcl), Declaration data, (vars) (funcs) Declaration data vars funcs 8 21
dcllist : $$ = new Declaration data; dcllist variable dcl lex SEMICOLON $1->varspush back($2); $$ = $1; dcllist function dcl $1->funcspush back($2); $$ = $1; 3 Declaration data, asth asth Return data, struct Declaration data ; std::list<variable*> vars; std::list<function*> funcs; Varible, map Function Variable #include <map> class Function; class Variable; 4 Part-1 ast build program int yylex(void); int yyerror(char*); Program* ast; Program* build program(declaration data* dd); 5 Part-2 Part-4, dcllist Part-2 Declaration data* declaration data; Part-4 %type <declaration data> dcllist 6 Part-7 build program "main", 8 22
Program* build program(declaration data* dd) std::list<function*> flist; Function* mainf; // dd funcs, "main" // mainf, flist std::list<function*>::iterator f; for(f = dd->funcsbegin(); f!= dd->funcsend(); f++) if ((*f)->name() == "main") mainf = *f; else flistpush back(*f); return new Program(dd->vars, flist, mainf); 7 Part-7 main ast int main(int argc, char *argv[]) if(std::file* fp = std::fopen(argv[1], "r")) linenum = 1; // lex 1 yyin = fp; yyparse(); ast->print(std::cout); else 8 // lex // printf(" %s \n", argv[1]); mini-c factormc mci 8 23
1: char separator; 2: 3: 4: int factor(int n) 5: 6: int d; 7: d = 2; 8: while (((d * d) <= n)) 9: if (((n % d) == 0)) 10: putint(d); 11: putchar(separator); 12: n = (n / d); 13: 14: else 15: d = (d + 1); 16: 17: 18: putint(n); 19: putchar( \n ); 20: 21: 22: 23: int main() 24: 25: int n; 26: putchar( n ); 27: putchar( = ); 28: n = getint(); 29: separator = * ; 30: factor(n); 31: OK 824, 1 Part-7 main ast->print(std::cout);, run ast->run(); 2 factormc mci, 825 mini-c,, 8 24
825 mini-c (8 25mc) parseyy lexll asth astcpp Nagisa ISHIURA Mini-C 1 ::= 2 ::= ( ";" ) 3 ::= 4 ::= "int" "char" 5 ::= "(" ")" "" "" 6 :: = "," 7 :: = ";" 8 :: = 9 ::= "" "" if while return 10 ::= "=" ";" 11 ::= 12 if ::= "if" "(" ")" "if" "(" ")" "else" 13 while ::= "while" "(" ")" 14 return ::= "return" ";" 15 ::= "(" ")" ";" 16 ::= "," 17 ::= ( "<" ">" "<=" ">=" "==" "!=" ) 18 ::= ( "+" "-" ) ( "+" "-" ) 19 ::= ( "*" "/" "%" ) 20 ::= "(" ")" 21 ::= "(" ")" 8 25