1 char rcsid_trim[] = "$Id$";
12 static void siblings ARGS((int, int));
13 static void findAllNexts ARGS((void));
14 static Relation *newAllPairs ARGS((void));
17 siblings(i, j) int i; int j;
24 allpairs[i][j].sibComputed = 1;
27 return; /* never trim start symbol */
36 for (k = 1; k < max_nonterminal; k++) {
42 if (!allpairs[k][i].rule) {
45 if (!allpairs[k][j].rule) {
48 ASSIGNCOST(tmp, allpairs[k][j].chain);
49 MINUSCOST(tmp, allpairs[k][i].chain);
51 if (LESSCOST(Max, tmp)) {
60 for (pl = rules; pl; pl = pl->next) {
61 Rule p = (Rule) pl->x;
62 Operator op = p->pat->op;
74 if (!allpairs[p->pat->children[0]->num ][ i].rule) {
78 for (oprule = op->table->rules; oprule; oprule = oprule->next) {
79 Rule s = (Rule) oprule->x;
85 if (!allpairs[p->lhs->num ][ s->lhs->num].rule
86 || !allpairs[s->pat->children[0]->num ][ j].rule) {
89 Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
90 Csj= allpairs[s->pat->children[0]->num ][ j].chain;
91 Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
93 ADDCOST(tmp, s->delta);
96 MINUSCOST(tmp, p->delta);
98 if (LESSCOST(tmp, Min)) {
103 ASSIGNCOST(Min, tmp);
110 if (LESSCOST(Max, Min)) {
111 ASSIGNCOST(Max, Min);
115 ASSIGNCOST(Max, Min);
119 /* do first dimension */
120 if (allpairs[p->pat->children[0]->num ][ i].rule) {
122 for (oprule = op->table->rules; oprule; oprule = oprule->next) {
123 Rule s = (Rule) oprule->x;
130 if (allpairs[p->lhs->num ][ s->lhs->num].rule
131 && allpairs[s->pat->children[0]->num ][ j].rule
132 && allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].rule) {
133 Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
134 Csj= allpairs[s->pat->children[0]->num ][ j].chain;
135 Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
136 Cb = allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].chain;
138 ADDCOST(tmp, s->delta);
142 MINUSCOST(tmp, p->delta);
144 if (LESSCOST(tmp, Min)) {
145 ASSIGNCOST(Min, tmp);
149 ASSIGNCOST(Min, tmp);
157 if (LESSCOST(Max, Min)) {
158 ASSIGNCOST(Max, Min);
162 ASSIGNCOST(Max, Min);
165 /* do second dimension */
166 if (allpairs[p->pat->children[1]->num ][ i].rule) {
168 for (oprule = op->table->rules; oprule; oprule = oprule->next) {
169 Rule s = (Rule) oprule->x;
176 if (allpairs[p->lhs->num ][ s->lhs->num].rule
177 && allpairs[s->pat->children[1]->num ][ j].rule
178 && allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].rule) {
179 Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
180 Csj= allpairs[s->pat->children[1]->num ][ j].chain;
181 Cpi= allpairs[p->pat->children[1]->num ][ i].chain;
182 Cb = allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].chain;
184 ADDCOST(tmp, s->delta);
188 MINUSCOST(tmp, p->delta);
190 if (LESSCOST(tmp, Min)) {
191 ASSIGNCOST(Min, tmp);
195 ASSIGNCOST(Min, tmp);
203 if (LESSCOST(Max, Min)) {
204 ASSIGNCOST(Max, Min);
208 ASSIGNCOST(Max, Min);
216 allpairs[i ][ j].sibFlag = foundmax;
217 ASSIGNCOST(allpairs[i ][ j].sibling, Max);
226 for (i = 1; i < max_nonterminal; i++) {
228 for (j = 1; j < max_nonterminal; j++) {
229 if (allpairs[i ][j].rule) {
230 allpairs[i ][ last].nextchain = j;
236 for (i = 1; i < max_nonterminal; i++) {
238 for (j = 1; j < max_nonterminal; j++) {
239 if (allpairs[i ][j].sibFlag) {
240 allpairs[i ][ last].nextsibling = j;
254 rv = (Relation*) zalloc(max_nonterminal * sizeof(Relation));
255 for (i = 0; i < max_nonterminal; i++) {
256 rv[i] = (Relation) zalloc(max_nonterminal * sizeof(struct relation));
268 allpairs = newAllPairs();
269 for (pl = chainrules; pl; pl = pl->next) {
270 Rule p = (Rule) pl->x;
271 NonTerminalNum rhs = p->pat->children[0]->num;
272 NonTerminalNum lhs = p->lhs->num;
273 Relation r = &allpairs[lhs ][ rhs];
275 if (LESSCOST(p->delta, r->chain)) {
276 ASSIGNCOST(r->chain, p->delta);
280 for (j = 1; j < max_nonterminal; j++) {
281 Relation r = &allpairs[j ][ j];
283 r->rule = &stub_rule;
288 for (pl = chainrules; pl; pl = pl->next) {
289 Rule p = (Rule) pl->x;
290 NonTerminalNum rhs = p->pat->children[0]->num;
291 NonTerminalNum lhs = p->lhs->num;
294 for (i = 1; i < max_nonterminal; i++) {
295 Relation r = &allpairs[rhs ][ i];
296 Relation s = &allpairs[lhs ][ i];
301 ASSIGNCOST(dc, p->delta);
302 ADDCOST(dc, r->chain);
303 if (!s->rule || LESSCOST(dc, s->chain)) {
305 ASSIGNCOST(s->chain, dc);
318 static short *vec = 0;
322 debug(debugTrim, printf("Begin Trim\n"));
323 debug(debugTrim, dumpItem_Set(t));
327 vec = (short*) zalloc(max_nonterminal * sizeof(*vec));
329 for (m = 1; m < max_nonterminal; m++) {
330 if (t->virgin[m].rule) {
334 for (m = 0; m < last; m++) {
341 for (j = allpairs[i ][ 0].nextchain; j; j = allpairs[i ][ j].nextchain) {
346 if (!t->virgin[j].rule) {
349 ASSIGNCOST(tmp, t->virgin[j].delta);
350 ADDCOST(tmp, allpairs[i ][ j].chain);
351 if (!LESSCOST(t->virgin[i].delta, tmp)) {
352 t->virgin[i].rule = 0;
353 ZEROCOST(t->virgin[i].delta);
354 debug(debugTrim, printf("Trimmed Chain (%d,%d)\n", i,j));
362 for (n = 0; n < last; n++) {
368 if (!t->virgin[j].rule) {
372 if (!allpairs[i][j].sibComputed) {
375 if (!allpairs[i][j].sibFlag) {
378 ASSIGNCOST(tmp, t->virgin[j].delta);
379 ADDCOST(tmp, allpairs[i ][ j].sibling);
380 if (!LESSCOST(t->virgin[i].delta, tmp)) {
381 t->virgin[i].rule = 0;
382 ZEROCOST(t->virgin[i].delta);
390 debug(debugTrim, dumpItem_Set(t));
391 debug(debugTrim, printf("End Trim\n"));
395 dumpRelation(r) Relation r;
397 printf("{ %d %ld %d %ld }", r->rule->erulenum, (long) r->chain, r->sibFlag, (long) r->sibling);
405 printf("Dumping AllPairs\n");
406 for (i = 1; i < max_nonterminal; i++) {
407 for (j = 1; j < max_nonterminal; j++) {
408 dumpRelation(&allpairs[i ][j]);