%{ #include #include #include #include "symtable.h" #include "chelper.h" #include "tree.h" #define MAX(A,B) (A > B ? A : B) %} %start Input %token STRUCT END METHOD VAR IF THEN ELSE WHILE DO RETURN NOT OR THIS IDENT NUM ASSIGN @macro xxputsin(xx,) @i xx = @Statement.sin@; @end @macro statinout() @i @Statement.sout@ = @Statement.sin@; /* das *> xxputsin(@Statement.sout@,) * geht nicht, weil verschachtelte macros deaktiviert sind */ @end @macro lblcountinout() @i @Statement.lblcnt_out@ = @Statement.lblcnt_in@; @end @macro varsinout() @i @Statement.vars_out@ = @Statement.vars_in@; @end /* beschreibung der attribute * s: symboltabelle * f: symboltabelle fuer quirks mit structur und parameter * gparamges: anzahl der parameter in einer methode * parms: parametercounter * node: baum fuer iburg * sin: symboltabelle fuer statement ("eingabe") * sout: symboltabelle die aus einem statement wieder rauskommt ("ausgabe") */ @autoinh s gparamges vars_in @autosyn node imm call @attributes { char *name; } IDENT @attributes { long val; } NUM @attributes { struct symbol *f; int paramges; int parms; } Parms @attributes { struct symbol *f; } Program Structdef; @attributes { struct symbol *f; int offsetcount; } FeldID @attributes { struct symbol *s; } Methoddef @attributes { struct symbol *s; int gparamges; int vars_in; int cnt; int paramcount; struct treenode *node; } Exprs @attributes { struct symbol *s; int gparamges; int lblcnt_in; int lblcnt_out; int vars_in; int vars_out; int call; } Statseq @attributes { struct symbol *s; int gparamges; int lblcnt_in; int lblcnt_out; int reallblcnt; int vars_in; int vars_out; int call; } Elsestat @attributes { struct symbol *s; int gparamges; int vars_in; struct treenode *node; short imm; int call; } Expr Minusterm Multerm Orterm Feld Term @attributes { struct symbol *s; int gparamges; int vars_in; struct treenode *node; } Lexpr @attributes { struct symbol *sin; int gparamges; struct symbol *sout; struct treenode *node; int vars_in; int vars_out; int lblcnt_in; int lblcnt_out; int call; } Statement @traversal @postorder c @traversal @preorder reg @traversal @preorder gen %% Input: Program @{ @i @Program.f@ = tab_new(); @gen printf("\t.section\t\".text\"\n"); @} ; Program: Methoddef ';' Program @{ @i @Methoddef.s@ = @Program.0.f@; @i @Program.1.f@ = @Program.0.f@; @} | Structdef ';' Program @{ @i @Program.1.f@ = tab_merge(@Program.0.f@, @Structdef.f@, 1); @} | ; Methoddef: METHOD IDENT '(' Parms ')' Statseq END @{ @i @Parms.parms@ = 1; @i @Statseq.s@ = tab_merge(@Methoddef.s@, @Parms.f@, 0); @i @Statseq.vars_in@ = 0; @i @Statseq.gparamges@ = @Parms.paramges@; @i @Statseq.lblcnt_in@ = 0; @gen func_header(@IDENT.name@, @Statseq.vars_out@, @Parms.paramges@, @Statseq.call@); @} ; Structdef: STRUCT FeldID END @{ @i @Structdef.f@ = @FeldID.f@; @i @FeldID.offsetcount@ = 0; @} ; Parms: /* lokale Vars werden in Statement in die tabelle eingefuegt */ IDENT Parms @{ @i @Parms.1.parms@ = @Parms.0.parms@ + 1; @i @Parms.0.paramges@ = @Parms.1.paramges@; @i @Parms.0.f@ = tab_add_symbol(@Parms.1.f@, @IDENT.name@, S_PARM, 1, @Parms.parms@, -1); @} | @{ @i @Parms.f@ = tab_new(); @i @Parms.paramges@ = @Parms.parms@; @} ; FeldID: IDENT FeldID @{ @i @FeldID.1.offsetcount@ = @FeldID.0.offsetcount@ + 1; @i @FeldID.0.f@ = tab_add_symbol(@FeldID.1.f@, @IDENT.name@, S_FIELD, 1, -1, @FeldID.0.offsetcount@); @} | @{ @i @FeldID.f@ = tab_new(); @} ; Statseq: Statement ';' Statseq @{ @i @Statement.sin@ = @Statseq.0.s@; @i @Statement.lblcnt_in@ = @Statseq.0.lblcnt_in@; @i @Statseq.1.s@ = @Statement.sout@; @i @Statseq.1.lblcnt_in@ = @Statement.lblcnt_out@; @i @Statseq.1.gparamges@ = @Statseq.0.gparamges@; @i @Statement.vars_in@ = @Statseq.0.vars_in@; @i @Statseq.1.vars_in@ = @Statement.vars_out@; @i @Statseq.0.lblcnt_out@ = @Statseq.1.lblcnt_out@; @i @Statseq.0.vars_out@ = @Statseq.1.vars_out@; @i @Statseq.0.call@ = @Statement.call@ || @Statseq.1.call@; @} | @{ @i @Statseq.0.lblcnt_out@ = @Statseq.0.lblcnt_in@; @i @Statseq.0.vars_out@ = @Statseq.0.vars_in@; @i @Statseq.0.call@ = 0; @} ; Statement: Lexpr ASSIGN Expr @{ statinout() lblcountinout() varsinout() xxputsin(@Lexpr.s@,) xxputsin(@Expr.s@,) @i @Statement.node@ = new_node(O_ASSIGN, @Expr.node@, @Lexpr.node@); @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@); @reg @Lexpr.node@->reg = next_reg(@Expr.node@->reg, @Expr.gparamges@); @gen write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1); @} | VAR IDENT ASSIGN Expr @{ /* tab_clone ist hier noetig, vgl. folgendes statement * > var x := x - 1; */ @i @Statement.sout@ = tab_add_symbol(tab_clone(@Statement.sin@), @IDENT.name@, S_VAR, 1, @Statement.gparamges@ + @Statement.vars_in@, -1); lblcountinout() @i @Statement.vars_out@ = @Statement.vars_in@ + 1; xxputsin(@Expr.s@,) @i @Statement.node@ = new_node(O_ASSIGN, @Expr.node@, new_param(O_ID, @IDENT.name@, TREENULL, TREENULL, @Statement.gparamges@ + @Statement.vars_in@)); @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@); @gen write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1); @} | Expr @{ statinout() varsinout() lblcountinout() xxputsin(@Expr.s@,) @i @Statement.node@ = new_node(O_EXPR, @Expr.node@, TREENULL); @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@); @gen write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1); @} | IF Expr THEN Statseq END @{ statinout() @i @Statseq.lblcnt_in@ = @Statement.lblcnt_in@ + 1; @i @Statement.lblcnt_out@ = @Statseq.lblcnt_out@; @i @Statseq.vars_in@ = @Statement.vars_in@; @i @Statement.vars_out@ = @Statseq.vars_out@; @i @Statement.call@ = @Expr.call@ || @Statseq.call@; xxputsin(@Expr.s@,) xxputsin(@Statseq.s@,) @i @Statement.node@ = new_node(O_IF, @Expr.node@, TREENULL); @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@); @gen { printf(".%s_ifstart_%d:\n", get_func_name(), @Statement.lblcnt_in@); write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1); printf("\tbeq 0,.%s_ifend_%d\n", get_func_name(), @Statement.lblcnt_in@); } @gen @revorder(1) printf(".%s_ifend_%d:\n", get_func_name(), @Statement.lblcnt_in@); @} | IF Expr THEN Statseq Elsestat END @{ statinout() @i @Statseq.0.lblcnt_in@ = @Statement.lblcnt_in@ + 1; @i @Elsestat.lblcnt_in@ = @Statseq.lblcnt_out@; @i @Statement.lblcnt_out@ = @Elsestat.lblcnt_out@; /* im Elsestat muss noch ein label numeriert werden */ @i @Elsestat.reallblcnt@ = @Statement.lblcnt_in@; @i @Statseq.vars_in@ = @Statement.vars_in@; @i @Elsestat.vars_in@ = @Statement.vars_in@; @i @Statement.vars_out@ = MAX(@Statseq.vars_out@, @Elsestat.vars_out@); @i @Statement.call@ = @Expr.call@ || @Statseq.call@ || @Elsestat.call@; xxputsin(@Expr.s@,) xxputsin(@Statseq.0.s@,) xxputsin(@Elsestat.s@,) @i @Statement.node@ = new_node(O_IF, @Expr.node@, TREENULL); @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@); @gen { printf(".%s_ifstart_%d:\n", get_func_name(), @Statement.lblcnt_in@); write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1); printf("\tbeq 0,.%s_ifelse_%d\n", get_func_name(), @Statement.lblcnt_in@); } @gen @revorder(1) printf(".%s_ifend_%d:\n", get_func_name(), @Statement.lblcnt_in@); @} | WHILE Expr DO Statseq END @{ statinout() @i @Statseq.lblcnt_in@ = @Statement.lblcnt_in@ + 1; @i @Statement.lblcnt_out@ = @Statseq.lblcnt_out@; @i @Statseq.vars_in@ = @Statement.vars_in@; @i @Statement.vars_out@ = @Statseq.vars_out@; @i @Statement.call@ = @Expr.call@ || @Statseq.call@; xxputsin(@Expr.s@,) xxputsin(@Statseq.s@,) @i @Statement.node@ = new_node(O_IF, @Expr.node@, TREENULL); @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@); @gen { printf(".%s_whilestart_%d:\n", get_func_name(), @Statement.lblcnt_in@); write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1); printf("\tbeq 0,.%s_whileend_%d\n", get_func_name(), @Statement.lblcnt_in@); } @gen @revorder(1) printf("\tb .%s_whilestart_%d\n.%s_whileend_%d:\n", get_func_name(), @Statement.lblcnt_in@, get_func_name(), @Statement.lblcnt_in@); @} | RETURN Expr @{ statinout() lblcountinout() varsinout() xxputsin(@Expr.s@,) @i @Statement.node@ = new_node(O_RET, @Expr.node@, TREENULL); @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@); @gen write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1); func_footer(); @} ; Elsestat: ELSE Statseq @{ @i @Statseq.lblcnt_in@ = @Elsestat.lblcnt_in@; @i @Elsestat.lblcnt_out@ = @Statseq.lblcnt_out@; @i @Statseq.vars_in@ = @Elsestat.vars_in@; @i @Elsestat.vars_out@ = @Statseq.vars_out@; @gen printf("\tb .%s_ifend_%d\n.%s_ifelse_%d:\n", get_func_name(), @Elsestat.reallblcnt@, get_func_name(), @Elsestat.reallblcnt@); @} Lexpr: IDENT @{ @c check(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM); /* TODO: selbe Code wie bei Term/IDENT -- schoener machen! */ @i { @Lexpr.node@ = TREENULL; if(tab_lookup(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) { /* es handelt sich um ein feldzugriff auf this */ @Lexpr.node@ = new_field(@IDENT.name@, new_param(O_ID, strdup("this"), TREENULL, TREENULL, 0), TREENULL, tab_lookup(@Lexpr.s@, @IDENT.name@, S_FIELD) == SYMNULL ? -1 : tab_lookup(@Lexpr.s@, @IDENT.name@, S_FIELD)->soffset); } else { /* param oder var */ int tmp = tab_lookup(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL ? -1 : tab_lookup(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM)->param_index; @Lexpr.node@ = new_param(O_ID, @IDENT.name@, TREENULL, TREENULL, tmp); } } @reg if(tab_lookup(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) { /* TODO: kein schoener hack? */ @Lexpr.node@->kids[0]->reg = @Lexpr.node@->reg; } @} | Feld ; Feld: Term '.' IDENT @{ @c check(@Feld.s@, @IDENT.name@, S_FIELD); @i @Feld.node@ = new_field(@IDENT.name@, @Term.node@, TREENULL, tab_lookup(@Feld.s@, @IDENT.name@, S_FIELD) == SYMNULL ? -1 : tab_lookup(@Feld.s@, @IDENT.name@, S_FIELD)->soffset); @reg @Term.node@->reg = next_reg(@Feld.node@->reg, @Term.gparamges@); @} ; Expr: Term @{ @reg @Term.node@->reg = @Expr.node@->reg; @} | NOT Term @{ @i @Expr.node@ = new_node(O_BOOL, new_node(O_EQ, @Term.node@, new_node(O_NULL, TREENULL, TREENULL)), TREENULL); @reg @Term.node@->reg = @Expr.node@->kids[0]->reg = @Expr.node@->reg; @} | Term Minusterm @{ @i @Expr.node@ = new_node(O_SUB, @Term.node@, @Minusterm.node@); @i @Expr.imm@ = @Term.imm@ && @Minusterm.imm@; @i @Expr.call@ = @Term.call@ || @Minusterm.call@; @reg { if(!(@Expr.node@->kids[0] == TREENULL && @Expr.node@->kids[1] == TREENULL)) { @Term.node@->reg = @Expr.node@->reg; if(@Minusterm.imm@) { @Minusterm.node@->reg = @Expr.node@->reg; } else { @Minusterm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@); } } } @} | Term Multerm @{ @i @Expr.node@ = new_node(O_MUL, @Term.node@, @Multerm.node@); @i @Expr.imm@ = @Term.imm@ && @Multerm.imm@; @i @Expr.call@ = @Term.call@ || @Multerm.call@; @reg { @Term.node@->reg = next_reg(@Expr.node@->reg, @Expr.gparamges@); if(@Term.imm@) { @Multerm.node@->reg = @Expr.node@->reg; } else { @Multerm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@); } } @} | Term Orterm @{ @i @Expr.node@ = new_node(O_OR, @Term.node@, @Orterm.node@); @i @Expr.imm@ = @Term.imm@ && @Orterm.imm@; @i @Expr.call@ = @Term.call@ || @Orterm.call@; @reg { @Term.node@->reg = @Expr.node@->reg; @Orterm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@); } @} | Term '<' Term @{ @i @Expr.node@ = new_node(O_BOOL, new_node(O_LESS, @Term.0.node@, @Term.1.node@), TREENULL); @i @Expr.imm@ = @Term.0.imm@ && @Term.1.imm@; @i @Expr.call@ = @Term.0.call@ || @Term.1.call@; @reg { @Term.0.node@->reg = @Expr.node@->kids[0]->reg = @Expr.node@->reg; @Term.1.node@->reg = next_reg(@Term.0.node@->reg, @Expr.gparamges@); } @} | Term '=' Term @{ @i @Expr.node@ = new_node(O_BOOL, new_node(O_EQ, @Term.0.node@, @Term.1.node@), TREENULL); @i @Expr.imm@ = @Term.0.imm@ && @Term.1.imm@; @i @Expr.call@ = @Term.0.call@ || @Term.1.call@; @reg { @Term.0.node@->reg = @Expr.node@->kids[0]->reg = @Expr.node@->reg; @Term.1.node@->reg = next_reg(@Term.0.node@->reg, @Expr.gparamges@); } @} ; Minusterm: '-' Term Minusterm @{ @i @Minusterm.node@ = new_node(O_ADD, @Minusterm.1.node@, @Term.node@); @i @Minusterm.0.imm@ = @Term.imm@ && @Minusterm.1.imm@; @i @Minusterm.0.call@ = @Term.call@ || @Minusterm.1.call@; @reg { @Minusterm.1.node@->reg = @Minusterm.node@->reg; if(@Minusterm.1.imm@) { @Term.node@->reg = @Minusterm.node@->reg; } else { @Term.node@->reg = next_reg(@Minusterm.1.node@->reg, @Minusterm.gparamges@); } } @} | '-' Term @{ @reg @Term.node@->reg = @Minusterm.node@->reg; @} ; Multerm: '*' Term Multerm @{ @i @Multerm.node@ = new_node(O_MUL, @Multerm.1.node@, @Term.node@); @i @Multerm.0.imm@ = @Term.imm@ && @Multerm.1.imm@; @i @Multerm.0.call@ = @Term.call@ || @Multerm.1.call@; @reg { @Multerm.1.node@->reg = @Multerm.node@->reg; if(@Multerm.1.imm@) { @Term.node@->reg = @Multerm.node@->reg; } else { @Term.node@->reg = next_reg(@Multerm.1.node@->reg, @Multerm.gparamges@); } } @} | '*' Term @{ @reg @Term.node@->reg = @Multerm.node@->reg; @} ; Orterm: OR Term Orterm @{ @i @Orterm.node@ = new_node(O_OR, @Orterm.1.node@, @Term.node@); @i @Orterm.0.imm@ = @Term.imm@ && @Orterm.1.imm@; @i @Orterm.0.call@ = @Term.call@ || @Orterm.1.call@; @reg { @Orterm.1.node@->reg = @Orterm.node@->reg; if(@Orterm.1.imm@) { @Term.node@->reg = @Orterm.node@->reg; } else { @Term.node@->reg = next_reg(@Orterm.1.node@->reg, @Orterm.gparamges@); } } @} | OR Term @{ @reg @Term.node@->reg = @Orterm.node@->reg; @} ; Term: '(' Expr ')' @{ @i @Term.node@ = @Expr.node@; @} | NUM @{ @i @Term.node@ = new_number(@NUM.val@); @i @Term.imm@ = 1; @i @Term.call@ = 0; @} | '-' NUM @{ @i @Term.node@ = new_number(-1 * (@NUM.val@)); @i @Term.imm@ = 1; @i @Term.call@ = 0; @} | THIS @{ @i @Term.node@ = new_param(O_ID, strdup("this"), TREENULL, TREENULL, 0); @i @Term.imm@ = 0; @i @Term.call@ = 0; @} | IDENT @{ @c check(@Term.s@, @IDENT.name@, S_VAR|S_PARM); @i @Term.imm@ = 0; @i @Term.call@ = 0; @i { @Term.node@ = TREENULL; if(tab_lookup(@Term.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) { /* es handelt sich um ein feldzugriff auf this */ @Term.node@ = new_field(@IDENT.name@, new_param(O_ID, strdup("this"), TREENULL, TREENULL, 0), TREENULL, tab_lookup(@Term.s@, @IDENT.name@, S_FIELD) == SYMNULL ? -1 : tab_lookup(@Term.s@, @IDENT.name@, S_FIELD)->soffset); } else { /* param oder var */ int tmp = tab_lookup(@Term.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL ? -1 : tab_lookup(@Term.s@, @IDENT.name@, S_VAR|S_PARM)->param_index; @Term.node@ = new_param(O_ID, @IDENT.name@, TREENULL, TREENULL, tmp); } } @reg if(tab_lookup(@Term.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) { /* TODO: kein schoener hack? */ @Term.node@->kids[0]->reg = @Term.node@->reg; } @} | Feld @{ @i @Term.node@ = @Feld.node@; @i @Term.imm@ = 0; @} | IDENT '(' Exprs ')' @{ @i { @Term.node@ = new_call(@IDENT.name@, new_arg(@Exprs.node@, new_nothing(), 0) /*this*/, TREENULL, @Term.gparamges@, @Term.vars_in@); @Term.node@->soffset = MAX(@Exprs.paramcount@, @Term.gparamges@); } @i @Exprs.cnt@ = 1; @i @Term.imm@ = 0; @i @Term.call@ = 1; @reg @Exprs.node@->reg = @Term.node@->reg; @} | Term '.' IDENT '(' Exprs ')' @{ @i { @Term.node@ = new_call(@IDENT.name@, new_arg(@Exprs.node@, @Term.1.node@, 0) /*this*/, TREENULL, @Term.gparamges@, @Term.vars_in@); @Term.node@->soffset = MAX(@Exprs.paramcount@, @Term.gparamges@); } @i @Exprs.cnt@ = 1; @i @Term.imm@ = 0; @i @Term.call@ = 1; @reg @Exprs.node@->reg = @Term.1.node@->reg = @Term.node@->kids[0]->reg = @Term.node@->reg; @} ; Exprs: Expr ',' Exprs @{ @i @Exprs.0.node@ = new_arg(@Expr.0.node@, @Exprs.1.node@, @Exprs.0.cnt@); @i @Exprs.0.paramcount@ = @Exprs.1.paramcount@; @i @Exprs.1.cnt@ = @Exprs.0.cnt@ + 1; @reg @Expr.node@->reg = @Exprs.0.node@->reg; @Exprs.1.node@->reg = next_reg(@Exprs.0.node@->reg, @Exprs.gparamges@); @} | Expr @{ @i @Exprs.0.node@ = new_arg(@Expr.0.node@, new_nothing(), @Exprs.cnt@); @i @Exprs.paramcount@ = @Exprs.cnt@ + 1; @reg @Expr.node@->reg = @Exprs.0.node@->reg; @} | @{ @i @Exprs.0.node@ = new_nothing(); @i @Exprs.paramcount@ = @Exprs.cnt@; @} ; %% extern int yylex(); extern int yylineno; int yyerror(char *error_text) { fprintf(stderr,"Zeile %i: %s\n", yylineno, error_text); exit(2); } int main(int argc, char **argv) { #if 0 yydebug=1; #endif yyparse(); return 0; }