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