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