Chris Lattner | 633a5b1 | 2002-09-17 23:03:30 +0000 | [diff] [blame^] | 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((char *, int)); |
| 310 | extern void yyerror ARGS((char *)); |
| 311 | extern void yyerror1 ARGS((char *)); |