Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / llvm / 633a5b1aacb135957b20e5f11e779ea23ccb9619 / . / utils / Burg / b.h
blob: f1b33edd9434f347723f2e5e790310ad66ceab34 [file] [log] [blame]
Chris Lattner633a5b12002-09-17 23:03:30 +0000[diff] [blame^]1/* $Id$ */
2
3#define MAX_ARITY 2
4
5typedef int ItemSetNum;
6typedef int OperatorNum;
7typedef int NonTerminalNum;
8typedef int RuleNum;
9typedef int ArityNum;
10typedef int ERuleNum;
11
12extern NonTerminalNum last_user_nonterminal;
13extern NonTerminalNum max_nonterminal;
14extern RuleNum max_rule;
15extern ERuleNum max_erule_num;
16extern 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
26typedef short DeltaCost[DELTAWIDTH];
27typedef short *DeltaPtr;
28extern void ASSIGNCOST ARGS((DeltaPtr, DeltaPtr));
29extern void ADDCOST ARGS((DeltaPtr, DeltaPtr));
30extern void MINUSCOST ARGS((DeltaPtr, DeltaPtr));
31extern void ZEROCOST ARGS((DeltaPtr));
32extern int LESSCOST ARGS((DeltaPtr, DeltaPtr));
33extern int EQUALCOST ARGS((DeltaPtr, DeltaPtr));
34#define PRINCIPLECOST(x) (x[0])
35#else
36#define DELTAWIDTH 1
37typedef int DeltaCost;
38typedef 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
49struct list {
50 void *x;
51 struct list *next;
52};
53typedef struct list *List;
54
55struct intlist {
56 int x;
57 struct intlist *next;
58};
59typedef struct intlist *IntList;
60
61struct 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};
70typedef struct operator *Operator;
71
72struct 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};
81typedef struct nonterminal *NonTerminal;
82
83struct pattern {
84 NonTerminal normalizer;
85 Operator op; /* NULL if NonTerm -> NonTerm */
86 NonTerminal children[MAX_ARITY];
87};
88typedef struct pattern *Pattern;
89
90struct 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};
99typedef struct rule *Rule;
100
101struct item {
102 DeltaCost delta;
103 Rule rule;
104};
105typedef struct item Item;
106
107typedef short *Relevant; /* relevant non-terminals */
108
109typedef Item *ItemArray;
110
111struct 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};
121typedef struct item_set *Item_Set;
122
123#define DIM_MAP_SIZE (1 << 8)
124#define GLOBAL_MAP_SIZE (1 << 15)
125
126struct 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};
133typedef struct mapping *Mapping;
134
135struct index_map {
136 ItemSetNum max_size;
137 Item_Set *class;
138};
139typedef struct index_map Index_Map;
140
141struct dimension {
142 Relevant relevant;
143 Index_Map index_map;
144 Mapping map;
145 ItemSetNum max_size;
146 struct plankMap *pmap;
147};
148typedef struct dimension *Dimension;
149
150
151struct 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};
159typedef struct table *Table;
160
161struct relation {
162 Rule rule;
163 DeltaCost chain;
164 NonTerminalNum nextchain;
165 DeltaCost sibling;
166 int sibFlag;
167 int sibComputed;
168};
169typedef struct relation *Relation;
170
171struct queue {
172 List head;
173 List tail;
174};
175typedef struct queue *Queue;
176
177struct plank {
178 char *name;
179 List fields;
180 int width;
181};
182typedef struct plank *Plank;
183
184struct except {
185 short index;
186 short value;
187};
188typedef struct except *Exception;
189
190struct plankMap {
191 List exceptions;
192 int offset;
193 struct stateMap *values;
194};
195typedef struct plankMap *PlankMap;
196
197struct stateMap {
198 char *fieldname;
199 Plank plank;
200 int width;
201 short *value;
202};
203typedef struct stateMap *StateMap;
204
205struct stateMapTable {
206 List maps;
207};
208
209extern void CHECKDIVERGE ARGS((DeltaPtr, Item_Set, int, int));
210extern void zero ARGS((Item_Set));
211extern ItemArray newItemArray ARGS((void));
212extern ItemArray itemArrayCopy ARGS((ItemArray));
213extern Item_Set newItem_Set ARGS((Relevant));
214extern void freeItem_Set ARGS((Item_Set));
215extern Mapping newMapping ARGS((int));
216extern NonTerminal newNonTerminal ARGS((char *));
217extern int nonTerminalName ARGS((char *, int));
218extern Operator newOperator ARGS((char *, OperatorNum, ArityNum));
219extern Pattern newPattern ARGS((Operator));
220extern Rule newRule ARGS((DeltaPtr, ERuleNum, NonTerminal, Pattern));
221extern List newList ARGS((void *, List));
222extern IntList newIntList ARGS((int, IntList));
223extern int length ARGS((List));
224extern List appendList ARGS((void *, List));
225extern Table newTable ARGS((Operator));
226extern Queue newQ ARGS((void));
227extern void addQ ARGS((Queue, Item_Set));
228extern Item_Set popQ ARGS((Queue));
229extern int equivSet ARGS((Item_Set, Item_Set));
230extern Item_Set decode ARGS((Mapping, ItemSetNum));
231extern Item_Set encode ARGS((Mapping, Item_Set, int *));
232extern void build ARGS((void));
233extern Item_Set *transLval ARGS((Table, int, int));
234
235typedef void * (*ListFn) ARGS((void *));
236extern void foreachList ARGS((ListFn, List));
237extern void reveachList ARGS((ListFn, List));
238
239extern void addToTable ARGS((Table, Item_Set));
240
241extern void closure ARGS((Item_Set));
242extern void trim ARGS((Item_Set));
243extern void findChainRules ARGS((void));
244extern void findAllPairs ARGS((void));
245extern void addRelevant ARGS((Relevant, NonTerminalNum));
246
247extern void *zalloc ARGS((unsigned int));
248extern void zfree ARGS((void *));
249
250extern NonTerminal start;
251extern List rules;
252extern List chainrules;
253extern List operators;
254extern List leaves;
255extern List nonterminals;
256extern List grammarNts;
257extern Queue globalQ;
258extern Mapping globalMap;
259extern int exceptionTolerance;
260extern int prevent_divergence;
261extern int principleCost;
262extern int lexical;
263extern struct rule stub_rule;
264extern Relation *allpairs;
265extern Item_Set *sortedStates;
266extern Item_Set errorState;
267
268extern void dumpRelevant ARGS((Relevant));
269extern void dumpOperator ARGS((Operator, int));
270extern void dumpOperator_s ARGS((Operator));
271extern void dumpOperator_l ARGS((Operator));
272extern void dumpNonTerminal ARGS((NonTerminal));
273extern void dumpRule ARGS((Rule));
274extern void dumpRuleList ARGS((List));
275extern void dumpItem ARGS((Item *));
276extern void dumpItem_Set ARGS((Item_Set));
277extern void dumpMapping ARGS((Mapping));
278extern void dumpQ ARGS((Queue));
279extern void dumpIndex_Map ARGS((Index_Map *));
280extern void dumpDimension ARGS((Dimension));
281extern void dumpPattern ARGS((Pattern));
282extern void dumpTable ARGS((Table, int));
283extern void dumpTransition ARGS((Table));
284extern void dumpCost ARGS((DeltaCost));
285extern void dumpAllPairs ARGS((void));
286extern void dumpRelation ARGS((Relation));
287extern void dumpSortedStates ARGS((void));
288extern void dumpSortedRules ARGS((void));
289extern int debugTrim;
290
291#ifdef DEBUG
292#define debug(a,b) if (a) b
293#else
294#define debug(a,b)
295#endif
296extern 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
307extern void doStart ARGS((char *));
308extern void exit ARGS((int));
309extern int fatal ARGS((char *, int));
310extern void yyerror ARGS((char *));
311extern void yyerror1 ARGS((char *));