codeb/parser.y

   1 %{
   2         #include <stdio.h>
   3         #include <stdlib.h>
   4         #include <string.h>
   5         #include "symtable.h"
   6         #include "chelper.h"
   7         #include "tree.h"
   8
   9         #define MAX(A,B) (A > B ? A : B)
  10 %}
  11
  12 %start Input
  13 %token STRUCT END METHOD VAR IF THEN ELSE WHILE DO RETURN NOT OR THIS IDENT NUM ASSIGN
  14
  15 @macro xxputsin(xx,)
  16         @i xx = @Statement.sin@;
  17 @end
  18
  19 @macro statinout()
  20         @i @Statement.sout@ = @Statement.sin@;
  21         /* das
  22          *> xxputsin(@Statement.sout@,)
  23          * geht nicht, weil verschachtelte macros deaktiviert sind */
  24 @end
  25
  26 @macro lblcountinout()
  27         @i @Statement.lblcnt_out@ = @Statement.lblcnt_in@;
  28 @end
  29
  30 /* beschreibung der attribute
  31  * s: symboltabelle
  32  * f: symboltabelle fuer quirks mit structur und parameter
  33  * gparamges: anzahl der parameter in einer methode
  34  * parms: parametercounter
  35  * node: baum fuer iburg
  36  * sin: symboltabelle fuer statement ("eingabe")
  37  * sout: symboltabelle die aus einem statement wieder rauskommt ("ausgabe")
  38  */
  39 @autoinh s gparamges
  40 @autosyn node imm
  41
  42 @attributes { char *name; } IDENT
  43 @attributes { long val; } NUM
  44 @attributes { struct symbol *f; int paramges; int parms; } Parms
  45 @attributes { struct symbol *f; } Program Structdef;
  46 @attributes { struct symbol *f; int offsetcount; } FeldID
  47 @attributes { struct symbol *s; } Methoddef
  48 @attributes { struct symbol *s; int gparamges; } Exprs
  49 @attributes { struct symbol *s; int gparamges; int lblcnt_in; int lblcnt_out; } Statseq
  50 @attributes { struct symbol *s; int gparamges; int lblcnt_in; int lblcnt_out; int reallblcnt; } Elsestat
  51 @attributes { struct symbol *s; int gparamges; struct treenode *node; short imm; } Expr Minusterm Multerm Orterm Feld Term
  52 @attributes { struct symbol *s; int gparamges; struct treenode *node; } Lexpr
  53 @attributes { struct symbol *sin; int gparamges; struct symbol *sout; struct treenode *node; int vars; int lblcnt_in; int lblcnt_out; } Statement
  54
  55 @traversal @postorder c
  56 @traversal @preorder reg
  57 @traversal @preorder gen
  58
  59 %%
  60 Input:
  61           Program
  62           @{
  63             @i @Program.f@ = tab_new();
  64             @gen printf("\t.text\n");
  65           @}
  66         ;
  67
  68 Program:
  69           Methoddef ';' Program
  70           @{
  71             @i @Methoddef.s@ = @Program.0.f@;
  72             @i @Program.1.f@ = @Program.0.f@;
  73           @}
  74
  75         | Structdef ';' Program
  76           @{
  77             @i @Program.1.f@ = tab_merge(@Program.0.f@, @Structdef.f@, 1);
  78           @}
  79         |
  80         ;
  81
  82 Methoddef:
  83           METHOD IDENT '(' Parms ')' Statseq END
  84           @{
  85             @i @Parms.parms@ = 1;
  86             @i @Statseq.s@ = tab_merge(@Methoddef.s@, @Parms.f@, 0);
  87                 @i @Statseq.gparamges@ = @Parms.paramges@;
  88                 @i @Statseq.lblcnt_in@ = 0;
  89             @gen func_header(@IDENT.name@);
  90           @}
  91         ;
  92
  93 Structdef:
  94           STRUCT FeldID END
  95           @{
  96             @i @Structdef.f@ = @FeldID.f@;
  97                 @i @FeldID.offsetcount@ = 0;
  98           @}
  99         ;
 100
 101 Parms:
 102           /* lokale Vars werden in Statement in die tabelle eingefuegt */
 103           IDENT Parms
 104           @{
 105             @i @Parms.1.parms@ = @Parms.0.parms@ + 1;
 106                 @i @Parms.0.paramges@ = @Parms.1.paramges@;
 107             @i @Parms.0.f@ = tab_add_symbol(@Parms.1.f@, @IDENT.name@, S_PARM, 1, @Parms.parms@, -1);
 108           @}
 109
 110         |
 111           @{
 112             @i @Parms.f@ = tab_new();
 113                 @i @Parms.paramges@ = @Parms.parms@;
 114           @}
 115         ;
 116
 117 FeldID:
 118           IDENT FeldID
 119           @{
 120             @i @FeldID.1.offsetcount@ = @FeldID.0.offsetcount@ + 1;
 121             @i @FeldID.0.f@ = tab_add_symbol(@FeldID.1.f@, @IDENT.name@, S_FIELD, 1, -1, @FeldID.0.offsetcount@);
 122           @}
 123
 124         |
 125           @{
 126             @i @FeldID.f@ = tab_new();
 127           @}
 128         ;
 129
 130 Statseq:
 131           Statement ';' Statseq
 132           @{
 133                 @i @Statement.sin@ = @Statseq.0.s@;
 134                 @i @Statement.lblcnt_in@ = @Statseq.0.lblcnt_in@;
 135
 136                 @i @Statseq.1.s@ = @Statement.sout@;
 137                 @i @Statseq.1.lblcnt_in@ = @Statement.lblcnt_out@;
 138                 @i @Statseq.1.gparamges@ = @Statseq.0.gparamges@ + @Statement.vars@;
 139
 140                 @i @Statseq.0.lblcnt_out@ = @Statseq.1.lblcnt_out@;
 141           @}
 142
 143         |
 144           @{
 145                 @i @Statseq.0.lblcnt_out@ = @Statseq.0.lblcnt_in@;
 146           @}
 147         ;
 148
 149 Statement:
 150           Lexpr ASSIGN Expr
 151           @{
 152                 statinout()
 153                 lblcountinout()
 154                 xxputsin(@Lexpr.s@,)
 155                 xxputsin(@Expr.s@,)
 156             @i @Statement.node@ = new_node(O_ASSIGN, @Expr.node@, @Lexpr.node@);
 157                 @i @Statement.vars@ = 0;
 158                 @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@);
 159                 @reg @Lexpr.node@->reg = next_reg(@Expr.node@->reg, @Expr.gparamges@);
 160
 161                 @gen write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1);
 162           @}
 163
 164         | VAR IDENT ASSIGN Expr
 165           @{
 166                 /* tab_clone ist hier noetig, vgl. folgendes statement
 167                  * > var x := x - 1; */
 168                 @i @Statement.sout@ = tab_add_symbol(tab_clone(@Statement.sin@), @IDENT.name@, S_VAR, 1, @Statement.gparamges@, -1);
 169                 lblcountinout()
 170                 xxputsin(@Expr.s@,)
 171
 172                 @i @Statement.node@ = new_node(O_ASSIGN, @Expr.node@, new_param(O_ID, @IDENT.name@, TREENULL, TREENULL, @Statement.gparamges@));
 173                 @i @Statement.vars@ = 1;
 174                 @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@);
 175
 176                 @gen write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1);
 177           @}
 178
 179         | Expr
 180           @{
 181                 statinout()
 182                 lblcountinout()
 183                 xxputsin(@Expr.s@,)
 184             @i @Statement.node@ = TREENULL;
 185                 @i @Statement.vars@ = 0;
 186           @}
 187
 188         | IF Expr THEN Statseq END
 189           @{
 190                 statinout()
 191                 @i @Statseq.lblcnt_in@ =  @Statement.lblcnt_in@ + 1;
 192                 @i @Statement.lblcnt_out@ = @Statseq.lblcnt_out@;
 193                 xxputsin(@Expr.s@,)
 194                 xxputsin(@Statseq.s@,)
 195
 196                 @i @Statement.node@ = new_node(O_IF, @Expr.node@, TREENULL);
 197                 @i @Statement.vars@ = 0;
 198
 199                 @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@);
 200                 @gen {
 201                         printf("%s_ifstart_%d:\n", get_func_name(), @Statement.lblcnt_in@);
 202                         write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1);
 203                         /* TODO: kann ich mir das test wirklich wegan and davor sparen? */
 204                         printf("\ttest %s1, %%rax\n\tjz %s_ifend_%d\n", "$", get_func_name(), @Statement.lblcnt_in@);
 205                 }
 206                 @gen @revorder(1) printf("%s_ifend_%d:\n", get_func_name(), @Statement.lblcnt_in@);
 207           @}
 208
 209         | IF Expr THEN Statseq Elsestat END
 210           @{
 211                 statinout()
 212                 @i @Statseq.0.lblcnt_in@ = @Statement.lblcnt_in@ + 1;
 213                 @i @Elsestat.lblcnt_in@ = @Statseq.lblcnt_out@;
 214                 @i @Statement.lblcnt_out@ = @Elsestat.lblcnt_out@;
 215
 216                 /* im Elsestat muss noch ein label numeriert werden */
 217                 @i @Elsestat.reallblcnt@ = @Statement.lblcnt_in@;
 218
 219                 xxputsin(@Expr.s@,)
 220                 xxputsin(@Statseq.0.s@,)
 221                 xxputsin(@Elsestat.s@,)
 222
 223                 @i @Statement.node@ = new_node(O_IF, @Expr.node@, TREENULL);
 224                 @i @Statement.vars@ = 0;
 225
 226                 @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@);
 227                 @gen {
 228                         printf("%s_ifstart_%d:\n", get_func_name(), @Statement.lblcnt_in@);
 229                         write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1);
 230                         /* TODO: kann ich mir das test wirklich wegan and davor sparen? */
 231                         printf("\ttest %s1, %%rax\n\tjz %s_ifelse_%d\n", "$", get_func_name(), @Statement.lblcnt_in@);
 232                 }
 233                 @gen @revorder(1) printf("%s_ifend_%d:\n", get_func_name(), @Statement.lblcnt_in@);
 234           @}
 235
 236         | WHILE Expr DO Statseq END
 237           @{
 238                 statinout()
 239                 @i @Statseq.lblcnt_in@ =  @Statement.lblcnt_in@ + 1;
 240                 @i @Statement.lblcnt_out@ = @Statseq.lblcnt_out@;
 241                 xxputsin(@Expr.s@,)
 242                 xxputsin(@Statseq.s@,)
 243
 244                 @i @Statement.node@ = new_node(O_IF, @Expr.node@, TREENULL);
 245                 @i @Statement.vars@ = 0;
 246
 247                 @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@);
 248                 @gen {
 249                         printf("%s_whilestart_%d:\n", get_func_name(), @Statement.lblcnt_in@);
 250                         write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1);
 251                         /* TODO: kann ich mir das test wirklich wegan and davor sparen? */
 252                         printf("\ttest %s1, %%rax\n\tjz %s_whileend_%d\n", "$", get_func_name(), @Statement.lblcnt_in@);
 253                 }
 254                 @gen @revorder(1) printf("\tjmp %s_whilestart_%d\n%s_whileend_%d:\n", get_func_name(), @Statement.lblcnt_in@, get_func_name(), @Statement.lblcnt_in@);
 255           @}
 256
 257         | RETURN Expr
 258           @{
 259                 statinout()
 260                 lblcountinout()
 261                 xxputsin(@Expr.s@,)
 262
 263                 @i @Statement.vars@ = 0;
 264                 @i @Statement.node@ = new_node(O_RET, @Expr.node@, TREENULL);
 265                 @reg @Statement.node@->reg = @Expr.node@->reg = next_reg((char *)NULL, @Expr.gparamges@);
 266
 267                 @gen write_tree(@Statement.node@, 0); burm_label(@Statement.node@); burm_reduce(@Statement.node@, 1);
 268           @}
 269         ;
 270
 271 Elsestat:
 272           ELSE Statseq
 273           @{
 274                 @i @Statseq.lblcnt_in@ =  @Elsestat.lblcnt_in@;
 275                 @i @Elsestat.lblcnt_out@ =  @Statseq.lblcnt_out@;
 276
 277                 @gen printf("\tjmp %s_ifend_%d\n%s_ifelse_%d:\n", get_func_name(), @Elsestat.reallblcnt@, get_func_name(), @Elsestat.reallblcnt@);
 278           @}
 279
 280 Lexpr:
 281           IDENT
 282           @{
 283             @c check(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM);
 284
 285                 /* TODO: selbe Code wie bei Term/IDENT -- schoener machen! */
 286             @i {
 287                         @Lexpr.node@ = TREENULL;
 288                         if(tab_lookup(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) {
 289                                 /* es handelt sich um ein feldzugriff auf this */
 290                                 @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);
 291                         } else { /* param oder var */
 292                                 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;
 293                                 @Lexpr.node@ = new_param(O_ID, @IDENT.name@, TREENULL, TREENULL, tmp);
 294                         }
 295                 }
 296
 297                 @reg if(tab_lookup(@Lexpr.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) {
 298                         /* TODO: kein schoener hack? */
 299                         @Lexpr.node@->kids[0]->reg = @Lexpr.node@->reg;
 300                 }
 301           @}
 302
 303         | Feld
 304         ;
 305
 306 Feld: Term '.' IDENT
 307           @{
 308             @c check(@Feld.s@, @IDENT.name@, S_FIELD);
 309             @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);
 310
 311                 @reg @Term.node@->reg = next_reg(@Feld.node@->reg, @Term.gparamges@);
 312           @}
 313         ;
 314
 315 Expr:
 316           Term
 317           @{
 318             @reg @Term.node@->reg = @Expr.node@->reg;
 319           @}
 320
 321         | NOT Term
 322           @{
 323                 @i @Expr.node@ = new_node(O_EQ, @Term.node@, new_node(O_NULL, TREENULL, TREENULL));
 324
 325                 @reg @Term.node@->reg = @Expr.node@->reg;
 326           @}
 327
 328         | Term Minusterm
 329           @{
 330             @i @Expr.node@ = new_node(O_SUB, @Term.node@, @Minusterm.node@);
 331                 @i @Expr.imm@ = @Term.imm@ && @Minusterm.imm@;
 332
 333                 @reg {
 334                         if(!(@Expr.node@->kids[0] == TREENULL && @Expr.node@->kids[1] == TREENULL)) {
 335                                 @Term.node@->reg = @Expr.node@->reg;
 336                                 if(@Minusterm.imm@) {
 337                                         @Minusterm.node@->reg = @Expr.node@->reg;
 338                                 } else {
 339                                         @Minusterm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@);
 340                                 }
 341                         }
 342                 }
 343           @}
 344
 345         | Term Multerm
 346           @{
 347             @i @Expr.node@ = new_node(O_MUL, @Term.node@, @Multerm.node@);
 348                 @i @Expr.imm@ = @Term.imm@ && @Multerm.imm@;
 349
 350                 @reg {
 351                         @Term.node@->reg = @Expr.node@->reg;
 352                         if(@Term.imm@) {
 353                                 @Multerm.node@->reg = @Expr.node@->reg;
 354                         } else {
 355                                 @Multerm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@);
 356                         }
 357                 }
 358           @}
 359
 360         | Term Orterm
 361           @{
 362             @i @Expr.node@ = new_node(O_OR, @Term.node@, @Orterm.node@);
 363                 @i @Expr.imm@ = @Term.imm@ && @Orterm.imm@;
 364
 365                 @reg {
 366                         @Term.node@->reg = @Expr.node@->reg;
 367                         @Orterm.node@->reg = next_reg(@Term.node@->reg, @Expr.gparamges@);
 368                 }
 369           @}
 370
 371         | Term '<' Term
 372           @{
 373             @i @Expr.node@ = new_node(O_LESS, @Term.0.node@, @Term.1.node@);
 374                 @i @Expr.imm@ = @Term.0.imm@ && @Term.0.imm@;
 375
 376                 @reg {
 377                         @Term.0.node@->reg = @Expr.node@->reg;
 378                         @Term.1.node@->reg = next_reg(@Term.0.node@->reg, @Expr.gparamges@);
 379                 }
 380           @}
 381
 382         | Term '=' Term
 383           @{
 384             @i @Expr.node@ = new_node(O_EQ, @Term.0.node@, @Term.1.node@);
 385                 @i @Expr.imm@ = @Term.0.imm@ && @Term.0.imm@;
 386
 387                 @reg {
 388                         @Term.0.node@->reg = @Expr.node@->reg;
 389                         @Term.1.node@->reg = next_reg(@Term.0.node@->reg, @Expr.gparamges@);
 390                 }
 391           @}
 392         ;
 393
 394 Minusterm:
 395           '-' Term Minusterm
 396           @{
 397             @i @Minusterm.node@ = new_node(O_ADD, @Minusterm.1.node@, @Term.node@);
 398                 @i @Minusterm.0.imm@ = @Term.imm@ && @Minusterm.1.imm@;
 399
 400             @reg {
 401                         @Minusterm.1.node@->reg = @Minusterm.node@->reg;
 402                         if(@Minusterm.1.imm@) {
 403                                 @Term.node@->reg = @Minusterm.node@->reg;
 404                         } else {
 405                                 @Term.node@->reg = next_reg(@Minusterm.1.node@->reg, @Minusterm.gparamges@);
 406                         }
 407                 }
 408           @}
 409
 410         | '-' Term
 411           @{
 412             @reg @Term.node@->reg = @Minusterm.node@->reg;
 413           @}
 414         ;
 415
 416 Multerm:
 417           '*' Term Multerm
 418           @{
 419             @i @Multerm.node@ = new_node(O_MUL, @Multerm.1.node@, @Term.node@);
 420                 @i @Multerm.0.imm@ = @Term.imm@ && @Multerm.1.imm@;
 421
 422             @reg {
 423                         @Multerm.1.node@->reg = @Multerm.node@->reg;
 424                         if(@Multerm.1.imm@) {
 425                                 @Term.node@->reg = @Multerm.node@->reg;
 426                         } else {
 427                                 @Term.node@->reg = next_reg(@Multerm.1.node@->reg, @Multerm.gparamges@);
 428                         }
 429                 }
 430           @}
 431
 432         | '*' Term
 433           @{
 434             @reg @Term.node@->reg = @Multerm.node@->reg;
 435           @}
 436         ;
 437
 438 Orterm:
 439           OR Term Orterm
 440           @{
 441             @i @Orterm.node@ = new_node(O_OR, @Orterm.1.node@, @Term.node@);
 442                 @i @Orterm.0.imm@ = @Term.imm@ && @Orterm.1.imm@;
 443
 444             @reg {
 445                         @Orterm.1.node@->reg = @Orterm.node@->reg;
 446                         if(@Orterm.1.imm@) {
 447                                 @Term.node@->reg = @Orterm.node@->reg;
 448                         } else {
 449                                 @Term.node@->reg = next_reg(@Orterm.1.node@->reg, @Orterm.gparamges@);
 450                         }
 451                 }
 452           @}
 453         | OR Term
 454           @{
 455             @reg @Term.node@->reg = @Orterm.node@->reg;
 456           @}
 457
 458         ;
 459
 460 Term:
 461           '(' Expr ')'
 462           @{
 463             @i @Term.node@ = @Expr.node@;
 464           @}
 465
 466         | NUM
 467           @{
 468             @i @Term.node@ = new_number(@NUM.val@);
 469                 @i @Term.imm@ = 1;
 470           @}
 471
 472         | '-' NUM
 473           @{
 474             @i @Term.node@ = new_number(-1 * (@NUM.val@));
 475                 @i @Term.imm@ = 1;
 476           @}
 477
 478         | THIS
 479           @{
 480             @i @Term.node@ = new_param(O_ID, strdup("this"), TREENULL, TREENULL, 0);
 481                 @i @Term.imm@ = 0;
 482           @}
 483
 484         | IDENT
 485           @{
 486             @c check(@Term.s@, @IDENT.name@, S_VAR|S_PARM);
 487
 488                 @i @Term.imm@ = 0;
 489             @i {
 490                         @Term.node@ = TREENULL;
 491                         if(tab_lookup(@Term.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) {
 492                                 /* es handelt sich um ein feldzugriff auf this */
 493                                 @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);
 494                         } else { /* param oder var */
 495                                 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;
 496                                 @Term.node@ = new_param(O_ID, @IDENT.name@, TREENULL, TREENULL, tmp);
 497                         }
 498                 }
 499
 500                 @reg if(tab_lookup(@Term.s@, @IDENT.name@, S_VAR|S_PARM) == SYMNULL) {
 501                         /* TODO: kein schoener hack? */
 502                         @Term.node@->kids[0]->reg = @Term.node@->reg;
 503                 }
 504           @}
 505
 506         | Feld
 507           @{
 508             @i @Term.node@ = @Feld.node@;
 509                 @i @Term.imm@ = 0;
 510           @}
 511
 512         | IDENT '(' Exprs ')'
 513           @{
 514             @i @Term.node@ = TREENULL;
 515                 @i @Term.imm@ = 0;
 516           @}
 517
 518         | Term '.' IDENT '(' Exprs ')'
 519           @{
 520             @i @Term.node@ = TREENULL;
 521                 @i @Term.imm@ = 0;
 522           @}
 523
 524         ;
 525
 526 Exprs:
 527           Expr ',' Exprs
 528         | Expr
 529         |
 530         ;
 531 %%
 532
 533 extern int yylex();
 534 extern int yylineno;
 535
 536 int yyerror(char *error_text)
 537 {
 538         fprintf(stderr,"Zeile %i: %s\n", yylineno, error_text);
 539         exit(2);
 540 }
 541
 542 int main(int argc, char **argv)
 543 {
 544         #if 0
 545         yydebug=1;
 546         #endif
 547         yyparse();
 548         return 0;
 549 }
 550