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