1 /* Copyright (c) 2007 by Ian Piumarta
2 * All rights reserved.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the 'Software'),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, provided that the above copyright notice(s) and this
10 * permission notice appear in all copies of the Software. Acknowledgement
11 * of the use of this Software in supporting documentation would be
12 * appreciated but is not required.
13 *
14 * THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK.
15 *
16 * Last edited: 2007-05-15 10:32:09 by piumarta on emilia
17 */
18
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include <assert.h>
23
24 #include "tree.h"
25
26 Node *actions= 0;
27 Node *rules= 0;
28 Node *thisRule= 0;
29 Node *start= 0;
30
31 FILE *output= 0;
32
33 int actionCount= 0;
34 int ruleCount= 0;
35 int lastToken= -1;
36
_newNode(int type,int size)37 static inline Node *_newNode(int type, int size)
38 {
39 Node *node= calloc(1, size);
40 node->type= type;
41 return node;
42 }
43
44 #define newNode(T) _newNode(T, sizeof(struct T))
45
makeRule(char * name)46 Node *makeRule(char *name)
47 {
48 Node *node= newNode(Rule);
49 node->rule.name= strdup(name);
50 node->rule.id= ++ruleCount;
51 node->rule.flags= 0;
52 node->rule.next= rules;
53 rules= node;
54 return node;
55 }
56
findRule(char * name)57 Node *findRule(char *name)
58 {
59 Node *n;
60 char *ptr;
61 for (ptr= name; *ptr; ptr++) if ('-' == *ptr) *ptr= '_';
62 for (n= rules; n; n= n->any.next)
63 {
64 assert(Rule == n->type);
65 if (!strcmp(name, n->rule.name))
66 return n;
67 }
68 return makeRule(name);
69 }
70
beginRule(Node * rule)71 Node *beginRule(Node *rule)
72 {
73 actionCount= 0;
74 return thisRule= rule;
75 }
76
Rule_setExpression(Node * node,Node * expression)77 void Rule_setExpression(Node *node, Node *expression)
78 {
79 assert(node);
80 #ifdef LEG_DEBUG
81 Node_print(node); fprintf(stderr, " [%d]<- ", node->type); Node_print(expression); fprintf(stderr, "\n");
82 #endif
83 assert(Rule == node->type);
84 node->rule.expression= expression;
85 if (!start || !strcmp(node->rule.name, "start"))
86 start= node;
87 }
88
makeVariable(char * name)89 Node *makeVariable(char *name)
90 {
91 Node *node;
92 assert(thisRule);
93 for (node= thisRule->rule.variables; node; node= node->variable.next)
94 if (!strcmp(name, node->variable.name))
95 return node;
96 node= newNode(Variable);
97 node->variable.name= strdup(name);
98 node->variable.next= thisRule->rule.variables;
99 thisRule->rule.variables= node;
100 return node;
101 }
102
makeName(Node * rule)103 Node *makeName(Node *rule)
104 {
105 Node *node= newNode(Name);
106 node->name.rule= rule;
107 node->name.variable= 0;
108 rule->rule.flags |= RuleUsed;
109 return node;
110 }
111
makeDot(void)112 Node *makeDot(void)
113 {
114 return newNode(Dot);
115 }
116
makeCharacter(char * text)117 Node *makeCharacter(char *text)
118 {
119 Node *node= newNode(Character);
120 node->character.value= strdup(text);
121 return node;
122 }
123
makeString(char * text)124 Node *makeString(char *text)
125 {
126 Node *node= newNode(String);
127 node->string.value= strdup(text);
128 return node;
129 }
130
makeClass(char * text)131 Node *makeClass(char *text)
132 {
133 Node *node= newNode(Class);
134 node->cclass.value= (unsigned char *)strdup(text);
135 return node;
136 }
137
makeAction(char * text)138 Node *makeAction(char *text)
139 {
140 Node *node= newNode(Action);
141 char name[1024];
142 assert(thisRule);
143 sprintf(name, "_%d_%s", ++actionCount, thisRule->rule.name);
144 node->action.name= strdup(name);
145 node->action.text= strdup(text);
146 node->action.list= actions;
147 node->action.rule= thisRule;
148 actions= node;
149 {
150 char *ptr;
151 for (ptr= node->action.text; *ptr; ++ptr)
152 if ('$' == ptr[0] && '$' == ptr[1])
153 ptr[1]= ptr[0]= 'y';
154 }
155 return node;
156 }
157
makePredicate(char * text)158 Node *makePredicate(char *text)
159 {
160 Node *node= newNode(Predicate);
161 node->predicate.text= strdup(text);
162 return node;
163 }
164
makeAlternate(Node * e)165 Node *makeAlternate(Node *e)
166 {
167 if (Alternate != e->type)
168 {
169 Node *node= newNode(Alternate);
170 assert(e);
171 assert(!e->any.next);
172 node->alternate.first=
173 node->alternate.last= e;
174 return node;
175 }
176 return e;
177 }
178
Alternate_append(Node * a,Node * e)179 Node *Alternate_append(Node *a, Node *e)
180 {
181 assert(a);
182 a= makeAlternate(a);
183 assert(a->alternate.last);
184 assert(e);
185 a->alternate.last->any.next= e;
186 a->alternate.last= e;
187 return a;
188 }
189
makeSequence(Node * e)190 Node *makeSequence(Node *e)
191 {
192 if (Sequence != e->type)
193 {
194 Node *node= newNode(Sequence);
195 assert(e);
196 assert(!e->any.next);
197 node->sequence.first=
198 node->sequence.last= e;
199 return node;
200 }
201 return e;
202 }
203
Sequence_append(Node * a,Node * e)204 Node *Sequence_append(Node *a, Node *e)
205 {
206 assert(a);
207 a= makeSequence(a);
208 assert(a->sequence.last);
209 assert(e);
210 a->sequence.last->any.next= e;
211 a->sequence.last= e;
212 return a;
213 }
214
makePeekFor(Node * e)215 Node *makePeekFor(Node *e)
216 {
217 Node *node= newNode(PeekFor);
218 node->peekFor.element= e;
219 return node;
220 }
221
makePeekNot(Node * e)222 Node *makePeekNot(Node *e)
223 {
224 Node *node= newNode(PeekNot);
225 node->peekNot.element= e;
226 return node;
227 }
228
makeQuery(Node * e)229 Node *makeQuery(Node *e)
230 {
231 Node *node= newNode(Query);
232 node->query.element= e;
233 return node;
234 }
235
makeStar(Node * e)236 Node *makeStar(Node *e)
237 {
238 Node *node= newNode(Star);
239 node->star.element= e;
240 return node;
241 }
242
makePlus(Node * e)243 Node *makePlus(Node *e)
244 {
245 Node *node= newNode(Plus);
246 node->plus.element= e;
247 return node;
248 }
249
250
251 static Node *stack[1024];
252 static Node **stackPointer= stack;
253
254
255 #ifdef LEG_DEBUG
dumpStack(void)256 static void dumpStack(void)
257 {
258 Node **p;
259 for (p= stack + 1; p <= stackPointer; ++p)
260 {
261 fprintf(stderr, "### %d\t", p - stack);
262 Node_print(*p);
263 fprintf(stderr, "\n");
264 }
265 }
266 #endif
267
push(Node * node)268 Node *push(Node *node)
269 {
270 assert(node);
271 assert(stackPointer < stack + 1023);
272 #ifdef LEG_DEBUG
273 dumpStack(); fprintf(stderr, " PUSH "); Node_print(node); fprintf(stderr, "\n");
274 #endif
275 return *++stackPointer= node;
276 }
277
top(void)278 Node *top(void)
279 {
280 assert(stackPointer > stack);
281 return *stackPointer;
282 }
283
pop(void)284 Node *pop(void)
285 {
286 assert(stackPointer > stack);
287 #ifdef LEG_DEBUG
288 dumpStack(); fprintf(stderr, " POP\n");
289 #endif
290 return *stackPointer--;
291 }
292
293
Node_fprint(FILE * stream,Node * node)294 static void Node_fprint(FILE *stream, Node *node)
295 {
296 assert(node);
297 switch (node->type)
298 {
299 case Rule: fprintf(stream, " %s", node->rule.name); break;
300 case Name: fprintf(stream, " %s", node->name.rule->rule.name); break;
301 case Dot: fprintf(stream, " ."); break;
302 case Character: fprintf(stream, " '%s'", node->character.value); break;
303 case String: fprintf(stream, " \"%s\"", node->string.value); break;
304 case Class: fprintf(stream, " [%s]", node->cclass.value); break;
305 case Action: fprintf(stream, " { %s }", node->action.text); break;
306 case Predicate: fprintf(stream, " ?{ %s }", node->action.text); break;
307
308 case Alternate: node= node->alternate.first;
309 fprintf(stream, " (");
310 Node_fprint(stream, node);
311 while ((node= node->any.next))
312 {
313 fprintf(stream, " |");
314 Node_fprint(stream, node);
315 }
316 fprintf(stream, " )");
317 break;
318
319 case Sequence: node= node->sequence.first;
320 fprintf(stream, " (");
321 Node_fprint(stream, node);
322 while ((node= node->any.next))
323 Node_fprint(stream, node);
324 fprintf(stream, " )");
325 break;
326
327 case PeekFor: fprintf(stream, "&"); Node_fprint(stream, node->query.element); break;
328 case PeekNot: fprintf(stream, "!"); Node_fprint(stream, node->query.element); break;
329 case Query: Node_fprint(stream, node->query.element); fprintf(stream, "?"); break;
330 case Star: Node_fprint(stream, node->query.element); fprintf(stream, "*"); break;
331 case Plus: Node_fprint(stream, node->query.element); fprintf(stream, "+"); break;
332 default:
333 fprintf(stream, "\nunknown node type %d\n", node->type);
334 exit(1);
335 }
336 }
337
Node_print(Node * node)338 void Node_print(Node *node) { Node_fprint(stderr, node); }
339
Rule_fprint(FILE * stream,Node * node)340 static void Rule_fprint(FILE *stream, Node *node)
341 {
342 assert(node);
343 assert(Rule == node->type);
344 fprintf(stream, "%s.%d =", node->rule.name, node->rule.id);
345 if (node->rule.expression)
346 Node_fprint(stream, node->rule.expression);
347 else
348 fprintf(stream, " UNDEFINED");
349 fprintf(stream, " ;\n");
350 }
351
Rule_print(Node * node)352 void Rule_print(Node *node) { Rule_fprint(stderr, node); }
353