1 char rcsid_plank[] = "$Id$";
13 Item_Set *sortedStates;
14 static struct stateMapTable smt;
15 int exceptionTolerance = 0;
16 static int plankSize = 32;
18 static Plank newPlank ARGS((void));
19 static PlankMap newPlankMap ARGS((int));
20 static StateMap newStateMap ARGS((void));
21 static Exception newException ARGS((int, int));
22 static void enterStateMap ARGS((PlankMap, short *, int, int *));
23 static List assemblePlanks ARGS((void));
24 static void assignRules ARGS((RuleAST));
25 static int stateCompare ARGS((Item_Set *, Item_Set *));
26 static int ruleCompare ARGS((RuleAST *, RuleAST *));
27 static void renumber ARGS((void));
28 static short * newVector ARGS((void));
29 static int width ARGS((int));
30 static PlankMap mapToPmap ARGS((Dimension));
31 static void doDimPmaps ARGS((Operator));
32 static void doNonTermPmaps ARGS((NonTerminal));
33 static void makePmaps ARGS((void));
34 static void outPlank ARGS((Plank));
35 static void purgePlanks ARGS((List));
36 static void inToEx ARGS((void));
37 static void makePlankRuleMacros ARGS((void));
38 static void makePlankRule ARGS((void));
39 static void exceptionSwitch ARGS((List, const char *, const char *, const char *, int, const char *));
40 static void doPlankLabel ARGS((Operator));
41 static void doPlankLabelSafely ARGS((Operator));
42 static void doPlankLabelMacrosSafely ARGS((Operator));
43 static void makePlankState ARGS((void));
52 p = (Plank) zalloc(sizeof(struct plank));
53 sprintf(buf, "%s_plank_%d", prefix, num++);
54 p->name = (char *) zalloc(strlen(buf)+1);
60 newPlankMap(offset) int offset;
64 im = (PlankMap) zalloc(sizeof(struct plankMap));
77 sm = (StateMap) zalloc(sizeof(struct stateMap));
78 sprintf(buf, "f%d", num++);
79 sm->fieldname = (char *) zalloc(strlen(buf)+1);
80 strcpy(sm->fieldname, buf);
85 newException(index, value) int index; int value;
89 e = (Exception) zalloc(sizeof(struct except));
96 enterStateMap(im, v, width, new) PlankMap im; short * v; int width; int *new;
106 size = globalMap->count;
108 for (l = smt.maps; l; l = l->next) {
111 sm = (StateMap) l->x;
113 for (i = 0; i < size; i++) {
114 if (v[i] != -1 && sm->value[i] != -1 && v[i] != sm->value[i]) {
115 if (++ecount > exceptionTolerance) {
120 for (i = 0; i < size; i++) {
122 assert(sm->value[i] >= 0);
126 if (sm->value[i] == -1) {
128 } else if (v[i] != sm->value[i]) {
129 im->exceptions = newList(newException(i,v[i]), im->exceptions);
133 if (width > sm->width) {
145 smt.maps = newList(sm, smt.maps);
156 for (s = smt.maps; s; s = s->next) {
157 StateMap sm = (StateMap) s->x;
158 for (p = planks; p; p = p->next) {
160 if (sm->width <= plankSize - pl->width) {
161 pl->width += sm->width;
162 pl->fields = newList(sm, pl->fields);
168 pl->width = sm->width;
169 pl->fields = newList(sm, 0);
171 planks = appendList(pl, planks);
177 RuleAST *sortedRules;
182 assignRules(ast) RuleAST ast;
184 sortedRules[count++] = ast;
188 stateCompare(s, t) Item_Set *s; Item_Set *t;
190 return strcmp((*s)->op->name, (*t)->op->name);
194 ruleCompare(s, t) RuleAST *s; RuleAST *t;
196 return strcmp((*s)->lhs, (*t)->lhs);
204 printf("dump Sorted States: ");
205 for (i = 0; i < globalMap->count; i++) {
206 printf("%d ", sortedStates[i]->num);
216 printf("dump Sorted Rules: ");
217 for (i = 0; i < max_ruleAST; i++) {
218 printf("%d ", sortedRules[i]->rule->erulenum);
228 NonTerminal previousLHS;
231 sortedStates = (Item_Set*) zalloc(globalMap->count * sizeof(Item_Set));
232 for (i = 1; i < globalMap->count; i++) {
233 sortedStates[i-1] = globalMap->set[i];
235 qsort(sortedStates, globalMap->count-1, sizeof(Item_Set), (int(*)(const void *, const void *))stateCompare);
237 for (i = 0; i < globalMap->count-1; i++) {
238 sortedStates[i]->newNum = i;
239 sortedStates[i]->op->stateCount++;
240 if (previousOp != sortedStates[i]->op) {
241 sortedStates[i]->op->baseNum = i;
242 previousOp = sortedStates[i]->op;
246 sortedRules = (RuleAST*) zalloc(max_ruleAST * sizeof(RuleAST));
248 foreachList((ListFn) assignRules, ruleASTs);
249 qsort(sortedRules, max_ruleAST, sizeof(RuleAST), (int(*)(const void *, const void *))ruleCompare);
252 for (i = 0; i < max_ruleAST; i++) {
253 if (previousLHS != sortedRules[i]->rule->lhs) {
254 sortedRules[i]->rule->lhs->baseNum = base_counter;
255 previousLHS = sortedRules[i]->rule->lhs;
256 base_counter++; /* make space for 0 */
258 sortedRules[i]->rule->newNum = base_counter;
259 sortedRules[i]->rule->lhs->ruleCount++;
260 sortedRules[i]->rule->lhs->sampleRule = sortedRules[i]->rule; /* kludge for diagnostics */
269 p = (short *) zalloc(globalMap->count* sizeof(short));
278 for (c = 0; v; v >>= 1) {
286 mapToPmap(d) Dimension d;
293 if (d->map->count == 1) {
296 assert(d->map->count > 1);
299 for (i = 0; i < globalMap->count-1; i++) {
300 int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
305 enterStateMap(im, v, width(d->map->count), &new);
313 doDimPmaps(op) Operator op;
321 if (!op->table->rules) {
328 d = op->table->dimen[0];
329 if (d->map->count > 1) {
331 im = newPlankMap(op->baseNum);
332 for (i = 0; i < globalMap->count-1; i++) {
333 int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
335 Item_Set *ts = transLval(op->table, index, 0);
336 v[i+1] = (*ts)->newNum - op->baseNum+1;
340 enterStateMap(im, v, width(d->map->count-1), &new);
348 if (op->table->dimen[0]->map->count == 1 && op->table->dimen[1]->map->count == 1) {
349 op->table->dimen[0]->pmap = 0;
350 op->table->dimen[1]->pmap = 0;
351 } else if (op->table->dimen[0]->map->count == 1) {
353 im = newPlankMap(op->baseNum);
354 d = op->table->dimen[1];
355 for (i = 0; i < globalMap->count-1; i++) {
356 int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
358 Item_Set *ts = transLval(op->table, 1, index);
359 v[i+1] = (*ts)->newNum - op->baseNum+1;
363 enterStateMap(im, v, width(d->map->count-1), &new);
368 } else if (op->table->dimen[1]->map->count == 1) {
370 im = newPlankMap(op->baseNum);
371 d = op->table->dimen[0];
372 for (i = 0; i < globalMap->count-1; i++) {
373 int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
375 Item_Set *ts = transLval(op->table, index, 1);
376 v[i +1] = (*ts)->newNum - op->baseNum +1;
377 assert(v[i +1] >= 0);
380 enterStateMap(im, v, width(d->map->count-1), &new);
386 op->table->dimen[0]->pmap = mapToPmap(op->table->dimen[0]);
387 op->table->dimen[1]->pmap = mapToPmap(op->table->dimen[1]);
389 fprintf(outfile, "static unsigned %s %s_%s_transition[%d][%d] = {",
390 op->stateCount <= 255 ? "char" : "short",
393 op->table->dimen[0]->map->count,
394 op->table->dimen[1]->map->count);
395 for (i = 0; i < op->table->dimen[0]->map->count; i++) {
397 fprintf(outfile, ",");
399 fprintf(outfile, "\n{");
400 for (j = 0; j < op->table->dimen[1]->map->count; j++) {
401 Item_Set *ts = transLval(op->table, i, j);
404 fprintf(outfile, ",");
406 fprintf(outfile, "\t/* row %d, cols %d-%d*/\n",
412 if ((*ts)->num > 0) {
413 diff = (*ts)->newNum - op->baseNum +1;
417 fprintf(outfile, "%5d", diff);
419 fprintf(outfile, "}\t/* row %d */", i);
421 fprintf(outfile, "\n};\n");
429 static NonTerminal *ntVector;
432 doNonTermPmaps(n) NonTerminal n;
439 ntVector[n->num] = n;
440 if (n->num >= last_user_nonterminal) {
443 if (n->ruleCount <= 0) {
446 im = newPlankMap(n->baseNum);
448 for (i = 0; i < globalMap->count-1; i++) {
449 Rule r = globalMap->set[sortedStates[i]->num]->closed[n->num].rule;
452 v[i+1] = r->newNum - n->baseNum /*safely*/;
456 enterStateMap(im, v, width(n->ruleCount+1), &new);
466 foreachList((ListFn) doDimPmaps, operators);
467 ntVector = (NonTerminal*) zalloc((max_nonterminal) * sizeof(NonTerminal));
468 foreachList((ListFn) doNonTermPmaps, nonterminals);
477 fprintf(outfile, "static struct {\n");
479 for (f = p->fields; f; f = f->next) {
480 StateMap sm = (StateMap) f->x;
481 fprintf(outfile, "\tunsigned int %s:%d;\n", sm->fieldname, sm->width);
484 fprintf(outfile, "} %s[] = {\n", p->name);
486 for (i = 0; i < globalMap->count; i++) {
487 fprintf(outfile, "\t{");
488 for (f = p->fields; f; f = f->next) {
489 StateMap sm = (StateMap) f->x;
490 fprintf(outfile, "%4d,", sm->value[i] == -1 ? ERROR_VAL : sm->value[i]);
492 fprintf(outfile, "},\t/* row %d */\n", i);
495 fprintf(outfile, "};\n");
499 purgePlanks(planks) List planks;
503 for (p = planks; p; p = p->next) {
504 Plank x = (Plank) p->x;
515 fprintf(outfile, "static short %s_eruleMap[] = {\n", prefix);
517 for (i = 0; i < max_ruleAST; i++) {
519 fprintf(outfile, ",");
520 if (counter % 10 == 0) {
521 fprintf(outfile, "\t/* %d-%d */\n", counter-10, counter-1);
524 if (counter < sortedRules[i]->rule->newNum) {
525 assert(counter == sortedRules[i]->rule->newNum-1);
526 fprintf(outfile, "%5d", 0);
529 fprintf(outfile, ",");
530 if (counter % 10 == 0) {
531 fprintf(outfile, "\t/* %d-%d */\n", counter-10, counter-1);
535 fprintf(outfile, "%5d", sortedRules[i]->rule->erulenum);
538 fprintf(outfile, "\n};\n");
542 makePlankRuleMacros()
546 for (i = 1; i < last_user_nonterminal; i++) {
548 PlankMap im = ntVector[i]->pmap;
549 fprintf(outfile, "#define %s_%s_rule(state)\t", prefix, ntVector[i]->name);
551 fprintf(outfile, "%s_eruleMap[", prefix);
552 for (es = im->exceptions; es; es = es->next) {
553 Exception e = (Exception) es->x;
554 fprintf(outfile, "((state) == %d ? %d :",
557 fprintf(outfile, "%s[state].%s",
558 im->values->plank->name,
559 im->values->fieldname);
560 for (es = im->exceptions; es; es = es->next) {
561 fprintf(outfile, ")");
563 fprintf(outfile, " +%d]", im->offset);
566 /* nonterminal never appears on LHS. */
567 assert(ntVector[i] == start);
568 fprintf(outfile, "0");
570 fprintf(outfile, "\n");
572 fprintf(outfile, "\n");
580 makePlankRuleMacros();
582 fprintf(outfile, "#ifdef __STDC__\n");
583 fprintf(outfile, "int %s_rule(int state, int goalnt) {\n", prefix);
584 fprintf(outfile, "#else\n");
585 fprintf(outfile, "int %s_rule(state, goalnt) int state; int goalnt; {\n", prefix);
586 fprintf(outfile, "#endif\n");
589 "\t%s_assert(state >= 0 && state < %d, %s_PANIC(\"Bad state %%d passed to %s_rule\\n\", state));\n",
590 prefix, globalMap->count, prefix, prefix);
591 fprintf(outfile, "\tswitch(goalnt) {\n");
593 for (i = 1; i < last_user_nonterminal; i++) {
594 fprintf(outfile, "\tcase %d:\n", i);
595 fprintf(outfile, "\t\treturn %s_%s_rule(state);\n", prefix, ntVector[i]->name);
597 fprintf(outfile, "\tdefault:\n");
598 fprintf(outfile, "\t\t%s_PANIC(\"Unknown nonterminal %%d in %s_rule;\\n\", goalnt);\n", prefix, prefix);
599 fprintf(outfile, "\t\tabort();\n");
600 fprintf(outfile, "\t\treturn 0;\n");
601 fprintf(outfile, "\t}\n");
602 fprintf(outfile, "}\n");
606 exceptionSwitch(es, sw, pre, post, offset, def) List es; const char *sw; const char *pre; const char *post; int offset; const char *def;
609 fprintf(outfile, "\t\tswitch (%s) {\n", sw);
610 for (; es; es = es->next) {
611 Exception e = (Exception) es->x;
612 fprintf(outfile, "\t\tcase %d: %s %d; %s\n", e->index, pre, e->value+offset, post);
615 fprintf(outfile, "\t\tdefault: %s;\n", def);
617 fprintf(outfile, "\t\t}\n");
620 fprintf(outfile, "\t\t%s;\n", def);
626 doPlankLabel(op) Operator op;
632 fprintf(outfile, "\tcase %d:\n", op->num);
635 fprintf(outfile, "\t\treturn %d;\n", op->table->transition[0]->newNum);
638 im0 = op->table->dimen[0]->pmap;
640 exceptionSwitch(im0->exceptions, "l", "return ", "", im0->offset, 0);
641 fprintf(outfile, "\t\treturn %s[l].%s + %d;\n",
642 im0->values->plank->name, im0->values->fieldname, im0->offset);
644 Item_Set *ts = transLval(op->table, 1, 0);
646 fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum);
648 fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
653 im0 = op->table->dimen[0]->pmap;
654 im1 = op->table->dimen[1]->pmap;
656 Item_Set *ts = transLval(op->table, 1, 1);
658 fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum);
660 fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
663 exceptionSwitch(im1->exceptions, "r", "return ", "", im1->offset, 0);
664 fprintf(outfile, "\t\treturn %s[r].%s + %d;\n",
665 im1->values->plank->name, im1->values->fieldname, im1->offset);
667 exceptionSwitch(im0->exceptions, "l", "return ", "", im0->offset, 0);
668 fprintf(outfile, "\t\treturn %s[l].%s + %d;\n",
669 im0->values->plank->name, im0->values->fieldname, im0->offset);
671 assert(im0->offset == 0);
672 assert(im1->offset == 0);
673 sprintf(buf, "l = %s[l].%s",
674 im0->values->plank->name, im0->values->fieldname);
675 exceptionSwitch(im0->exceptions, "l", "l =", "break;", 0, buf);
676 sprintf(buf, "r = %s[r].%s",
677 im1->values->plank->name, im1->values->fieldname);
678 exceptionSwitch(im1->exceptions, "r", "r =", "break;", 0, buf);
680 fprintf(outfile, "\t\treturn %s_%s_transition[l][r] + %d;\n",
692 doPlankLabelMacrosSafely(op) Operator op;
699 fprintf(outfile, "#define %s_%s_state\t0\n", prefix, op->name);
702 fprintf(outfile, "#define %s_%s_state", prefix, op->name);
703 fprintf(outfile, "\t%d\n", op->table->transition[0]->newNum+1);
706 fprintf(outfile, "#define %s_%s_state(l)", prefix, op->name);
707 im0 = op->table->dimen[0]->pmap;
709 if (im0->exceptions) {
710 List es = im0->exceptions;
712 fprintf(outfile, "\t\tswitch (l) {\n");
713 for (; es; es = es->next) {
714 Exception e = (Exception) es->x;
715 fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im0->offset : 0);
717 fprintf(outfile, "\t\t}\n");
720 fprintf(outfile, "\t( %s[l].%s + %d )\n",
721 im0->values->plank->name, im0->values->fieldname,
724 fprintf(outfile, "\t( (%s_TEMP = %s[l].%s) ? %s_TEMP + %d : 0 )\n",
726 im0->values->plank->name, im0->values->fieldname,
731 Item_Set *ts = transLval(op->table, 1, 0);
733 fprintf(outfile, "\t%d\n", (*ts)->newNum+1);
735 fprintf(outfile, "\t%d\n", 0);
740 fprintf(outfile, "#define %s_%s_state(l,r)", prefix, op->name);
742 im0 = op->table->dimen[0]->pmap;
743 im1 = op->table->dimen[1]->pmap;
745 Item_Set *ts = transLval(op->table, 1, 1);
748 fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum+1);
750 fprintf(outfile, "\t\treturn %d;\n", 0);
754 if (im1->exceptions) {
755 List es = im1->exceptions;
756 fprintf(outfile, "\t\tswitch (r) {\n");
757 for (; es; es = es->next) {
758 Exception e = (Exception) es->x;
759 fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im1->offset : 0);
761 fprintf(outfile, "\t\t}\n");
763 fprintf(outfile, "\t\tstate = %s[r].%s; offset = %d;\n",
764 im1->values->plank->name, im1->values->fieldname, im1->offset);
765 fprintf(outfile, "\t\tbreak;\n");
768 if (im0->exceptions) {
769 List es = im0->exceptions;
770 fprintf(outfile, "\t\tswitch (l) {\n");
771 for (; es; es = es->next) {
772 Exception e = (Exception) es->x;
773 fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im0->offset : 0);
775 fprintf(outfile, "\t\t}\n");
777 fprintf(outfile, "\t\tstate = %s[l].%s; offset = %d;\n",
778 im0->values->plank->name, im0->values->fieldname, im0->offset);
779 fprintf(outfile, "\t\tbreak;\n");
781 assert(im0->offset == 0);
782 assert(im1->offset == 0);
784 sprintf(buf, "l = %s[l].%s",
785 im0->values->plank->name, im0->values->fieldname);
786 exceptionSwitch(im0->exceptions, "l", "l =", "break;", 0, buf);
787 sprintf(buf, "r = %s[r].%s",
788 im1->values->plank->name, im1->values->fieldname);
789 exceptionSwitch(im1->exceptions, "r", "r =", "break;", 0, buf);
791 fprintf(outfile, "\t\tstate = %s_%s_transition[l][r]; offset = %d;\n",
795 fprintf(outfile, "\t\tbreak;\n");
799 fprintf(outfile, "\t( %s_%s_transition[%s[l].%s][%s[r].%s] + %d)\n",
802 im0->values->plank->name, im0->values->fieldname,
803 im1->values->plank->name, im1->values->fieldname,
806 fprintf(outfile, "\t( (%s_TEMP = %s_%s_transition[%s[l].%s][%s[r].%s]) ? ",
810 im0->values->plank->name, im0->values->fieldname,
811 im1->values->plank->name, im1->values->fieldname);
812 fprintf(outfile, "%s_TEMP + %d : 0 )\n",
823 doPlankLabelSafely(op) Operator op;
825 fprintf(outfile, "\tcase %d:\n", op->num);
828 fprintf(outfile, "\t\treturn 0;\n");
831 fprintf(outfile, "\t\treturn %s_%s_state;\n", prefix, op->name);
834 fprintf(outfile, "\t\treturn %s_%s_state(l);\n", prefix, op->name);
837 fprintf(outfile, "\t\treturn %s_%s_state(l,r);\n", prefix, op->name);
847 fprintf(outfile, "\n");
848 fprintf(outfile, "int %s_TEMP;\n", prefix);
849 foreachList((ListFn) doPlankLabelMacrosSafely, operators);
850 fprintf(outfile, "\n");
852 fprintf(outfile, "#ifdef __STDC__\n");
855 fprintf(stderr, "ERROR: no terminals in grammar.\n");
858 fprintf(outfile, "int %s_state(int op) {\n", prefix);
859 fprintf(outfile, "#else\n");
860 fprintf(outfile, "int %s_state(op) int op; {\n", prefix);
863 fprintf(outfile, "int %s_state(int op, int l) {\n", prefix);
864 fprintf(outfile, "#else\n");
865 fprintf(outfile, "int %s_state(op, l) int op; int l; {\n", prefix);
868 fprintf(outfile, "int %s_state(int op, int l, int r) {\n", prefix);
869 fprintf(outfile, "#else\n");
870 fprintf(outfile, "int %s_state(op, l, r) int op; int l; int r; {\n", prefix);
875 fprintf(outfile, "#endif\n");
877 fprintf(outfile, "\tregister int %s_TEMP;\n", prefix);
879 fprintf(outfile, "#ifndef NDEBUG\n");
881 fprintf(outfile, "\tswitch (op) {\n");
883 if (max_arity >= 2) {
885 "\t\t%s_assert(r >= 0 && r < %d, %s_PANIC(\"Bad state %%d passed to %s_state\\n\", r));\n",
886 prefix, globalMap->count, prefix, prefix);
887 fprintf(outfile, "\t\t/*FALLTHROUGH*/\n");
892 "\t\t%s_assert(l >= 0 && l < %d, %s_PANIC(\"Bad state %%d passed to %s_state\\n\", l));\n",
893 prefix, globalMap->count, prefix, prefix);
894 fprintf(outfile, "\t\t/*FALLTHROUGH*/\n");
897 fprintf(outfile, "\t\tbreak;\n");
898 fprintf(outfile, "\t}\n");
899 fprintf(outfile, "#endif\n");
901 fprintf(outfile, "\tswitch (op) {\n");
902 fprintf(outfile,"\tdefault: %s_PANIC(\"Unknown op %%d in %s_state\\n\", op); abort(); return 0;\n",
904 foreachList((ListFn) doPlankLabelSafely, operators);
905 fprintf(outfile, "\t}\n");
907 fprintf(outfile, "}\n");
916 planks = assemblePlanks();