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