]>
Commit | Line | Data |
---|---|---|
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 |