]> git.proxmox.com Git - mirror_edk2.git/blame - Tools/CCode/Source/Pccts/antlr/fset2.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 / fset2.c
CommitLineData
878ddf1f 1/*\r
2 * fset2.c\r
3 *\r
4 * Compute FIRST sets for full LL(k)\r
5 *\r
6 * SOFTWARE RIGHTS\r
7 *\r
8 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
9 * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
10 * company may do whatever they wish with source code distributed with\r
11 * PCCTS or the code generated by PCCTS, including the incorporation of\r
12 * PCCTS, or its output, into commerical software.\r
13 *\r
14 * We encourage users to develop software with PCCTS. However, we do ask\r
15 * that credit is given to us for developing PCCTS. By "credit",\r
16 * we mean that if you incorporate our source code into one of your\r
17 * programs (commercial product, research project, or otherwise) that you\r
18 * acknowledge this fact somewhere in the documentation, research report,\r
19 * etc... If you like PCCTS and have developed a nice tool with the\r
20 * output, please mention that you developed it using PCCTS. In\r
21 * addition, we ask that this header remain intact in our source code.\r
22 * As long as these guidelines are kept, we expect to continue enhancing\r
23 * this system and expect to make other tools available as they are\r
24 * completed.\r
25 *\r
26 * ANTLR 1.33\r
27 * Terence Parr\r
28 * Parr Research Corporation\r
29 * with Purdue University and AHPCRC, University of Minnesota\r
30 * 1989-2001\r
31 */\r
32\r
33#include <stdio.h>\r
34#include "pcctscfg.h"\r
35#include <stdlib.h>\r
36\r
37#ifdef PCCTS_USE_STDARG\r
38#include <stdarg.h>\r
39#else\r
40#include <varargs.h>\r
41#endif\r
42\r
43#include "set.h"\r
44#include "syn.h"\r
45#include "hash.h"\r
46#include "generic.h"\r
47#include "dlgdef.h"\r
48\r
49/* ick! globals. Used by permute() to track which elements of a set have been used */\r
50\r
51static int *findex;\r
52set *fset; /* MR11 make global */\r
53static unsigned **ftbl;\r
54static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */\r
55int ConstrainSearch;\r
56int maxk; /* set to initial k upon tree construction request */\r
57 /* MR11 make global */\r
58static Tree *FreeList = NULL;\r
59\r
60#ifdef __USE_PROTOS\r
61static int tmember_of_context(Tree *, Predicate *);\r
62#else\r
63static int tmember_of_context();\r
64#endif\r
65\r
66#if TREE_DEBUG\r
67set set_of_tnodes_in_use;\r
68int stop_on_tnode_seq_number=(-1); /* (-1) to disable */\r
69#endif\r
70\r
71/* Do root\r
72 * Then each sibling\r
73 */\r
74\r
75void\r
76#ifdef __USE_PROTOS\r
77preorder( Tree *tree )\r
78#else\r
79preorder( tree )\r
80Tree *tree;\r
81#endif\r
82{\r
83 if ( tree == NULL ) return;\r
84 if ( tree->down != NULL ) fprintf(stderr, " (");\r
85 if ( tree->token == ALT ) fprintf(stderr, " ALT");\r
86 else fprintf(stderr, " %s", TerminalString(tree->token));\r
87 if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);\r
88 preorder(tree->down);\r
89 if ( tree->down != NULL ) fprintf(stderr, " )");\r
90 preorder(tree->right);\r
91}\r
92\r
93#ifdef __USE_PROTOS\r
94int MR_tree_matches_constraints(int k,set * constrain,Tree *t)\r
95#else\r
96int MR_tree_matches_constraints(k,constrain,t)\r
97 int k;\r
98 set * constrain;\r
99 Tree * t;\r
100#endif\r
101{\r
102 int i;\r
103 Tree *u;\r
104\r
105 if (k == 0) return 1;\r
106\r
107 /* for testing guard predicates: if the guard tree is shorter\r
108 than the constraint then it is a match. The reason is that\r
109 a guard of (A B) should be equivalent to a guard of (A B . . .)\r
110 where "." matches every token. Thus a match which runs out\r
111 of tree before constraint is a match.\r
112 */\r
113\r
114 if (t == NULL) return 1;\r
115 require (set_deg(constrain[0]) == 1,\r
116 "MR_tree_matches_constraints: set_deg != 1");\r
117 i=set_int(constrain[0]);\r
118 if (t->token != i) return 0;\r
119 if (k-1 == 0) return 1;\r
120 for (u=t->down; u != NULL; u=u->right) {\r
121 if (MR_tree_matches_constraints(k-1,&constrain[1],u)) {\r
122 return 1;\r
123 };\r
124 };\r
125 return 0;\r
126}\r
127\r
128/* check the depth of each primary sibling to see that it is exactly\r
129 * k deep. e.g.;\r
130 *\r
131 * ALT\r
132 * |\r
133 * A ------- B\r
134 * | |\r
135 * C -- D E\r
136 *\r
137 * Remove all branches <= k deep.\r
138 *\r
139 * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work.\r
140 */\r
141\r
142static int pruneCount=0;\r
143static int prunePeak=200;\r
144\r
145Tree *\r
146#ifdef __USE_PROTOS\r
147prune( Tree *t, int k )\r
148#else\r
149prune( t, k )\r
150Tree *t;\r
151int k;\r
152#endif\r
153{\r
154 pruneCount++;\r
155 if (pruneCount > prunePeak+100) {\r
156 prunePeak=pruneCount;\r
157#if 0\r
158*** fprintf(stderr,"pruneCount=%d\n",pruneCount);\r
159/*** preorder(t); ***/\r
160*** fprintf(stderr,"\n",pruneCount);\r
161#endif\r
162 };\r
163 if ( t == NULL ) {\r
164 pruneCount--;\r
165 return NULL;\r
166 };\r
167 if ( t->token == ALT ) fatal_internal("prune: ALT node in FIRST tree");\r
168 if ( t->right!=NULL ) t->right = prune(t->right, k);\r
169 if ( k>1 )\r
170 {\r
171 if ( t->down!=NULL ) t->down = prune(t->down, k-1);\r
172 if ( t->down == NULL )\r
173 {\r
174 Tree *r = t->right;\r
175 t->right = NULL;\r
176 Tfree(t);\r
177 pruneCount--;\r
178 return r;\r
179 }\r
180 }\r
181 pruneCount--;\r
182 return t;\r
183}\r
184\r
185/* build a tree (root child1 child2 ... NULL) */\r
186#ifdef PCCTS_USE_STDARG\r
187Tree *tmake(Tree *root, ...)\r
188#else\r
189Tree *tmake(va_alist)\r
190va_dcl\r
191#endif\r
192{\r
193 Tree *w;\r
194 va_list ap;\r
195 Tree *child, *sibling=NULL, *tail=NULL;\r
196#ifndef PCCTS_USE_STDARG\r
197 Tree *root;\r
198#endif\r
199\r
200#ifdef PCCTS_USE_STDARG\r
201 va_start(ap, root);\r
202#else\r
203 va_start(ap);\r
204 root = va_arg(ap, Tree *);\r
205#endif\r
206 child = va_arg(ap, Tree *);\r
207 while ( child != NULL )\r
208 {\r
209#ifdef DUM\r
210 /* added "find end of child" thing TJP March 1994 */\r
211 for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */\r
212#else\r
213 w = child;\r
214#endif\r
215\r
216 if ( sibling == NULL ) {sibling = child; tail = w;}\r
217 else {tail->right = child; tail = w;}\r
218 child = va_arg(ap, Tree *);\r
219 }\r
220\r
221 /* was "root->down = sibling;" */\r
222 if ( root==NULL ) root = sibling;\r
223 else root->down = sibling;\r
224\r
225 va_end(ap);\r
226 return root;\r
227}\r
228\r
229Tree *\r
230#ifdef __USE_PROTOS\r
231tnode( int tok )\r
232#else\r
233tnode( tok )\r
234int tok;\r
235#endif\r
236{\r
237 Tree *p, *newblk;\r
238 static int n=0;\r
239 \r
240 if ( FreeList == NULL )\r
241 {\r
242 /*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/\r
243 if ( TreeResourceLimit > 0 )\r
244 {\r
245 if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )\r
246 {\r
247 fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);\r
248 fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n",\r
249 CurAmbigAlt1,\r
250 CurAmbigAlt2,\r
251 CurAmbigbtype);\r
252 exit(PCCTS_EXIT_FAILURE);\r
253 }\r
254 }\r
255 newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));\r
256 if ( newblk == NULL )\r
257 {\r
258 fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);\r
259 fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n",\r
260 CurAmbigAlt1,\r
261 CurAmbigAlt2,\r
262 CurAmbigbtype);\r
263 exit(PCCTS_EXIT_FAILURE);\r
264 }\r
265 n += TreeBlockAllocSize;\r
266 for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)\r
267 {\r
268 p->right = FreeList; /* add all new Tree nodes to Free List */\r
269 FreeList = p;\r
270 }\r
271 }\r
272 p = FreeList;\r
273 FreeList = FreeList->right; /* remove a tree node */\r
274 p->right = NULL; /* zero out ptrs */\r
275 p->down = NULL;\r
276 p->token = tok;\r
277\r
278 TnodesAllocated++; /* MR10 */\r
279 TnodesInUse++; /* MR10 */\r
280 if (TnodesInUse > TnodesPeak) TnodesPeak=TnodesInUse; /* MR10 */\r
281\r
282#ifdef TREE_DEBUG\r
283 require(!p->in_use, "tnode: node in use!");\r
284 p->in_use = 1;\r
285 p->seq=TnodesAllocated;\r
286 set_orel( (unsigned) TnodesAllocated,&set_of_tnodes_in_use);\r
287 if (stop_on_tnode_seq_number == p->seq) {\r
288 fprintf(stderr,"\n*** just allocated tnode #%d ***\n",\r
289 stop_on_tnode_seq_number);\r
290 };\r
291#endif\r
292 return p;\r
293}\r
294\r
295static Tree *\r
296#ifdef __USE_PROTOS\r
297eofnode( int k )\r
298#else\r
299eofnode( k )\r
300int k;\r
301#endif\r
302{\r
303 Tree *t=NULL;\r
304 int i;\r
305\r
306 for (i=1; i<=k; i++)\r
307 {\r
308 t = tmake(tnode((TokenInd!=NULL?TokenInd[EofToken]:EofToken)), t, NULL);\r
309 }\r
310 return t;\r
311}\r
312\r
313\r
314\r
315void\r
316#ifdef __USE_PROTOS\r
317_Tfree( Tree *t )\r
318#else\r
319_Tfree( t )\r
320Tree *t;\r
321#endif\r
322{\r
323 if ( t!=NULL )\r
324 {\r
325#ifdef TREE_DEBUG\r
326 if (t->seq == stop_on_tnode_seq_number) {\r
327 fprintf(stderr,"\n*** just freed tnode #%d ***\n",t->seq);\r
328 };\r
329 require(t->in_use, "_Tfree: node not in use!");\r
330 t->in_use = 0;\r
331 set_rm( (unsigned) t->seq,set_of_tnodes_in_use);\r
332#endif\r
333 t->right = FreeList;\r
334 FreeList = t;\r
335 TnodesInUse--; /* MR10 */\r
336 }\r
337}\r
338\r
339/* tree duplicate */\r
340Tree *\r
341#ifdef __USE_PROTOS\r
342tdup( Tree *t )\r
343#else\r
344tdup( t )\r
345Tree *t;\r
346#endif\r
347{\r
348 Tree *u;\r
349 \r
350 if ( t == NULL ) return NULL;\r
351 u = tnode(t->token);\r
352 u->v.rk = t->v.rk;\r
353 u->right = tdup(t->right);\r
354 u->down = tdup(t->down);\r
355 return u;\r
356}\r
357\r
358/* tree duplicate (assume tree is a chain downwards) */\r
359Tree *\r
360#ifdef __USE_PROTOS\r
361tdup_chain( Tree *t )\r
362#else\r
363tdup_chain( t )\r
364Tree *t;\r
365#endif\r
366{\r
367 Tree *u;\r
368 \r
369 if ( t == NULL ) return NULL;\r
370 u = tnode(t->token);\r
371 u->v.rk = t->v.rk;\r
372 u->down = tdup(t->down);\r
373 return u;\r
374}\r
375\r
376Tree *\r
377#ifdef __USE_PROTOS\r
378tappend( Tree *t, Tree *u )\r
379#else\r
380tappend( t, u )\r
381Tree *t;\r
382Tree *u;\r
383#endif\r
384{\r
385 Tree *w;\r
386\r
387/*** fprintf(stderr, "tappend(");\r
388 *** preorder(t); fprintf(stderr, ",");\r
389 *** preorder(u); fprintf(stderr, " )\n");\r
390*/\r
391 if ( t == NULL ) return u;\r
392 if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);\r
393 for (w=t; w->right!=NULL; w=w->right) {;}\r
394 w->right = u;\r
395 return t;\r
396}\r
397\r
398/* dealloc all nodes in a tree */\r
399void\r
400#ifdef __USE_PROTOS\r
401Tfree( Tree *t )\r
402#else\r
403Tfree( t )\r
404Tree *t;\r
405#endif\r
406{\r
407 if ( t == NULL ) return;\r
408 Tfree( t->down );\r
409 Tfree( t->right );\r
410 _Tfree( t );\r
411}\r
412\r
413/* find all children (alts) of t that require remaining_k nodes to be LL_k\r
414 * tokens long.\r
415 *\r
416 * t-->o\r
417 * |\r
418 * a1--a2--...--an <-- LL(1) tokens\r
419 * | | |\r
420 * b1 b2 ... bn <-- LL(2) tokens\r
421 * | | |\r
422 * . . .\r
423 * . . .\r
424 * z1 z2 ... zn <-- LL(LL_k) tokens\r
425 *\r
426 * We look for all [Ep] needing remaining_k nodes and replace with u.\r
427 * u is not destroyed or actually used by the tree (a copy is made).\r
428 */\r
429Tree *\r
430#ifdef __USE_PROTOS\r
431tlink( Tree *t, Tree *u, int remaining_k )\r
432#else\r
433tlink( t, u, remaining_k )\r
434Tree *t;\r
435Tree *u;\r
436int remaining_k;\r
437#endif\r
438{\r
439 Tree *p;\r
440 require(remaining_k!=0, "tlink: bad tree");\r
441\r
442 if ( t==NULL ) return NULL;\r
443 /*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/\r
444 if ( t->token == EpToken && t->v.rk == remaining_k )\r
445 {\r
446 require(t->down==NULL, "tlink: invalid tree");\r
447 if ( u == NULL ) {\r
448/* MR10 */ Tree *tt=t->right;\r
449/* MR10 */ _Tfree(t);\r
450/* MR10 */ return tt;\r
451 };\r
452 p = tdup( u );\r
453 p->right = t->right;\r
454 _Tfree( t );\r
455 return p;\r
456 }\r
457 t->down = tlink(t->down, u, remaining_k);\r
458 t->right = tlink(t->right, u, remaining_k);\r
459 return t;\r
460}\r
461\r
462/* remove as many ALT nodes as possible while still maintaining semantics */\r
463Tree *\r
464#ifdef __USE_PROTOS\r
465tshrink( Tree *t )\r
466#else\r
467tshrink( t )\r
468Tree *t;\r
469#endif\r
470{\r
471 if ( t == NULL ) return NULL;\r
472 t->down = tshrink( t->down );\r
473 t->right = tshrink( t->right );\r
474 if ( t->down == NULL )\r
475 {\r
476 if ( t->token == ALT )\r
477 {\r
478 Tree *u = t->right;\r
479 _Tfree(t);\r
480 return u; /* remove useless alts */\r
481 }\r
482 return t;\r
483 }\r
484\r
485 /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */\r
486 if ( t->token == ALT && t->down->right == NULL)\r
487 {\r
488 Tree *u = t->down;\r
489 u->right = t->right;\r
490 _Tfree( t );\r
491 return u;\r
492 }\r
493 /* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */\r
494 if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )\r
495 {\r
496 Tree *u = t->down->down;\r
497 _Tfree( t->down );\r
498 t->down = u;\r
499 return t;\r
500 }\r
501 return t;\r
502}\r
503\r
504Tree *\r
505#ifdef __USE_PROTOS\r
506tflatten( Tree *t )\r
507#else\r
508tflatten( t )\r
509Tree *t;\r
510#endif\r
511{\r
512 if ( t == NULL ) return NULL;\r
513 t->down = tflatten( t->down );\r
514 t->right = tflatten( t->right );\r
515 if ( t->down == NULL ) return t;\r
516 \r
517 if ( t->token == ALT )\r
518 {\r
519 Tree *u;\r
520 /* find tail of children */\r
521 for (u=t->down; u->right!=NULL; u=u->right) {;}\r
522 u->right = t->right;\r
523 u = t->down;\r
524 _Tfree( t );\r
525 return u;\r
526 }\r
527 return t;\r
528}\r
529\r
530Tree *\r
531#ifdef __USE_PROTOS\r
532tJunc( Junction *p, int k, set *rk )\r
533#else\r
534tJunc( p, k, rk )\r
535Junction *p;\r
536int k;\r
537set *rk;\r
538#endif\r
539{\r
540 Tree *t=NULL, *u=NULL;\r
541 Junction *alt;\r
542 Tree *tail=NULL, *r;\r
543\r
544#ifdef DBG_TRAV\r
545 fprintf(stderr, "tJunc(%d): %s in rule %s\n", k,\r
546 decodeJType[p->jtype], ((Junction *)p)->rname);\r
547#endif\r
548\r
549/* MR14 */ if (AlphaBetaTrace && p->alpha_beta_guess_end) {\r
550/* MR14 */ warnFL(\r
551/* MR14 */ "not possible to compute follow set for alpha in an \"(alpha)? beta\" block. ",\r
552/* MR14 */ FileStr[p->file],p->line);\r
553/* MR14 */ MR_alphaBetaTraceReport();\r
554/* MR14 */ };\r
555\r
556/* MR14 */ if (p->alpha_beta_guess_end) {\r
557/* MR14 */ return NULL;\r
558/* MR14 */ }\r
559\r
560 if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||\r
561 p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )\r
562 {\r
563 if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {\r
564 require(p->lock!=NULL, "rJunc: lock array is NULL");\r
565 if ( p->lock[k] ) return NULL;\r
566 p->lock[k] = TRUE;\r
567 }\r
568\r
569/* MR10 */ if (MR_MaintainBackTrace) {\r
570/* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);\r
571/* MR10 */ };\r
572\r
573 TRAV(p->p1, k, rk, tail);\r
574\r
575/* MR10 */ if (MR_MaintainBackTrace) {\r
576/* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);\r
577/* MR10 */ };\r
578\r
579 if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}\r
580 r = tmake(tnode(ALT), tail, NULL);\r
581 for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)\r
582 {\r
583 /* if this is one of the added optional alts for (...)+ then break */\r
584 if ( alt->ignore ) break;\r
585\r
586 if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}\r
587 else\r
588 {\r
589/* MR10 */ if (MR_MaintainBackTrace) {\r
590/* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);\r
591/* MR10 */ };\r
592\r
593 TRAV(alt->p1, k, rk, tail->right);\r
594\r
595/* MR10 */ if (MR_MaintainBackTrace) {\r
596/* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);\r
597/* MR10 */ };\r
598 if ( tail->right != NULL ) tail = tail->right;\r
599 }\r
600 }\r
601 if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;\r
602#ifdef DBG_TREES\r
603 fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n");\r
604#endif\r
605 if ( r->down == NULL ) {_Tfree(r); return NULL;}\r
606 return r;\r
607 }\r
608\r
609 if ( p->jtype==EndRule )\r
610 {\r
611 if ( p->halt ) /* don't want FOLLOW here? */\r
612 {\r
613/**** if ( ContextGuardTRAV ) return NULL; ****/\r
614 set_orel( (unsigned) k, rk); /* indicate this k value needed */ /* MR10 cast */\r
615 t = tnode(EpToken);\r
616 t->v.rk = k;\r
617 return t;\r
618 }\r
619 require(p->lock!=NULL, "rJunc: lock array is NULL");\r
620 if ( p->lock[k] ) return NULL;\r
621 /* if no FOLLOW assume k EOF's */\r
622 if ( p->p1 == NULL ) return eofnode(k);\r
623 p->lock[k] = TRUE;\r
624 }\r
625\r
626/* MR14 */ if (p->p1 != NULL && p->guess && p->guess_analysis_point == NULL) {\r
627/* MR14 */ Node * guess_point;\r
628/* MR14 */ guess_point=(Node *)analysis_point(p);\r
629/* MR14 */ if (guess_point == (Node *)p) {\r
630/* MR14 */ guess_point=p->p1;\r
631/* MR14 */ }\r
632/* MR14 */ p->guess_analysis_point=guess_point;\r
633/* MR14 */ } \r
634\r
635 if ( p->p2 == NULL )\r
636 {\r
637\r
638/* MR10 */ if (MR_MaintainBackTrace) {\r
639/* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);\r
640/* MR10 */ };\r
641\r
642/* M14 */ if (p->guess_analysis_point != NULL) {\r
643/* M14 */ TRAV(p->guess_analysis_point, k, rk,t);\r
644/* M14 */ } else {\r
645 TRAV(p->p1, k, rk,t);\r
646/* M14 */ }\r
647\r
648/* MR10 */ if (MR_MaintainBackTrace) {\r
649/* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);\r
650/* MR10 */ };\r
651\r
652 if ( p->jtype==EndRule ) p->lock[k]=FALSE;\r
653 return t;\r
654 }\r
655\r
656/* MR10 */ if (MR_MaintainBackTrace) {\r
657/* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);\r
658/* MR10 */ };\r
659\r
660/* M14 */ if (p->guess_analysis_point != NULL) {\r
661/* M14 */ TRAV(p->guess_analysis_point, k, rk,t);\r
662/* M14 */ } else {\r
663 TRAV(p->p1, k, rk,t);\r
664/* M14 */ }\r
665\r
666/* MR10 */ if (MR_MaintainBackTrace) {\r
667/* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);\r
668/* MR10 */ };\r
669\r
670 if ( p->jtype!=RuleBlk && /* MR14 */ !p->guess) TRAV(p->p2, k, rk, u);\r
671\r
672 if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */\r
673\r
674 if ( t==NULL ) return tmake(tnode(ALT), u, NULL);\r
675 return tmake(tnode(ALT), t, u, NULL);\r
676}\r
677\r
678Tree *\r
679#ifdef __USE_PROTOS\r
680tRuleRef( RuleRefNode *p, int k, set *rk_out )\r
681#else\r
682tRuleRef( p, k, rk_out )\r
683RuleRefNode *p;\r
684int k;\r
685set *rk_out;\r
686#endif\r
687{\r
688 int k2;\r
689 Tree *t=NULL, *u=NULL;\r
690 Junction *r;\r
691 set rk, rk2;\r
692 int save_halt;\r
693 RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);\r
694 \r
695#ifdef DBG_TRAV\r
696 fprintf(stderr, "tRuleRef: %s\n", p->text);\r
697#endif\r
698 if ( q == NULL )\r
699 {\r
700 TRAV(p->next, k, rk_out, t);/* ignore undefined rules */\r
701 return t;\r
702 }\r
703 rk = rk2 = empty;\r
704 if (RulePtr == NULL) fatal("RulePtr==NULL");\r
705 r = RulePtr[q->rulenum];\r
706 if ( r->lock[k] ) return NULL;\r
707 save_halt = r->end->halt;\r
708 r->end->halt = TRUE; /* don't let reach fall off end of rule here */\r
709\r
710/* MR10 */ if (MR_MaintainBackTrace) {\r
711/* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p);\r
712/* MR10 */ };\r
713\r
714 TRAV(r, k, &rk, t);\r
715\r
716/* MR10 */ if (MR_MaintainBackTrace) {\r
717/* MR10 */ MR_pointerStackPop(&MR_BackTraceStack);\r
718/* MR10 */ };\r
719\r
720 r->end->halt = save_halt;\r
721#ifdef DBG_TREES\r
722 fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n");\r
723#endif\r
724 t = tshrink( t );\r
725 while ( !set_nil(rk) ) { /* any k left to do? if so, link onto tree */\r
726 k2 = set_int(rk);\r
727 set_rm(k2, rk);\r
728\r
729/* MR10 */ if (MR_MaintainBackTrace) {\r
730/* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p);\r
731/* MR10 */ };\r
732\r
733 TRAV(p->next, k2, &rk2, u);\r
734\r
735/* MR10 */ if (MR_MaintainBackTrace) {\r
736/* MR10 */ MR_pointerStackPop(&MR_BackTraceStack);\r
737/* MR10 */ };\r
738\r
739 t = tlink(t, u, k2); /* any alts missing k2 toks, add u onto end */\r
740 Tfree(u); /* MR10 */\r
741 }\r
742 set_free(rk); /* rk is empty, but free it's memory */\r
743 set_orin(rk_out, rk2); /* remember what we couldn't do */\r
744 set_free(rk2);\r
745 return t;\r
746}\r
747\r
748Tree *\r
749#ifdef __USE_PROTOS\r
750tToken( TokNode *p, int k, set *rk )\r
751#else\r
752tToken( p, k, rk )\r
753TokNode *p;\r
754int k;\r
755set *rk;\r
756#endif\r
757{\r
758 Tree *t=NULL, *tset=NULL, *u;\r
759\r
760 if (ConstrainSearch) {\r
761 if (MR_AmbSourceSearch) {\r
762 require(constrain>=fset&&constrain<=&(fset[CLL_k]),"tToken: constrain is not a valid set");\r
763 } else {\r
764 require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");\r
765 };\r
766 constrain = &fset[maxk-k+1];\r
767 }\r
768\r
769#ifdef DBG_TRAV\r
770 fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token));\r
771 if ( ConstrainSearch ) {\r
772 fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n");\r
773 }\r
774#endif\r
775\r
776 /* is it a meta token (set of tokens)? */\r
777\r
778 if ( !set_nil(p->tset) )\r
779 {\r
780 unsigned e=0;\r
781 set a;\r
782 Tree *n, *tail = NULL;\r
783\r
784 if ( ConstrainSearch ) {\r
785 a = set_and(p->tset, *constrain);\r
786 if (set_nil(a)) { /* MR10 */\r
787 set_free(a); /* MR11 */\r
788 return NULL; /* MR10 */\r
789 }; /* MR10 */\r
790 } else {\r
791 a = set_dup(p->tset);\r
792 };\r
793\r
794 for (; !set_nil(a); set_rm(e, a))\r
795 {\r
796 e = set_int(a);\r
797 n = tnode(e);\r
798 if ( tset==NULL ) { tset = n; tail = n; }\r
799 else { tail->right = n; tail = n; }\r
800 }\r
801 set_free( a );\r
802 }\r
803 else if ( ConstrainSearch && !set_el(p->token, *constrain) )\r
804 {\r
805/* fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),\r
806 k);*/\r
807 return NULL;\r
808 }\r
809 else {\r
810 tset = tnode( p->token );\r
811 };\r
812\r
813/* MR10 */ if (MR_MaintainBackTrace) {\r
814/* MR10 */ if (k == 1) {\r
815/* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p);\r
816/* MR13 */ if (MR_SuppressSearch) {\r
817/* MR13 */ MR_suppressSearchReport();\r
818/* MR13 */ } else {\r
819/* MR10 */ MR_backTraceReport();\r
820/* MR13 */ };\r
821/* MR10 */ MR_pointerStackPop(&MR_BackTraceStack);\r
822/* MR11 */ Tfree(tset);\r
823/* MR11 */ return NULL;\r
824/* MR10 */ };\r
825/* MR10 */ };\r
826\r
827 if ( k == 1 ) return tset;\r
828\r
829 if (MR_MaintainBackTrace) {\r
830 MR_pointerStackPush(&MR_BackTraceStack,p);\r
831 };\r
832\r
833 TRAV(p->next, k-1, rk, t);\r
834\r
835 if (MR_MaintainBackTrace) {\r
836 Tfree(t);\r
837 Tfree(tset);\r
838 MR_pointerStackPop(&MR_BackTraceStack);\r
839 return NULL;\r
840 };\r
841\r
842 /* here, we are positive that, at least, this tree will not contribute\r
843 * to the LL(2) tree since it will be too shallow, IF t==NULL.\r
844 * If doing a context guard walk, then don't prune.\r
845 */\r
846 if ( t == NULL && !ContextGuardTRAV ) /* tree will be too shallow */\r
847 {\r
848 if ( tset!=NULL ) Tfree( tset );\r
849 return NULL;\r
850 }\r
851#ifdef DBG_TREES\r
852 fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n");\r
853#endif\r
854\r
855 /* if single token root, then just make new tree and return */\r
856 /* MR10 - set_nil(p->tset) isn't a good test because of ConstraintSearch */\r
857\r
858 if (tset->right == NULL) return tmake(tset, t, NULL); /* MR10 */\r
859\r
860 /* here we must make a copy of t as a child of each element of the tset;\r
861 * e.g., "T1..T3 A" would yield ( nil ( T1 A ) ( T2 A ) ( T3 A ) )\r
862 */\r
863 for (u=tset; u!=NULL; u=u->right)\r
864 {\r
865 /* make a copy of t and hook it onto bottom of u */\r
866 u->down = tdup(t);\r
867 }\r
868 Tfree( t );\r
869#ifdef DBG_TREES\r
870 fprintf(stderr, "range is:"); preorder(tset); fprintf(stderr, "\n");\r
871#endif\r
872 return tset;\r
873}\r
874\r
875Tree *\r
876#ifdef __USE_PROTOS\r
877tAction( ActionNode *p, int k, set *rk )\r
878#else\r
879tAction( p, k, rk )\r
880ActionNode *p;\r
881int k;\r
882set *rk;\r
883#endif\r
884{\r
885 Tree *t=NULL;\r
886 set *save_fset=NULL;\r
887 int i;\r
888\r
889 /* fprintf(stderr, "tAction\n"); */\r
890\r
891/* An MR_SuppressSearch is looking for things that can be\r
892 reached even when the predicate is false.\r
893\r
894 There are three kinds of predicates:\r
895 plain: r1: <<p>>? r2\r
896 guarded: r1: (A)? => <<p>>? r2\r
897 ampersand style: r1: (A)? && <<p>>? r2\r
898\r
899 Of the three kinds of predicates, only a guard predicate\r
900 has things which are reachable even when the predicate\r
901 is false. To be reachable the constraint must *not*\r
902 match the guard.\r
903\r
904*/\r
905\r
906 if (p->is_predicate && MR_SuppressSearch) {\r
907\r
908 Predicate *pred=p->guardpred;\r
909\r
910 if (pred == NULL) {\r
911 t=NULL;\r
912 goto EXIT;\r
913 };\r
914 constrain = &fset[maxk-k+1];\r
915 if (pred->k == 1) {\r
916 set dif;\r
917 dif=set_dif(*constrain,pred->scontext[1]);\r
918 if (set_nil(dif)) {\r
919 set_free(dif);\r
920 t=NULL;\r
921 goto EXIT;\r
922 };\r
923 set_free(dif);\r
924 } else {\r
925 if (MR_tree_matches_constraints(k,constrain,pred->tcontext)) {\r
926 t=NULL;\r
927 goto EXIT;\r
928 };\r
929 }\r
930 };\r
931\r
932 /* The ampersand predicate differs from the\r
933 other predicates because its first set\r
934 is a subset of the first set behind the predicate\r
935\r
936 r1: (A)? && <<p>>? r2 ;\r
937 r2: A | B;\r
938\r
939 In this case first[1] of r1 is A, even\r
940 though first[1] of r2 is {A B}.\r
941 */\r
942\r
943 if (p->is_predicate && p->ampersandPred != NULL) {\r
944\r
945 Predicate *pred=p->ampersandPred;\r
946 Tree *tAND;\r
947 Tree *tset;\r
948\r
949 if (k <= pred->k) {\r
950 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);\r
951 TRAV(p->guardNodes,k,rk,t);\r
952 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
953 return t;\r
954 } else {\r
955 require (k>1,"tAction for ampersandpred: k <= 1");\r
956 if (ConstrainSearch) {\r
957 if (MR_AmbSourceSearch) {\r
958 require(constrain>=fset&&constrain<=&(fset[CLL_k]),\r
959 "tToken: constrain is not a valid set");\r
960 } else {\r
961 require(constrain>=fset&&constrain<=&(fset[LL_k]),\r
962 "tToken: constrain is not a valid set");\r
963 };\r
964 save_fset=(set *) calloc (CLL_k+1,sizeof(set));\r
965 require (save_fset != NULL,"tAction save_fset alloc");\r
966 for (i=1; i <= CLL_k ; i++) {\r
967 save_fset[i]=set_dup(fset[i]);\r
968 };\r
969 if (pred->k == 1) {\r
970 constrain = &fset[maxk-k+1];\r
971 set_andin(constrain,pred->scontext[1]);\r
972 if (set_nil(*constrain)) {\r
973 t=NULL;\r
974 goto EXIT;\r
975 };\r
976 } else {\r
977 constrain = &fset[maxk-k+1];\r
978 if (! MR_tree_matches_constraints(pred->k,constrain,pred->tcontext)) {\r
979 t=NULL;\r
980 goto EXIT;\r
981 }; /* end loop on i */\r
982 }; /* end loop on pred scontext/tcontext */\r
983 }; /* end if on k > pred->k */\r
984 }; /* end if on constrain search */\r
985\r
986 TRAV(p->next,k,rk,t);\r
987\r
988 if (t != NULL) {\r
989 t=tshrink(t);\r
990 t=tflatten(t);\r
991 t=tleft_factor(t);\r
992 if (pred->tcontext != NULL) {\r
993 tAND=MR_computeTreeAND(t,pred->tcontext);\r
994 } else {\r
995 tset=MR_make_tree_from_set(pred->scontext[1]);\r
996 tAND=MR_computeTreeAND(t,tset);\r
997 Tfree(tset);\r
998 };\r
999 Tfree(t);\r
1000 t=tAND;\r
1001 };\r
1002 goto EXIT;\r
1003\r
1004 }; /* end if on ampersand predicate */\r
1005\r
1006 TRAV(p->next,k,rk,t);\r
1007\r
1008EXIT:\r
1009 if (save_fset != NULL) {\r
1010 for (i=1 ; i <= CLL_k ; i++) {\r
1011 set_free(fset[i]);\r
1012 fset[i]=save_fset[i];\r
1013 };\r
1014 free ( (char *) save_fset);\r
1015 };\r
1016 return t;\r
1017}\r
1018\r
1019/* see if e exists in s as a possible input permutation (e is always a chain) */\r
1020\r
1021int\r
1022#ifdef __USE_PROTOS\r
1023tmember( Tree *e, Tree *s )\r
1024#else\r
1025tmember( e, s )\r
1026Tree *e;\r
1027Tree *s;\r
1028#endif\r
1029{\r
1030 if ( e==NULL||s==NULL ) return 0;\r
1031/** fprintf(stderr, "tmember(");\r
1032*** preorder(e); fprintf(stderr, ",");\r
1033*** preorder(s); fprintf(stderr, " )\n");\r
1034*/\r
1035 if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);\r
1036 if ( e->token!=s->token )\r
1037 {\r
1038 if ( s->right==NULL ) return 0;\r
1039 return tmember(e, s->right);\r
1040 }\r
1041 if ( e->down==NULL && s->down == NULL ) return 1;\r
1042 if ( tmember(e->down, s->down) ) return 1;\r
1043 if ( s->right==NULL ) return 0;\r
1044 return tmember(e, s->right);\r
1045}\r
1046\r
1047/* see if e exists in s as a possible input permutation (e is always a chain);\r
1048 * Only check s to the depth of e. In other words, 'e' can be a shorter\r
1049 * sequence than s.\r
1050 */\r
1051int\r
1052#ifdef __USE_PROTOS\r
1053tmember_constrained( Tree *e, Tree *s)\r
1054#else\r
1055tmember_constrained( e, s )\r
1056Tree *e;\r
1057Tree *s;\r
1058#endif\r
1059{\r
1060 if ( e==NULL||s==NULL ) return 0;\r
1061/** fprintf(stderr, "tmember_constrained(");\r
1062*** preorder(e); fprintf(stderr, ",");\r
1063*** preorder(s); fprintf(stderr, " )\n");\r
1064**/\r
1065 if ( s->token == ALT && s->right == NULL )\r
1066 return tmember_constrained(e, s->down);\r
1067 if ( e->token!=s->token )\r
1068 {\r
1069 if ( s->right==NULL ) return 0;\r
1070 return tmember_constrained(e, s->right);\r
1071 }\r
1072 if ( e->down == NULL ) return 1; /* if s is matched to depth of e return */\r
1073 if ( tmember_constrained(e->down, s->down) ) return 1;\r
1074 if ( s->right==NULL ) return 0;\r
1075 return tmember_constrained(e, s->right);\r
1076}\r
1077\r
1078/* combine (? (A t) ... (A u) ...) into (? (A t u)) */\r
1079Tree *\r
1080#ifdef __USE_PROTOS\r
1081tleft_factor( Tree *t )\r
1082#else\r
1083tleft_factor( t )\r
1084Tree *t;\r
1085#endif\r
1086{\r
1087 Tree *u, *v, *trail, *w;\r
1088\r
1089 /* left-factor what is at this level */\r
1090 if ( t == NULL ) return NULL;\r
1091 for (u=t; u!=NULL; u=u->right)\r
1092 {\r
1093 trail = u;\r
1094 v=u->right;\r
1095 while ( v!=NULL )\r
1096 {\r
1097 if ( u->token == v->token )\r
1098 {\r
1099 if ( u->down!=NULL )\r
1100 {\r
1101 for (w=u->down; w->right!=NULL; w=w->right) {;}\r
1102 w->right = v->down; /* link children together */\r
1103 }\r
1104 else u->down = v->down;\r
1105 trail->right = v->right; /* unlink factored node */\r
1106 _Tfree( v );\r
1107 v = trail->right;\r
1108 }\r
1109 else {trail = v; v=v->right;}\r
1110 }\r
1111 }\r
1112 /* left-factor what is below */\r
1113 for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );\r
1114 return t;\r
1115}\r
1116\r
1117/* remove the permutation p from t if present */\r
1118Tree *\r
1119#ifdef __USE_PROTOS\r
1120trm_perm( Tree *t, Tree *p )\r
1121#else\r
1122trm_perm( t, p )\r
1123Tree *t;\r
1124Tree *p;\r
1125#endif\r
1126{\r
1127 /*\r
1128 fprintf(stderr, "trm_perm(");\r
1129 preorder(t); fprintf(stderr, ",");\r
1130 preorder(p); fprintf(stderr, " )\n");\r
1131 */\r
1132 if ( t == NULL || p == NULL ) return NULL;\r
1133 if ( t->token == ALT )\r
1134 {\r
1135 t->down = trm_perm(t->down, p);\r
1136 if ( t->down == NULL ) /* nothing left below, rm cur node */\r
1137 {\r
1138 Tree *u = t->right;\r
1139 _Tfree( t );\r
1140 return trm_perm(u, p);\r
1141 }\r
1142 t->right = trm_perm(t->right, p); /* look for more instances of p */\r
1143 return t;\r
1144 }\r
1145 if ( p->token != t->token ) /* not found, try a sibling */\r
1146 {\r
1147 t->right = trm_perm(t->right, p);\r
1148 return t;\r
1149 }\r
1150 t->down = trm_perm(t->down, p->down);\r
1151 if ( t->down == NULL ) /* nothing left below, rm cur node */\r
1152 {\r
1153 Tree *u = t->right;\r
1154 _Tfree( t );\r
1155 return trm_perm(u, p);\r
1156 }\r
1157 t->right = trm_perm(t->right, p); /* look for more instances of p */\r
1158 return t;\r
1159}\r
1160\r
1161/* add the permutation 'perm' to the LL_k sets in 'fset' */\r
1162void\r
1163#ifdef __USE_PROTOS\r
1164tcvt( set *fset, Tree *perm )\r
1165#else\r
1166tcvt( fset, perm )\r
1167set *fset;\r
1168Tree *perm;\r
1169#endif\r
1170{\r
1171 if ( perm==NULL ) return;\r
1172 set_orel(perm->token, fset);\r
1173 tcvt(fset+1, perm->down);\r
1174}\r
1175\r
1176/* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])\r
1177 * as a child.\r
1178 */\r
1179Tree *\r
1180#ifdef __USE_PROTOS\r
1181permute( int k, int max_k )\r
1182#else\r
1183permute( k, max_k )\r
1184int k, max_k;\r
1185#endif\r
1186{\r
1187 Tree *t, *u;\r
1188 \r
1189 if ( k>max_k ) return NULL;\r
1190 if ( ftbl[k][findex[k]] == nil ) return NULL;\r
1191 t = permute(k+1, max_k);\r
1192 if ( t==NULL&&k<max_k ) /* no permutation left below for k+1 tokens? */\r
1193 {\r
1194 findex[k+1] = 0;\r
1195 (findex[k])++; /* try next token at this k */\r
1196 return permute(k, max_k);\r
1197 }\r
1198 \r
1199 u = tmake(tnode(ftbl[k][findex[k]]), t, NULL);\r
1200 if ( k == max_k ) (findex[k])++;\r
1201 return u;\r
1202}\r
1203\r
1204/* Compute LL(k) trees for alts alt1 and alt2 of p.\r
1205 * function result is tree of ambiguous input permutations\r
1206 *\r
1207 * ALGORITHM may change to look for something other than LL_k size\r
1208 * trees ==> maxk will have to change.\r
1209 */\r
1210Tree *\r
1211#ifdef __USE_PROTOS\r
1212VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig )\r
1213#else\r
1214VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig )\r
1215Junction *alt1;\r
1216Junction *alt2;\r
1217unsigned **ft;\r
1218set *fs;\r
1219Tree **t;\r
1220Tree **u;\r
1221int *numAmbig;\r
1222#endif\r
1223{\r
1224 set rk;\r
1225 Tree *perm, *ambig=NULL;\r
1226 Junction *p;\r
1227 int k;\r
1228 int tnodes_at_start=TnodesAllocated;\r
1229 int tnodes_at_end;\r
1230 int tnodes_used;\r
1231 set *save_fs;\r
1232 int j;\r
1233\r
1234 save_fs=(set *) calloc(CLL_k+1,sizeof(set));\r
1235 require(save_fs != NULL,"save_fs calloc");\r
1236\r
1237 for (j=0; j <= CLL_k ; j++) save_fs[j]=set_dup(fs[j]);\r
1238\r
1239 maxk = LL_k; /* NOTE: for now, we look for LL_k */\r
1240 ftbl = ft;\r
1241 fset = fs;\r
1242 constrain = &(fset[1]);\r
1243 findex = (int *) calloc(LL_k+1, sizeof(int));\r
1244 if ( findex == NULL )\r
1245 {\r
1246 fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);\r
1247 fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n",\r
1248 CurAmbigAlt1,\r
1249 CurAmbigAlt2,\r
1250 CurAmbigbtype);\r
1251 exit(PCCTS_EXIT_FAILURE);\r
1252 }\r
1253 for (k=1; k<=LL_k; k++) findex[k] = 0;\r
1254\r
1255 rk = empty;\r
1256 ConstrainSearch = 1; /* consider only tokens in ambig sets */\r
1257\r
1258 p = analysis_point((Junction *)alt1->p1);\r
1259 TRAV(p, LL_k, &rk, *t);\r
1260 *t = tshrink( *t );\r
1261 *t = tflatten( *t );\r
1262 *t = tleft_factor( *t ); /* MR10 */\r
1263 *t = prune(*t, LL_k);\r
1264 *t = tleft_factor( *t );\r
1265\r
1266/*** fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/\r
1267 if ( *t == NULL )\r
1268 {\r
1269/*** fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/\r
1270 Tfree( *t ); /* kill if impossible to have ambig */\r
1271 *t = NULL;\r
1272 }\r
1273\r
1274 p = analysis_point((Junction *)alt2->p1);\r
1275\r
1276 TRAV(p, LL_k, &rk, *u);\r
1277 *u = tshrink( *u );\r
1278 *u = tflatten( *u );\r
1279 *t = tleft_factor( *t ); /* MR10 */\r
1280 *u = prune(*u, LL_k);\r
1281 *u = tleft_factor( *u );\r
1282/* fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/\r
1283 if ( *u == NULL )\r
1284 {\r
1285/* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/\r
1286 Tfree( *u );\r
1287 *u = NULL;\r
1288 }\r
1289\r
1290 for (k=1; k<=LL_k; k++) set_clr( fs[k] );\r
1291\r
1292 ambig = tnode(ALT);\r
1293 k = 0;\r
1294 if ( *t!=NULL && *u!=NULL )\r
1295 {\r
1296 while ( (perm=permute(1,LL_k))!=NULL )\r
1297 {\r
1298/* fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/\r
1299 if ( tmember(perm, *t) && tmember(perm, *u) )\r
1300 {\r
1301/* fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/\r
1302\r
1303 k++;\r
1304 perm->right = ambig->down;\r
1305 ambig->down = perm;\r
1306 tcvt(&(fs[1]), perm);\r
1307 }\r
1308 else Tfree( perm );\r
1309 }\r
1310 }\r
1311\r
1312 for (j=0; j <= CLL_k ; j++) fs[j]=save_fs[j];\r
1313 free( (char *) save_fs);\r
1314\r
1315 tnodes_at_end=TnodesAllocated;\r
1316 tnodes_used=tnodes_at_end - tnodes_at_start;\r
1317\r
1318 if (TnodesReportThreshold > 0 && tnodes_used > TnodesReportThreshold) {\r
1319 fprintf(stdout,"There were %d tuples whose ambiguity could not be resolved by full lookahead\n",k);\r
1320 fprintf(stdout,"There were %d tnodes created to resolve ambiguity between:\n\n",tnodes_used);\r
1321 fprintf(stdout," Choice 1: %s line %d file %s\n",\r
1322 MR_ruleNamePlusOffset( (Node *) alt1),alt1->line,FileStr[alt1->file]);\r
1323 fprintf(stdout," Choice 2: %s line %d file %s\n",\r
1324 MR_ruleNamePlusOffset( (Node *) alt2),alt2->line,FileStr[alt2->file]);\r
1325 for (j=1; j <= CLL_k ; j++) {\r
1326 fprintf(stdout,"\n Intersection of lookahead[%d] sets:\n",j);\r
1327 MR_dumpTokenSet(stdout,2,fs[j]);\r
1328 };\r
1329 fprintf(stdout,"\n");\r
1330 };\r
1331\r
1332 *numAmbig = k;\r
1333 if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;}\r
1334 free( (char *)findex );\r
1335/* fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/\r
1336 return ambig;\r
1337}\r
1338\r
1339static Tree *\r
1340#ifdef __USE_PROTOS\r
1341bottom_of_chain( Tree *t )\r
1342#else\r
1343bottom_of_chain( t )\r
1344Tree *t;\r
1345#endif\r
1346{\r
1347 if ( t==NULL ) return NULL;\r
1348 for (; t->down != NULL; t=t->down) {;}\r
1349 return t;\r
1350}\r
1351\r
1352/*\r
1353 * Make a tree from k sets where the degree of the first k-1 sets is 1.\r
1354 */\r
1355Tree *\r
1356#ifdef __USE_PROTOS\r
1357make_tree_from_sets( set *fset1, set *fset2 )\r
1358#else\r
1359make_tree_from_sets( fset1, fset2 )\r
1360set *fset1;\r
1361set *fset2;\r
1362#endif\r
1363{\r
1364 set inter;\r
1365 int i;\r
1366 Tree *t=NULL, *n, *u;\r
1367 unsigned *p,*q;\r
1368 require(LL_k>1, "make_tree_from_sets: LL_k must be > 1");\r
1369\r
1370 /* do the degree 1 sets first */\r
1371 for (i=1; i<=LL_k-1; i++)\r
1372 {\r
1373 inter = set_and(fset1[i], fset2[i]);\r
1374 require(set_deg(inter)==1, "invalid set to tree conversion");\r
1375 n = tnode(set_int(inter));\r
1376 if (t==NULL) t=n; else tmake(t, n, NULL);\r
1377 set_free(inter);\r
1378 }\r
1379\r
1380 /* now add the chain of tokens at depth k */\r
1381 u = bottom_of_chain(t);\r
1382 inter = set_and(fset1[LL_k], fset2[LL_k]);\r
1383 if ( (q=p=set_pdq(inter)) == NULL ) fatal_internal("Can't alloc space for set_pdq");\r
1384 /* first one is linked to bottom, then others are sibling linked */\r
1385 n = tnode(*p++);\r
1386 u->down = n;\r
1387 u = u->down;\r
1388 while ( *p != nil )\r
1389 {\r
1390 n = tnode(*p);\r
1391 u->right = n;\r
1392 u = u->right;\r
1393 p++;\r
1394 }\r
1395 free((char *)q);\r
1396\r
1397 return t;\r
1398}\r
1399\r
1400/* create and return the tree of lookahead k-sequences that are in t, but not\r
1401 * in the context of predicates in predicate list p.\r
1402 */\r
1403Tree *\r
1404#ifdef __USE_PROTOS\r
1405tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 )\r
1406#else\r
1407tdif( ambig_tuples, p, fset1, fset2 )\r
1408Tree *ambig_tuples;\r
1409Predicate *p;\r
1410set *fset1;\r
1411set *fset2;\r
1412#endif\r
1413{\r
1414 unsigned **ft;\r
1415 Tree *dif=NULL;\r
1416 Tree *perm;\r
1417 set b;\r
1418 int i,k;\r
1419\r
1420 if ( p == NULL ) return tdup(ambig_tuples);\r
1421\r
1422 ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));\r
1423 require(ft!=NULL, "cannot allocate ft");\r
1424 for (i=1; i<=CLL_k; i++)\r
1425 {\r
1426 b = set_and(fset1[i], fset2[i]);\r
1427 ft[i] = set_pdq(b);\r
1428 set_free(b);\r
1429 }\r
1430 findex = (int *) calloc(LL_k+1, sizeof(int));\r
1431 if ( findex == NULL )\r
1432 {\r
1433 fatal_internal("out of memory in tdif while checking predicates");\r
1434 }\r
1435 for (k=1; k<=LL_k; k++) findex[k] = 0;\r
1436\r
1437#ifdef DBG_TRAV\r
1438 fprintf(stderr, "tdif_%d[", p->k);\r
1439 preorder(ambig_tuples);\r
1440 fprintf(stderr, ",");\r
1441 preorder(p->tcontext);\r
1442 fprintf(stderr, "] =");\r
1443#endif\r
1444\r
1445 ftbl = ft;\r
1446 while ( (perm=permute(1,p->k))!=NULL )\r
1447 {\r
1448#ifdef DBG_TRAV\r
1449 fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "\n");\r
1450#endif\r
1451 if ( tmember_constrained(perm, ambig_tuples) &&\r
1452 !tmember_of_context(perm, p) )\r
1453 {\r
1454#ifdef DBG_TRAV\r
1455 fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "\n");\r
1456#endif\r
1457 k++;\r
1458 if ( dif==NULL ) dif = perm;\r
1459 else\r
1460 {\r
1461 perm->right = dif;\r
1462 dif = perm;\r
1463 }\r
1464 }\r
1465 else Tfree( perm );\r
1466 }\r
1467\r
1468#ifdef DBG_TRAV\r
1469 preorder(dif);\r
1470 fprintf(stderr, "\n");\r
1471#endif\r
1472\r
1473 for (i=1; i<=CLL_k; i++) free( (char *)ft[i] );\r
1474 free((char *)ft);\r
1475 free((char *)findex);\r
1476\r
1477 return dif;\r
1478}\r
1479\r
1480/* is lookahead sequence t a member of any context tree for any\r
1481 * predicate in p?\r
1482 */\r
1483static int\r
1484#ifdef __USE_PROTOS\r
1485tmember_of_context( Tree *t, Predicate *p )\r
1486#else\r
1487tmember_of_context( t, p )\r
1488Tree *t;\r
1489Predicate *p;\r
1490#endif\r
1491{\r
1492 for (; p!=NULL; p=p->right)\r
1493 {\r
1494 if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST )\r
1495 return tmember_of_context(t, p->down);\r
1496 if ( tmember_constrained(t, p->tcontext) ) return 1;\r
1497 if ( tmember_of_context(t, p->down) ) return 1;\r
1498 }\r
1499 return 0;\r
1500}\r
1501\r
1502int\r
1503#ifdef __USE_PROTOS\r
1504is_single_tuple( Tree *t )\r
1505#else\r
1506is_single_tuple( t )\r
1507Tree *t;\r
1508#endif\r
1509{\r
1510 if ( t == NULL ) return 0;\r
1511 if ( t->right != NULL ) return 0;\r
1512 if ( t->down == NULL ) return 1;\r
1513 return is_single_tuple(t->down);\r
1514}\r
1515\r
1516\r
1517/* MR10 Check that a context guard contains only allowed things */\r
1518/* MR10 (mainly token references). */\r
1519\r
1520#ifdef __USE_PROTOS\r
1521int contextGuardOK(Node *p,int h,int *hmax)\r
1522#else\r
1523int contextGuardOK(p,h,hmax)\r
1524 Node *p;\r
1525 int h;\r
1526 int *hmax;\r
1527#endif\r
1528{\r
1529 Junction *j;\r
1530 TokNode *tn;\r
1531\r
1532 if (p == NULL) return 1;\r
1533 if (p->ntype == nToken) {\r
1534 h++;\r
1535 if (h > *hmax) *hmax=h;\r
1536 tn=(TokNode *)p;\r
1537 if (tn->el_label != NULL) {\r
1538 warnFL(eMsg1("a label (\"%s\") for a context guard element is meaningless",tn->el_label),\r
1539 FileStr[p->file],p->line);\r
1540 };\r
1541 return contextGuardOK( ( (TokNode *) p)->next,h,hmax);\r
1542 } else if (p->ntype == nAction) {\r
1543 goto Fail;\r
1544 } else if (p->ntype == nRuleRef) {\r
1545 goto Fail;\r
1546 } else {\r
1547 require (p->ntype == nJunction,"Unexpected ntype");\r
1548 j=(Junction *) p;\r
1549 if (j->jtype != Generic &&\r
1550 j->jtype != aSubBlk && /* pretty sure this one is allowed */\r
1551/**** j->jtype != aOptBlk && ****/ /* pretty sure this one is allowed */ /* MR11 not any more ! */\r
1552 j->jtype != EndBlk) {\r
1553 errFL("A context guard may not contain an option block: {...} or looping block: (...)* or (...)+",\r
1554 FileStr[p->file],p->line);\r
1555 contextGuardOK(j->p1,h,hmax);\r
1556 return 0;\r
1557 };\r
1558 /* do both p1 and p2 so use | rather than || */\r
1559 return contextGuardOK(j->p2,h,hmax) | contextGuardOK(j->p1,h,hmax);\r
1560 };\r
1561Fail:\r
1562 errFL("A context guard may contain only Token references - guard will be ignored",\r
1563 FileStr[p->file],p->line);\r
1564 contextGuardOK( ( (ActionNode *) p)->next,h,hmax);\r
1565 return 0;\r
1566}\r
1567\r
1568/*\r
1569 * Look at a (...)? generalized-predicate context-guard and compute\r
1570 * either a lookahead set (k==1) or a lookahead tree for k>1. The\r
1571 * k level is determined by the guard itself rather than the LL_k\r
1572 * variable. For example, ( A B )? is an LL(2) guard and ( ID )?\r
1573 * is an LL(1) guard. For the moment, you can only have a single\r
1574 * tuple in the guard. Physically, the block must look like this\r
1575 * --o-->TOKEN-->o-->o-->TOKEN-->o-- ... -->o-->TOKEN-->o--\r
1576 * An error is printed for any other type.\r
1577 */\r
1578Predicate *\r
1579#ifdef __USE_PROTOS\r
1580computePredFromContextGuard(Graph blk,int *msgDone) /* MR10 */\r
1581#else\r
1582computePredFromContextGuard(blk,msgDone) /* MR10 */\r
1583 Graph blk;\r
1584 int *msgDone; /* MR10 */\r
1585#endif\r
1586{\r
1587 Junction *junc = (Junction *)blk.left, *p;\r
1588 Tree *t=NULL;\r
1589 Predicate *pred = NULL;\r
1590 set scontext, rk;\r
1591 int ok;\r
1592 int hmax=0;\r
1593\r
1594 require(junc!=NULL && junc->ntype == nJunction, "bad context guard");\r
1595\r
1596/* MR10 Check for anything other than Tokens and generic junctions */\r
1597\r
1598 *msgDone=0; /* MR10 */\r
1599 ok=contextGuardOK( (Node *)junc,0,&hmax); /* MR10 */\r
1600 if (! ok) { /* MR10 */\r
1601 *msgDone=1; /* MR10 */\r
1602 return NULL; /* MR10 */\r
1603 }; /* MR10 */\r
1604 if (hmax == 0) {\r
1605errFL("guard is 0 tokens long",FileStr[junc->file],junc->line); /* MR11 */\r
1606 *msgDone=1;\r
1607 return NULL;\r
1608 };\r
1609 if (hmax > CLL_k) { /* MR10 */\r
1610errFL(eMsgd2("guard is %d tokens long - lookahead is limited to max(k,ck)==%d", /* MR10 */\r
1611 hmax,CLL_k), /* MR10 */\r
1612 FileStr[junc->file],junc->line); /* MR10 */\r
1613 *msgDone=1; /* MR10 */\r
1614 return NULL; /* MR10 */\r
1615 }; /* MR10 */\r
1616\r
1617 rk = empty;\r
1618 p = junc;\r
1619 pred = new_pred();\r
1620 pred->k = hmax; /* MR10 should be CLL_k, not LLK ? */\r
1621 if (hmax > 1 ) /* MR10 was LL_k */\r
1622 {\r
1623 ConstrainSearch = 0;\r
1624 ContextGuardTRAV = 1;\r
1625 TRAV(p, hmax, &rk, t); /* MR10 was LL_k */\r
1626 ContextGuardTRAV = 0;\r
1627 set_free(rk);\r
1628 t = tshrink( t );\r
1629 t = tflatten( t );\r
1630 t = tleft_factor( t );\r
1631/*\r
1632 fprintf(stderr, "ctx guard:");\r
1633 preorder(t);\r
1634 fprintf(stderr, "\n");\r
1635*/\r
1636 pred->tcontext = t;\r
1637 }\r
1638 else\r
1639 {\r
1640 REACH(p, 1, &rk, scontext);\r
1641 require(set_nil(rk), "rk != nil");\r
1642 set_free(rk);\r
1643/*\r
1644 fprintf(stderr, "LL(1) ctx guard is:");\r
1645 s_fprT(stderr, scontext);\r
1646 fprintf(stderr, "\n");\r
1647*/\r
1648 pred->scontext[1] = scontext;\r
1649 }\r
1650\r
1651 list_add(&ContextGuardPredicateList,pred); /* MR13 */\r
1652\r
1653 return pred;\r
1654}\r
1655\r
1656/* MR13\r
1657 When the context guard is originally computed the\r
1658 meta-tokens are not known.\r
1659*/\r
1660\r
1661#ifdef __USE_PROTOS\r
1662void recomputeContextGuard(Predicate *pred)\r
1663#else\r
1664void recomputeContextGuard(pred)\r
1665 Predicate *pred;\r
1666#endif\r
1667{\r
1668 Tree * t=NULL;\r
1669 set scontext;\r
1670 set rk;\r
1671 ActionNode * actionNode;\r
1672 Junction * p;\r
1673\r
1674 actionNode=pred->source;\r
1675 require (actionNode != NULL,"context predicate's source == NULL");\r
1676\r
1677 p=actionNode->guardNodes;\r
1678 require (p != NULL,"context predicate's guardNodes == NULL");\r
1679\r
1680 rk = empty;\r
1681 if (pred->k > 1 )\r
1682 {\r
1683 ConstrainSearch = 0;\r
1684 ContextGuardTRAV = 1;\r
1685 TRAV(p, pred->k, &rk, t);\r
1686 ContextGuardTRAV = 0;\r
1687 set_free(rk);\r
1688 t = tshrink( t );\r
1689 t = tflatten( t );\r
1690 t = tleft_factor( t );\r
1691 Tfree(pred->tcontext);\r
1692 pred->tcontext = t;\r
1693 }\r
1694 else\r
1695 {\r
1696 REACH(p, 1, &rk, scontext);\r
1697 require(set_nil(rk), "rk != nil");\r
1698 set_free(rk);\r
1699 set_free(pred->scontext[1]);\r
1700 pred->scontext[1] = scontext;\r
1701 }\r
1702}\r
1703\r
1704/* MR11 - had enough of flags yet ? */\r
1705\r
1706int MR_AmbSourceSearch=0;\r
1707int MR_AmbSourceSearchGroup=0;\r
1708int MR_AmbSourceSearchChoice=0;\r
1709int MR_AmbSourceSearchLimit=0;\r
1710int MR_matched_AmbAidRule=0;\r
1711\r
1712static set *matchSets[2]={NULL,NULL};\r
1713static int *tokensInChain=NULL;\r
1714static Junction *MR_AmbSourceSearchJ[2];\r
1715\r
1716void MR_traceAmbSourceKclient()\r
1717{\r
1718 int i;\r
1719 set *save_fset;\r
1720 int save_ConstrainSearch;\r
1721 set incomplete;\r
1722 Tree *t;\r
1723\r
1724 if (matchSets[0] == NULL) {\r
1725 matchSets[0]=(set *) calloc (CLL_k+1,sizeof(set));\r
1726 require (matchSets[0] != NULL,"matchSets[0] alloc");\r
1727 matchSets[1]=(set *) calloc (CLL_k+1,sizeof(set));\r
1728 require (matchSets[1] != NULL,"matchSets[1] alloc");\r
1729 };\r
1730\r
1731 for (i=1 ; i <= MR_AmbSourceSearchLimit ; i++) {\r
1732 set_clr(matchSets[0][i]);\r
1733 set_orel( (unsigned) tokensInChain[i],\r
1734 &matchSets[0][i]);\r
1735 set_clr(matchSets[1][i]);\r
1736 set_orel( (unsigned) tokensInChain[i],\r
1737 &matchSets[1][i]);\r
1738 };\r
1739\r
1740 save_fset=fset;\r
1741 save_ConstrainSearch=ConstrainSearch;\r
1742\r
1743\r
1744\r
1745 for (i=0 ; i < 2 ; i++) {\r
1746\r
1747#if 0\r
1748** fprintf(stdout," Choice:%d Depth:%d ",i+1,MR_AmbSourceSearchLimit);\r
1749** fprintf(stdout,"(");\r
1750** for (j=1 ; j <= MR_AmbSourceSearchLimit ; j++) {\r
1751** if (j != 1) fprintf(stdout," ");\r
1752** fprintf(stdout,"%s",TerminalString(tokensInChain[j]));\r
1753** };\r
1754** fprintf(stdout,")\n\n");\r
1755#endif\r
1756\r
1757 fset=matchSets[i];\r
1758\r
1759 MR_AmbSourceSearch=1;\r
1760 MR_MaintainBackTrace=1;\r
1761 MR_AmbSourceSearchChoice=i;\r
1762 ConstrainSearch=1;\r
1763\r
1764 maxk = MR_AmbSourceSearchLimit;\r
1765\r
1766 incomplete=empty;\r
1767 t=NULL;\r
1768\r
1769 constrain = &(fset[1]);\r
1770 MR_pointerStackReset(&MR_BackTraceStack);\r
1771\r
1772 TRAV(MR_AmbSourceSearchJ[i],maxk,&incomplete,t);\r
1773\r
1774 Tfree(t);\r
1775\r
1776 require (set_nil(incomplete),"MR_traceAmbSourceK TRAV incomplete");\r
1777 require (MR_BackTraceStack.count == 0,"K: MR_BackTraceStack.count != 0");\r
1778\r
1779 set_free(incomplete);\r
1780 };\r
1781\r
1782 ConstrainSearch=save_ConstrainSearch;\r
1783 fset=save_fset;\r
1784 MR_AmbSourceSearch=0;\r
1785 MR_MaintainBackTrace=0;\r
1786 MR_AmbSourceSearchChoice=0;\r
1787}\r
1788\r
1789#ifdef __USE_PROTOS\r
1790Tree *tTrunc(Tree *t,int depth)\r
1791#else\r
1792Tree *tTrunc(t,depth)\r
1793 Tree *t;\r
1794#endif\r
1795{\r
1796 Tree *u;\r
1797\r
1798 require ( ! (t == NULL && depth > 0),"tree too short");\r
1799\r
1800 if (depth == 0) return NULL;\r
1801\r
1802 if (t->token == ALT) {\r
1803 u=tTrunc(t->down,depth);\r
1804 } else {\r
1805 u=tnode(t->token);\r
1806 u->down=tTrunc(t->down,depth-1);\r
1807 };\r
1808 if (t->right != NULL) u->right=tTrunc(t->right,depth);\r
1809 return u;\r
1810}\r
1811\r
1812#ifdef __USE_PROTOS\r
1813void MR_iterateOverTree(Tree *t,int chain[])\r
1814#else\r
1815void MR_iterateOverTree(t,chain)\r
1816 Tree *t;\r
1817 int chain[];\r
1818#endif\r
1819{\r
1820 if (t == NULL) return;\r
1821 chain[0]=t->token;\r
1822 if (t->down != NULL) {\r
1823 MR_iterateOverTree(t->down,&chain[1]);\r
1824 } else {\r
1825 MR_traceAmbSourceKclient();\r
1826 };\r
1827 MR_iterateOverTree(t->right,&chain[0]);\r
1828 chain[0]=0;\r
1829}\r
1830\r
1831#ifdef __USE_PROTOS\r
1832void MR_traceAmbSourceK(Tree *t,Junction *alt1,Junction *alt2)\r
1833#else\r
1834void MR_traceAmbSourceK(t,alt1,alt2)\r
1835 Tree *t;\r
1836 Junction *alt1;\r
1837 Junction *alt2;\r
1838#endif\r
1839{\r
1840 int i;\r
1841 int depth;\r
1842 int maxDepth;\r
1843 Tree *truncatedTree;\r
1844\r
1845 if (MR_AmbAidRule == NULL) return;\r
1846\r
1847 if ( ! (\r
1848 strcmp(MR_AmbAidRule,alt1->rname) == 0 ||\r
1849 strcmp(MR_AmbAidRule,alt2->rname) == 0 ||\r
1850 MR_AmbAidLine==alt1->line ||\r
1851 MR_AmbAidLine==alt2->line\r
1852 )\r
1853 ) return;\r
1854\r
1855 MR_matched_AmbAidRule++;\r
1856\r
1857 /* there are no token sets in trees, only in TokNodes */\r
1858\r
1859 MR_AmbSourceSearchJ[0]=analysis_point( (Junction *) alt1->p1);\r
1860 MR_AmbSourceSearchJ[1]=analysis_point( (Junction *) alt2->p1);\r
1861\r
1862 if (tokensInChain == NULL) {\r
1863 tokensInChain=(int *) calloc (CLL_k+1,sizeof(int));\r
1864 require (tokensInChain != NULL,"tokensInChain alloc");\r
1865 };\r
1866\r
1867 MR_AmbSourceSearchGroup=0;\r
1868\r
1869 fprintf(stdout,"\n");\r
1870 fprintf(stdout," Ambiguity Aid ");\r
1871 fprintf(stdout,\r
1872 (MR_AmbAidDepth <= LL_k ?\r
1873 "(-k %d -aa %s %s -aad %d)\n\n" :\r
1874 "(-k %d -aa %s %s [-k value limits -aad %d])\n\n"),\r
1875 LL_k,\r
1876 MR_AmbAidRule,\r
1877 (MR_AmbAidMultiple ? "-aam" : ""),\r
1878 MR_AmbAidDepth);\r
1879\r
1880 for (i=0 ; i < 2 ; i++) {\r
1881 fprintf(stdout," Choice %d: %-25s line %d file %s\n",\r
1882 (i+1),\r
1883 MR_ruleNamePlusOffset( (Node *) MR_AmbSourceSearchJ[i]),\r
1884 MR_AmbSourceSearchJ[i]->line,\r
1885 FileStr[MR_AmbSourceSearchJ[i]->file]);\r
1886 };\r
1887\r
1888 fprintf(stdout,"\n");\r
1889\r
1890 if (MR_AmbAidDepth < LL_k) {\r
1891 maxDepth=MR_AmbAidDepth;\r
1892 } else {\r
1893 maxDepth=LL_k;\r
1894 };\r
1895\r
1896 for (depth=1 ; depth <= maxDepth; depth++) {\r
1897 MR_AmbSourceSearchLimit=depth;\r
1898 if (depth < LL_k) {\r
1899 truncatedTree=tTrunc(t,depth);\r
1900 truncatedTree=tleft_factor(truncatedTree);\r
1901 MR_iterateOverTree(truncatedTree,&tokensInChain[1]); /* <===== */\r
1902 Tfree(truncatedTree);\r
1903 } else {\r
1904 MR_iterateOverTree(t,tokensInChain); /* <===== */\r
1905 };\r
1906 fflush(stdout);\r
1907 fflush(stderr);\r
1908 };\r
1909\r
1910 fprintf(stdout,"\n");\r
1911 MR_AmbSourceSearch=0;\r
1912 MR_MaintainBackTrace=0;\r
1913 MR_AmbSourceSearchGroup=0;\r
1914 MR_AmbSourceSearchChoice=0;\r
1915 MR_AmbSourceSearchLimit=0;\r
1916\r
1917}\r
1918\r
1919\r
1920/* this if for k=1 grammars only\r
1921\r
1922 this is approximate only because of the limitations of linear\r
1923 approximation lookahead. Don't want to do a k=3 search when\r
1924 the user only specified a ck=3 grammar\r
1925*/\r
1926\r
1927#ifdef __USE_PROTOS\r
1928void MR_traceAmbSource(set *matchSets,Junction *alt1, Junction *alt2)\r
1929#else\r
1930void MR_traceAmbSource(matchSets,alt1,alt2)\r
1931 set *matchSets;\r
1932 Junction *alt1;\r
1933 Junction *alt2;\r
1934#endif\r
1935{\r
1936 set *save_fset;\r
1937 Junction *p[2];\r
1938 int i;\r
1939 int j;\r
1940 set *dup_matchSets;\r
1941 set intersection;\r
1942 set incomplete;\r
1943 set tokensUsed;\r
1944 int depth;\r
1945\r
1946 if (MR_AmbAidRule == NULL) return;\r
1947 if ( ! (\r
1948 strcmp(MR_AmbAidRule,alt1->rname) == 0 ||\r
1949 strcmp(MR_AmbAidRule,alt2->rname) == 0 ||\r
1950 MR_AmbAidLine==alt1->line ||\r
1951 MR_AmbAidLine==alt2->line\r
1952 )\r
1953 ) return;\r
1954\r
1955 MR_matched_AmbAidRule++;\r
1956\r
1957 save_fset=fset;\r
1958\r
1959 dup_matchSets=(set *) calloc(CLL_k+1,sizeof(set));\r
1960 require (dup_matchSets != NULL,"Can't allocate dup_matchSets");\r
1961\r
1962 p[0]=analysis_point( (Junction *) alt1->p1);\r
1963 p[1]=analysis_point( (Junction *) alt2->p1);\r
1964\r
1965 fprintf(stdout,"\n");\r
1966\r
1967 fprintf(stdout," Ambiguity Aid ");\r
1968 fprintf(stdout,\r
1969 (MR_AmbAidDepth <= CLL_k ?\r
1970 "(-ck %d -aa %s %s -aad %d)\n\n" :\r
1971 "(-ck %d -aa %s %s [-ck value limits -aad %d])\n\n"),\r
1972 CLL_k,\r
1973 MR_AmbAidRule,\r
1974 (MR_AmbAidMultiple ? "-aam" : ""),\r
1975 MR_AmbAidDepth);\r
1976\r
1977 for (i=0 ; i < 2 ; i++) {\r
1978 fprintf(stdout," Choice %d: %-25s line %d file %s\n",\r
1979 (i+1),\r
1980 MR_ruleNamePlusOffset( (Node *) p[i]),\r
1981 p[i]->line,FileStr[p[i]->file]);\r
1982 };\r
1983\r
1984 for (j=1; j <= CLL_k ; j++) {\r
1985 fprintf(stdout,"\n Intersection of lookahead[%d] sets:\n",j);\r
1986 intersection=set_and(alt1->fset[j],alt2->fset[j]);\r
1987 MR_dumpTokenSet(stdout,2,intersection);\r
1988 set_free(intersection);\r
1989 };\r
1990\r
1991 fprintf(stdout,"\n");\r
1992\r
1993 require (1 <= MR_AmbAidDepth && MR_AmbAidDepth <= CLL_k,\r
1994 "illegal MR_AmbAidDepth");\r
1995\r
1996 MR_AmbSourceSearchGroup=0;\r
1997 for (depth=1; depth <= MR_AmbAidDepth; depth++) {\r
1998 MR_AmbSourceSearchLimit=depth;\r
1999 for (i=0 ; i < 2 ; i++) {\r
2000\r
2001/*** fprintf(stdout," Choice:%d Depth:%d\n\n",i+1,depth); ***/\r
2002\r
2003 for (j=0 ; j <= CLL_k ; j++) { dup_matchSets[j]=set_dup(matchSets[j]); };\r
2004 fset=dup_matchSets;\r
2005\r
2006 fflush(output);\r
2007 fflush(stdout);\r
2008\r
2009 MR_AmbSourceSearch=1;\r
2010 MR_MaintainBackTrace=1;\r
2011 MR_AmbSourceSearchChoice=i;\r
2012\r
2013 maxk = depth;\r
2014 tokensUsed=empty;\r
2015 incomplete=empty;\r
2016\r
2017 constrain = &(fset[1]);\r
2018 MR_pointerStackReset(&MR_BackTraceStack);\r
2019\r
2020 REACH(p[i],depth,&incomplete,tokensUsed);\r
2021\r
2022 fflush(output);\r
2023 fflush(stdout);\r
2024\r
2025 require (set_nil(incomplete),"MR_traceAmbSource REACH incomplete");\r
2026 require (MR_BackTraceStack.count == 0,"1: MR_BackTraceStack.count != 0");\r
2027\r
2028 set_free(incomplete);\r
2029 set_free(tokensUsed);\r
2030\r
2031 for (j=0 ; j <= CLL_k ; j++) { set_free(dup_matchSets[j]); };\r
2032 };\r
2033 };\r
2034\r
2035 fprintf(stdout,"\n");\r
2036\r
2037 MR_AmbSourceSearch=0;\r
2038 MR_MaintainBackTrace=0;\r
2039 MR_AmbSourceSearchGroup=0;\r
2040 MR_AmbSourceSearchChoice=0;\r
2041 MR_AmbSourceSearchLimit=0;\r
2042\r
2043 fset=save_fset;\r
2044 free ( (char *) dup_matchSets);\r
2045}\r
2046\r
2047static int itemCount;\r
2048\r
2049void MR_backTraceDumpItemReset() {\r
2050 itemCount=0;\r
2051}\r
2052\r
2053#ifdef __USE_PROTOS\r
2054void MR_backTraceDumpItem(FILE *f,int skip,Node *n)\r
2055#else\r
2056void MR_backTraceDumpItem(f,skip,n)\r
2057 FILE *f;\r
2058 int skip;\r
2059 Node *n;\r
2060#endif\r
2061{\r
2062 TokNode *tn;\r
2063 RuleRefNode *rrn;\r
2064 Junction *j;\r
2065 ActionNode *a;\r
2066\r
2067 switch (n->ntype) {\r
2068 case nToken:\r
2069 itemCount++; if (skip) goto EXIT;\r
2070 tn=(TokNode *)n;\r
2071 if (set_nil(tn->tset)) {\r
2072 fprintf(f," %2d #token %-23s",itemCount,TerminalString(tn->token));\r
2073 } else {\r
2074 fprintf(f," %2d #tokclass %-20s",itemCount,TerminalString(tn->token));\r
2075 };\r
2076 break;\r
2077 case nRuleRef:\r
2078 itemCount++; if (skip) goto EXIT;\r
2079 rrn=(RuleRefNode *)n;\r
2080 fprintf(f," %2d to %-27s",itemCount,rrn->text);\r
2081 break;\r
2082 case nAction:\r
2083 a=(ActionNode *)n;\r
2084 goto EXIT;\r
2085 case nJunction:\r
2086\r
2087 j=(Junction *)n;\r
2088\r
2089 switch (j->jtype) {\r
2090 case aSubBlk:\r
2091 if (j->guess) {\r
2092 itemCount++; if (skip) goto EXIT;\r
2093 fprintf(f," %2d %-30s",itemCount,"in (...)? block at");\r
2094 break;\r
2095 };\r
2096/****** fprintf(f," %2d %-32s",itemCount,"in (...) block at"); *******/\r
2097/****** break; *******/\r
2098 goto EXIT;\r
2099 case aOptBlk:\r
2100 itemCount++; if (skip) goto EXIT;\r
2101 fprintf(f," %2d %-30s",itemCount,"in {...} block");\r
2102 break;\r
2103 case aLoopBlk:\r
2104 itemCount++; if (skip) goto EXIT;\r
2105 fprintf(f," %2d %-30s",itemCount,"in (...)* block");\r
2106 break;\r
2107 case EndBlk:\r
2108 if (j->alpha_beta_guess_end) {\r
2109 itemCount++; if (skip) goto EXIT;\r
2110 fprintf(f," %2d %-30s",itemCount,"end (...)? block at");\r
2111 break;\r
2112 };\r
2113 goto EXIT;\r
2114/****** fprintf(f," %2d %-32s",itemCount,"end of a block at"); *****/\r
2115/****** break; *****/\r
2116 case RuleBlk:\r
2117 itemCount++; if (skip) goto EXIT;\r
2118 fprintf(f," %2d %-30s",itemCount,j->rname);\r
2119 break;\r
2120 case Generic:\r
2121 goto EXIT;\r
2122 case EndRule:\r
2123 itemCount++; if (skip) goto EXIT;\r
2124 fprintf (f," %2d end %-26s",itemCount,j->rname);\r
2125 break;\r
2126 case aPlusBlk:\r
2127 itemCount++; if (skip) goto EXIT;\r
2128 fprintf(f," %2d %-30s",itemCount,"in (...)+ block");\r
2129 break;\r
2130 case aLoopBegin:\r
2131 goto EXIT;\r
2132 };\r
2133 break;\r
2134 };\r
2135 fprintf(f," %-23s line %-4d %s\n",MR_ruleNamePlusOffset(n),n->line,FileStr[n->file]);\r
2136EXIT:\r
2137 return;\r
2138}\r
2139\r
2140\r
2141static PointerStack previousBackTrace={0,0,NULL};\r
2142\r
2143#ifdef __USE_PROTOS\r
2144void MR_backTraceReport(void)\r
2145#else\r
2146void MR_backTraceReport()\r
2147#endif\r
2148{\r
2149 int i;\r
2150 int match = 0;\r
2151 int limitMatch;\r
2152\r
2153 Node *p;\r
2154 TokNode *tn;\r
2155 set remainder;\r
2156 int depth;\r
2157\r
2158 /* Even when doing a k=2 search this routine can get\r
2159 called when there is only 1 token on the stack.\r
2160 This is because something like rRuleRef can change\r
2161 the search value of k from 2 to 1 temporarily.\r
2162 It does this because the it wants to know the k=1\r
2163 first set before it does a k=2 search\r
2164 */\r
2165\r
2166 depth=0;\r
2167 for (i=0; i < MR_BackTraceStack.count ; i++) {\r
2168 p=(Node *) MR_BackTraceStack.data[i];\r
2169 if (p->ntype == nToken) depth++;\r
2170 };\r
2171\r
2172/* MR14 */ if (MR_AmbSourceSearch) {\r
2173/* MR14 */ require (depth <= MR_AmbSourceSearchLimit,"depth > MR_AmbSourceSearchLimit");\r
2174/* MR14 */ }\r
2175\r
2176 /* MR23 THM - Traceback report was being called at the wrong time for -alpha reports */\r
2177 /* Reported by Arpad Beszedes (beszedes@inf.u-szeged.hu) */\r
2178\r
2179 if (MR_AmbSourceSearchLimit == 0 || depth < MR_AmbSourceSearchLimit) {\r
2180 return;\r
2181 };\r
2182\r
2183 MR_backTraceDumpItemReset();\r
2184\r
2185 limitMatch=MR_BackTraceStack.count;\r
2186 if (limitMatch > previousBackTrace.count) {\r
2187 limitMatch=previousBackTrace.count;\r
2188 };\r
2189\r
2190 for (match=0; match < limitMatch; match++) {\r
2191 if (MR_BackTraceStack.data[match] !=\r
2192 previousBackTrace.data[match]) {\r
2193 break;\r
2194 };\r
2195 };\r
2196\r
2197 /* not sure at the moment why there would be duplicates */\r
2198\r
2199 if (match != MR_BackTraceStack.count) {\r
2200\r
2201 fprintf(stdout," Choice:%d Depth:%d Group:%d",\r
2202 (MR_AmbSourceSearchChoice+1),\r
2203 MR_AmbSourceSearchLimit,\r
2204 ++MR_AmbSourceSearchGroup);\r
2205\r
2206 depth=0;\r
2207 fprintf(stdout," (");\r
2208 for (i=0; i < MR_BackTraceStack.count ; i++) {\r
2209 p=(Node *) MR_BackTraceStack.data[i];\r
2210 if (p->ntype != nToken) continue;\r
2211 tn=(TokNode *)p;\r
2212 if (depth != 0) fprintf(stdout," ");\r
2213 fprintf(stdout,TerminalString(tn->token));\r
2214 depth++;\r
2215 if (! MR_AmbAidMultiple) {\r
2216 if (set_nil(tn->tset)) {\r
2217 set_rm( (unsigned) tn->token,fset[depth]);\r
2218 } else {\r
2219 remainder=set_dif(fset[depth],tn->tset);\r
2220 set_free(fset[depth]);\r
2221 fset[depth]=remainder;\r
2222 };\r
2223 };\r
2224 };\r
2225 fprintf(stdout,")\n");\r
2226\r
2227 for (i=0; i < MR_BackTraceStack.count ; i++) {\r
2228 MR_backTraceDumpItem(stdout, (i<match) ,(Node *) MR_BackTraceStack.data[i]);\r
2229 };\r
2230 fprintf(stdout,"\n");\r
2231 fflush(stdout);\r
2232\r
2233 MR_pointerStackReset(&previousBackTrace);\r
2234\r
2235 for (i=0; i < MR_BackTraceStack.count ; i++) {\r
2236 MR_pointerStackPush(&previousBackTrace,MR_BackTraceStack.data[i]);\r
2237 };\r
2238\r
2239 };\r
2240}\r
2241\r
2242#ifdef __USE_PROTOS\r
2243void MR_setConstrainPointer(set * newConstrainValue)\r
2244#else\r
2245void MR_setConstrainPointer(newConstrainValue)\r
2246 set * newConstrainValue;\r
2247#endif\r
2248{\r
2249 constrain=newConstrainValue;\r
2250}\r
EFI Development Kit II mirror for PVE