mono/monoburg/monoburg.c

   1 /*
   2  * monoburg.c: an iburg like code generator generator
   3  *
   4  * Author:
   5  *   Dietmar Maurer (dietmar@ximian.com)
   6  *
   7  * (C) 2001 Ximian, Inc.
   8  */
   9
  10 #include <stdio.h>
  11 #include <string.h>
  12 #include <stdlib.h>
  13 #include "monoburg.h"
  14
  15 extern void yyparse (void);
  16
  17 static GHashTable *term_hash;
  18 static GList *term_list;
  19 static GHashTable *nonterm_hash;
  20 static GList *nonterm_list;
  21 static GList *rule_list;
  22 static GList *prefix_list;
  23
  24 FILE *inputfd;
  25 FILE *outputfd;
  26 GHashTable *definedvars;
  27 static FILE *deffd;
  28 static FILE *cfd;
  29
  30 static int dag_mode = 0;
  31 static int predefined_terms = 0;
  32 static int default_cost = 0;
  33
  34 static void output (char *fmt, ...)
  35 {
  36         va_list ap;
  37
  38         va_start(ap, fmt);
  39         vfprintf (outputfd, fmt, ap);
  40         va_end (ap);
  41 }
  42
  43 Rule*
  44 make_rule (char *id, Tree *tree)
  45 {
  46         Rule *rule = g_new0 (Rule, 1);
  47         rule->lhs = nonterm (id);
  48         rule->tree = tree;
  49
  50         return rule;
  51 }
  52
  53 void
  54 rule_add (Rule *rule, char *code, char *cost, char *cfunc)
  55 {
  56         if (!cfunc && !cost)
  57                 cost = g_strdup_printf ("%d", default_cost);
  58
  59         rule_list = g_list_append (rule_list, rule);
  60         rule->cost = g_strdup (cost);
  61         rule->cfunc = g_strdup (cfunc);
  62         rule->code = g_strdup (code);
  63
  64         if (cfunc) {
  65                 if (cost)
  66                         yyerror ("duplicated costs (constant costs and cost function)");
  67                 else {
  68                         if (dag_mode)
  69                                 rule->cost = g_strdup_printf ("mono_burg_cost_%d (p, data)",
  70                                                               g_list_length (rule_list));
  71                         else
  72                                 rule->cost = g_strdup_printf ("mono_burg_cost_%d (tree, data)",
  73                                                               g_list_length (rule_list));
  74                 }
  75         }
  76
  77         rule->lhs->rules = g_list_append (rule->lhs->rules, rule);
  78
  79         if (rule->tree->op)
  80                 rule->tree->op->rules = g_list_append (rule->tree->op->rules, rule);
  81         else
  82                 rule->tree->nonterm->chain = g_list_append (rule->tree->nonterm->chain, rule);
  83 }
  84
  85 void
  86 create_rule (char *id, Tree *tree, char *code, char *cost, char *cfunc)
  87 {
  88         Rule *rule = make_rule (id, tree);
  89
  90         rule_add (rule, code, cost, cfunc);
  91 }
  92
  93 Tree *
  94 create_tree (char *id, Tree *left, Tree *right)
  95 {
  96         int arity = (left != NULL) + (right != NULL);
  97         Term *term = NULL;
  98         Tree *tree = g_new0 (Tree, 1);
  99
 100         if (term_hash)
 101                 term = g_hash_table_lookup (term_hash, id);
 102
 103         /* try if id has termprefix */
 104         if (!term) {
 105                 GList *pl;
 106                 for (pl = prefix_list; pl; pl = pl->next) {
 107                         char *pfx = (char *)pl->data;
 108                         if (!strncmp (pfx, id, strlen (pfx))) {
 109                                 term = create_term (id, -1);
 110                                 break;
 111                         }
 112                 }
 113
 114         }
 115
 116         if (term) {
 117                 if (term->arity == -1)
 118                         term->arity = arity;
 119
 120                 if (term->arity != arity)
 121                         yyerror ("changed arity of terminal %s from %d to %d",
 122                                  id, term->arity, arity);
 123
 124                 tree->op = term;
 125                 tree->left = left;
 126                 tree->right = right;
 127         } else {
 128                 tree->nonterm = nonterm (id);
 129         }
 130
 131         return tree;
 132 }
 133
 134 static void
 135 check_term_num (char *key, Term *value, int num)
 136 {
 137         if (num != -1 && value->number == num)
 138                 yyerror ("duplicate terminal id \"%s\"", key);
 139 }
 140
 141 void
 142 create_term_prefix (char *id)
 143 {
 144         if (!predefined_terms)
 145                 yyerror ("%termprefix is only available with -p option");
 146
 147         prefix_list = g_list_prepend (prefix_list, g_strdup (id));
 148 }
 149
 150 Term *
 151 create_term (char *id, int num)
 152 {
 153         Term *term;
 154
 155         if (!predefined_terms && nonterm_list)
 156                 yyerror ("terminal definition after nonterminal definition");
 157
 158         if (num < -1)
 159                 yyerror ("invalid terminal number %d", num);
 160
 161         if (!term_hash)
 162                 term_hash = g_hash_table_new (g_str_hash , g_str_equal);
 163
 164         g_hash_table_foreach (term_hash, (GHFunc) check_term_num, GINT_TO_POINTER (num));
 165
 166         term = g_new0 (Term, 1);
 167
 168         term->name = g_strdup (id);
 169         term->number = num;
 170         term->arity = -1;
 171
 172         term_list = g_list_append (term_list, term);
 173
 174         g_hash_table_insert (term_hash, term->name, term);
 175
 176         return term;
 177 }
 178
 179 NonTerm *
 180 nonterm (char *id)
 181 {
 182         NonTerm *nterm;
 183
 184         if (!nonterm_hash)
 185                 nonterm_hash = g_hash_table_new (g_str_hash , g_str_equal);
 186
 187         if ((nterm = g_hash_table_lookup (nonterm_hash, id)))
 188                 return nterm;
 189
 190         nterm = g_new0 (NonTerm, 1);
 191
 192         nterm->name = g_strdup (id);
 193         nonterm_list = g_list_append (nonterm_list, nterm);
 194         nterm->number = g_list_length (nonterm_list);
 195
 196         g_hash_table_insert (nonterm_hash, nterm->name, nterm);
 197
 198         return nterm;
 199 }
 200
 201 void
 202 start_nonterm (char *id)
 203 {
 204         static gboolean start_def;
 205
 206         if (start_def)
 207                 yyerror ("start symbol redeclared");
 208
 209         start_def = TRUE;
 210         nonterm (id);
 211 }
 212
 213 static void
 214 emit_tree_string (Tree *tree)
 215 {
 216         if (tree->op) {
 217                 output ("%s", tree->op->name);
 218                 if (tree->op->arity) {
 219                         output ("(");
 220                         emit_tree_string (tree->left);
 221                         if (tree->right) {
 222                                 output (", ");
 223                                 emit_tree_string (tree->right);
 224                         }
 225                         output (")");
 226                 }
 227         } else
 228                 output ("%s", tree->nonterm->name);
 229 }
 230
 231 static void
 232 emit_rule_string (Rule *rule, char *fill)
 233 {
 234         output ("%s/* ", fill);
 235
 236         output ("%s: ", rule->lhs->name);
 237
 238         emit_tree_string (rule->tree);
 239
 240         output (" */\n");
 241 }
 242
 243 static int
 244 next_term_num ()
 245 {
 246         GList *l = term_list;
 247         int i = 1;
 248
 249         while (l) {
 250                 Term *t = (Term *)l->data;
 251                 if (t->number == i) {
 252                         l = term_list;
 253                         i++;
 254                 } else
 255                         l = l->next;
 256         }
 257         return i;
 258 }
 259
 260 static int
 261 term_compare_func (Term *t1, Term *t2)
 262 {
 263         return t1->number - t2->number;
 264 }
 265
 266 static void
 267 emit_header ()
 268 {
 269         GList *l;
 270
 271         output ("#include <glib.h>\n");
 272         output ("\n");
 273
 274         output ("#ifndef MBTREE_TYPE\n#error MBTREE_TYPE undefined\n#endif\n");
 275         output ("#ifndef MBTREE_OP\n#define MBTREE_OP(t) ((t)->op)\n#endif\n");
 276         output ("#ifndef MBTREE_LEFT\n#define MBTREE_LEFT(t) ((t)->left)\n#endif\n");
 277         output ("#ifndef MBTREE_RIGHT\n#define MBTREE_RIGHT(t) ((t)->right)\n#endif\n");
 278         output ("#ifndef MBTREE_STATE\n#define MBTREE_STATE(t) ((t)->state)\n#endif\n");
 279         output ("#ifndef MBREG_TYPE\n#define MBREG_TYPE gint32\n#endif\n");
 280         output ("#ifndef MBCGEN_TYPE\n#define MBCGEN_TYPE int\n#endif\n");
 281         output ("#ifndef MBALLOC_STATE\n#define MBALLOC_STATE g_new (MBState, 1)\n#endif\n");
 282         output ("#ifndef MBCOST_DATA\n#define MBCOST_DATA gpointer\n#endif\n");
 283         output ("\n");
 284         output ("#define MBMAXCOST 32768\n");
 285
 286         output ("\n");
 287         output ("#define MBCOND(x) if (!(x)) return MBMAXCOST;\n");
 288
 289         output ("\n");
 290
 291         for (l = term_list; l; l = l->next) {
 292                 Term *t = (Term *)l->data;
 293                 if (t->number == -1)
 294                         t->number = next_term_num ();
 295         }
 296         term_list = g_list_sort (term_list, (GCompareFunc)term_compare_func);
 297
 298         for (l = term_list; l; l = l->next) {
 299                 Term *t = (Term *)l->data;
 300                 if (t->number == -1)
 301                         t->number = next_term_num ();
 302
 303                 if (predefined_terms)
 304                         output ("#define MB_TERM_%s\t %s\n", t->name, t->name);
 305                 else
 306                         output ("#define MB_TERM_%s\t %d\n", t->name, t->number);
 307
 308         }
 309         output ("\n");
 310
 311 }
 312
 313 static void
 314 emit_nonterm ()
 315 {
 316         GList *l;
 317
 318         for (l = nonterm_list; l; l = l->next) {
 319                 NonTerm *n = (NonTerm *)l->data;
 320                 output ("#define MB_NTERM_%s\t%d\n", n->name, n->number);
 321         }
 322         output ("#define MB_MAX_NTERMS\t%d\n", g_list_length (nonterm_list));
 323         output ("\n");
 324 }
 325
 326 static void
 327 emit_state ()
 328 {
 329         GList *l;
 330         int i, j;
 331
 332         output ("typedef struct _MBState MBState;\n");
 333         output ("struct _MBState {\n");
 334         output ("\tint\t\t op;\n");
 335
 336         if (dag_mode) {
 337                 output ("\tMBTREE_TYPE\t *tree;\n");
 338                 output ("\tMBREG_TYPE\t reg1;\n");
 339                 output ("\tMBREG_TYPE\t reg2;\n");
 340         }
 341
 342         output ("\tMBState\t\t*left, *right;\n");
 343         output ("\tguint16\t\tcost[%d];\n", g_list_length (nonterm_list) + 1);
 344
 345         for (l = nonterm_list; l; l = l->next) {
 346                 NonTerm *n = (NonTerm *)l->data;
 347                 g_assert (g_list_length (n->rules) < 256);
 348                 i = g_list_length (n->rules);
 349                 j = 1;
 350                 while (i >>= 1)
 351                         j++;
 352                 output ("\tunsigned int\t rule_%s:%d;\n",  n->name, j);
 353         }
 354         output ("};\n\n");
 355 }
 356
 357 static void
 358 emit_decoders ()
 359 {
 360         GList *l;
 361         GList *rl;
 362
 363         for (l = nonterm_list; l; l = l->next) {
 364                 NonTerm *n = (NonTerm *)l->data;
 365                 output ("const short mono_burg_decode_%s[] = {\n", n->name);
 366                 output ("\t0,\n");
 367                 for (rl = n->rules; rl; rl = rl->next) {
 368                         Rule *rule = (Rule *)rl->data;
 369                         output ("\t%d,\n", g_list_index (rule_list, rule) + 1);
 370                 }
 371
 372                 output ("};\n\n");
 373         }
 374 }
 375
 376 static void
 377 emit_tree_match (char *st, Tree *t)
 378 {
 379         char *tn;
 380         int not_first = strcmp (st, "p->");
 381
 382         /* we can omit this check at the top level */
 383         if (not_first) {
 384                 if (predefined_terms)
 385                         output ("\t\t\t%sop == %s /* %s */", st, t->op->name, t->op->name);
 386                 else
 387                         output ("\t\t\t%sop == %d /* %s */", st, t->op->number, t->op->name);
 388         }
 389
 390         if (t->left && t->left->op) {
 391                 tn = g_strconcat (st, "left->", NULL);
 392                 if (not_first)
 393                         output (" &&\n");
 394                 not_first = 1;
 395                 emit_tree_match (tn, t->left);
 396                 g_free (tn);
 397         }
 398
 399         if (t->right && t->right->op) {
 400                 tn = g_strconcat (st, "right->", NULL);
 401                 if (not_first)
 402                         output (" &&\n");
 403                 emit_tree_match (tn, t->right);
 404                 g_free (tn);
 405         }
 406 }
 407
 408 static void
 409 emit_rule_match (Rule *rule)
 410 {
 411         Tree *t = rule->tree;
 412
 413         if ((t->left && t->left->op) ||
 414             (t->right && t->right->op)) {
 415                 output ("\t\tif (\n");
 416                 emit_tree_match ("p->", t);
 417                 output ("\n\t\t)\n");
 418         }
 419 }
 420
 421 static void
 422 emit_costs (char *st, Tree *t)
 423 {
 424         char *tn;
 425
 426         if (t->op) {
 427
 428                 if (t->left) {
 429                         tn = g_strconcat (st, "left->", NULL);
 430                         emit_costs (tn, t->left);
 431                         g_free (tn);
 432                 }
 433
 434                 if (t->right) {
 435                         tn = g_strconcat (st, "right->", NULL);
 436                         emit_costs (tn, t->right);
 437                 }
 438         } else
 439                 output ("%scost[MB_NTERM_%s] + ", st, t->nonterm->name);
 440 }
 441
 442 static void
 443 emit_cond_assign (Rule *rule, char *cost, char *fill)
 444 {
 445         char *rc;
 446
 447         if (cost)
 448                 rc = g_strconcat ("c + ", cost, NULL);
 449         else
 450                 rc = g_strdup ("c");
 451
 452
 453         output ("%sif (%s < p->cost[MB_NTERM_%s]) {\n", fill, rc, rule->lhs->name);
 454
 455         output ("%s\tp->cost[MB_NTERM_%s] = %s;\n", fill, rule->lhs->name, rc);
 456
 457         output ("%s\tp->rule_%s = %d;\n", fill, rule->lhs->name,
 458                 g_list_index (rule->lhs->rules, rule) + 1);
 459
 460         if (rule->lhs->chain)
 461                 output ("%s\tclosure_%s (p, %s);\n", fill, rule->lhs->name, rc);
 462
 463         output ("%s}\n", fill);
 464
 465         g_free (rc);
 466
 467 }
 468
 469 static void
 470 emit_label_func ()
 471 {
 472         GList *l;
 473         int i;
 474
 475         if (dag_mode) {
 476                 output ("static void\n");
 477                 output ("mono_burg_label_priv (MBTREE_TYPE *tree, MBCOST_DATA *data, MBState *p) {\n");
 478         } else {
 479                 output ("static MBState *\n");
 480                 output ("mono_burg_label_priv (MBTREE_TYPE *tree, MBCOST_DATA *data) {\n");
 481         }
 482
 483         output ("\tint arity;\n");
 484         output ("\tint c;\n");
 485         if (!dag_mode)
 486                 output ("\tMBState *p;\n");
 487         output ("\tMBState *left = NULL, *right = NULL;\n\n");
 488
 489         output ("\tswitch (mono_burg_arity [MBTREE_OP(tree)]) {\n");
 490         output ("\tcase 0:\n");
 491         output ("\t\tbreak;\n");
 492         output ("\tcase 1:\n");
 493         if (dag_mode) {
 494                 output ("\t\tleft = MBALLOC_STATE;\n");
 495                 output ("\t\tmono_burg_label_priv (MBTREE_LEFT(tree), data, left);\n");
 496         } else {
 497                 output ("\t\tleft = mono_burg_label_priv (MBTREE_LEFT(tree), data);\n");
 498                 output ("\t\tright = NULL;\n");
 499         }
 500         output ("\t\tbreak;\n");
 501         output ("\tcase 2:\n");
 502         if (dag_mode) {
 503                 output ("\t\tleft = MBALLOC_STATE;\n");
 504                 output ("\t\tmono_burg_label_priv (MBTREE_LEFT(tree), data, left);\n");
 505                 output ("\t\tright = MBALLOC_STATE;\n");
 506                 output ("\t\tmono_burg_label_priv (MBTREE_RIGHT(tree), data, right);\n");
 507         } else {
 508                 output ("\t\tleft = mono_burg_label_priv (MBTREE_LEFT(tree), data);\n");
 509                 output ("\t\tright = mono_burg_label_priv (MBTREE_RIGHT(tree), data);\n");
 510         }
 511         output ("\t}\n\n");
 512
 513         output ("\tarity = (left != NULL) + (right != NULL);\n");
 514         output ("\tg_assert (arity == mono_burg_arity [MBTREE_OP(tree)]);\n\n");
 515
 516         if (!dag_mode)
 517                 output ("\tp = MBALLOC_STATE;\n");
 518
 519         output ("\tmemset (p, 0, sizeof (MBState));\n");
 520         output ("\tp->op = MBTREE_OP(tree);\n");
 521         output ("\tp->left = left;\n");
 522         output ("\tp->right = right;\n");
 523
 524         if (dag_mode)
 525                 output ("\tp->tree = tree;\n");
 526
 527         for (l = nonterm_list, i = 0; l; l = l->next) {
 528                 output ("\tp->cost [%d] = 32767;\n", ++i);
 529         }
 530         output ("\n");
 531
 532         output ("\tswitch (MBTREE_OP(tree)) {\n");
 533         for (l = term_list; l; l = l->next) {
 534                 Term *t = (Term *)l->data;
 535                 GList *rl;
 536
 537                 if (predefined_terms)
 538                         output ("\tcase %s: /* %s */\n", t->name, t->name);
 539                 else
 540                         output ("\tcase %d: /* %s */\n", t->number, t->name);
 541
 542                 for (rl = t->rules; rl; rl = rl->next) {
 543                         Rule *rule = (Rule *)rl->data;
 544                         Tree *t = rule->tree;
 545
 546                         emit_rule_string (rule, "\t\t");
 547
 548                         emit_rule_match (rule);
 549
 550                         output ("\t\t{\n");
 551
 552                         output ("\t\t\tc = ");
 553
 554                         emit_costs ("", t);
 555
 556                         output ("%s;\n", rule->cost);
 557
 558                         emit_cond_assign (rule, NULL, "\t\t\t");
 559
 560                         output ("\t\t}\n");
 561                 }
 562
 563                 output ("\t\tbreak;\n");
 564         }
 565
 566         output ("\tdefault:\n");
 567         output ("#ifdef MBGET_OP_NAME\n");
 568         output ("\t\tg_error (\"unknown operator: %%s\", MBGET_OP_NAME(MBTREE_OP(tree)));\n");
 569         output ("#else\n");
 570         output ("\t\tg_error (\"unknown operator: 0x%%04x\", MBTREE_OP(tree));\n");
 571         output ("#endif\n");
 572         output ("\t}\n\n");
 573
 574         if (!dag_mode) {
 575                 output ("\tMBTREE_STATE(tree) = p;\n");
 576                 output ("\treturn p;\n");
 577         }
 578
 579         output ("}\n\n");
 580
 581         output ("MBState *\n");
 582         output ("mono_burg_label (MBTREE_TYPE *tree, MBCOST_DATA *data)\n{\n");
 583         if (dag_mode) {
 584                 output ("\tMBState *p = MBALLOC_STATE;\n");
 585                 output ("\tmono_burg_label_priv (tree, data, p);\n");
 586         } else {
 587                 output ("\tMBState *p = mono_burg_label_priv (tree, data);\n");
 588         }
 589         output ("\treturn p->rule_%s ? p : NULL;\n", ((NonTerm *)nonterm_list->data)->name);
 590         output ("}\n\n");
 591 }
 592
 593 static char *
 594 compute_kids (char *ts, Tree *tree, int *n)
 595 {
 596         char *res;
 597
 598         if (tree->nonterm) {
 599                 return g_strdup_printf ("\t\tkids[%d] = %s;\n", (*n)++, ts);
 600         } else if (tree->op && tree->op->arity) {
 601                 char *res2 = NULL;
 602
 603                 if (dag_mode) {
 604                         res = compute_kids (g_strdup_printf ("%s->left", ts),
 605                                             tree->left, n);
 606                         if (tree->op->arity == 2)
 607                                 res2 = compute_kids (g_strdup_printf ("%s->right", ts),
 608                                                      tree->right, n);
 609                 } else {
 610                         res = compute_kids (g_strdup_printf ("MBTREE_LEFT(%s)", ts),
 611                                             tree->left, n);
 612                         if (tree->op->arity == 2)
 613                                 res2 = compute_kids (g_strdup_printf ("MBTREE_RIGHT(%s)", ts),
 614                                                      tree->right, n);
 615                 }
 616
 617                 return g_strconcat (res, res2, NULL);
 618         }
 619         return "";
 620 }
 621
 622 static void
 623 emit_kids ()
 624 {
 625         GList *l, *nl;
 626         int i, j, c, n, *si;
 627         char **sa;
 628
 629         output ("int\n");
 630         output ("mono_burg_rule (MBState *state, int goal)\n{\n");
 631
 632         output ("\tg_return_val_if_fail (state != NULL, 0);\n");
 633         output ("\tg_return_val_if_fail (goal > 0, 0);\n\n");
 634
 635         output ("\tswitch (goal) {\n");
 636
 637         for (nl = nonterm_list; nl; nl = nl->next) {
 638                 NonTerm *n = (NonTerm *)nl->data;
 639                 output ("\tcase MB_NTERM_%s:\n", n->name);
 640                 output ("\t\treturn mono_burg_decode_%s [state->rule_%s];\n",
 641                         n->name, n->name);
 642         }
 643
 644         output ("\tdefault: g_assert_not_reached ();\n");
 645         output ("\t}\n");
 646         output ("\treturn 0;\n");
 647         output ("}\n\n");
 648
 649
 650         if (dag_mode) {
 651                 output ("MBState **\n");
 652                 output ("mono_burg_kids (MBState *state, int rulenr, MBState *kids [])\n{\n");
 653                 output ("\tg_return_val_if_fail (state != NULL, NULL);\n");
 654                 output ("\tg_return_val_if_fail (kids != NULL, NULL);\n\n");
 655
 656         } else {
 657                 output ("MBTREE_TYPE **\n");
 658                 output ("mono_burg_kids (MBTREE_TYPE *tree, int rulenr, MBTREE_TYPE *kids [])\n{\n");
 659                 output ("\tg_return_val_if_fail (tree != NULL, NULL);\n");
 660                 output ("\tg_return_val_if_fail (kids != NULL, NULL);\n\n");
 661         }
 662
 663         output ("\tswitch (rulenr) {\n");
 664
 665         n = g_list_length (rule_list);
 666         sa = g_new0 (char *, n);
 667         si = g_new0 (int, n);
 668
 669         /* compress the case statement */
 670         for (l = rule_list, i = 0, c = 0; l; l = l->next) {
 671                 Rule *rule = (Rule *)l->data;
 672                 int kn = 0;
 673                 char *k;
 674
 675                 if (dag_mode)
 676                         k = compute_kids ("state", rule->tree, &kn);
 677                 else
 678                         k = compute_kids ("tree", rule->tree, &kn);
 679
 680                 for (j = 0; j < c; j++)
 681                         if (!strcmp (sa [j], k))
 682                                 break;
 683
 684                 si [i++] = j;
 685                 if (j == c)
 686                         sa [c++] = k;
 687         }
 688
 689         for (i = 0; i < c; i++) {
 690                 for (l = rule_list, j = 0; l; l = l->next, j++)
 691                         if (i == si [j])
 692                                 output ("\tcase %d:\n", j + 1);
 693                 output ("%s", sa [i]);
 694                 output ("\t\tbreak;\n");
 695         }
 696
 697         output ("\tdefault:\n\t\tg_assert_not_reached ();\n");
 698         output ("\t}\n");
 699         output ("\treturn kids;\n");
 700         output ("}\n\n");
 701
 702 }
 703
 704 static void
 705 emit_emitter_func ()
 706 {
 707         GList *l;
 708         int i;
 709         GHashTable *cache = g_hash_table_new (g_str_hash, g_str_equal);
 710
 711         for (l =  rule_list, i = 0; l; l = l->next) {
 712                 Rule *rule = (Rule *)l->data;
 713
 714                 if (rule->code) {
 715                         GList *cases;
 716                         if ((cases = g_hash_table_lookup (cache, rule->code))) {
 717                                 cases = g_list_append (cases, GINT_TO_POINTER (i));
 718                         } else {
 719                                 cases = g_list_append (NULL, GINT_TO_POINTER (i));
 720                         }
 721                         g_hash_table_insert (cache, rule->code, cases);
 722                 }
 723                 i++;
 724         }
 725
 726         output ("void mono_burg_emit (int ern, MBState *state, MBTREE_TYPE *tree, MBCGEN_TYPE *s)\n {\n");
 727         output ("\tswitch (ern) {");
 728         for (l =  rule_list, i = 0; l; l = l->next) {
 729                 Rule *rule = (Rule *)l->data;
 730
 731                 if (rule->code) {
 732                         GList *cases, *tmp;
 733                         cases = g_hash_table_lookup (cache, rule->code);
 734                         if (cases && i != GPOINTER_TO_INT (cases->data)) {
 735                                 i++;
 736                                 continue;
 737                         }
 738                         emit_rule_string (rule, "");
 739                         for (tmp = cases; tmp; tmp = tmp->next) {
 740                                 output ("\tcase %d:\n", GPOINTER_TO_INT (tmp->data) + 1);
 741                         }
 742                         output ("\t{\n");
 743                         output ("%s\n", rule->code);
 744                         output ("\t}\n\treturn;\n");
 745                 }
 746                 i++;
 747         }
 748         output ("\t}\n}\n\n");
 749         g_hash_table_destroy (cache);
 750 }
 751
 752 static void
 753 emit_cost_func ()
 754 {
 755         GList *l;
 756         int i;
 757
 758         for (l =  rule_list, i = 0; l; l = l->next) {
 759                 Rule *rule = (Rule *)l->data;
 760
 761                 if (rule->cfunc) {
 762                         output ("inline static guint16\n");
 763
 764                         emit_rule_string (rule, "");
 765
 766                         if (dag_mode)
 767                                 output ("mono_burg_cost_%d (MBState *state, MBCOST_DATA *data)\n", i + 1);
 768                         else
 769                                 output ("mono_burg_cost_%d (MBTREE_TYPE *tree, MBCOST_DATA *data)\n", i + 1);
 770                         output ("{\n");
 771                         output ("%s\n", rule->cfunc);
 772                         output ("}\n\n");
 773                 }
 774                 i++;
 775         }
 776 }
 777
 778 static void
 779 emit_closure ()
 780 {
 781         GList *l, *rl;
 782
 783         for (l = nonterm_list; l; l = l->next) {
 784                 NonTerm *n = (NonTerm *)l->data;
 785
 786                 if (n->chain)
 787                         output ("static void closure_%s (MBState *p, int c);\n", n->name);
 788         }
 789
 790         output ("\n");
 791
 792         for (l = nonterm_list; l; l = l->next) {
 793                 NonTerm *n = (NonTerm *)l->data;
 794
 795                 if (n->chain) {
 796                         output ("static void\n");
 797                         output ("closure_%s (MBState *p, int c)\n{\n", n->name);
 798                         for (rl = n->chain; rl; rl = rl->next) {
 799                                 Rule *rule = (Rule *)rl->data;
 800
 801                                 emit_rule_string (rule, "\t");
 802                                 emit_cond_assign (rule, rule->cost, "\t");
 803                         }
 804                         output ("}\n\n");
 805                 }
 806         }
 807 }
 808
 809 static char *
 810 compute_nonterms (Tree *tree)
 811 {
 812         if (!tree)
 813                 return "";
 814
 815         if (tree->nonterm) {
 816                 return g_strdup_printf ("MB_NTERM_%s, ", tree->nonterm->name);
 817         } else {
 818                 return g_strconcat (compute_nonterms (tree->left),
 819                                     compute_nonterms (tree->right), NULL);
 820         }
 821 }
 822
 823 static int
 824 count_nonterms (Tree *tree)
 825 {
 826         if (!tree)
 827                 return 0;
 828
 829         if (tree->nonterm) {
 830                 return 1;
 831         } else {
 832                 return count_nonterms (tree->left) + count_nonterms (tree->right);
 833         }
 834 }
 835
 836 static void
 837 emit_vardefs ()
 838 {
 839         GList *l;
 840         int i, j, c, n, *si;
 841         char **sa;
 842         int *nts_offsets;
 843         int current_offset;
 844
 845         output ("\n");
 846         if (predefined_terms) {
 847                 output ("#if HAVE_ARRAY_ELEM_INIT\n");
 848                 output ("const guint8 mono_burg_arity [MBMAX_OPCODES] = {\n");
 849                 for (l = term_list, i = 0; l; l = l->next) {
 850                         Term *t = (Term *)l->data;
 851                         output ("\t [%s] = %d, /* %s */\n", t->name, t->arity, t->name);
 852                 }
 853                 output ("};\n\n");
 854                 output ("void\nmono_burg_init (void) {\n");
 855                 output ("}\n\n");
 856                 output ("#else\n");
 857                 output ("guint8 mono_burg_arity [MBMAX_OPCODES];\n");
 858
 859                 output ("void\nmono_burg_init (void)\n{\n");
 860
 861                 for (l = term_list, i = 0; l; l = l->next) {
 862                         Term *t = (Term *)l->data;
 863                         output ("\tmono_burg_arity [%s] = %d; /* %s */\n", t->name, t->arity, t->name);
 864                 }
 865                 output ("}\n\n");
 866                 output ("#endif /* HAVE_ARRAY_ELEM_INIT */\n");
 867
 868         } else {
 869                 output ("const guint8 mono_burg_arity [] = {\n");
 870                 for (l = term_list, i = 0; l; l = l->next) {
 871                         Term *t = (Term *)l->data;
 872
 873                         while (i < t->number) {
 874                                 output ("\t0,\n");
 875                                 i++;
 876                         }
 877
 878                         output ("\t%d, /* %s */\n", t->arity, t->name);
 879
 880                         i++;
 881                 }
 882                 output ("};\n\n");
 883
 884                 output ("const char *const mono_burg_term_string [] = {\n");
 885                 output ("\tNULL,\n");
 886                 for (l = term_list, i = 0; l; l = l->next) {
 887                         Term *t = (Term *)l->data;
 888                         output ("\t\"%s\",\n", t->name);
 889                 }
 890                 output ("};\n\n");
 891         }
 892
 893         output ("#if MONOBURG_LOG\n");
 894         output ("const char * const mono_burg_rule_string [] = {\n");
 895         output ("\tNULL,\n");
 896         for (l = rule_list, i = 0; l; l = l->next) {
 897                 Rule *rule = (Rule *)l->data;
 898                 output ("\t\"%s: ", rule->lhs->name);
 899                 emit_tree_string (rule->tree);
 900                 output ("\",\n");
 901         }
 902         output ("};\n");
 903         output ("#endif /* MONOBURG_LOG */\n\n");
 904
 905         n = g_list_length (rule_list);
 906         sa = g_new0 (char *, n);
 907         si = g_new0 (int, n);
 908         nts_offsets = g_new0 (int, n);
 909
 910         /* at offset 0 we store 0 to mean end of list */
 911         current_offset = 1;
 912         output ("const guint16 mono_burg_nts_data [] = {\n\t0,\n");
 913         /* compress the _nts array */
 914         for (l = rule_list, i = 0, c = 0; l; l = l->next) {
 915                 Rule *rule = (Rule *)l->data;
 916                 char *s = compute_nonterms (rule->tree);
 917
 918                 for (j = 0; j < c; j++)
 919                         if (!strcmp (sa [j], s))
 920                                 break;
 921
 922                 si [i++] = j;
 923                 if (j == c) {
 924                         output ("\t%s0,\n", s);
 925                         nts_offsets [c] = current_offset;
 926                         sa [c++] = s;
 927                         current_offset += count_nonterms (rule->tree) + 1;
 928                 }
 929         }
 930         output ("\t0\n};\n\n");
 931
 932         output ("const guint8 mono_burg_nts [] = {\n");
 933         output ("\t0,\n");
 934         for (l = rule_list, i = 0; l; l = l->next) {
 935                 Rule *rule = (Rule *)l->data;
 936                 output ("\t%d, /* %s */ ", nts_offsets [si [i]], sa [si [i]]);
 937                 ++i;
 938                 emit_rule_string (rule, "");
 939         }
 940         output ("};\n\n");
 941 }
 942
 943 static void
 944 emit_prototypes ()
 945 {
 946         output ("extern const char * const mono_burg_term_string [];\n");
 947         output ("#if MONOBURG_LOG\n");
 948         output ("extern const char * const mono_burg_rule_string [];\n");
 949         output ("#endif /* MONOBURG_LOG */\n");
 950         output ("extern const guint16 mono_burg_nts_data [];\n");
 951         output ("extern const guint8 mono_burg_nts [];\n");
 952         output ("extern void mono_burg_emit (int ern, MBState *state, MBTREE_TYPE *tree, MBCGEN_TYPE *s);\n\n");
 953
 954         output ("MBState *mono_burg_label (MBTREE_TYPE *tree, MBCOST_DATA *data);\n");
 955         output ("int mono_burg_rule (MBState *state, int goal);\n");
 956
 957         if (dag_mode)
 958                 output ("MBState **mono_burg_kids (MBState *state, int rulenr, MBState *kids []);\n");
 959         else
 960                 output ("MBTREE_TYPE **mono_burg_kids (MBTREE_TYPE *tree, int rulenr, MBTREE_TYPE *kids []);\n");
 961
 962         output ("extern void mono_burg_init (void);\n");
 963         output ("\n");
 964 }
 965
 966 static void check_reach (NonTerm *n);
 967
 968 static void
 969 mark_reached (Tree *tree)
 970 {
 971         if (tree->nonterm && !tree->nonterm->reached)
 972                 check_reach (tree->nonterm);
 973         if (tree->left)
 974                 mark_reached (tree->left);
 975         if (tree->right)
 976                 mark_reached (tree->right);
 977 }
 978
 979 static void
 980 check_reach (NonTerm *n)
 981 {
 982         GList *l;
 983
 984         n->reached = 1;
 985         for (l = n->rules; l; l = l->next) {
 986                 Rule *rule = (Rule *)l->data;
 987                 mark_reached (rule->tree);
 988         }
 989 }
 990
 991 static void
 992 check_result ()
 993 {
 994         GList *l;
 995
 996         for (l = term_list; l; l = l->next) {
 997                 Term *term = (Term *)l->data;
 998                 if (term->arity == -1)
 999                         g_warning ("unused terminal \"%s\"",term->name);
1000         }
1001
1002         check_reach (((NonTerm *)nonterm_list->data));
1003
1004         for (l = nonterm_list; l; l = l->next) {
1005                 NonTerm *n = (NonTerm *)l->data;
1006                 if (!n->reached)
1007                         g_warning ("unreachable nonterm \"%s\"", n->name);
1008         }
1009 }
1010
1011 static void
1012 usage ()
1013 {
1014         fprintf (stderr,
1015                  "Usage is: monoburg -d file.h -s file.c [inputfile] \n");
1016         exit (1);
1017 }
1018
1019 static void
1020 warning_handler (const gchar *log_domain,
1021                  GLogLevelFlags log_level,
1022                  const gchar *message,
1023                  gpointer user_data)
1024 {
1025         (void) fprintf ((FILE *) user_data, "** WARNING **: %s\n", message);
1026 }
1027
1028 int
1029 main (int argc, char *argv [])
1030 {
1031         char *cfile = NULL;
1032         char *deffile = NULL;
1033         GList *infiles = NULL;
1034         int i;
1035
1036         definedvars = g_hash_table_new (g_str_hash, g_str_equal);
1037         g_log_set_handler (NULL, G_LOG_LEVEL_WARNING, warning_handler, stderr);
1038
1039         for (i = 1; i < argc; i++){
1040                 if (argv [i][0] == '-'){
1041                         if (argv [i][1] == 'h') {
1042                                 usage ();
1043                         } else if (argv [i][1] == 'e') {
1044                                 dag_mode = 1;
1045                         } else if (argv [i][1] == 'p') {
1046                                 predefined_terms = 1;
1047                         } else if (argv [i][1] == 'd') {
1048                                 deffile = argv [++i];
1049                         } else if (argv [i][1] == 's') {
1050                                 cfile = argv [++i];
1051                         } else if (argv [i][1] == 'c') {
1052                                 default_cost = atoi (argv [++i]);
1053                         } else if (argv [i][1] == 'D') {
1054                                 g_hash_table_insert (definedvars, &argv [i][2],
1055                                                      GUINT_TO_POINTER (1));
1056                         } else {
1057                                 usage ();
1058                         }
1059                 } else {
1060                         infiles = g_list_append (infiles, argv [i]);
1061                 }
1062         }
1063
1064         if (deffile) {
1065                 if (!(deffd = fopen (deffile, "w"))) {
1066                         perror ("cant open header output file");
1067                         exit (-1);
1068                 }
1069                 outputfd = deffd;
1070                 output ("#ifndef _MONO_BURG_DEFS_\n");
1071                 output ("#define _MONO_BURG_DEFS_\n\n");
1072         } else
1073                 outputfd = stdout;
1074
1075
1076         if (infiles) {
1077                 GList *l = infiles;
1078                 while (l) {
1079                         char *infile = (char *)l->data;
1080                         if (!(inputfd = fopen (infile, "r"))) {
1081                                 perror ("cant open input file");
1082                                 exit (-1);
1083                         }
1084
1085                         yyparse ();
1086
1087                         reset_parser ();
1088
1089                         l->data = inputfd;
1090                         l = l->next;
1091                 }
1092         } else {
1093                 inputfd = stdin;
1094                 yyparse ();
1095         }
1096
1097         check_result ();
1098
1099         if (!nonterm_list)
1100                 g_error ("no start symbol found");
1101
1102         emit_header ();
1103         emit_nonterm ();
1104         emit_state ();
1105         emit_prototypes ();
1106
1107         if (deffd) {
1108                 output ("#endif /* _MONO_BURG_DEFS_ */\n");
1109                 fclose (deffd);
1110
1111                 if (cfile == NULL)
1112                         outputfd = stdout;
1113                 else {
1114                         if (!(cfd = fopen (cfile, "w"))) {
1115                                 perror ("cant open c output file");
1116                                 (void) remove (deffile);
1117                                 exit (-1);
1118                         }
1119
1120                         outputfd = cfd;
1121                 }
1122
1123                 output ("#include \"%s\"\n\n", deffile);
1124         }
1125
1126         if (infiles) {
1127                 GList *l = infiles;
1128                 while (l) {
1129                         inputfd = l->data;
1130                         yyparsetail ();
1131                         fclose (inputfd);
1132                         l = l->next;
1133                 }
1134         } else {
1135                 yyparsetail ();
1136         }
1137
1138         emit_vardefs ();
1139         emit_cost_func ();
1140         emit_emitter_func ();
1141         emit_decoders ();
1142
1143         emit_closure ();
1144         emit_label_func ();
1145
1146         emit_kids ();
1147
1148         if (cfile)
1149                 fclose (cfd);
1150
1151         return 0;
1152 }