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