summaryrefslogtreecommitdiff
path: root/support/tools/Burg/trim.c
diff options
context:
space:
mode:
Diffstat (limited to 'support/tools/Burg/trim.c')
-rw-r--r--support/tools/Burg/trim.c412
1 files changed, 0 insertions, 412 deletions
diff --git a/support/tools/Burg/trim.c b/support/tools/Burg/trim.c
deleted file mode 100644
index 05ee2d0f64..0000000000
--- a/support/tools/Burg/trim.c
+++ /dev/null
@@ -1,412 +0,0 @@
-char rcsid_trim[] = "$Id$";
-
-#include <stdio.h>
-#include "b.h"
-#include "fe.h"
-
-Relation *allpairs;
-
-int trimflag = 0;
-int debugTrim = 0;
-
-static void siblings ARGS((int, int));
-static void findAllNexts ARGS((void));
-static Relation *newAllPairs ARGS((void));
-
-static void
-siblings(i, j) int i; int j;
-{
- int k;
- List pl;
- DeltaCost Max;
- int foundmax;
-
- allpairs[i][j].sibComputed = 1;
-
- if (i == 1) {
- return; /* never trim start symbol */
- }
- if (i==j) {
- return;
- }
-
- ZEROCOST(Max);
- foundmax = 0;
-
- for (k = 1; k < max_nonterminal; k++) {
- DeltaCost tmp;
-
- if (k==i || k==j) {
- continue;
- }
- if (!allpairs[k][i].rule) {
- continue;
- }
- if (!allpairs[k][j].rule) {
- return;
- }
- ASSIGNCOST(tmp, allpairs[k][j].chain);
- MINUSCOST(tmp, allpairs[k][i].chain);
- if (foundmax) {
- if (LESSCOST(Max, tmp)) {
- ASSIGNCOST(Max, tmp);
- }
- } else {
- foundmax = 1;
- ASSIGNCOST(Max, tmp);
- }
- }
-
- for (pl = rules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- Operator op = p->pat->op;
- List oprule;
- DeltaCost Min;
- int foundmin;
-
- if (!op) {
- continue;
- }
- switch (op->arity) {
- case 0:
- continue;
- case 1:
- if (!allpairs[p->pat->children[0]->num ][ i].rule) {
- continue;
- }
- foundmin = 0;
- for (oprule = op->table->rules; oprule; oprule = oprule->next) {
- Rule s = (Rule) oprule->x;
- DeltaPtr Cx;
- DeltaPtr Csj;
- DeltaPtr Cpi;
- DeltaCost tmp;
-
- if (!allpairs[p->lhs->num ][ s->lhs->num].rule
- || !allpairs[s->pat->children[0]->num ][ j].rule) {
- continue;
- }
- Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
- Csj= allpairs[s->pat->children[0]->num ][ j].chain;
- Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
- ASSIGNCOST(tmp, Cx);
- ADDCOST(tmp, s->delta);
- ADDCOST(tmp, Csj);
- MINUSCOST(tmp, Cpi);
- MINUSCOST(tmp, p->delta);
- if (foundmin) {
- if (LESSCOST(tmp, Min)) {
- ASSIGNCOST(Min, tmp);
- }
- } else {
- foundmin = 1;
- ASSIGNCOST(Min, tmp);
- }
- }
- if (!foundmin) {
- return;
- }
- if (foundmax) {
- if (LESSCOST(Max, Min)) {
- ASSIGNCOST(Max, Min);
- }
- } else {
- foundmax = 1;
- ASSIGNCOST(Max, Min);
- }
- break;
- case 2:
- /* do first dimension */
- if (allpairs[p->pat->children[0]->num ][ i].rule) {
- foundmin = 0;
- for (oprule = op->table->rules; oprule; oprule = oprule->next) {
- Rule s = (Rule) oprule->x;
- DeltaPtr Cx;
- DeltaPtr Cb;
- DeltaPtr Csj;
- DeltaPtr Cpi;
- DeltaCost tmp;
-
- if (allpairs[p->lhs->num ][ s->lhs->num].rule
- && allpairs[s->pat->children[0]->num ][ j].rule
- && allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].rule) {
- Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
- Csj= allpairs[s->pat->children[0]->num ][ j].chain;
- Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
- Cb = allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].chain;
- ASSIGNCOST(tmp, Cx);
- ADDCOST(tmp, s->delta);
- ADDCOST(tmp, Csj);
- ADDCOST(tmp, Cb);
- MINUSCOST(tmp, Cpi);
- MINUSCOST(tmp, p->delta);
- if (foundmin) {
- if (LESSCOST(tmp, Min)) {
- ASSIGNCOST(Min, tmp);
- }
- } else {
- foundmin = 1;
- ASSIGNCOST(Min, tmp);
- }
- }
- }
- if (!foundmin) {
- return;
- }
- if (foundmax) {
- if (LESSCOST(Max, Min)) {
- ASSIGNCOST(Max, Min);
- }
- } else {
- foundmax = 1;
- ASSIGNCOST(Max, Min);
- }
- }
- /* do second dimension */
- if (allpairs[p->pat->children[1]->num ][ i].rule) {
- foundmin = 0;
- for (oprule = op->table->rules; oprule; oprule = oprule->next) {
- Rule s = (Rule) oprule->x;
- DeltaPtr Cx;
- DeltaPtr Cb;
- DeltaPtr Csj;
- DeltaPtr Cpi;
- DeltaCost tmp;
-
- if (allpairs[p->lhs->num ][ s->lhs->num].rule
- && allpairs[s->pat->children[1]->num ][ j].rule
- && allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].rule) {
- Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
- Csj= allpairs[s->pat->children[1]->num ][ j].chain;
- Cpi= allpairs[p->pat->children[1]->num ][ i].chain;
- Cb = allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].chain;
- ASSIGNCOST(tmp, Cx);
- ADDCOST(tmp, s->delta);
- ADDCOST(tmp, Csj);
- ADDCOST(tmp, Cb);
- MINUSCOST(tmp, Cpi);
- MINUSCOST(tmp, p->delta);
- if (foundmin) {
- if (LESSCOST(tmp, Min)) {
- ASSIGNCOST(Min, tmp);
- }
- } else {
- foundmin = 1;
- ASSIGNCOST(Min, tmp);
- }
- }
- }
- if (!foundmin) {
- return;
- }
- if (foundmax) {
- if (LESSCOST(Max, Min)) {
- ASSIGNCOST(Max, Min);
- }
- } else {
- foundmax = 1;
- ASSIGNCOST(Max, Min);
- }
- }
- break;
- default:
- assert(0);
- }
- }
- allpairs[i ][ j].sibFlag = foundmax;
- ASSIGNCOST(allpairs[i ][ j].sibling, Max);
-}
-
-static void
-findAllNexts()
-{
- int i,j;
- int last;
-
- for (i = 1; i < max_nonterminal; i++) {
- last = 0;
- for (j = 1; j < max_nonterminal; j++) {
- if (allpairs[i ][j].rule) {
- allpairs[i ][ last].nextchain = j;
- last = j;
- }
- }
- }
- /*
- for (i = 1; i < max_nonterminal; i++) {
- last = 0;
- for (j = 1; j < max_nonterminal; j++) {
- if (allpairs[i ][j].sibFlag) {
- allpairs[i ][ last].nextsibling = j;
- last = j;
- }
- }
- }
- */
-}
-
-static Relation *
-newAllPairs()
-{
- int i;
- Relation *rv;
-
- rv = (Relation*) zalloc(max_nonterminal * sizeof(Relation));
- for (i = 0; i < max_nonterminal; i++) {
- rv[i] = (Relation) zalloc(max_nonterminal * sizeof(struct relation));
- }
- return rv;
-}
-
-void
-findAllPairs()
-{
- List pl;
- int changes;
- int j;
-
- allpairs = newAllPairs();
- for (pl = chainrules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- NonTerminalNum rhs = p->pat->children[0]->num;
- NonTerminalNum lhs = p->lhs->num;
- Relation r = &allpairs[lhs ][ rhs];
-
- if (LESSCOST(p->delta, r->chain)) {
- ASSIGNCOST(r->chain, p->delta);
- r->rule = p;
- }
- }
- for (j = 1; j < max_nonterminal; j++) {
- Relation r = &allpairs[j ][ j];
- ZEROCOST(r->chain);
- r->rule = &stub_rule;
- }
- changes = 1;
- while (changes) {
- changes = 0;
- for (pl = chainrules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- NonTerminalNum rhs = p->pat->children[0]->num;
- NonTerminalNum lhs = p->lhs->num;
- int i;
-
- for (i = 1; i < max_nonterminal; i++) {
- Relation r = &allpairs[rhs ][ i];
- Relation s = &allpairs[lhs ][ i];
- DeltaCost dc;
- if (!r->rule) {
- continue;
- }
- ASSIGNCOST(dc, p->delta);
- ADDCOST(dc, r->chain);
- if (!s->rule || LESSCOST(dc, s->chain)) {
- s->rule = p;
- ASSIGNCOST(s->chain, dc);
- changes = 1;
- }
- }
- }
- }
- findAllNexts();
-}
-
-void
-trim(t) Item_Set t;
-{
- int m,n;
- static short *vec = 0;
- int last;
-
- assert(!t->closed);
- debug(debugTrim, printf("Begin Trim\n"));
- debug(debugTrim, dumpItem_Set(t));
-
- last = 0;
- if (!vec) {
- vec = (short*) zalloc(max_nonterminal * sizeof(*vec));
- }
- for (m = 1; m < max_nonterminal; m++) {
- if (t->virgin[m].rule) {
- vec[last++] = m;
- }
- }
- for (m = 0; m < last; m++) {
- DeltaCost tmp;
- int j;
- int i;
-
- i = vec[m];
-
- for (j = allpairs[i ][ 0].nextchain; j; j = allpairs[i ][ j].nextchain) {
-
- if (i == j) {
- continue;
- }
- if (!t->virgin[j].rule) {
- continue;
- }
- ASSIGNCOST(tmp, t->virgin[j].delta);
- ADDCOST(tmp, allpairs[i ][ j].chain);
- if (!LESSCOST(t->virgin[i].delta, tmp)) {
- t->virgin[i].rule = 0;
- ZEROCOST(t->virgin[i].delta);
- debug(debugTrim, printf("Trimmed Chain (%d,%d)\n", i,j));
- goto outer;
- }
-
- }
- if (!trimflag) {
- continue;
- }
- for (n = 0; n < last; n++) {
- j = vec[n];
- if (i == j) {
- continue;
- }
-
- if (!t->virgin[j].rule) {
- continue;
- }
-
- if (!allpairs[i][j].sibComputed) {
- siblings(i,j);
- }
- if (!allpairs[i][j].sibFlag) {
- continue;
- }
- ASSIGNCOST(tmp, t->virgin[j].delta);
- ADDCOST(tmp, allpairs[i ][ j].sibling);
- if (!LESSCOST(t->virgin[i].delta, tmp)) {
- t->virgin[i].rule = 0;
- ZEROCOST(t->virgin[i].delta);
- goto outer;
- }
- }
-
- outer: ;
- }
-
- debug(debugTrim, dumpItem_Set(t));
- debug(debugTrim, printf("End Trim\n"));
-}
-
-void
-dumpRelation(r) Relation r;
-{
- printf("{ %d %ld %d %ld }", r->rule->erulenum, (long) r->chain, r->sibFlag, (long) r->sibling);
-}
-
-void
-dumpAllPairs()
-{
- int i,j;
-
- printf("Dumping AllPairs\n");
- for (i = 1; i < max_nonterminal; i++) {
- for (j = 1; j < max_nonterminal; j++) {
- dumpRelation(&allpairs[i ][j]);
- }
- printf("\n");
- }
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-18 08:51:23 +0000