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