]> git.proxmox.com Git - mirror_edk2.git/blame - Tools/CCode/Source/Pccts/antlr/misc.c
projects / mirror_edk2.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Fixed all scripts to use new directory layout.
[mirror_edk2.git] / Tools / CCode / Source / Pccts / antlr / misc.c
CommitLineData
878ddf1f 1/*\r
2 * misc.c\r
3 *\r
4 * Manage tokens, regular expressions.\r
5 * Print methods for debugging\r
6 * Compute follow lists onto tail ends of rules.\r
7 *\r
8 * The following functions are visible:\r
9 *\r
10 * int addTname(char *); Add token name\r
11 * int addTexpr(char *); Add token expression\r
12 * int Tnum(char *); Get number of expr/token\r
13 * void Tklink(char *, char *); Link a name with an expression\r
14 * int hasAction(expr); Does expr already have action assigned?\r
15 * void setHasAction(expr); Indicate that expr now has an action\r
16 * Entry *newEntry(char *,int); Create new table entry with certain size\r
17 * void list_add(ListNode **list, char *e)\r
18 * void list_free(ListNode **list, int freeData); *** MR10 ***\r
19 * void list_apply(ListNode *list, void (*f)())\r
20 * void lexclass(char *m); switch to new/old lexical class\r
21 * void lexmode(int i); switch to old lexical class i\r
22 *\r
23 * SOFTWARE RIGHTS\r
24 *\r
25 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
26 * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
27 * company may do whatever they wish with source code distributed with\r
28 * PCCTS or the code generated by PCCTS, including the incorporation of\r
29 * PCCTS, or its output, into commerical software.\r
30 *\r
31 * We encourage users to develop software with PCCTS. However, we do ask\r
32 * that credit is given to us for developing PCCTS. By "credit",\r
33 * we mean that if you incorporate our source code into one of your\r
34 * programs (commercial product, research project, or otherwise) that you\r
35 * acknowledge this fact somewhere in the documentation, research report,\r
36 * etc... If you like PCCTS and have developed a nice tool with the\r
37 * output, please mention that you developed it using PCCTS. In\r
38 * addition, we ask that this header remain intact in our source code.\r
39 * As long as these guidelines are kept, we expect to continue enhancing\r
40 * this system and expect to make other tools available as they are\r
41 * completed.\r
42 *\r
43 * ANTLR 1.33\r
44 * Terence Parr\r
45 * Parr Research Corporation\r
46 * with Purdue University and AHPCRC, University of Minnesota\r
47 * 1989-2001\r
48 */\r
49\r
50#include <stdio.h>\r
51#include "pcctscfg.h"\r
52#include "set.h"\r
53#include "syn.h"\r
54#include "hash.h"\r
55#include "generic.h"\r
56#include "dlgdef.h"\r
57#include <ctype.h>\r
58\r
59static int tsize=TSChunk; /* size of token str arrays */\r
60\r
61static void\r
62#ifdef __USE_PROTOS\r
63RemapForcedTokensInSyntaxDiagram(Node *);\r
64#else\r
65RemapForcedTokensInSyntaxDiagram();\r
66#endif\r
67\r
68 /* T o k e n M a n i p u l a t i o n */\r
69\r
70/*\r
71 * add token 't' to the TokenStr/Expr array. Make more room if necessary.\r
72 * 't' is either an expression or a token name.\r
73 *\r
74 * There is only one TokenStr array, but multiple ExprStr's. Therefore,\r
75 * for each lex class (element of lclass) we must extend the ExprStr array.\r
76 * ExprStr's and TokenStr are always all the same size.\r
77 *\r
78 * Also, there is a Texpr hash table for each automaton.\r
79 */\r
80static void\r
81#ifdef __USE_PROTOS\r
82Ttrack( char *t )\r
83#else\r
84Ttrack( t )\r
85char *t;\r
86#endif\r
87{\r
88 if ( TokenNum >= tsize ) /* terminal table overflow? */\r
89 {\r
90 char **p;\r
91 int i, more, j;\r
92\r
93 more = TSChunk * (1 + ((TokenNum-tsize) / TSChunk));\r
94 tsize += more;\r
95 TokenStr = (char **) realloc((char *)TokenStr, tsize*sizeof(char *));\r
96 require(TokenStr != NULL, "Ttrack: can't extend TokenStr");\r
97 for (i=0; i<NumLexClasses; i++)\r
98 {\r
99 lclass[i].exprs = (char **)\r
100 realloc((char *)lclass[i].exprs, tsize*sizeof(char *));\r
101 require(lclass[i].exprs != NULL, "Ttrack: can't extend ExprStr");\r
102 for (p= &lclass[i].exprs[tsize-more],j=1; j<=more; j++) *p++ = NULL;\r
103 }\r
104 for (p= &TokenStr[tsize-more],i=1; i<=more; i++) *p++ = NULL;\r
105 lexmode( CurrentLexClass ); /* reset ExprStr in case table moved */\r
106 }\r
107 /* note: we use the actual ExprStr/TokenStr array\r
108 * here as TokenInd doesn't exist yet\r
109 */\r
110 if ( *t == '"' ) ExprStr[TokenNum] = t;\r
111 else TokenStr[TokenNum] = t;\r
112}\r
113\r
114static Expr *\r
115#ifdef __USE_PROTOS\r
116newExpr( char *e )\r
117#else\r
118newExpr( e )\r
119char *e;\r
120#endif\r
121{\r
122 Expr *p = (Expr *) calloc(1, sizeof(Expr));\r
123 require(p!=NULL, "newExpr: cannot alloc Expr node");\r
124\r
125 p->expr = e;\r
126 p->lclass = CurrentLexClass;\r
127 return p;\r
128}\r
129\r
130/* switch to lexical class/mode m. This amounts to creating a new\r
131 * lex mode if one does not already exist and making ExprStr point\r
132 * to the correct char string array. We must also switch Texpr tables.\r
133 *\r
134 * BTW, we need multiple ExprStr arrays because more than one automaton\r
135 * may have the same label for a token, but with different expressions.\r
136 * We need to track an expr for each automaton. If we disallowed this\r
137 * feature, only one ExprStr would be required.\r
138 */\r
139void\r
140#ifdef __USE_PROTOS\r
141lexclass( char *m )\r
142#else\r
143lexclass( m )\r
144char *m;\r
145#endif\r
146{\r
147 int i;\r
148 TermEntry *p;\r
149 static char EOFSTR[] = "\"@\"";\r
150\r
151 if ( hash_get(Tname, m) != NULL )\r
152 {\r
153 warn(eMsg1("lexclass name conflicts with token/errclass label '%s'",m));\r
154 }\r
155 /* does m already exist? */\r
156 i = LexClassIndex(m);\r
157 if ( i != -1 ) {lexmode(i); return;}\r
158 /* must make new one */\r
159 NumLexClasses++;\r
160 CurrentLexClass = NumLexClasses-1;\r
161 require(NumLexClasses<=MaxLexClasses, "number of allowable lexclasses exceeded\nIncrease MaxLexClasses in generic.h and recompile all C files");\r
162 lclass[CurrentLexClass].classnum = m;\r
163 lclass[CurrentLexClass].exprs = (char **) calloc(tsize, sizeof(char *));\r
164 require(lclass[CurrentLexClass].exprs!=NULL,\r
165 "lexclass: cannot allocate ExprStr");\r
166 lclass[CurrentLexClass].htable = newHashTable();\r
167 ExprStr = lclass[CurrentLexClass].exprs;\r
168 Texpr = lclass[CurrentLexClass].htable;\r
169 /* define EOF for each automaton */\r
170 p = newTermEntry( EOFSTR );\r
171 p->token = EofToken; /* couldn't have remapped tokens yet, use EofToken */\r
172 hash_add(Texpr, EOFSTR, (Entry *)p);\r
173 list_add(&ExprOrder, (void *)newExpr(EOFSTR));\r
174 /* note: we use the actual ExprStr array\r
175 * here as TokenInd doesn't exist yet\r
176 */\r
177 ExprStr[EofToken] = EOFSTR;\r
178}\r
179\r
180void\r
181#ifdef __USE_PROTOS\r
182lexmode( int i )\r
183#else\r
184lexmode( i )\r
185int i;\r
186#endif\r
187{\r
188 require(i<NumLexClasses, "lexmode: invalid mode");\r
189 ExprStr = lclass[i].exprs;\r
190 Texpr = lclass[i].htable;\r
191 CurrentLexClass = i;\r
192}\r
193\r
194/* return index into lclass array of lexical class. return -1 if nonexistent */\r
195int\r
196#ifdef __USE_PROTOS\r
197LexClassIndex( char *cl )\r
198#else\r
199LexClassIndex( cl )\r
200char *cl;\r
201#endif\r
202{\r
203 int i;\r
204\r
205 for (i=0; i<NumLexClasses; i++)\r
206 {\r
207 if ( strcmp(lclass[i].classnum, cl) == 0 ) return i;\r
208 }\r
209 return -1;\r
210}\r
211\r
212int\r
213#ifdef __USE_PROTOS\r
214hasAction( char *expr )\r
215#else\r
216hasAction( expr )\r
217char *expr;\r
218#endif\r
219{\r
220 TermEntry *p;\r
221 require(expr!=NULL, "hasAction: invalid expr");\r
222\r
223 p = (TermEntry *) hash_get(Texpr, expr);\r
224 require(p!=NULL, eMsg1("hasAction: expr '%s' doesn't exist",expr));\r
225 return (p->action!=NULL);\r
226}\r
227\r
228void\r
229#ifdef __USE_PROTOS\r
230setHasAction( char *expr, char *action )\r
231#else\r
232setHasAction( expr, action )\r
233char *expr;\r
234char *action;\r
235#endif\r
236{\r
237 TermEntry *p;\r
238 require(expr!=NULL, "setHasAction: invalid expr");\r
239\r
240 p = (TermEntry *) hash_get(Texpr, expr);\r
241 require(p!=NULL, eMsg1("setHasAction: expr '%s' doesn't exist",expr));\r
242 p->action = action;\r
243}\r
244\r
245ForcedToken *\r
246#ifdef __USE_PROTOS\r
247newForcedToken(char *token, int tnum)\r
248#else\r
249newForcedToken(token, tnum)\r
250char *token;\r
251int tnum;\r
252#endif\r
253{\r
254 ForcedToken *ft = (ForcedToken *) calloc(1, sizeof(ForcedToken));\r
255 require(ft!=NULL, "out of memory");\r
256 ft->token = token;\r
257 ft->tnum = tnum;\r
258 return ft;\r
259}\r
260\r
261/*\r
262 * Make a token indirection array that remaps token numbers and then walk\r
263 * the appropriate symbol tables and SynDiag to change token numbers\r
264 */\r
265void\r
266#ifdef __USE_PROTOS\r
267RemapForcedTokens(void)\r
268#else\r
269RemapForcedTokens()\r
270#endif\r
271{\r
272 ListNode *p;\r
273 ForcedToken *q;\r
274 int max_token_number=0; /* MR9 23-Sep-97 Removed "unsigned" */\r
275 int i;\r
276\r
277 if ( ForcedTokens == NULL ) return;\r
278\r
279 /* find max token num */\r
280 for (p = ForcedTokens->next; p!=NULL; p=p->next)\r
281 {\r
282 q = (ForcedToken *) p->elem;\r
283 if ( q->tnum > max_token_number ) max_token_number = q->tnum;\r
284 }\r
285 fprintf(stderr, "max token number is %d\n", max_token_number);\r
286\r
287 /* make token indirection array */\r
288 TokenInd = (int *) calloc(max_token_number+1, sizeof(int));\r
289 LastTokenCounted = TokenNum;\r
290 TokenNum = max_token_number+1;\r
291 require(TokenInd!=NULL, "RemapForcedTokens: cannot allocate TokenInd");\r
292\r
293 /* fill token indirection array and change token id htable ; swap token indices */\r
294 for (i=1; i<TokenNum; i++) TokenInd[i] = i;\r
295 for (p = ForcedTokens->next; p!=NULL; p=p->next)\r
296 {\r
297 TermEntry *te;\r
298 int old_pos, t;\r
299\r
300 q = (ForcedToken *) p->elem;\r
301 fprintf(stderr, "%s forced to %d\n", q->token, q->tnum);\r
302 te = (TermEntry *) hash_get(Tname, q->token);\r
303 require(te!=NULL, "RemapForcedTokens: token not in hash table");\r
304 old_pos = te->token;\r
305 fprintf(stderr, "Before: TokenInd[old_pos==%d] is %d\n", old_pos, TokenInd[old_pos]);\r
306 fprintf(stderr, "Before: TokenInd[target==%d] is %d\n", q->tnum, TokenInd[q->tnum]);\r
307 q = (ForcedToken *) p->elem;\r
308 t = TokenInd[old_pos];\r
309 TokenInd[old_pos] = q->tnum;\r
310 TokenInd[q->tnum] = t;\r
311 te->token = q->tnum; /* update token type id symbol table */\r
312 fprintf(stderr, "After: TokenInd[old_pos==%d] is %d\n", old_pos, TokenInd[old_pos]);\r
313 fprintf(stderr, "After: TokenInd[target==%d] is %d\n", q->tnum, TokenInd[q->tnum]);\r
314\r
315 /* Change the token number in the sym tab entry for the exprs\r
316 * at the old position of the token id and the target position\r
317 */\r
318 /* update expr at target (if any) of forced token id */\r
319 if ( q->tnum < TokenNum ) /* is it a valid position? */\r
320 {\r
321 for (i=0; i<NumLexClasses; i++)\r
322 {\r
323 if ( lclass[i].exprs[q->tnum]!=NULL )\r
324 {\r
325 /* update the symbol table for this expr */\r
326 TermEntry *e = (TermEntry *) hash_get(lclass[i].htable, lclass[i].exprs[q->tnum]);\r
327 require(e!=NULL, "RemapForcedTokens: expr not in hash table");\r
328 e->token = old_pos;\r
329 fprintf(stderr, "found expr '%s' at target %d in lclass[%d]; changed to %d\n",\r
330 lclass[i].exprs[q->tnum], q->tnum, i, old_pos);\r
331 }\r
332 }\r
333 }\r
334 /* update expr at old position (if any) of forced token id */\r
335 for (i=0; i<NumLexClasses; i++)\r
336 {\r
337 if ( lclass[i].exprs[old_pos]!=NULL )\r
338 {\r
339 /* update the symbol table for this expr */\r
340 TermEntry *e = (TermEntry *) hash_get(lclass[i].htable, lclass[i].exprs[old_pos]);\r
341 require(e!=NULL, "RemapForcedTokens: expr not in hash table");\r
342 e->token = q->tnum;\r
343 fprintf(stderr, "found expr '%s' for id %s in lclass[%d]; changed to %d\n",\r
344 lclass[i].exprs[old_pos], q->token, i, q->tnum);\r
345 }\r
346 }\r
347 }\r
348\r
349 /* Update SynDiag */\r
350 RemapForcedTokensInSyntaxDiagram((Node *)SynDiag);\r
351}\r
352\r
353static void\r
354#ifdef __USE_PROTOS\r
355RemapForcedTokensInSyntaxDiagram(Node *p)\r
356#else\r
357RemapForcedTokensInSyntaxDiagram(p)\r
358Node *p;\r
359#endif\r
360{\r
361 Junction *j = (Junction *) p;\r
362 RuleRefNode *r = (RuleRefNode *) p;\r
363 TokNode *t = (TokNode *)p;\r
364\r
365 if ( p==NULL ) return;\r
366 require(p->ntype>=1 && p->ntype<=NumNodeTypes, "Remap...: invalid diagram node");\r
367 switch ( p->ntype )\r
368 {\r
369 case nJunction :\r
370 if ( j->visited ) return;\r
371 if ( j->jtype == EndRule ) return;\r
372 j->visited = TRUE;\r
373 RemapForcedTokensInSyntaxDiagram( j->p1 );\r
374 RemapForcedTokensInSyntaxDiagram( j->p2 );\r
375 j->visited = FALSE;\r
376 return;\r
377 case nRuleRef :\r
378 RemapForcedTokensInSyntaxDiagram( r->next );\r
379 return;\r
380 case nToken :\r
381 if ( t->remapped ) return; /* we've been here before */\r
382 t->remapped = 1;\r
383 fprintf(stderr, "remapping %d to %d\n", t->token, TokenInd[t->token]);\r
384 t->token = TokenInd[t->token];\r
385 RemapForcedTokensInSyntaxDiagram( t->next );\r
386 return;\r
387 case nAction :\r
388 RemapForcedTokensInSyntaxDiagram( ((ActionNode *)p)->next );\r
389 return;\r
390 default :\r
391 fatal_internal("invalid node type");\r
392 }\r
393}\r
394\r
395/*\r
396 * Add a token name. Return the token number associated with it. If it already\r
397 * exists, then return the token number assigned to it.\r
398 *\r
399 * Track the order in which tokens are found so that the DLG output maintains\r
400 * that order. It also lets us map token numbers to strings.\r
401 */\r
402int\r
403#ifdef __USE_PROTOS\r
404addTname( char *token )\r
405#else\r
406addTname( token )\r
407char *token;\r
408#endif\r
409{\r
410 TermEntry *p;\r
411 require(token!=NULL, "addTname: invalid token name");\r
412\r
413 if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;\r
414 p = newTermEntry( token );\r
415 Ttrack( p->str );\r
416 p->token = TokenNum++;\r
417 hash_add(Tname, token, (Entry *)p);\r
418 return p->token;\r
419}\r
420\r
421/* This is the same as addTname except we force the TokenNum to be tnum.\r
422 * We don't have to use the Forced token stuff as no tokens will have\r
423 * been defined with #tokens when this is called. This is only called\r
424 * when a #tokdefs meta-op is used.\r
425 */\r
426int\r
427#ifdef __USE_PROTOS\r
428addForcedTname( char *token, int tnum )\r
429#else\r
430addForcedTname( token, tnum )\r
431char *token;\r
432int tnum;\r
433#endif\r
434{\r
435 TermEntry *p;\r
436 require(token!=NULL, "addTname: invalid token name");\r
437\r
438 if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;\r
439 p = newTermEntry( token );\r
440 Ttrack( p->str );\r
441 p->token = tnum;\r
442 hash_add(Tname, token, (Entry *)p);\r
443 return p->token;\r
444}\r
445\r
446/*\r
447 * Add a token expr. Return the token number associated with it. If it already\r
448 * exists, then return the token number assigned to it.\r
449 */\r
450int\r
451#ifdef __USE_PROTOS\r
452addTexpr( char *expr )\r
453#else\r
454addTexpr( expr )\r
455char *expr;\r
456#endif\r
457{\r
458 TermEntry *p;\r
459 require(expr!=NULL, "addTexpr: invalid regular expression");\r
460\r
461 if ( (p=(TermEntry *)hash_get(Texpr, expr)) != NULL ) return p->token;\r
462 p = newTermEntry( expr );\r
463 Ttrack( p->str );\r
464 /* track the order in which they occur */\r
465 list_add(&ExprOrder, (void *)newExpr(p->str));\r
466 p->token = TokenNum++;\r
467 hash_add(Texpr, expr, (Entry *)p);\r
468 return p->token;\r
469}\r
470\r
471/* return the token number of 'term'. Return 0 if no 'term' exists */\r
472int\r
473#ifdef __USE_PROTOS\r
474Tnum( char *term )\r
475#else\r
476Tnum( term )\r
477char *term;\r
478#endif\r
479{\r
480 TermEntry *p;\r
481 require(term!=NULL, "Tnum: invalid terminal");\r
482 \r
483 if ( *term=='"' ) p = (TermEntry *) hash_get(Texpr, term);\r
484 else p = (TermEntry *) hash_get(Tname, term);\r
485 if ( p == NULL ) return 0;\r
486 else return p->token;\r
487}\r
488\r
489/* associate a Name with an expr. If both have been already assigned\r
490 * token numbers, then an error is reported. Add the token or expr\r
491 * that has not been added if no error. This 'represents' the #token\r
492 * ANTLR pseudo-op. If both have not been defined, define them both\r
493 * linked to same token number.\r
494 */\r
495void\r
496#ifdef __USE_PROTOS\r
497Tklink( char *token, char *expr )\r
498#else\r
499Tklink( token, expr )\r
500char *token;\r
501char *expr;\r
502#endif\r
503{\r
504 TermEntry *p, *q;\r
505 require(token!=NULL && expr!=NULL, "Tklink: invalid token name and/or expr");\r
506\r
507 p = (TermEntry *) hash_get(Tname, token);\r
508 q = (TermEntry *) hash_get(Texpr, expr);\r
509 if ( p != NULL && q != NULL ) /* both defined */\r
510 {\r
511 warn( eMsg2("token name %s and rexpr %s already defined; ignored",\r
512 token, expr) );\r
513 return;\r
514 }\r
515 if ( p==NULL && q==NULL ) /* both not defined */\r
516 {\r
517 int t = addTname( token );\r
518 q = newTermEntry( expr );\r
519 hash_add(Texpr, expr, (Entry *)q);\r
520 q->token = t;\r
521 /* note: we use the actual ExprStr array\r
522 * here as TokenInd doesn't exist yet\r
523 */\r
524 ExprStr[t] = q->str;\r
525 /* track the order in which they occur */\r
526 list_add(&ExprOrder, (void *)newExpr(q->str));\r
527 return;\r
528 }\r
529 if ( p != NULL ) /* one is defined, one is not */\r
530 {\r
531 q = newTermEntry( expr );\r
532 hash_add(Texpr, expr, (Entry *)q);\r
533 q->token = p->token;\r
534 ExprStr[p->token] = q->str; /* both expr and token str defined now */\r
535 list_add(&ExprOrder, (void *)newExpr(q->str));\r
536 }\r
537 else /* trying to associate name with expr here*/\r
538 {\r
539 p = newTermEntry( token );\r
540 hash_add(Tname, token, (Entry *)p);\r
541 p->token = q->token;\r
542 TokenStr[p->token] = p->str;/* both expr and token str defined now */\r
543 }\r
544}\r
545\r
546/*\r
547 * Given a string, this function allocates and returns a pointer to a\r
548 * hash table record of size 'sz' whose "str" pointer is reset to a position\r
549 * in the string table.\r
550 */\r
551Entry *\r
552#ifdef __USE_PROTOS\r
553newEntry( char *text, int sz )\r
554#else\r
555newEntry( text, sz )\r
556char *text;\r
557int sz;\r
558#endif\r
559{\r
560 Entry *p;\r
561 require(text!=NULL, "new: NULL terminal");\r
562 \r
563 if ( (p = (Entry *) calloc(1,sz)) == 0 )\r
564 {\r
565 fatal_internal("newEntry: out of memory for terminals\n");\r
566 exit(PCCTS_EXIT_FAILURE);\r
567 }\r
568 p->str = mystrdup(text);\r
569 \r
570 return(p);\r
571}\r
572\r
573/*\r
574 * add an element to a list.\r
575 *\r
576 * Any non-empty list has a sentinel node whose 'elem' pointer is really\r
577 * a pointer to the last element. (i.e. length(list) = #elemIn(list)+1).\r
578 * Elements are appended to the list.\r
579 */\r
580void\r
581#ifdef __USE_PROTOS\r
582list_add( ListNode **list, void *e )\r
583#else\r
584list_add( list, e )\r
585ListNode **list;\r
586void *e;\r
587#endif\r
588{\r
589 ListNode *p, *tail;\r
590 require(e!=NULL, "list_add: attempting to add NULL list element");\r
591\r
592 p = newListNode;\r
593 require(p!=NULL, "list_add: cannot alloc new list node");\r
594 p->elem = e;\r
595 if ( *list == NULL )\r
596 {\r
597 ListNode *sentinel = newListNode;\r
598 require(sentinel!=NULL, "list_add: cannot alloc sentinel node");\r
599 *list=sentinel;\r
600 sentinel->next = p;\r
601 sentinel->elem = (char *)p; /* set tail pointer */\r
602 }\r
603 else /* find end of list */\r
604 {\r
605 tail = (ListNode *) (*list)->elem; /* get tail pointer */\r
606 tail->next = p;\r
607 (*list)->elem = (char *) p; /* reset tail */\r
608 }\r
609}\r
610\r
611/* MR10 list_free() frees the ListNode elements in the list */\r
612/* MR10 if freeData then free the data elements of the list too */\r
613\r
614void\r
615#ifdef __USE_PROTOS\r
616list_free(ListNode **list,int freeData)\r
617#else\r
618list_free(list,freeData)\r
619 ListNode **list;\r
620 int freeData;\r
621#endif\r
622{\r
623 ListNode *p;\r
624 ListNode *next;\r
625\r
626 if (list == NULL) return;\r
627 if (*list == NULL) return;\r
628 for (p=*list; p != NULL; p=next) {\r
629 next=p->next;\r
630 if (freeData && p->elem != NULL) {\r
631 free( (char *) p->elem);\r
632 };\r
633 free( (char *) p);\r
634 };\r
635 *list=NULL;\r
636}\r
637\r
638void\r
639#ifdef __USE_PROTOS\r
640list_apply( ListNode *list, void (*f)(void *) )\r
641#else\r
642list_apply( list, f )\r
643ListNode *list;\r
644void (*f)();\r
645#endif\r
646{\r
647 ListNode *p;\r
648 require(f!=NULL, "list_apply: NULL function to apply");\r
649\r
650 if ( list == NULL ) return;\r
651 for (p = list->next; p!=NULL; p=p->next) (*f)( p->elem );\r
652}\r
653\r
654/* MR27 */\r
655\r
656#ifdef __USE_PROTOS\r
657int list_search_cstring(ListNode *list, char * cstring)\r
658#else\r
659int list_search_cstring(list, cstring)\r
660 ListNode * list;\r
661 char * cstring;\r
662#endif\r
663{\r
664 ListNode *p;\r
665 if (list == NULL ) return 0;\r
666 for (p = list->next; p!=NULL; p=p->next) {\r
667 if (p->elem == NULL) continue;\r
668 if (0 == strcmp((char *) p->elem , cstring)) return 1;\r
669 }\r
670 return 0;\r
671}\r
672\r
673 /* F O L L O W C y c l e S t u f f */\r
674 \r
675/* make a key based upon (rulename, computation, k value).\r
676 * Computation values are 'i'==FIRST, 'o'==FOLLOW.\r
677 */\r
678\r
679/* MR10 Make the key all characters so it can be read easily */\r
680/* MR10 by a simple dump program. Also, separates */\r
681/* MR10 'o' and 'i' from rule name */\r
682\r
683char *\r
684#ifdef __USE_PROTOS\r
685Fkey( char *rule, int computation, int k )\r
686#else\r
687Fkey( rule, computation, k )\r
688char *rule;\r
689int computation;\r
690int k;\r
691#endif\r
692{\r
693 static char key[MaxRuleName+2+2+1]; /* MR10 */\r
694 int i;\r
695 \r
696 if ( k > 99 ) /* MR10 */\r
697 fatal("k>99 is too big for this implementation of ANTLR!\n"); /* MR10 */\r
698 if ( (i=strlen(rule)) > MaxRuleName ) /* MR10 */\r
699 fatal( eMsgd("rule name > max of %d\n", MaxRuleName) ); /* MR10 */\r
700 strcpy(key,rule);\r
701\r
702/* MR10 */ key[i]='*';\r
703/* MR10 */ key[i+1] = (char) computation; /* MR20 G. Hobbelt */\r
704/* MR10 */ if (k < 10) {\r
705/* MR10 */ key[i+2] = (char) ( '0' + k);\r
706/* MR10 */ key[i+3] = '\0';\r
707/* MR10 */ } else {\r
708/* MR10 */ key[i+2] = (char) ( '0' + k/10);\r
709/* MR10 */ key[i+3] = (char) ( '0' + k % 10);\r
710/* MR10 */ key[i+4] = '\0';\r
711/* MR10 */ };\r
712\r
713 return key;\r
714}\r
715\r
716/* Push a rule onto the kth FOLLOW stack */\r
717void\r
718#ifdef __USE_PROTOS\r
719FoPush( char *rule, int k )\r
720#else\r
721FoPush( rule, k )\r
722char *rule;\r
723int k;\r
724#endif\r
725{\r
726 RuleEntry *r;\r
727 require(rule!=NULL, "FoPush: tried to push NULL rule");\r
728 require(k<=CLL_k, "FoPush: tried to access non-existent stack");\r
729\r
730 /*fprintf(stderr, "FoPush(%s)\n", rule);*/\r
731 r = (RuleEntry *) hash_get(Rname, rule);\r
732 if ( r == NULL ) {fatal_internal( eMsg1("rule %s must be defined but isn't", rule) );}\r
733 if ( FoStack[k] == NULL ) /* Does the kth stack exist yet? */\r
734 {\r
735 /*fprintf(stderr, "allocating FoStack\n");*/\r
736 FoStack[k] = (int *) calloc(FoStackSize, sizeof(int));\r
737 require(FoStack[k]!=NULL, "FoPush: cannot allocate FOLLOW stack\n");\r
738 }\r
739 if ( FoTOS[k] == NULL )\r
740 {\r
741 FoTOS[k]=FoStack[k];\r
742 *(FoTOS[k]) = r->rulenum;\r
743 }\r
744 else\r
745 {\r
746#ifdef MEMCHK\r
747 require(valid(FoStack[k]), "FoPush: invalid FoStack");\r
748#endif\r
749 if ( FoTOS[k] >= &(FoStack[k][FoStackSize-1]) )\r
750 fatal( eMsgd("exceeded max depth of FOLLOW recursion (%d)\n",\r
751 FoStackSize) );\r
752 require(FoTOS[k]>=FoStack[k],\r
753 eMsg1("FoPush: FoStack stack-ptr is playing out of its sandbox",\r
754 rule));\r
755 ++(FoTOS[k]);\r
756 *(FoTOS[k]) = r->rulenum;\r
757 }\r
758 {\r
759 /*\r
760**** int *p;\r
761**** fprintf(stderr, "FoStack[k=%d]:\n", k);\r
762**** for (p=FoStack[k]; p<=FoTOS[k]; p++)\r
763**** {\r
764**** fprintf(stderr, "\t%s\n", RulePtr[*p]->rname);\r
765**** }\r
766 */\r
767 }\r
768}\r
769\r
770/* Pop one rule off of the FOLLOW stack. TOS ptr is NULL if empty. */\r
771void\r
772#ifdef __USE_PROTOS\r
773FoPop( int k )\r
774#else\r
775FoPop( k )\r
776int k;\r
777#endif\r
778{\r
779 require(k<=CLL_k, "FoPop: tried to access non-existent stack");\r
780 /*fprintf(stderr, "FoPop\n");*/\r
781 require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),\r
782 "FoPop: FoStack stack-ptr is playing out of its sandbox");\r
783 if ( FoTOS[k] == FoStack[k] ) FoTOS[k] = NULL;\r
784 else (FoTOS[k])--;\r
785}\r
786\r
787/* Compute FOLLOW cycle.\r
788 * Mark all FOLLOW sets for rules in cycle as incomplete.\r
789 * Then, save cycle on the cycle list (Cycles) for later resolution.\r
790 * The Cycle is stored in the form:\r
791 * (head of cycle==croot, rest of rules in cycle==cyclicDep)\r
792 *\r
793 * e.g. (Fo means "FOLLOW of", "-->" means requires or depends on)\r
794 *\r
795 * Fo(x)-->Fo(a)-->Fo(b)-->Fo(c)-->Fo(x)\r
796 * ^----Infinite recursion (cycle)\r
797 *\r
798 * the cycle would be: x -> {a,b,c} or stored as (x,{a,b,c}). Fo(x) depends\r
799 * on the FOLLOW of a,b, and c. The root of a cycle is always complete after\r
800 * Fo(x) finishes. Fo(a,b,c) however are not. It turns out that all rules\r
801 * in a FOLLOW cycle have the same FOLLOW set.\r
802 */\r
803void\r
804#ifdef __USE_PROTOS\r
805RegisterCycle( char *rule, int k )\r
806#else\r
807RegisterCycle( rule, k )\r
808char *rule;\r
809int k;\r
810#endif\r
811{\r
812 CacheEntry *f;\r
813 Cycle *c;\r
814 int *p;\r
815 RuleEntry *r;\r
816 require(rule!=NULL, "RegisterCycle: tried to register NULL rule");\r
817 require(k<=CLL_k, "RegisterCycle: tried to access non-existent stack");\r
818\r
819 /*fprintf(stderr, "RegisterCycle(%s)\n", rule);*/\r
820 /* Find cycle start */\r
821 r = (RuleEntry *) hash_get(Rname, rule);\r
822 require(r!=NULL,eMsg1("rule %s must be defined but isn't", rule));\r
823 require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),\r
824 eMsg1("RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox",\r
825 rule));\r
826/*** if ( FoTOS[k]<FoStack[k]||FoTOS[k]>&(FoStack[k][FoStackSize-1]) )\r
827**** {\r
828**** fprintf(stderr, "RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox\n",\r
829**** rule);\r
830**** fprintf(stderr, "RegisterCycle: sp==0x%x out of bounds 0x%x...0x%x\n",\r
831**** FoTOS[k], FoStack[k], &(FoStack[k][FoStackSize-1]));\r
832**** exit(PCCTS_EXIT_FAILURE);\r
833**** }\r
834****/\r
835\r
836#ifdef MEMCHK\r
837 require(valid(FoStack[k]), "RegisterCycle: invalid FoStack");\r
838#endif\r
839 for (p=FoTOS[k]; *p != r->rulenum && p >= FoStack[k]; --p) {;}\r
840 require(p>=FoStack[k], "RegisterCycle: FoStack is screwed up beyond belief");\r
841 if ( p == FoTOS[k] ) return; /* don't worry about cycles to oneself */\r
842 \r
843 /* compute cyclic dependents (rules in cycle except head) */\r
844 c = newCycle;\r
845 require(c!=NULL, "RegisterCycle: couldn't alloc new cycle");\r
846 c->cyclicDep = empty;\r
847 c->croot = *p++; /* record root of cycle */\r
848 for (; p<=FoTOS[k]; p++)\r
849 {\r
850 /* Mark all dependent rules as incomplete */\r
851 f = (CacheEntry *) hash_get(Fcache, Fkey(RulePtr[*p]->rname,'o',k));\r
852 if ( f==NULL )\r
853 {\r
854 f = newCacheEntry( Fkey(RulePtr[*p]->rname,'o',k) );\r
855 hash_add(Fcache, Fkey(RulePtr[*p]->rname,'o',k), (Entry *)f);\r
856 }\r
857 f->incomplete = TRUE;\r
858 \r
859 set_orel(*p, &(c->cyclicDep)); /* mark rule as dependent of croot */\r
860 }\r
861 list_add(&(Cycles[k]), (void *)c);\r
862}\r
863\r
864/* make all rules in cycle complete\r
865 *\r
866 * while ( some set has changed ) do\r
867 * for each cycle do\r
868 * if degree of FOLLOW set for croot > old degree then\r
869 * update all FOLLOW sets for rules in cyclic dependency\r
870 * change = TRUE\r
871 * endif\r
872 * endfor\r
873 * endwhile\r
874 */\r
875void\r
876#ifdef __USE_PROTOS\r
877ResolveFoCycles( int k )\r
878#else\r
879ResolveFoCycles( k )\r
880int k;\r
881#endif\r
882{\r
883 ListNode *p, *q;\r
884 Cycle *c;\r
885 int changed = 1;\r
886 CacheEntry *f,*g;\r
887 int r;\r
888/* int i; */ /* MR10 not useful */\r
889 unsigned d;\r
890\r
891 unsigned *cursor; /* MR10 */\r
892 unsigned *origin; /* MR10 */\r
893 \r
894 /*fprintf(stderr, "Resolving following cycles for %d\n", k);*/\r
895 while ( changed )\r
896 {\r
897 changed = 0;\r
898/* MR10 i = 0; */\r
899 for (p = Cycles[k]->next; p!=NULL; p=p->next)\r
900 {\r
901 c = (Cycle *) p->elem;\r
902 /*fprintf(stderr, "cycle %d: %s -->", i++, RulePtr[c->croot]->rname);*/\r
903 /*s_fprT(stderr, c->cyclicDep);*/\r
904 /*fprintf(stderr, "\n");*/\r
905 f = (CacheEntry *)\r
906 hash_get(Fcache, Fkey(RulePtr[c->croot]->rname,'o',k));\r
907 require(f!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[c->croot]->rname) );\r
908 if ( (d=set_deg(f->fset)) > c->deg )\r
909 {\r
910 /*fprintf(stderr, "Fo(%s) has changed\n", RulePtr[c->croot]->rname);*/\r
911 changed = 1;\r
912 c->deg = d; /* update cycle FOLLOW set degree */\r
913\r
914/* MR10 */ origin=set_pdq(c->cyclicDep);\r
915/* MR10 */ for (cursor=origin; *cursor != nil; cursor++) {\r
916/* MR10 */ r=*cursor;\r
917\r
918/******** while ( !set_nil(c->cyclicDep) ) { *****/\r
919/******** r = set_int(c->cyclicDep); *****/\r
920/******** set_rm(r, c->cyclicDep); *****/\r
921\r
922 /*fprintf(stderr, "updating Fo(%s)\n", RulePtr[r]->rname);*/\r
923 g = (CacheEntry *)\r
924 hash_get(Fcache, Fkey(RulePtr[r]->rname,'o',k));\r
925 require(g!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[r]->rname) );\r
926 set_orin(&(g->fset), f->fset);\r
927 g->incomplete = FALSE;\r
928 }\r
929/* MR10 */ free( (char *) origin);\r
930/* MR10 */ origin=NULL;\r
931 }\r
932 }\r
933/* MR10 - this if statement appears to be meaningless since i is always 0 */\r
934/* MR10 if ( i == 1 ) changed = 0; */ /* if only 1 cycle, no need to repeat */\r
935 }\r
936 /* kill Cycle list */\r
937 for (q = Cycles[k]->next; q != NULL; q=p)\r
938 {\r
939 p = q->next;\r
940 set_free( ((Cycle *)q->elem)->cyclicDep );\r
941 free((char *)q);\r
942 }\r
943 free( (char *)Cycles[k] );\r
944 Cycles[k] = NULL;\r
945}\r
946\r
947\r
948 /* P r i n t i n g S y n t a x D i a g r a m s */\r
949\r
950static void\r
951#ifdef __USE_PROTOS\r
952pBlk( Junction *q, int btype )\r
953#else\r
954pBlk( q, btype )\r
955Junction *q;\r
956int btype;\r
957#endif\r
958{\r
959 int k,a;\r
960 Junction *alt, *p;\r
961\r
962 q->end->pvisited = TRUE;\r
963 if ( btype == aLoopBegin )\r
964 {\r
965 require(q->p2!=NULL, "pBlk: invalid ()* block");\r
966 PRINT(q->p1);\r
967 alt = (Junction *)q->p2;\r
968 PRINT(alt->p1);\r
969 if ( PrintAnnotate )\r
970 {\r
971 printf(" /* Opt ");\r
972 k = 1;\r
973 while ( !set_nil(alt->fset[k]) )\r
974 {\r
975 s_fprT(stdout, alt->fset[k]);\r
976 if ( k++ == CLL_k ) break;\r
977 if ( !set_nil(alt->fset[k]) ) printf(", ");\r
978 }\r
979 printf(" */\n");\r
980 }\r
981 return;\r
982 }\r
983 for (a=1,alt=q; alt != NULL; alt= (Junction *) alt->p2, a++)\r
984 {\r
985 if ( alt->p1 != NULL ) PRINT(alt->p1);\r
986 if ( PrintAnnotate )\r
987 {\r
988 printf( " /* [%d] ", alt->altnum);\r
989 k = 1;\r
990 while ( !set_nil(alt->fset[k]) )\r
991 {\r
992 s_fprT(stdout, alt->fset[k]);\r
993 if ( k++ == CLL_k ) break;\r
994 if ( !set_nil(alt->fset[k]) ) printf(", ");\r
995 }\r
996 if ( alt->p2 == NULL && btype == aOptBlk )\r
997 printf( " (optional branch) */\n");\r
998 else printf( " */\n");\r
999 }\r
1000\r
1001 /* ignore implied empty alt of Plus blocks */\r
1002 if ( alt->p2 != NULL && ((Junction *)alt->p2)->ignore ) break;\r
1003\r
1004 if ( alt->p2 != NULL && !(((Junction *)alt->p2)->p2==NULL && btype == aOptBlk) )\r
1005 {\r
1006 if ( pLevel == 1 )\r
1007 {\r
1008 printf("\n");\r
1009 if ( a+1==pAlt1 || a+1==pAlt2 ) printf("=>");\r
1010 printf("\t");\r
1011 }\r
1012 else printf(" ");\r
1013 printf("|");\r
1014 if ( pLevel == 1 )\r
1015 {\r
1016 p = (Junction *) ((Junction *)alt->p2)->p1;\r
1017 while ( p!=NULL )\r
1018 {\r
1019 if ( p->ntype==nAction )\r
1020 {\r
1021 p=(Junction *)((ActionNode *)p)->next;\r
1022 continue;\r
1023 }\r
1024 if ( p->ntype!=nJunction )\r
1025 {\r
1026 break;\r
1027 }\r
1028 if ( p->jtype==EndBlk || p->jtype==EndRule )\r
1029 {\r
1030 p = NULL;\r
1031 break;\r
1032 }\r
1033 p = (Junction *)p->p1;\r
1034 }\r
1035 if ( p==NULL ) printf("\n\t"); /* Empty alt? */\r
1036 }\r
1037 }\r
1038 }\r
1039 q->end->pvisited = FALSE;\r
1040}\r
1041\r
1042/* How to print out a junction */\r
1043void\r
1044#ifdef __USE_PROTOS\r
1045pJunc( Junction *q )\r
1046#else\r
1047pJunc( q )\r
1048Junction *q;\r
1049#endif\r
1050{\r
1051 int dum_k;\r
1052 int doing_rule;\r
1053 require(q!=NULL, "pJunc: NULL node");\r
1054 require(q->ntype==nJunction, "pJunc: not junction");\r
1055 \r
1056 if ( q->pvisited == TRUE ) return;\r
1057 q->pvisited = TRUE;\r
1058 switch ( q->jtype )\r
1059 {\r
1060 case aSubBlk :\r
1061 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);\r
1062 if ( q->end->p1 != NULL && ((Junction *)q->end->p1)->ntype==nJunction &&\r
1063 ((Junction *)q->end->p1)->jtype == EndRule ) doing_rule = 1;\r
1064 else doing_rule = 0;\r
1065 pLevel++;\r
1066 if ( pLevel==1 )\r
1067 {\r
1068 if ( pAlt1==1 ) printf("=>");\r
1069 printf("\t");\r
1070 }\r
1071 else printf(" ");\r
1072 if ( doing_rule )\r
1073 {\r
1074 if ( pLevel==1 ) printf(" ");\r
1075 pBlk(q,q->jtype);\r
1076 }\r
1077 else {\r
1078 printf("(");\r
1079 if ( pLevel==1 ) printf(" ");\r
1080 pBlk(q,q->jtype);\r
1081 if ( pLevel>1 ) printf(" ");\r
1082 printf(")");\r
1083 }\r
1084 if ( q->guess ) printf("?");\r
1085 pLevel--;\r
1086 if ( PrintAnnotate ) freeBlkFsets(q);\r
1087 if ( q->end->p1 != NULL ) PRINT(q->end->p1);\r
1088 break;\r
1089 case aOptBlk :\r
1090 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);\r
1091 pLevel++;\r
1092 if ( pLevel==1 )\r
1093 {\r
1094 if ( pAlt1==1 ) printf("=>");\r
1095 printf("\t");\r
1096 }\r
1097 else printf(" ");\r
1098 printf("{");\r
1099 if ( pLevel==1 ) printf(" ");\r
1100 pBlk(q,q->jtype);\r
1101 if ( pLevel>1 ) printf(" ");\r
1102 else printf("\n\t");\r
1103 printf("}");\r
1104 pLevel--;\r
1105 if ( PrintAnnotate ) freeBlkFsets(q);\r
1106 if ( q->end->p1 != NULL ) PRINT(q->end->p1);\r
1107 break;\r
1108 case aLoopBegin :\r
1109 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);\r
1110 pLevel++;\r
1111 if ( pLevel==1 )\r
1112 {\r
1113 if ( pAlt1==1 ) printf("=>");\r
1114 printf("\t");\r
1115 }\r
1116 else printf(" ");\r
1117 printf("(");\r
1118 if ( pLevel==1 ) printf(" ");\r
1119 pBlk(q,q->jtype);\r
1120 if ( pLevel>1 ) printf(" ");\r
1121 else printf("\n\t");\r
1122 printf(")*");\r
1123 pLevel--;\r
1124 if ( PrintAnnotate ) freeBlkFsets(q);\r
1125 if ( q->end->p1 != NULL ) PRINT(q->end->p1);\r
1126 break;\r
1127 case aLoopBlk :\r
1128 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);\r
1129 pBlk(q,q->jtype);\r
1130 if ( PrintAnnotate ) freeBlkFsets(q);\r
1131 break;\r
1132 case aPlusBlk :\r
1133 if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);\r
1134 pLevel++;\r
1135 if ( pLevel==1 )\r
1136 {\r
1137 if ( pAlt1==1 ) printf("=>");\r
1138 printf("\t");\r
1139 }\r
1140 else printf(" ");\r
1141 printf("(");\r
1142 if ( pLevel==1 ) printf(" ");\r
1143 pBlk(q,q->jtype);\r
1144 if ( pLevel>1 ) printf(" ");\r
1145 printf(")+");\r
1146 pLevel--;\r
1147 if ( PrintAnnotate ) freeBlkFsets(q);\r
1148 if ( q->end->p1 != NULL ) PRINT(q->end->p1);\r
1149 break;\r
1150 case EndBlk :\r
1151 break;\r
1152 case RuleBlk :\r
1153 printf( "\n%s :\n", q->rname);\r
1154 PRINT(q->p1);\r
1155 if ( q->p2 != NULL ) PRINT(q->p2);\r
1156 break;\r
1157 case Generic :\r
1158 if ( q->p1 != NULL ) PRINT(q->p1);\r
1159 q->pvisited = FALSE;\r
1160 if ( q->p2 != NULL ) PRINT(q->p2);\r
1161 break;\r
1162 case EndRule :\r
1163 printf( "\n\t;\n");\r
1164 break;\r
1165 }\r
1166 q->pvisited = FALSE;\r
1167}\r
1168\r
1169/* How to print out a rule reference node */\r
1170void\r
1171#ifdef __USE_PROTOS\r
1172pRuleRef( RuleRefNode *p )\r
1173#else\r
1174pRuleRef( p )\r
1175RuleRefNode *p;\r
1176#endif\r
1177{\r
1178 require(p!=NULL, "pRuleRef: NULL node");\r
1179 require(p->ntype==nRuleRef, "pRuleRef: not rule ref node");\r
1180 \r
1181 printf( " %s", p->text);\r
1182 PRINT(p->next);\r
1183}\r
1184\r
1185/* How to print out a terminal node */\r
1186void\r
1187#ifdef __USE_PROTOS\r
1188pToken( TokNode *p )\r
1189#else\r
1190pToken( p )\r
1191TokNode *p;\r
1192#endif\r
1193{\r
1194 require(p!=NULL, "pToken: NULL node");\r
1195 require(p->ntype==nToken, "pToken: not token node");\r
1196\r
1197 if ( p->wild_card ) printf(" .");\r
1198 printf( " %s", TerminalString(p->token));\r
1199 PRINT(p->next);\r
1200}\r
1201\r
1202/* How to print out a terminal node */\r
1203void\r
1204#ifdef __USE_PROTOS\r
1205pAction( ActionNode *p )\r
1206#else\r
1207pAction( p )\r
1208ActionNode *p;\r
1209#endif\r
1210{\r
1211 require(p!=NULL, "pAction: NULL node");\r
1212 require(p->ntype==nAction, "pAction: not action node");\r
1213 \r
1214 PRINT(p->next);\r
1215}\r
1216\r
1217 /* F i l l F o l l o w L i s t s */\r
1218\r
1219/*\r
1220 * Search all rules for all rule reference nodes, q to rule, r.\r
1221 * Add q->next to follow list dangling off of rule r.\r
1222 * i.e.\r
1223 *\r
1224 * r: -o-R-o-->o--> Ptr to node following rule r in another rule\r
1225 * |\r
1226 * o--> Ptr to node following another reference to r.\r
1227 *\r
1228 * This is the data structure employed to avoid FOLLOW set computation. We\r
1229 * simply compute the FIRST (reach) of the EndRule Node which follows the\r
1230 * list found at the end of all rules which are referenced elsewhere. Rules\r
1231 * not invoked by other rules have no follow list (r->end->p1==NULL).\r
1232 * Generally, only start symbols are not invoked by another rule.\r
1233 *\r
1234 * Note that this mechanism also gives a free cross-reference mechanism.\r
1235 *\r
1236 * The entire syntax diagram is layed out like this:\r
1237 *\r
1238 * SynDiag\r
1239 * |\r
1240 * v\r
1241 * o-->R1--o\r
1242 * |\r
1243 * o-->R2--o\r
1244 * |\r
1245 * ...\r
1246 * |\r
1247 * o-->Rn--o\r
1248 *\r
1249 */\r
1250void\r
1251#ifdef __USE_PROTOS\r
1252FoLink( Node *p )\r
1253#else\r
1254FoLink( p )\r
1255Node *p;\r
1256#endif\r
1257{\r
1258 RuleEntry *q;\r
1259 Junction *j = (Junction *) p;\r
1260 RuleRefNode *r = (RuleRefNode *) p;\r
1261\r
1262 if ( p==NULL ) return;\r
1263 require(p->ntype>=1 && p->ntype<=NumNodeTypes,\r
1264 eMsgd("FoLink: invalid diagram node: ntype==%d",p->ntype));\r
1265 switch ( p->ntype )\r
1266 {\r
1267 case nJunction :\r
1268 if ( j->fvisited ) return;\r
1269 if ( j->jtype == EndRule ) return;\r
1270 j->fvisited = TRUE;\r
1271 FoLink( j->p1 );\r
1272 FoLink( j->p2 );\r
1273/* MR14 */\r
1274/* MR14 */ /* Need to determine whether the guess block is an */\r
1275/* MR14 */ /* of the form (alpha)? beta before follow sets are */\r
1276/* MR14 */ /* computed. This is necessary to solve problem */\r
1277/* MR14 */ /* of doing follow on the alpha of an (alpha)? beta block. */\r
1278/* MR14 */\r
1279/* MR14 */ /* This is performed by analysis_point as a side-effect. */\r
1280/* MR14 */\r
1281/* MR14 */\r
1282/* MR14 */ if (j->jtype == aSubBlk && j->guess) {\r
1283/* MR14 */ Junction *ignore;\r
1284/* MR14 */ ignore=analysis_point(j);\r
1285/* MR14 */ }\r
1286/* MR14 */\r
1287 return;\r
1288 case nRuleRef :\r
1289 if ( r->linked ) return;\r
1290 q = (RuleEntry *) hash_get(Rname, r->text);\r
1291 if ( q == NULL )\r
1292 {\r
1293 warnFL( eMsg1("rule %s not defined",r->text), FileStr[r->file], r->line );\r
1294 }\r
1295 else\r
1296 {\r
1297 if ( r->parms!=NULL && RulePtr[q->rulenum]->pdecl==NULL )\r
1298 {\r
1299 warnFL( eMsg1("rule %s accepts no parameter(s)", r->text),\r
1300 FileStr[r->file], r->line );\r
1301 }\r
1302 if ( r->parms==NULL && RulePtr[q->rulenum]->pdecl!=NULL )\r
1303 {\r
1304 warnFL( eMsg1("rule %s requires parameter(s)", r->text),\r
1305 FileStr[r->file], r->line );\r
1306 }\r
1307 if ( r->assign!=NULL && RulePtr[q->rulenum]->ret==NULL )\r
1308 {\r
1309 warnFL( eMsg1("rule %s yields no return value(s)", r->text),\r
1310 FileStr[r->file], r->line );\r
1311 }\r
1312 if ( r->assign==NULL && RulePtr[q->rulenum]->ret!=NULL )\r
1313 {\r
1314 warnFL( eMsg1("rule %s returns a value(s)", r->text),\r
1315 FileStr[r->file], r->line );\r
1316 }\r
1317 if ( !r->linked )\r
1318 {\r
1319 addFoLink( r->next, r->rname, RulePtr[q->rulenum] );\r
1320 r->linked = TRUE;\r
1321 }\r
1322 }\r
1323 FoLink( r->next );\r
1324 return;\r
1325 case nToken :\r
1326 FoLink( ((TokNode *)p)->next );\r
1327 return;\r
1328 case nAction :\r
1329 FoLink( ((ActionNode *)p)->next );\r
1330 return;\r
1331 default :\r
1332 fatal_internal("invalid node type");\r
1333 }\r
1334}\r
1335\r
1336/*\r
1337 * Add a reference to the end of a rule.\r
1338 *\r
1339 * 'r' points to the RuleBlk node in a rule. r->end points to the last node\r
1340 * (EndRule jtype) in a rule.\r
1341 *\r
1342 * Initial:\r
1343 * r->end --> o\r
1344 *\r
1345 * After:\r
1346 * r->end --> o-->o--> Ptr to node following rule r in another rule\r
1347 * |\r
1348 * o--> Ptr to node following another reference to r.\r
1349 *\r
1350 * Note that the links are added to the head of the list so that r->end->p1\r
1351 * always points to the most recently added follow-link. At the end, it should\r
1352 * point to the last reference found in the grammar (starting from the 1st rule).\r
1353 */\r
1354void\r
1355#ifdef __USE_PROTOS\r
1356addFoLink( Node *p, char *rname, Junction *r )\r
1357#else\r
1358addFoLink( p, rname, r )\r
1359Node *p;\r
1360char *rname;\r
1361Junction *r;\r
1362#endif\r
1363{\r
1364 Junction *j;\r
1365 require(r!=NULL, "addFoLink: incorrect rule graph");\r
1366 require(r->end!=NULL, "addFoLink: incorrect rule graph");\r
1367 require(r->end->jtype==EndRule, "addFoLink: incorrect rule graph");\r
1368 require(p!=NULL, "addFoLink: NULL FOLLOW link");\r
1369\r
1370 j = newJunction();\r
1371 j->rname = rname; /* rname on follow links point to target rule */\r
1372 j->p1 = p; /* link to other rule */\r
1373 j->p2 = (Node *) r->end->p1;/* point to head of list */\r
1374 r->end->p1 = (Node *) j; /* reset head to point to new node */\r
1375}\r
1376\r
1377void\r
1378#ifdef __USE_PROTOS\r
1379GenCrossRef( Junction *p )\r
1380#else\r
1381GenCrossRef( p )\r
1382Junction *p;\r
1383#endif\r
1384{\r
1385 set a;\r
1386 Junction *j;\r
1387 RuleEntry *q;\r
1388 unsigned e;\r
1389 require(p!=NULL, "GenCrossRef: why are you passing me a null grammar?");\r
1390\r
1391 printf("Cross Reference:\n\n");\r
1392 a = empty;\r
1393 for (; p!=NULL; p = (Junction *)p->p2)\r
1394 {\r
1395 printf("Rule %20s referenced by {", p->rname);\r
1396 /* make a set of rules for uniqueness */\r
1397 for (j = (Junction *)(p->end)->p1; j!=NULL; j = (Junction *)j->p2)\r
1398 {\r
1399 q = (RuleEntry *) hash_get(Rname, j->rname);\r
1400 require(q!=NULL, "GenCrossRef: FoLinks are screwed up");\r
1401 set_orel(q->rulenum, &a);\r
1402 }\r
1403 for (; !set_nil(a); set_rm(e, a))\r
1404 {\r
1405 e = set_int(a);\r
1406 printf(" %s", RulePtr[e]->rname);\r
1407 }\r
1408 printf(" }\n");\r
1409 }\r
1410 set_free( a );\r
1411}\r
1412\r
1413/*\r
1414 The single argument is a pointer to the start of an element of a\r
1415 C++ style function prototypet list. Given a pointer to the start of\r
1416 an formal we must locate the comma (or the end of the string)\r
1417 and locate the datatype, formal name, and initial value expression.\r
1418\r
1419 The function returns a pointer to the character following the comma\r
1420 which terminates the formal declaration, or a pointer to the end of\r
1421 the string if none was found.\r
1422\r
1423 I thought we were parsing specialists, how come I'm doing this by\r
1424 hand written code ?\r
1425\r
1426 Examples of input:\r
1427 \r
1428 Foo f,\r
1429 Foo f = Foo(1),\r
1430 Foo f = Foo(1,2),\r
1431 Foo f = &farray[1,2],\r
1432 Foo f = ",",\r
1433 Foo f = ',',\r
1434 TFoo<int,char> f = TFoo<int,char>(1,2),\r
1435\r
1436 A non-zero value for nesting indicates a problem matching '(' and ')',\r
1437 '[' and ']', '<' and '>', '{' and '}', or improperly terminated string\r
1438 or character literal.\r
1439\r
1440*/\r
1441\r
1442\r
1443/*\r
1444 * Don't care if it is a valid string literal or not, just find the end\r
1445 * Start with pointer to leading "\""\r
1446 */\r
1447\r
1448#ifdef __USE_PROTOS\r
1449char * skipStringLiteral(char *pCurrent)\r
1450#else\r
1451char * skipStringLiteral(pCurrent)\r
1452char *pCurrent;\r
1453#endif\r
1454{\r
1455 char *p = pCurrent;\r
1456 if (*p == 0) return p;\r
1457 require (*p == '\"', "skipStringLiteral")\r
1458 p++;\r
1459 for (p = p; *p != 0; p++) {\r
1460 if (*p == '\\') {\r
1461 p++;\r
1462 if (*p == 0) break;\r
1463 p++;\r
1464 }\r
1465 if (*p == '\"') {\r
1466 p++;\r
1467 break;\r
1468 }\r
1469 }\r
1470 return p;\r
1471}\r
1472\r
1473/*\r
1474 * Don't care if it is a valid character literal or not, just find the end\r
1475 * Start with pointer to leading "'"\r
1476 */\r
1477\r
1478#ifdef __USE_PROTOS\r
1479char * skipCharLiteral(char *pStart)\r
1480#else\r
1481char * skipCharLiteral(pStart)\r
1482 char *pStart;\r
1483#endif\r
1484{\r
1485 char *p = pStart;\r
1486 if (*p == 0) return p;\r
1487 require (*p == '\'', "skipCharLiteral")\r
1488 p++;\r
1489 for (p = p; *p != 0; p++) {\r
1490 if (*p == '\\') {\r
1491 p++;\r
1492 if (*p == 0) break;\r
1493 p++;\r
1494 }\r
1495 if (*p == '\'') {\r
1496 p++;\r
1497 break;\r
1498 }\r
1499 }\r
1500 return p;\r
1501}\r
1502\r
1503#ifdef __USE_PROTOS\r
1504char * skipSpaces(char *pStart)\r
1505#else\r
1506char * skipSpaces(pStart)\r
1507char * pStart;\r
1508#endif\r
1509{\r
1510 char *p = pStart;\r
1511 while (*p != 0 && isspace(*p)) p++;\r
1512 return p;\r
1513}\r
1514\r
1515#ifdef __USE_PROTOS\r
1516char * skipToSeparatorOrEqualSign(char *pStart, int *pNest)\r
1517#else\r
1518char * skipToSeparatorOrEqualSign(pStart, pNest)\r
1519char *pStart;\r
1520int *pNest;\r
1521#endif\r
1522{\r
1523 char *p = pStart;\r
1524 \r
1525 int nest = 0;\r
1526\r
1527 *pNest = (-1);\r
1528\r
1529 while (*p != 0) {\r
1530 switch (*p) {\r
1531\r
1532 case '(' :\r
1533 case '[' :\r
1534 case '<' :\r
1535 case '{' :\r
1536 nest++;\r
1537 p++;\r
1538 break;\r
1539\r
1540 case ')' :\r
1541 case ']' :\r
1542 case '>' :\r
1543 case '}' :\r
1544 nest--;\r
1545 p++;\r
1546 break;\r
1547 \r
1548 case '"' :\r
1549 p = skipStringLiteral(p);\r
1550 break;\r
1551 \r
1552 case '\'' :\r
1553 p = skipCharLiteral(p);\r
1554 break;\r
1555\r
1556 case '\\':\r
1557 p++;\r
1558 if (*p == 0) goto EXIT;\r
1559 p++;\r
1560 break;\r
1561\r
1562 case ',':\r
1563 case '=':\r
1564 if (nest == 0) goto EXIT;\r
1565 p++;\r
1566 break;\r
1567\r
1568 default:\r
1569 p++;\r
1570 }\r
1571 }\r
1572EXIT:\r
1573 *pNest = nest;\r
1574 return p;\r
1575}\r
1576\r
1577#ifdef __USE_PROTOS\r
1578char * skipToSeparator(char *pStart, int *pNest)\r
1579#else\r
1580char * skipToSeparator(pStart, pNest)\r
1581char *pStart;\r
1582int *pNest;\r
1583#endif\r
1584{\r
1585 char * p = pStart;\r
1586 for ( ; ; ) {\r
1587 p = skipToSeparatorOrEqualSign(p, pNest);\r
1588 if (*pNest != 0) return p;\r
1589 if (*p == ',') return p;\r
1590 if (*p == 0) return p;\r
1591 p++;\r
1592 }\r
1593}\r
1594\r
1595/* skip to just past the "=" separating the declaration from the initialization value */\r
1596\r
1597#ifdef __USE_PROTOS\r
1598char * getInitializer(char *pStart)\r
1599#else\r
1600char * getInitializer(pStart)\r
1601char * pStart;\r
1602#endif\r
1603{\r
1604 char *p;\r
1605 char *pDataType;\r
1606 char *pSymbol;\r
1607 char *pEqualSign;\r
1608 char *pValue;\r
1609 char *pSeparator;\r
1610 int nest = 0;\r
1611\r
1612 require(pStart!=NULL, "getInitializer: invalid string"); \r
1613\r
1614 p = endFormal(pStart,\r
1615 &pDataType,\r
1616 &pSymbol,\r
1617 &pEqualSign,\r
1618 &pValue,\r
1619 &pSeparator,\r
1620 &nest);\r
1621 if (nest != 0) return NULL;\r
1622 if (pEqualSign == NULL) return NULL;\r
1623 if (pValue == NULL) return NULL;\r
1624 return strBetween(pValue, NULL, pSeparator);\r
1625}\r
1626\r
1627/*\r
1628 Examines the string from pStart to pEnd-1.\r
1629 If the string has 0 length or is entirely white space\r
1630 returns 1. Otherwise 0.\r
1631*/\r
1632\r
1633#ifdef __USE_PROTOS\r
1634int isWhiteString(const char *pStart, const char *pEnd)\r
1635#else\r
1636int isWhiteString(pStart, pEnd)\r
1637const char *pStart;\r
1638const char *pEnd;\r
1639#endif\r
1640{\r
1641 const char *p;\r
1642 for (p = pStart; p < pEnd; p++) {\r
1643 if (! isspace(*p)) return 0;\r
1644 }\r
1645 return 1;\r
1646}\r
1647\r
1648/*\r
1649 This replaces HasComma() which couldn't distinguish\r
1650\r
1651 foo ["a,b"]\r
1652\r
1653 from:\r
1654\r
1655 foo[a,b]\r
1656\r
1657*/\r
1658\r
1659#ifdef __USE_PROTOS\r
1660int hasMultipleOperands(char *pStart)\r
1661#else\r
1662int hasMultipleOperands(pStart)\r
1663char *pStart;\r
1664#endif\r
1665{\r
1666 char *p = pStart;\r
1667 int nest = 0;\r
1668\r
1669 p = skipSpaces(p);\r
1670 if (*p == 0) return 0;\r
1671 p = skipToSeparator(p, &nest);\r
1672 if (nest == 0 && *p == ',') return 1;\r
1673 return 0;\r
1674}\r
1675\r
1676\r
1677#define MAX_STR_BETWEEN_WORK_AREA 1000\r
1678\r
1679static char strBetweenWorkArea[MAX_STR_BETWEEN_WORK_AREA];\r
1680\r
1681\r
1682/*\r
1683 strBetween(pStart, pNext, pStop)\r
1684\r
1685 Creates a null terminated string by copying the text between two pointers\r
1686 to a work area. The start of the string is pStart. The end of the string\r
1687 is the character before pNext, or if pNext is null then the character before\r
1688 pStop. Trailing spaces are not included in the copy operation.\r
1689 \r
1690 This is used when a string contains several parts. The pNext part may be\r
1691 optional. The pStop will stop the scan when the optional part is not present\r
1692 (is a null pointer).\r
1693*/\r
1694\r
1695#ifdef __USE_PROTOS\r
1696char *strBetween(char *pStart, char *pNext, char *pStop)\r
1697#else\r
1698char *strBetween(pStart, pNext, pStop)\r
1699char *pStart;\r
1700char *pNext;\r
1701char *pStop;\r
1702#endif\r
1703{\r
1704 char *p;\r
1705 char *q = strBetweenWorkArea;\r
1706 const char *pEnd;\r
1707\r
1708 pEnd = (pNext != NULL) ? pNext : pStop;\r
1709\r
1710 require (pEnd != NULL, "pEnd == NULL");\r
1711 require (pEnd >= pStart, "pEnd < pStart");\r
1712 for (pEnd--; pEnd >= pStart; pEnd--) { /* MR31 */\r
1713 if (! isspace(*pEnd)) break;\r
1714 }\r
1715 for (p = pStart;\r
1716 p <= pEnd && q < &strBetweenWorkArea[MAX_STR_BETWEEN_WORK_AREA-2];\r
1717 p++, q++) {\r
1718 *q = *p;\r
1719 }\r
1720 *q = 0;\r
1721 return strBetweenWorkArea;\r
1722}\r
1723\r
1724/*\r
1725 function Returns pointer to character following separator at\r
1726 value which to continue search for next formal. If at the\r
1727 end of the string a pointer to the null byte at the\r
1728 end of the string is returned.\r
1729\r
1730 pStart Pointer to the starting position of the formal list\r
1731\r
1732 This may be the middle of a longer string, for example\r
1733 when looking for the end of formal #3 starting from\r
1734 the middle of the complete formal list.\r
1735\r
1736 ppDataType Returns a pointer to the start of the data type in the\r
1737 formal. Example: pointer to "Foo".\r
1738\r
1739 ppSymbol Returns a pointer to the start of the formal symbol.\r
1740 Example: pointer to "f".\r
1741\r
1742 ppEqualSign Returns a pointer to the equal sign separating the\r
1743 formal symbol from the initial value. If there is \r
1744 no "=" then this will be NULL.\r
1745\r
1746 ppValue Returns a pointer to the initial value part of the\r
1747 formal declaration. Example: pointer to "&farray[1,2]"\r
1748\r
1749 ppSeparator Returns a pointer to the character which terminated the\r
1750 scan. This should be a pointer to a comma or a null\r
1751 byte which terminates the string.\r
1752\r
1753 pNest Returns the nesting level when a separator was found.\r
1754 This is non-zero for any kind of error. This is zero\r
1755 for a successful parse of this portion of the formal\r
1756 list.\r
1757\r
1758*/ \r
1759 \r
1760#ifdef __USE_PROTOS\r
1761char * endFormal(char *pStart,\r
1762 char **ppDataType,\r
1763 char **ppSymbol,\r
1764 char **ppEqualSign,\r
1765 char **ppValue,\r
1766 char **ppSeparator,\r
1767 int *pNest)\r
1768#else\r
1769char * endFormal(pStart,\r
1770 ppDataType,\r
1771 ppSymbol,\r
1772 ppEqualSign,\r
1773 ppValue,\r
1774 ppSeparator,\r
1775 pNest)\r
1776char *pStart;\r
1777char **ppDataType;\r
1778char **ppSymbol;\r
1779char **ppEqualSign;\r
1780char **ppValue;\r
1781char **ppSeparator;\r
1782int *pNest;\r
1783\r
1784#endif\r
1785{\r
1786 char *p = pStart;\r
1787 char *q;\r
1788\r
1789 *ppDataType = NULL;\r
1790 *ppSymbol = NULL;\r
1791 *ppEqualSign = NULL;\r
1792 *ppValue = NULL;\r
1793 *ppSeparator = NULL;\r
1794\r
1795 *pNest = 0;\r
1796\r
1797 /* The first non-blank is the start of the datatype */\r
1798\r
1799 p = skipSpaces(p);\r
1800 if (*p == 0) goto EXIT;\r
1801 *ppDataType = p;\r
1802\r
1803 /* We are not looking for the symbol, we are looking\r
1804 for the separator that follows the symbol. Then\r
1805 we'll back up.\r
1806 \r
1807 Search for the ',' or '=" or null terminator.\r
1808 */\r
1809\r
1810 p = skipToSeparatorOrEqualSign(p, pNest);\r
1811\r
1812 if (*pNest != 0) goto EXIT;\r
1813\r
1814 /*\r
1815 Work backwards to find start of symbol\r
1816 Skip spaces between the end of symbol and separator\r
1817 Assume that there are no spaces in the formal, but\r
1818 there is a space preceding the formal\r
1819 */\r
1820\r
1821 for (q = &p[-1]; q >= *ppDataType; q--) {\r
1822 if (! isspace(*q)) break;\r
1823 }\r
1824 if (q < *ppDataType) goto EXIT;\r
1825\r
1826 /*\r
1827 MR26 Handle things like: IIR_Bool (IIR_Decl::*constraint)()\r
1828 Backup until we hit the end of a symbol string, then find the\r
1829 start of the symbol string. This wont' work for functions\r
1830 with prototypes, but works for the most common cases. For\r
1831 others, use typedef names.\r
1832 */\r
1833\r
1834/* MR26 */ for (q = q; q >= *ppDataType; q--) {\r
1835/* MR26 */ if (isalpha(*q) || isdigit(*q) || *q == '_' || *q == '$') break;\r
1836/* MR26 */ }\r
1837/* MR26 */ if (q < *ppDataType) goto EXIT;\r
1838\r
1839 for (q = q; q >= *ppDataType; q--) {\r
1840 if ( ! (isalpha(*q) || isdigit(*q) || *q == '_' || *q == '$')) break;\r
1841 }\r
1842\r
1843 *ppSymbol = &q[1];\r
1844\r
1845 if (*p == ',' || *p == 0) {\r
1846 *ppSeparator = p;\r
1847 goto EXIT;\r
1848 }\r
1849\r
1850 *ppEqualSign = p;\r
1851 p = skipSpaces(++p);\r
1852 *ppValue = p;\r
1853 if (*p == 0) goto EXIT;\r
1854\r
1855\r
1856 while (*p != 0 && *pNest == 0 && *p != ',') {\r
1857 p = skipToSeparator(p, pNest);\r
1858 }\r
1859 if (*pNest == 0) *ppSeparator = p;\r
1860\r
1861EXIT:\r
1862 if (*p == ',') p++;\r
1863 return p;\r
1864}\r
EFI Development Kit II mirror for PVE