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 |
51 | static int *findex;\r |
52 | set *fset; /* MR11 make global */\r |
53 | static unsigned **ftbl;\r |
54 | static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */\r |
55 | int ConstrainSearch;\r |
56 | int maxk; /* set to initial k upon tree construction request */\r |
57 | /* MR11 make global */\r |
58 | static Tree *FreeList = NULL;\r |
59 | \r |
60 | #ifdef __USE_PROTOS\r |
61 | static int tmember_of_context(Tree *, Predicate *);\r |
62 | #else\r |
63 | static int tmember_of_context();\r |
64 | #endif\r |
65 | \r |
66 | #if TREE_DEBUG\r |
67 | set set_of_tnodes_in_use;\r |
68 | int 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 |
75 | void\r |
76 | #ifdef __USE_PROTOS\r |
77 | preorder( Tree *tree )\r |
78 | #else\r |
79 | preorder( tree )\r |
80 | Tree *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 |
94 | int MR_tree_matches_constraints(int k,set * constrain,Tree *t)\r |
95 | #else\r |
96 | int 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 |
142 | static int pruneCount=0;\r |
143 | static int prunePeak=200;\r |
144 | \r |
145 | Tree *\r |
146 | #ifdef __USE_PROTOS\r |
147 | prune( Tree *t, int k )\r |
148 | #else\r |
149 | prune( t, k )\r |
150 | Tree *t;\r |
151 | int 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 |
187 | Tree *tmake(Tree *root, ...)\r |
188 | #else\r |
189 | Tree *tmake(va_alist)\r |
190 | va_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 |
229 | Tree *\r |
230 | #ifdef __USE_PROTOS\r |
231 | tnode( int tok )\r |
232 | #else\r |
233 | tnode( tok )\r |
234 | int 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 |
295 | static Tree *\r |
296 | #ifdef __USE_PROTOS\r |
297 | eofnode( int k )\r |
298 | #else\r |
299 | eofnode( k )\r |
300 | int 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 |
315 | void\r |
316 | #ifdef __USE_PROTOS\r |
317 | _Tfree( Tree *t )\r |
318 | #else\r |
319 | _Tfree( t )\r |
320 | Tree *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 |
340 | Tree *\r |
341 | #ifdef __USE_PROTOS\r |
342 | tdup( Tree *t )\r |
343 | #else\r |
344 | tdup( t )\r |
345 | Tree *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 |
359 | Tree *\r |
360 | #ifdef __USE_PROTOS\r |
361 | tdup_chain( Tree *t )\r |
362 | #else\r |
363 | tdup_chain( t )\r |
364 | Tree *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 |
376 | Tree *\r |
377 | #ifdef __USE_PROTOS\r |
378 | tappend( Tree *t, Tree *u )\r |
379 | #else\r |
380 | tappend( t, u )\r |
381 | Tree *t;\r |
382 | Tree *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 |
399 | void\r |
400 | #ifdef __USE_PROTOS\r |
401 | Tfree( Tree *t )\r |
402 | #else\r |
403 | Tfree( t )\r |
404 | Tree *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 |
429 | Tree *\r |
430 | #ifdef __USE_PROTOS\r |
431 | tlink( Tree *t, Tree *u, int remaining_k )\r |
432 | #else\r |
433 | tlink( t, u, remaining_k )\r |
434 | Tree *t;\r |
435 | Tree *u;\r |
436 | int 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 |
463 | Tree *\r |
464 | #ifdef __USE_PROTOS\r |
465 | tshrink( Tree *t )\r |
466 | #else\r |
467 | tshrink( t )\r |
468 | Tree *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 |
504 | Tree *\r |
505 | #ifdef __USE_PROTOS\r |
506 | tflatten( Tree *t )\r |
507 | #else\r |
508 | tflatten( t )\r |
509 | Tree *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 |
530 | Tree *\r |
531 | #ifdef __USE_PROTOS\r |
532 | tJunc( Junction *p, int k, set *rk )\r |
533 | #else\r |
534 | tJunc( p, k, rk )\r |
535 | Junction *p;\r |
536 | int k;\r |
537 | set *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 |
678 | Tree *\r |
679 | #ifdef __USE_PROTOS\r |
680 | tRuleRef( RuleRefNode *p, int k, set *rk_out )\r |
681 | #else\r |
682 | tRuleRef( p, k, rk_out )\r |
683 | RuleRefNode *p;\r |
684 | int k;\r |
685 | set *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 |
748 | Tree *\r |
749 | #ifdef __USE_PROTOS\r |
750 | tToken( TokNode *p, int k, set *rk )\r |
751 | #else\r |
752 | tToken( p, k, rk )\r |
753 | TokNode *p;\r |
754 | int k;\r |
755 | set *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 |
875 | Tree *\r |
876 | #ifdef __USE_PROTOS\r |
877 | tAction( ActionNode *p, int k, set *rk )\r |
878 | #else\r |
879 | tAction( p, k, rk )\r |
880 | ActionNode *p;\r |
881 | int k;\r |
882 | set *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 |
1008 | EXIT:\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 |
1021 | int\r |
1022 | #ifdef __USE_PROTOS\r |
1023 | tmember( Tree *e, Tree *s )\r |
1024 | #else\r |
1025 | tmember( e, s )\r |
1026 | Tree *e;\r |
1027 | Tree *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 |
1051 | int\r |
1052 | #ifdef __USE_PROTOS\r |
1053 | tmember_constrained( Tree *e, Tree *s)\r |
1054 | #else\r |
1055 | tmember_constrained( e, s )\r |
1056 | Tree *e;\r |
1057 | Tree *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 |
1079 | Tree *\r |
1080 | #ifdef __USE_PROTOS\r |
1081 | tleft_factor( Tree *t )\r |
1082 | #else\r |
1083 | tleft_factor( t )\r |
1084 | Tree *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 |
1118 | Tree *\r |
1119 | #ifdef __USE_PROTOS\r |
1120 | trm_perm( Tree *t, Tree *p )\r |
1121 | #else\r |
1122 | trm_perm( t, p )\r |
1123 | Tree *t;\r |
1124 | Tree *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 |
1162 | void\r |
1163 | #ifdef __USE_PROTOS\r |
1164 | tcvt( set *fset, Tree *perm )\r |
1165 | #else\r |
1166 | tcvt( fset, perm )\r |
1167 | set *fset;\r |
1168 | Tree *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 |
1179 | Tree *\r |
1180 | #ifdef __USE_PROTOS\r |
1181 | permute( int k, int max_k )\r |
1182 | #else\r |
1183 | permute( k, max_k )\r |
1184 | int 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 |
1210 | Tree *\r |
1211 | #ifdef __USE_PROTOS\r |
1212 | VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig )\r |
1213 | #else\r |
1214 | VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig )\r |
1215 | Junction *alt1;\r |
1216 | Junction *alt2;\r |
1217 | unsigned **ft;\r |
1218 | set *fs;\r |
1219 | Tree **t;\r |
1220 | Tree **u;\r |
1221 | int *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 |
1339 | static Tree *\r |
1340 | #ifdef __USE_PROTOS\r |
1341 | bottom_of_chain( Tree *t )\r |
1342 | #else\r |
1343 | bottom_of_chain( t )\r |
1344 | Tree *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 |
1355 | Tree *\r |
1356 | #ifdef __USE_PROTOS\r |
1357 | make_tree_from_sets( set *fset1, set *fset2 )\r |
1358 | #else\r |
1359 | make_tree_from_sets( fset1, fset2 )\r |
1360 | set *fset1;\r |
1361 | set *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 |
1403 | Tree *\r |
1404 | #ifdef __USE_PROTOS\r |
1405 | tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 )\r |
1406 | #else\r |
1407 | tdif( ambig_tuples, p, fset1, fset2 )\r |
1408 | Tree *ambig_tuples;\r |
1409 | Predicate *p;\r |
1410 | set *fset1;\r |
1411 | set *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 |
1483 | static int\r |
1484 | #ifdef __USE_PROTOS\r |
1485 | tmember_of_context( Tree *t, Predicate *p )\r |
1486 | #else\r |
1487 | tmember_of_context( t, p )\r |
1488 | Tree *t;\r |
1489 | Predicate *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 |
1502 | int\r |
1503 | #ifdef __USE_PROTOS\r |
1504 | is_single_tuple( Tree *t )\r |
1505 | #else\r |
1506 | is_single_tuple( t )\r |
1507 | Tree *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 |
1521 | int contextGuardOK(Node *p,int h,int *hmax)\r |
1522 | #else\r |
1523 | int 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 |
1561 | Fail:\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 |
1578 | Predicate *\r |
1579 | #ifdef __USE_PROTOS\r |
1580 | computePredFromContextGuard(Graph blk,int *msgDone) /* MR10 */\r |
1581 | #else\r |
1582 | computePredFromContextGuard(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 |
1605 | errFL("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 |
1610 | errFL(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 |
1662 | void recomputeContextGuard(Predicate *pred)\r |
1663 | #else\r |
1664 | void 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 |
1706 | int MR_AmbSourceSearch=0;\r |
1707 | int MR_AmbSourceSearchGroup=0;\r |
1708 | int MR_AmbSourceSearchChoice=0;\r |
1709 | int MR_AmbSourceSearchLimit=0;\r |
1710 | int MR_matched_AmbAidRule=0;\r |
1711 | \r |
1712 | static set *matchSets[2]={NULL,NULL};\r |
1713 | static int *tokensInChain=NULL;\r |
1714 | static Junction *MR_AmbSourceSearchJ[2];\r |
1715 | \r |
1716 | void 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 |
1790 | Tree *tTrunc(Tree *t,int depth)\r |
1791 | #else\r |
1792 | Tree *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 |
1813 | void MR_iterateOverTree(Tree *t,int chain[])\r |
1814 | #else\r |
1815 | void 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 |
1832 | void MR_traceAmbSourceK(Tree *t,Junction *alt1,Junction *alt2)\r |
1833 | #else\r |
1834 | void 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 |
1928 | void MR_traceAmbSource(set *matchSets,Junction *alt1, Junction *alt2)\r |
1929 | #else\r |
1930 | void 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 |
2047 | static int itemCount;\r |
2048 | \r |
2049 | void MR_backTraceDumpItemReset() {\r |
2050 | itemCount=0;\r |
2051 | }\r |
2052 | \r |
2053 | #ifdef __USE_PROTOS\r |
2054 | void MR_backTraceDumpItem(FILE *f,int skip,Node *n)\r |
2055 | #else\r |
2056 | void 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 |
2136 | EXIT:\r |
2137 | return;\r |
2138 | }\r |
2139 | \r |
2140 | \r |
2141 | static PointerStack previousBackTrace={0,0,NULL};\r |
2142 | \r |
2143 | #ifdef __USE_PROTOS\r |
2144 | void MR_backTraceReport(void)\r |
2145 | #else\r |
2146 | void 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 |
2243 | void MR_setConstrainPointer(set * newConstrainValue)\r |
2244 | #else\r |
2245 | void MR_setConstrainPointer(newConstrainValue)\r |
2246 | set * newConstrainValue;\r |
2247 | #endif\r |
2248 | {\r |
2249 | constrain=newConstrainValue;\r |
2250 | }\r |