utils/Burg/b.h

   1 /* $Id$ */
   2
   3 #define MAX_ARITY       2
   4
   5 typedef int ItemSetNum;
   6 typedef int OperatorNum;
   7 typedef int NonTerminalNum;
   8 typedef int RuleNum;
   9 typedef int ArityNum;
  10 typedef int ERuleNum;
  11
  12 extern NonTerminalNum   last_user_nonterminal;
  13 extern NonTerminalNum   max_nonterminal;
  14 extern RuleNum          max_rule;
  15 extern ERuleNum         max_erule_num;
  16 extern int              max_arity;
  17
  18 #ifdef __STDC__
  19 #define ARGS(x) x
  20 #else
  21 #define ARGS(x) ()
  22 #endif
  23
  24 #ifndef NOLEX
  25 #define DELTAWIDTH      4
  26 typedef short DeltaCost[DELTAWIDTH];
  27 typedef short *DeltaPtr;
  28 extern void ASSIGNCOST ARGS((DeltaPtr, DeltaPtr));
  29 extern void ADDCOST ARGS((DeltaPtr, DeltaPtr));
  30 extern void MINUSCOST ARGS((DeltaPtr, DeltaPtr));
  31 extern void ZEROCOST ARGS((DeltaPtr));
  32 extern int LESSCOST ARGS((DeltaPtr, DeltaPtr));
  33 extern int EQUALCOST ARGS((DeltaPtr, DeltaPtr));
  34 #define PRINCIPLECOST(x)        (x[0])
  35 #else
  36 #define DELTAWIDTH      1
  37 typedef int DeltaCost;
  38 typedef int DeltaPtr;
  39 #define ASSIGNCOST(l, r)        ((l) = (r))
  40 #define ADDCOST(l, r)           ((l) += (r))
  41 #define MINUSCOST(l, r)         ((l) -= (r))
  42 #define ZEROCOST(x)             ((x) = 0)
  43 #define LESSCOST(l, r)          ((l) < (r))
  44 #define EQUALCOST(l, r)         ((l) == (r))
  45 #define PRINCIPLECOST(x)        (x)
  46 #endif /* NOLEX */
  47 #define NODIVERGE(c,state,nt,base)              if (prevent_divergence > 0) CHECKDIVERGE(c,state,nt,base);
  48
  49 struct list {
  50         void            *x;
  51         struct list     *next;
  52 };
  53 typedef struct list     *List;
  54
  55 struct intlist {
  56         int             x;
  57         struct intlist  *next;
  58 };
  59 typedef struct intlist  *IntList;
  60
  61 struct operator {
  62         char            *name;
  63         unsigned int    ref:1;
  64         OperatorNum     num;
  65         ItemSetNum      baseNum;
  66         ItemSetNum      stateCount;
  67         ArityNum        arity;
  68         struct table    *table;
  69 };
  70 typedef struct operator *Operator;
  71
  72 struct nonterminal {
  73         char            *name;
  74         NonTerminalNum  num;
  75         ItemSetNum      baseNum;
  76         ItemSetNum      ruleCount;
  77         struct plankMap *pmap;
  78
  79         struct rule     *sampleRule; /* diagnostic---gives "a" rule that with this lhs */
  80 };
  81 typedef struct nonterminal      *NonTerminal;
  82
  83 struct pattern {
  84         NonTerminal     normalizer;
  85         Operator        op;             /* NULL if NonTerm -> NonTerm */
  86         NonTerminal     children[MAX_ARITY];
  87 };
  88 typedef struct pattern  *Pattern;
  89
  90 struct rule {
  91         DeltaCost       delta;
  92         ERuleNum        erulenum;
  93         RuleNum         num;
  94         RuleNum         newNum;
  95         NonTerminal     lhs;
  96         Pattern         pat;
  97         unsigned int    used:1;
  98 };
  99 typedef struct rule     *Rule;
 100
 101 struct item {
 102         DeltaCost       delta;
 103         Rule            rule;
 104 };
 105 typedef struct item     Item;
 106
 107 typedef short   *Relevant;      /* relevant non-terminals */
 108
 109 typedef Item    *ItemArray;
 110
 111 struct item_set {       /* indexed by NonTerminal */
 112         ItemSetNum      num;
 113         ItemSetNum      newNum;
 114         Operator        op;
 115         struct item_set *kids[2];
 116         struct item_set *representative;
 117         Relevant        relevant;
 118         ItemArray       virgin;
 119         ItemArray       closed;
 120 };
 121 typedef struct item_set *Item_Set;
 122
 123 #define DIM_MAP_SIZE    (1 << 8)
 124 #define GLOBAL_MAP_SIZE (1 << 15)
 125
 126 struct mapping {        /* should be a hash table for TS -> int */
 127         List            *hash;
 128         int             hash_size;
 129         int             max_size;
 130         ItemSetNum      count;
 131         Item_Set        *set;   /* map: int <-> Item_Set */
 132 };
 133 typedef struct mapping  *Mapping;
 134
 135 struct index_map {
 136         ItemSetNum      max_size;
 137         Item_Set        *class;
 138 };
 139 typedef struct index_map        Index_Map;
 140
 141 struct dimension {
 142         Relevant        relevant;
 143         Index_Map       index_map;
 144         Mapping         map;
 145         ItemSetNum      max_size;
 146         struct plankMap *pmap;
 147 };
 148 typedef struct dimension        *Dimension;
 149
 150
 151 struct table {
 152         Operator        op;
 153         List            rules;
 154         Relevant        relevant;
 155         Dimension       dimen[MAX_ARITY];       /* 1 for each dimension */
 156         Item_Set        *transition;    /* maps local indices to global
 157                                                 itemsets */
 158 };
 159 typedef struct table    *Table;
 160
 161 struct relation {
 162         Rule    rule;
 163         DeltaCost       chain;
 164         NonTerminalNum  nextchain;
 165         DeltaCost       sibling;
 166         int             sibFlag;
 167         int             sibComputed;
 168 };
 169 typedef struct relation *Relation;
 170
 171 struct queue {
 172         List head;
 173         List tail;
 174 };
 175 typedef struct queue    *Queue;
 176
 177 struct plank {
 178         char *name;
 179         List fields;
 180         int width;
 181 };
 182 typedef struct plank    *Plank;
 183
 184 struct except {
 185         short index;
 186         short value;
 187 };
 188 typedef struct except   *Exception;
 189
 190 struct plankMap {
 191         List exceptions;
 192         int offset;
 193         struct stateMap *values;
 194 };
 195 typedef struct plankMap *PlankMap;
 196
 197 struct stateMap {
 198         char *fieldname;
 199         Plank plank;
 200         int width;
 201         short *value;
 202 };
 203 typedef struct stateMap *StateMap;
 204
 205 struct stateMapTable {
 206         List maps;
 207 };
 208
 209 extern void CHECKDIVERGE ARGS((DeltaPtr, Item_Set, int, int));
 210 extern void zero ARGS((Item_Set));
 211 extern ItemArray newItemArray ARGS((void));
 212 extern ItemArray itemArrayCopy ARGS((ItemArray));
 213 extern Item_Set newItem_Set ARGS((Relevant));
 214 extern void freeItem_Set ARGS((Item_Set));
 215 extern Mapping newMapping ARGS((int));
 216 extern NonTerminal newNonTerminal ARGS((char *));
 217 extern int nonTerminalName ARGS((char *, int));
 218 extern Operator newOperator ARGS((char *, OperatorNum, ArityNum));
 219 extern Pattern newPattern ARGS((Operator));
 220 extern Rule newRule ARGS((DeltaPtr, ERuleNum, NonTerminal, Pattern));
 221 extern List newList ARGS((void *, List));
 222 extern IntList newIntList ARGS((int, IntList));
 223 extern int length ARGS((List));
 224 extern List appendList ARGS((void *, List));
 225 extern Table newTable ARGS((Operator));
 226 extern Queue newQ ARGS((void));
 227 extern void addQ ARGS((Queue, Item_Set));
 228 extern Item_Set popQ ARGS((Queue));
 229 extern int equivSet ARGS((Item_Set, Item_Set));
 230 extern Item_Set decode ARGS((Mapping, ItemSetNum));
 231 extern Item_Set encode ARGS((Mapping, Item_Set, int *));
 232 extern void build ARGS((void));
 233 extern Item_Set *transLval ARGS((Table, int, int));
 234
 235 typedef void *  (*ListFn) ARGS((void *));
 236 extern void foreachList ARGS((ListFn, List));
 237 extern void reveachList ARGS((ListFn, List));
 238
 239 extern void addToTable ARGS((Table, Item_Set));
 240
 241 extern void closure ARGS((Item_Set));
 242 extern void trim ARGS((Item_Set));
 243 extern void findChainRules ARGS((void));
 244 extern void findAllPairs ARGS((void));
 245 extern void addRelevant ARGS((Relevant, NonTerminalNum));
 246
 247 extern void *zalloc ARGS((unsigned int));
 248 extern void zfree ARGS((void *));
 249
 250 extern NonTerminal      start;
 251 extern List             rules;
 252 extern List             chainrules;
 253 extern List             operators;
 254 extern List             leaves;
 255 extern List             nonterminals;
 256 extern List             grammarNts;
 257 extern Queue            globalQ;
 258 extern Mapping          globalMap;
 259 extern int              exceptionTolerance;
 260 extern int              prevent_divergence;
 261 extern int              principleCost;
 262 extern int              lexical;
 263 extern struct rule      stub_rule;
 264 extern Relation         *allpairs;
 265 extern Item_Set         *sortedStates;
 266 extern Item_Set         errorState;
 267
 268 extern void dumpRelevant ARGS((Relevant));
 269 extern void dumpOperator ARGS((Operator, int));
 270 extern void dumpOperator_s ARGS((Operator));
 271 extern void dumpOperator_l ARGS((Operator));
 272 extern void dumpNonTerminal ARGS((NonTerminal));
 273 extern void dumpRule ARGS((Rule));
 274 extern void dumpRuleList ARGS((List));
 275 extern void dumpItem ARGS((Item *));
 276 extern void dumpItem_Set ARGS((Item_Set));
 277 extern void dumpMapping ARGS((Mapping));
 278 extern void dumpQ ARGS((Queue));
 279 extern void dumpIndex_Map ARGS((Index_Map *));
 280 extern void dumpDimension ARGS((Dimension));
 281 extern void dumpPattern ARGS((Pattern));
 282 extern void dumpTable ARGS((Table, int));
 283 extern void dumpTransition ARGS((Table));
 284 extern void dumpCost ARGS((DeltaCost));
 285 extern void dumpAllPairs ARGS((void));
 286 extern void dumpRelation ARGS((Relation));
 287 extern void dumpSortedStates ARGS((void));
 288 extern void dumpSortedRules ARGS((void));
 289 extern int debugTrim;
 290
 291 #ifdef DEBUG
 292 #define debug(a,b)      if (a) b
 293 #else
 294 #define debug(a,b)
 295 #endif
 296 extern int debugTables;
 297
 298 #define TABLE_INCR      8
 299 #define STATES_INCR     64
 300
 301 #ifdef NDEBUG
 302 #define assert(c) ((void) 0)
 303 #else
 304 #define assert(c) ((void) ((c) || fatal(__FILE__,__LINE__)))
 305 #endif
 306
 307 extern void doStart ARGS((char *));
 308 extern void exit ARGS((int));
 309 extern int fatal ARGS((const char *, int));
 310 extern void yyerror ARGS((const char *));
 311 extern void yyerror1 ARGS((const char *));