utils/Burg/closure.c

   1 char rcsid_closure[] = "$Id$";
   2
   3 #include <stdio.h>
   4 #include "b.h"
   5
   6 int prevent_divergence = 0;
   7
   8 List chainrules;
   9
  10 void
  11 findChainRules()
  12 {
  13         List pl;
  14
  15         assert(!chainrules);
  16
  17         for (pl = rules; pl; pl = pl->next) {
  18                 Rule p = (Rule) pl->x;
  19                 if (!p->pat->op) {
  20                         chainrules = newList(p, chainrules);
  21                 } else {
  22                         p->pat->op->table->rules = newList(p, p->pat->op->table->rules);
  23                         addRelevant(p->pat->op->table->relevant, p->lhs->num);
  24                 }
  25         }
  26 }
  27
  28 void
  29 zero(t) Item_Set t;
  30 {
  31         int i;
  32         DeltaCost base;
  33         int exists;
  34         int base_nt = 0;
  35
  36         assert(!t->closed);
  37
  38         ZEROCOST(base);
  39         exists = 0;
  40         for (i = 0; i < max_nonterminal; i++) {
  41                 if (t->virgin[i].rule) {
  42                         if (exists) {
  43                                 if (LESSCOST(t->virgin[i].delta, base)) {
  44                                         ASSIGNCOST(base, t->virgin[i].delta);
  45                                         base_nt = i;
  46                                 }
  47                         } else {
  48                                 ASSIGNCOST(base, t->virgin[i].delta);
  49                                 exists = 1;
  50                                 base_nt = i;
  51                         }
  52                 }
  53         }
  54         if (!exists) {
  55                 return;
  56         }
  57         for (i = 0; i < max_nonterminal; i++) {
  58                 if (t->virgin[i].rule) {
  59                         MINUSCOST(t->virgin[i].delta, base);
  60                 }
  61                 NODIVERGE(t->virgin[i].delta, t, i, base_nt);
  62         }
  63 }
  64
  65 void
  66 closure(t) Item_Set t;
  67 {
  68         int changes;
  69         List pl;
  70
  71         assert(!t->closed);
  72         t->closed = itemArrayCopy(t->virgin);
  73
  74         changes = 1;
  75         while (changes) {
  76                 changes = 0;
  77                 for (pl = chainrules; pl; pl = pl->next) {
  78                         Rule p = (Rule) pl->x;
  79                         register Item *rhs_item = &t->closed[p->pat->children[0]->num];
  80
  81                         if (rhs_item->rule) {   /* rhs is active */
  82                                 DeltaCost dc;
  83                                 register Item *lhs_item = &t->closed[p->lhs->num];
  84
  85                                 ASSIGNCOST(dc, rhs_item->delta);
  86                                 ADDCOST(dc, p->delta);
  87                                 if (LESSCOST(dc, lhs_item->delta) || !lhs_item->rule) {
  88                                         ASSIGNCOST(lhs_item->delta, dc);
  89                                         lhs_item->rule = p;
  90                                         changes = 1;
  91                                 }
  92                         }
  93                 }
  94         }
  95 }