1 /* 2 * mrhoist.c 3 * 4 * SOFTWARE RIGHTS 5 * 6 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool 7 * Set (PCCTS) -- PCCTS is in the public domain. An individual or 8 * company may do whatever they wish with source code distributed with 9 * PCCTS or the code generated by PCCTS, including the incorporation of 10 * PCCTS, or its output, into commerical software. 11 * 12 * We encourage users to develop software with PCCTS. However, we do ask 13 * that credit is given to us for developing PCCTS. By "credit", 14 * we mean that if you incorporate our source code into one of your 15 * programs (commercial product, research project, or otherwise) that you 16 * acknowledge this fact somewhere in the documentation, research report, 17 * etc... If you like PCCTS and have developed a nice tool with the 18 * output, please mention that you developed it using PCCTS. In 19 * addition, we ask that this header remain intact in our source code. 20 * As long as these guidelines are kept, we expect to continue enhancing 21 * this system and expect to make other tools available as they are 22 * completed. 23 * 24 * ANTLR 1.33MR10 25 * 26 */ 27 28 #include <stdio.h> 29 30 #include "pcctscfg.h" 31 32 #include "set.h" 33 #include "syn.h" 34 #include "hash.h" 35 #include "generic.h" 36 #include "dlgdef.h" 37 #include <ctype.h> 38 39 #ifdef __USE_PROTOS 40 void dumppred(Predicate *); 41 #else 42 void dumppred(); 43 #endif 44 45 /* 46 Try to determine whether predicate "first" is true for 47 all cases where "second" is true. Comparison takes place 48 without regard to context. 49 Assumes that predicate symbols have been expanded. 50 Assumes that there are no NAND or NOR nodes 51 52 */ 53 54 #ifdef __USE_PROTOS 55 int MR_secondPredicateUnreachable(Predicate *first,Predicate *second) 56 #else 57 int MR_secondPredicateUnreachable(first,second) 58 Predicate *first; 59 Predicate *second; 60 #endif 61 { 62 Predicate *f; 63 Predicate *s; 64 65 if (first == NULL) { 66 return 1; 67 } else if (second == NULL) { 68 return 0; 69 } else if (first->down == NULL && second->down == NULL) { 70 if (first->source == second->source && 71 first->inverted == second->inverted) { 72 return 1; /* look identical - will never reach alt2 */ 73 } else { 74 return 0; /* look different */ 75 }; 76 } else if (first->down == NULL && second->down != NULL) { 77 78 if (second->expr == PRED_AND_LIST) { 79 80 /* unreachable if first covers any child of second */ 81 82 for (s=second->down; s != NULL; s=s->right) { 83 if (MR_secondPredicateUnreachable(first,s)) { 84 return 1; 85 }; 86 }; 87 return 0; 88 } else if (second->expr == PRED_OR_LIST) { 89 90 /* unreachable if first covers every child of second */ 91 92 for (s=second->down; s != NULL; s=s->right) { 93 if (!MR_secondPredicateUnreachable(first,s)) { 94 return 0; 95 }; 96 }; 97 return 1; 98 } else { 99 require (0,"Illegal pred->expr"); 100 return 0; /* MR20 Make compiler happy */ 101 }; 102 } else if (first->down != NULL && second->down == NULL) { 103 if (first->expr == PRED_AND_LIST) { 104 105 /* unreachable if every child of first covers second */ 106 107 for (f=first->down; f != NULL; f=f->right) { 108 if (!MR_secondPredicateUnreachable(f,second)) { 109 return 0; 110 }; 111 }; 112 return 1; 113 } else if (first->expr == PRED_OR_LIST) { 114 115 /* unreachable if any child of first covers second */ 116 117 for (f=first->down; f != NULL; f=f->right) { 118 if (MR_secondPredicateUnreachable(f,second)) { 119 return 1; 120 }; 121 }; 122 return 0; 123 } else { 124 require (0,"Illegal predicate->expr"); 125 return 0; /* MR20 Make compiler happy */ 126 }; 127 } else { 128 129 if (first->expr == PRED_AND_LIST && second->expr == PRED_AND_LIST) { 130 131 /* unreachable if each child of first covers at least one child of second */ 132 133 for (f=first->down; f != NULL ; f=f->right) { 134 for (s=second->down; s != NULL ; s=s->right) { 135 if (MR_secondPredicateUnreachable(f,s)) goto A_next_f; 136 }; 137 return 0; 138 A_next_f: 139 continue; 140 }; 141 return 1; 142 143 } else if (first->expr == PRED_AND_LIST && second->expr == PRED_OR_LIST) { 144 145 /* unreachable if each child of first covers ALL of second's children */ 146 147 for (f=first->down; f != NULL ; f=f->right) { 148 for (s=second->down; s != NULL ; s=s->right) { 149 if (!MR_secondPredicateUnreachable(f,s)) return 0; 150 }; 151 }; 152 return 1; 153 154 } else if (first->expr == PRED_OR_LIST && second->expr == PRED_AND_LIST) { 155 156 /* unreachable if any child of second is covered by any child of first */ 157 158 for (f=first->down; f != NULL ; f=f->right) { 159 for (s=second->down; s != NULL ; s=s->right) { 160 if (MR_secondPredicateUnreachable(f,s)) return 1; 161 }; 162 }; 163 return 0; 164 165 } else if (first->expr == PRED_OR_LIST && second->expr == PRED_OR_LIST) { 166 167 /* unreachable if every child of second is covered by some child of first */ 168 169 for (f=first->down; f != NULL ; f=f->right) { 170 for (s=second->down; s != NULL ; s=s->right) { 171 if (MR_secondPredicateUnreachable(f,s)) goto B_next_f; 172 }; 173 return 0; 174 B_next_f: 175 continue; 176 }; 177 return 1; 178 179 } else { 180 require (0,"Illegal predicate->expr"); 181 return 0; /* MR20 Make compiler happy */ 182 }; 183 }; 184 return 0; /* MR20 MSVC 5.0 complains about missing return statement */ 185 } 186 187 #ifdef __USE_PROTOS 188 void MR_xxxIndent(FILE *f,int depth) 189 #else 190 void MR_xxxIndent(f,depth) 191 FILE *f; 192 int depth; 193 #endif 194 { 195 int i; 196 197 for (i=0; i<depth ; i++) { 198 fprintf(f," "); 199 }; 200 } 201 202 #ifdef __USE_PROTOS 203 void MR_stderrIndent(int depth) 204 #else 205 void MR_stderrIndent(depth) 206 int depth; 207 #endif 208 { 209 MR_xxxIndent(stderr,depth); 210 } 211 212 #ifdef __USE_PROTOS 213 void MR_outputIndent(int depth) 214 #else 215 void MR_outputIndent(depth) 216 int depth; 217 #endif 218 { 219 MR_xxxIndent(output,depth); 220 } 221 222 #ifdef __USE_PROTOS 223 void MR_set_reuse(set *s) 224 #else 225 void MR_set_reuse(s) 226 set *s; 227 #endif 228 { 229 set_free(*s); 230 *s=empty; 231 } 232 233 #ifdef __USE_PROTOS 234 void MR_dumpPredRuleRefStack(FILE *iounit,int indent) 235 #else 236 void MR_dumpPredRuleRefStack(iounit,indent) 237 FILE *iounit; 238 int indent; 239 #endif 240 { 241 int i; 242 int j; 243 int count=MR_PredRuleRefStack.count; 244 RuleRefNode *rrn=NULL; 245 Junction *lastOne; 246 247 if (count == 0) { 248 fprintf(iounit,"empty\n"); 249 return; 250 }; 251 for (i=0; i < count; i++) { 252 rrn=(RuleRefNode *) MR_PredRuleRefStack.data[i]; 253 for (j=0; j<indent; j++) fprintf(iounit," "); 254 fprintf(iounit,"#%-2d in rule %s (line %d %s) to rule %s\n", 255 i,rrn->rname,rrn->line,FileStr[rrn->file],rrn->text); 256 }; 257 lastOne=MR_ruleReferenced(rrn); 258 if (lastOne != NULL) { 259 for (j=0; j<indent; j++) fprintf(iounit," "); 260 fprintf(iounit,"#%-2d in rule %s (line %d %s)\n", 261 count,lastOne->rname,lastOne->line,FileStr[lastOne->file]); 262 }; 263 } 264 265 #ifdef __USE_PROTOS 266 void MR_dumpTreeF(FILE *f,int depth,Tree *tree,int across) 267 #else 268 void MR_dumpTreeF(f,depth,tree,across) 269 FILE *f; 270 Tree *tree; 271 int depth; 272 int across; 273 #endif 274 { 275 int newAcross=across; 276 277 if (tree == NULL ) return; 278 if (tree->down != NULL ) { 279 fprintf(output,"\n"); 280 MR_outputIndent(depth); 281 fprintf(output, "(root ="); 282 }; 283 if (tree->token == ALT ) { 284 fprintf(output," %-16s","Alt"); 285 } else if (tree->token==EpToken ) { 286 fprintf(output,"(%d)%13s",tree->v.rk," "); 287 } else { 288 fprintf(output," %-16s",TerminalString(tree->token)); 289 }; 290 if (tree->down != NULL) { 291 fprintf(output,"\n"); 292 MR_outputIndent(depth+1); 293 MR_dumpTreeF(f,depth+1,tree->down,1); 294 newAcross=0; 295 fprintf(output,"\n"); 296 MR_outputIndent(depth); 297 fprintf(output,")"); 298 }; 299 if (newAcross > 3) { 300 fprintf(output,"\n"); 301 MR_outputIndent(depth); 302 newAcross=0; 303 }; 304 MR_dumpTreeF(f,depth,tree->right,newAcross+1); 305 } 306 307 #ifdef __USE_PROTOS 308 void MR_dumpTreeX(int depth,Tree *tree,int across) 309 #else 310 void MR_dumpTreeX(depth,tree,across) 311 Tree *tree; 312 int depth; 313 int across; 314 #endif 315 { 316 MR_dumpTreeF(output,depth,tree,across); 317 } 318 319 #ifdef __USE_PROTOS 320 void MR_dumpTokenSet(FILE *f,int depth,set s) 321 #else 322 void MR_dumpTokenSet(f,depth,s) 323 FILE *f; 324 int depth; 325 set s; 326 #endif 327 { 328 int i; 329 int j; 330 331 unsigned *pdq; 332 333 if (set_nil(s)) { 334 fprintf(f,"\n"); 335 MR_xxxIndent(f,depth+1); 336 fprintf(f,"nil\n"); 337 return; 338 }; 339 340 pdq=set_pdq(s); 341 require(pdq != NULL,"set_pdq failed"); 342 i=0; 343 for (i=0 ; ; i=i+4) { 344 fprintf(f,"\n"); 345 MR_xxxIndent(f,depth+1); 346 for (j=0; j < 4 ; j++) { 347 if (pdq[i+j] == nil) break; 348 fprintf(f," %-16s",TerminalString(pdq[i+j])); 349 }; 350 if (pdq[i+j] == nil) break; 351 }; 352 fprintf(f,"\n"); 353 free( (char *) pdq); 354 } 355 356 #ifdef __USE_PROTOS 357 void MR_dumpPred1(int depth,Predicate *p,int withContext) 358 #else 359 void MR_dumpPred1(depth,p,withContext) 360 int depth; 361 Predicate *p; 362 int withContext; 363 #endif 364 { 365 unsigned k; 366 367 if (p == NULL) { 368 MR_outputIndent(depth); 369 fprintf(output,"The predicate is empty (or always true)\n\n"); 370 return; 371 }; 372 if (p->down != NULL) { 373 MR_outputIndent(depth); 374 if (p->inverted) { 375 376 /* MR14a Left out print expression in fprintf 377 Reported by Manuel Kessler (mlkessle (at) cip.physik.uni-wuerzburg.de) 378 */ 379 380 if (p->expr == PRED_AND_LIST) fprintf(output,"%s NAND (not AND) expr\n\n",p->expr); 381 if (p->expr == PRED_OR_LIST) fprintf(output,"%s NOR (not OR) expr\n\n",p->expr); 382 } else { 383 fprintf(output,"%s expr\n\n",p->expr); 384 }; 385 } else { 386 MR_outputIndent(depth); 387 fprintf(output,"pred %s <<%s>>?\n", 388 (p->inverted ? " *not*" : ""), 389 (p->expr == NULL ? "null expr" : p->expr)); 390 MR_outputIndent(depth+1); 391 fprintf(output," "); 392 fprintf(output," depth=k=%d",p->k); 393 if (p->source != NULL && p->source->guardpred) { 394 fprintf(output," (\"=>\" guard)"); 395 } 396 if (p->source != NULL && p->source->ampersandPred != NULL) { 397 fprintf(output," (\"&&\" guard)"); 398 }; 399 k=set_int(p->completionSet); 400 if (k != nil) { 401 fprintf(output," Incomplete Set at k=%d !",k); 402 }; 403 k=set_int(p->completionTree); 404 if (k != nil) { 405 fprintf(output," Incomplete Tree at k=%d !",k); 406 }; 407 if (p->source != NULL) { 408 fprintf(output," rule %s line %d %s", 409 p->source->rname,p->source->line,FileStr[p->source->file]); 410 }; 411 fprintf(output,"\n"); 412 if (withContext && 413 (HoistPredicateContext || 414 ! set_nil(p->scontext[1]) || 415 p->tcontext != NULL)) { 416 if (p->k == 1) { 417 MR_outputIndent(depth+1); 418 fprintf(output,"set context: "); 419 MR_dumpTokenSet(output,depth+1,p->scontext[1]); 420 } 421 if (p->k != 1) { 422 MR_outputIndent(depth+1); 423 fprintf(output,"tree context:"); 424 if (p->tcontext == NULL) { 425 fprintf(output," null"); 426 } else { 427 MR_dumpTreeX(depth+2,p->tcontext,0); 428 }; 429 fprintf(output,"\n"); 430 }; 431 }; 432 fprintf(output,"\n"); 433 }; 434 if (p->down != NULL) { 435 MR_dumpPred1(depth+1,p->down,withContext); 436 }; 437 if (p->right != NULL) { 438 MR_dumpPred1(depth,p->right,withContext); 439 }; 440 } 441 442 #ifdef __USE_PROTOS 443 void MR_dumpPred(Predicate *p,int withContext) 444 #else 445 void MR_dumpPred(p,withContext) 446 Predicate *p; 447 int withContext; 448 #endif 449 { 450 MR_dumpPred1(0,p,withContext); 451 } 452 453 #ifdef __USE_PROTOS 454 Tree * MR_make_tree_from_set(set s) 455 #else 456 Tree * MR_make_tree_from_set(s) 457 set s; 458 #endif 459 { 460 Tree *t=NULL; 461 Tree *node; 462 Tree **tp=&t; 463 int i; 464 465 unsigned *pdq=set_pdq(s); 466 467 if (pdq != NULL) { 468 for (i=0 ; pdq[i] != nil ; i++) { 469 node=tnode( (int) pdq[i]); 470 *tp=node; 471 tp=&(node->right); 472 }; 473 *tp=NULL; 474 free ( (char *) pdq); 475 }; 476 return t; 477 } 478 479 #ifdef __USE_PROTOS 480 void MR_check_pred_too_long(Predicate *p,set completion) 481 #else 482 void MR_check_pred_too_long(p,completion) 483 Predicate *p; 484 set completion; 485 #endif 486 { 487 if (p != NULL && 488 p->source != NULL && 489 ! p->source->predTooLong) { 490 if ( !set_nil(completion)) { 491 p->source->predTooLong=1; 492 warnFL("It is unusual (but ok) for a semantic predicate to test context past the end of its own rule", 493 FileStr[p->source->file],p->source->line); 494 }; 495 }; 496 } 497 498 #ifdef __USE_PROTOS 499 int MR_predicate_context_completed(Predicate *p) 500 #else 501 int MR_predicate_context_completed(p) 502 Predicate *p; 503 #endif 504 { 505 if (p == NULL) return 1; 506 if (p->expr != PRED_AND_LIST && 507 p->expr != PRED_OR_LIST) { 508 if ( ! set_nil(p->completionSet)) return 0; 509 if ( ! set_nil(p->completionTree)) return 0; 510 }; 511 return MR_predicate_context_completed(p->down) & 512 MR_predicate_context_completed(p->right); 513 } 514 515 #ifdef __USE_PROTOS 516 Node * MR_advance(Node *n) 517 #else 518 Node * MR_advance(n) 519 Node *n; 520 #endif 521 { 522 if (n == NULL) return NULL; 523 switch (n->ntype) { 524 case nJunction: return ((Junction *)n)->p1; 525 case nToken: return ((TokNode *)n)->next; 526 case nRuleRef: return ((RuleRefNode *)n)->next; 527 case nAction: return ((ActionNode *)n)->next; 528 default: return NULL; 529 }; 530 return NULL; /* MSVC 5.0 complains about missing return statement */ 531 } 532 533 #ifdef __USE_PROTOS 534 Junction * MR_find_endRule(Node *n) 535 #else 536 Junction * MR_find_endRule(n) 537 Node *n; 538 #endif 539 { 540 Node *next; 541 if (n == NULL) return NULL; 542 for (next=n; next != NULL; next=MR_advance(next)) { 543 if (next->ntype == nJunction && 544 ( (Junction *) next)->jtype == EndRule) { 545 break; 546 }; 547 }; 548 return (Junction *)next; 549 } 550 551 /* 552 Intersection: a branch which is shorter is chosen 553 over one which is longer: (A B C) intersect (A B) yields (A B). 554 555 AND: a branch which is longer is chosen over the one 556 which is shorter: (A B C) AND (A B) yields (A B C) 557 558 */ 559 560 #ifdef __USE_PROTOS 561 Tree *MR_computeTreeIntersection(Tree *l,Tree *r) 562 #else 563 Tree *MR_computeTreeIntersection(l,r) 564 Tree *l; 565 Tree *r; 566 #endif 567 { 568 Tree *result=NULL; 569 Tree **tail; 570 Tree *p; 571 Tree *q; 572 Tree *match; 573 574 if (l == NULL || r == NULL) return NULL; 575 for (p=l; p != NULL; p=p->right) { 576 require(p->token != EpToken,"MR_computeTreeIntersection: p->EpToken unexpected\n"); 577 require (p->token != ALT,"MR_computeTreeIntersection: p->ALT unexpected\n"); 578 }; 579 for (q=r; q != NULL; q=q->right) { 580 require(q->token != EpToken,"MR_computeTreeIntersection: q->EpToken unexpected\n"); 581 require(q->token != ALT,"MR_computeTreeIntersection: q->ALT unexpected\n"); 582 }; 583 584 result=tnode(ALT); 585 tail=&(result->down); 586 587 for (p=l; p != NULL ; p=p->right) { 588 for (q=r; q != NULL ; q=q->right) { 589 if (p->token == q->token) { 590 match=tnode(p->token); 591 match->down=MR_computeTreeIntersection(p->down,q->down); 592 *tail=match; 593 tail=&(match->right); 594 }; 595 }; 596 }; 597 598 *tail=NULL; 599 result=tshrink(result); 600 result=tflatten( result ); 601 result=tleft_factor( result ); 602 return result; 603 } 604 605 /* the predicates which are ANDed together have a common 606 context: they must all have common roots. Thus the 607 AND operation is more like an OR operation because 608 branches which are longer are grafted onto shorter 609 branches of the AND tree. For instance combining 610 (A B C) with (A B C D) gives (A B C D). There 611 should never be a case of (A B C) and (A B D) because 612 they have the same context. 613 614 Actually, this may not be true once one throws in 615 guard predicates which are defined by the user, not 616 the context. 617 */ 618 619 /* requires input trees to be in "canonical" format */ 620 621 #ifdef __USE_PROTOS 622 Tree *MR_computeTreeAND(Tree *l,Tree *r) 623 #else 624 Tree *MR_computeTreeAND(l,r) 625 Tree *l; 626 Tree *r; 627 #endif 628 { 629 Tree *result=NULL; 630 Tree **tail; 631 Tree *p; 632 Tree *q; 633 Tree *match; 634 635 if (l == NULL) return tdup(r); 636 if (r == NULL) return tdup(l); 637 638 for (p=l; p != NULL; p=p->right) { 639 /**** require(p->token != EpToken,"MR_computeTreeAND: p->EpToken unexpected\n"); ****/ 640 require (p->token != ALT,"MR_computeTreeAND: p->ALT unexpected\n"); 641 }; 642 for (q=r; q != NULL; q=q->right) { 643 /**** require(q->token != EpToken,"MR_computeTreeAND: q->EpToken unexpected\n"); ****/ 644 require(q->token != ALT,"MR_computeTreeAND: q->ALT unexpected\n"); 645 }; 646 647 result=tnode(ALT); 648 tail=&(result->down); 649 650 for (p=l; p != NULL ; p=p->right) { 651 for (q=r; q != NULL ; q=q->right) { 652 if (p->token == q->token) { 653 match=tnode(p->token); 654 match->down=MR_computeTreeAND(p->down,q->down); 655 *tail=match; 656 tail=&(match->right); 657 }; 658 }; 659 }; 660 661 *tail=NULL; 662 result=tshrink(result); 663 result=tflatten( result ); 664 result=tleft_factor( result ); 665 return result; 666 } 667 668 #ifdef __USE_PROTOS 669 void MR_union_plain_sets1(Predicate *p,set *theUnion) 670 #else 671 void MR_union_plain_sets1(p,theUnion) 672 Predicate *p; 673 set *theUnion; 674 #endif 675 { 676 if (p == NULL) return; 677 MR_union_plain_sets1(p->down,theUnion); 678 MR_union_plain_sets1(p->right,theUnion); 679 set_orin(theUnion,p->plainSet); 680 return; 681 } 682 683 #ifdef __USE_PROTOS 684 set MR_union_plain_sets(Predicate *p) 685 #else 686 set MR_union_plain_sets(p) 687 Predicate *p; 688 #endif 689 { 690 set theUnion; 691 692 theUnion=empty; 693 694 MR_union_plain_sets1(p,&theUnion); 695 return theUnion; 696 } 697 698 /* does NOT left factor: do not want to merge 699 (A B) with (A) to get (A B) 700 in fact the opposite: (A B) with (A) gives (A) 701 */ 702 703 #ifdef __USE_PROTOS 704 Tree *MR_compute_pred_tree_ctxXX(Predicate *p) 705 #else 706 Tree *MR_compute_pred_tree_ctxXX(p) 707 Predicate *p; 708 #endif 709 { 710 Tree *result=NULL; 711 Predicate *q; 712 Tree *t; 713 714 if (p == NULL) return NULL; 715 716 /* this appears strange: why do we OR the context 717 of and AND predicate ? It is because of the way 718 that predicates are evaluated: if the context is 719 wrong then it's the same as if the predicate was 720 true. That means that even when one leg of an 721 AND has unmatched context, if the other leg has 722 matched context and is true then the predicate 723 succeeds. It's only when all the legs have unmatched 724 context that this one can skip evaluation of the 725 predicates. 726 */ 727 if (p->expr == PRED_OR_LIST || 728 p->expr == PRED_AND_LIST) { 729 for (q=p->down; q != NULL ; q=q->right) { 730 t=MR_compute_pred_tree_ctxXX(q); 731 result=tappend(result,t); 732 t=NULL; 733 }; 734 735 result=tshrink(result); 736 result=tflatten( result ); 737 738 /* does NOT left factor: do not want to merge 739 (A B) with (A) to get (A B) 740 in fact the opposite: (A B) with (A) gives (A) 741 */ 742 743 /**** result=tleft_factor( result ); ****/ 744 return result; 745 }; 746 747 #if 0 748 ** if (p->expr == PRED_AND_LIST) { 749 ** 750 ** Predicate *l; 751 ** Predicate *r; 752 ** Tree *l1; 753 ** Tree *r1; 754 ** Tree *prevl1; 755 ** 756 ** l=p->down; 757 ** require (l->right != NULL,"MR_compute_pred_tree - AND has only one child"); 758 ** 759 **/* l1 and r1 should already be in "canonical" format */ 760 ** 761 ** l1=MR_compute_pred_tree(l); 762 ** for (r=l->right; r != NULL; r=r->right) { 763 ** r1=MR_compute_pred_tree(r); 764 ** prevl1=l1; 765 ** l1=MR_computeTreeAND(l1,r1); 766 ** Tfree(r1); 767 ** Tfree(prevl1); 768 ** }; 769 ** 770 **/* result from computeTreeAND should be in "canonical" format */ 771 ** 772 ** result=l1; 773 ** 774 **/* result of MR_computeTreeAND should be in "canonical" format */ 775 ** 776 ** return result; 777 ** }; 778 #endif 779 780 if (p->k == 1) { 781 result=MR_make_tree_from_set(p->scontext[1]); 782 } else { 783 result=tdup(p->tcontext); 784 result=MR_remove_epsilon_from_tree(result); 785 result=tshrink(result); 786 result=tflatten(result); 787 result=tleft_factor(result); 788 }; 789 return result; 790 } 791 792 #ifdef __USE_PROTOS 793 void MR_pred_depth(Predicate *p,int *maxDepth) 794 #else 795 void MR_pred_depth(p,maxDepth) 796 Predicate *p; 797 int *maxDepth; 798 #endif 799 { 800 if (p == NULL) return; 801 if (p->expr != PRED_OR_LIST && 802 p->expr != PRED_AND_LIST) { 803 if (p->k > *maxDepth) *maxDepth=p->k; 804 }; 805 MR_pred_depth(p->down,maxDepth); 806 MR_pred_depth(p->right,maxDepth); 807 } 808 809 /* this computes the OR of all the contexts */ 810 811 #ifdef __USE_PROTOS 812 set MR_compute_pred_set(Predicate *p) 813 #else 814 set MR_compute_pred_set(p) 815 Predicate *p; 816 #endif 817 { 818 set result; 819 Predicate *q; 820 821 result=empty; 822 823 if (p == NULL) return empty; 824 825 if (p->expr == PRED_OR_LIST || 826 p->expr == PRED_AND_LIST) { /* yes, I do mean PRED_AND_LIST ! */ 827 /* remember: r1: (A)? => <<p>>? r2; */ 828 /* r2: (B)? => <<q>>? r3; */ 829 set t; 830 831 t=empty; 832 result=empty; 833 834 for (q=p->down; q != NULL; q=q->right) { 835 t=MR_compute_pred_set(q); 836 set_orin(&result,t); 837 set_free(t); 838 }; 839 return result; 840 } else if (p->k > 1) { 841 return empty; 842 } else { 843 return set_dup(p->scontext[1]); 844 }; 845 } 846 847 #ifdef __USE_PROTOS 848 set MR_First(int ck,Junction *j,set *incomplete) 849 #else 850 set MR_First(ck,j,incomplete) 851 int ck; 852 Junction *j; 853 set *incomplete; 854 #endif 855 { 856 Junction *p; 857 set tokensUsed; 858 859 tokensUsed=empty; 860 861 require(j->ntype==nJunction, "MR_First: non junction passed"); 862 863 p = analysis_point((Junction *)j->p1); 864 865 REACH(p,ck,incomplete,tokensUsed); 866 867 return tokensUsed; 868 } 869 870 #ifdef __USE_PROTOS 871 void MR_cleanup_pred_trees(Predicate *p) 872 #else 873 void MR_cleanup_pred_trees(p) 874 Predicate *p; 875 #endif 876 { 877 Tree *t; 878 879 if (p == NULL) return; 880 if (p->expr != PRED_OR_LIST && 881 p->expr != PRED_AND_LIST) { 882 t=p->tcontext; 883 t=tshrink(t); 884 t=tflatten(t); 885 t=tleft_factor(t); 886 p->tcontext=t; 887 }; 888 MR_cleanup_pred_trees(p->down); 889 MR_cleanup_pred_trees(p->right); 890 } 891 892 /* does NOT return canonical tree */ 893 894 #ifdef __USE_PROTOS 895 Tree * MR_remove_epsilon_from_tree(Tree *t) 896 #else 897 Tree * MR_remove_epsilon_from_tree(t) 898 Tree *t; 899 #endif 900 { 901 if (t == NULL) return NULL; 902 903 /* I think ALT can be ignored as a special case */ 904 905 if (t->token != EpToken) { 906 t->down=MR_remove_epsilon_from_tree(t->down); 907 t->right=MR_remove_epsilon_from_tree(t->right); 908 return t; 909 } else { 910 Tree *u; 911 u=MR_remove_epsilon_from_tree(t->right); 912 t->right=NULL; 913 Tfree(t); 914 return u; 915 }; 916 } 917 918 #ifdef __USE_PROTOS 919 void MR_complete_set(int predDepth,set *tokensUsed,set *incomplete) 920 #else 921 void MR_complete_set(predDepth,tokensUsed,incomplete) 922 int predDepth; 923 set *tokensUsed; 924 set *incomplete; 925 #endif 926 { 927 int i; 928 RuleRefNode *ruleRef; 929 set rk2; 930 set b; 931 int k2; 932 Junction *save_MR_RuleBlkWithHalt; 933 934 if (set_int(*incomplete) > (unsigned) predDepth) { 935 return; 936 }; 937 938 require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count, 939 "RuleRefStack and RuleBlkWithHaltStack not same size"); 940 941 require(MR_RuleBlkWithHalt == NULL || 942 (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE), 943 "RuleBlkWithHalt has no halt set"); 944 945 save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt; 946 947 if (MR_RuleBlkWithHalt != NULL) { 948 MR_RuleBlkWithHalt->end->halt=FALSE; 949 }; 950 951 for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) { 952 ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i]; 953 if (ruleRef == NULL) continue; 954 955 MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i]; 956 if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE; 957 958 rk2=empty; 959 b=empty; 960 961 while ( !set_nil(*incomplete) ) { 962 k2=set_int(*incomplete); 963 if (k2 > predDepth) break; /* <=== another exit from loop */ 964 set_rm(k2,*incomplete); 965 REACH(ruleRef->next,k2,&rk2,b); 966 set_orin(tokensUsed,b); 967 set_free(b); 968 }; 969 970 if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE; 971 972 set_orin(incomplete,rk2); /* remember what we couldn't do */ 973 set_free(rk2); 974 if (set_int(*incomplete) > (unsigned) predDepth) break; /* <=== another exit from loop */ 975 }; 976 977 MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt; 978 if (MR_RuleBlkWithHalt != NULL) { 979 MR_RuleBlkWithHalt->end->halt=TRUE; 980 }; 981 } 982 983 #ifdef __USE_PROTOS 984 void MR_complete_tree(int predDepth,Tree **t,set *incomplete) 985 #else 986 void MR_complete_tree(predDepth,t,incomplete) 987 int predDepth; 988 Tree **t; 989 set *incomplete; 990 #endif 991 { 992 int i; 993 RuleRefNode *ruleRef; 994 set rk2; 995 Tree *u; 996 unsigned k2; 997 Junction *save_MR_RuleBlkWithHalt; 998 int saveConstrainSearch; 999 1000 if (set_int(*incomplete) > (unsigned) predDepth) { 1001 return; 1002 }; 1003 1004 require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count, 1005 "RuleRefStack and RuleBlkWithHaltStack not same size"); 1006 1007 require(MR_RuleBlkWithHalt == NULL || 1008 (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE), 1009 "RuleBlkWithHalt has no halt set"); 1010 1011 save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt; 1012 saveConstrainSearch=ConstrainSearch; 1013 ConstrainSearch=0; 1014 1015 if (MR_RuleBlkWithHalt != NULL) { 1016 MR_RuleBlkWithHalt->end->halt=FALSE; 1017 }; 1018 1019 for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) { 1020 ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i]; 1021 if (ruleRef == NULL) continue; 1022 1023 MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i]; 1024 1025 if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE; 1026 1027 rk2=empty; 1028 1029 while ( !set_nil(*incomplete) ) { 1030 k2 = set_int(*incomplete); 1031 if (k2 > (unsigned) predDepth) break; /* <=== another exit from loop */ 1032 set_rm(k2,*incomplete); 1033 u = NULL; 1034 1035 TRAV(ruleRef->next,k2,&rk2,u); 1036 1037 /* any subtrees missing k2 tokens, add u onto end */ 1038 1039 *t=tlink(*t,u,k2); 1040 Tfree(u); 1041 } 1042 1043 set_orin(incomplete,rk2); /* remember what we couldn't do */ 1044 set_free(rk2); 1045 1046 if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE; 1047 1048 if (set_int(*incomplete) > (unsigned) predDepth) break; /* <=== another exit from loop */ 1049 }; 1050 1051 MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt; 1052 1053 if (MR_RuleBlkWithHalt != NULL) { 1054 MR_RuleBlkWithHalt->end->halt=TRUE; 1055 }; 1056 ConstrainSearch=saveConstrainSearch; 1057 } 1058 1059 #ifdef __USE_PROTOS 1060 void MR_complete_predicates(int predDepth,Predicate *pred) 1061 #else 1062 void MR_complete_predicates(predDepth,pred) 1063 int predDepth; 1064 Predicate *pred; 1065 #endif 1066 { 1067 if (pred == NULL) return; 1068 if (pred->expr != PRED_AND_LIST && 1069 pred->expr != PRED_OR_LIST) { 1070 MR_complete_set(predDepth,&(pred->scontext[1]),&(pred->completionSet)); 1071 MR_complete_tree(predDepth,&(pred->tcontext),&(pred->completionTree)); 1072 }; 1073 MR_complete_predicates(predDepth,pred->down); 1074 MR_complete_predicates(predDepth,pred->right); 1075 } 1076 1077 #ifdef __USE_PROTOS 1078 Junction * MR_junctionWithoutP2(Junction *j) 1079 #else 1080 Junction * MR_junctionWithoutP2(j) 1081 Junction *j; 1082 #endif 1083 { 1084 Junction *thisAlt; 1085 1086 /* don't want to follow p2 to the next alternative of this rule */ 1087 /* insert a generic node with null p2 if necessary */ 1088 /* however FIRST requires a junction */ 1089 1090 thisAlt=j; 1091 if (thisAlt->p2 != NULL) { 1092 if (thisAlt->p1->ntype == nJunction) { 1093 thisAlt=(Junction *) thisAlt->p1; 1094 } else { 1095 thisAlt=newJunction(); 1096 thisAlt->p1=j->p1; 1097 thisAlt->rname=j->rname; 1098 thisAlt->file=j->file; 1099 thisAlt->line=j->line; 1100 j->p1=(Node *)thisAlt; 1101 }; 1102 }; 1103 return thisAlt; 1104 } 1105 1106 #ifdef __USE_PROTOS 1107 int MR_tree_equ(Tree *big, Tree *small) { 1108 #else 1109 int MR_tree_equ(big,small) 1110 Tree *big; 1111 Tree *small; 1112 { 1113 #endif 1114 1115 Tree *b; 1116 Tree *s; 1117 int bcount=0; 1118 int scount=0; 1119 1120 if (small == NULL && big == NULL) return 1; 1121 if (small == NULL) return 0; 1122 if (big == NULL) return 0; 1123 1124 if (small->token == ALT) { 1125 require(small->right == NULL, 1126 "MR_tree_equ: small: ALT node has siblings"); 1127 return MR_tree_equ(big,small->down); 1128 }; 1129 if (big->token == ALT) { 1130 require(big->right == NULL, 1131 "MR_tree_equ: big: ALT node has siblings"); 1132 return MR_tree_equ(big->down,small); 1133 }; 1134 for (s=small; s != NULL; s=s->right) { 1135 scount++; 1136 require(s->token != EpToken,"MR_tree_equ: s->EpToken unexpected\n"); 1137 }; 1138 for (b=big; b != NULL; b=b->right) { 1139 bcount++; 1140 require(b->token != EpToken,"MR_tree_equ: b->EpToken unexpected\n"); 1141 }; 1142 1143 if (bcount != scount) return 0; 1144 1145 for (s=small; s != NULL; s=s->right) { 1146 for (b=big; b!= NULL; b=b->right) { 1147 if (s->token == b->token) { 1148 if (MR_tree_equ(b->down,s->down)) goto next_s; 1149 }; 1150 }; 1151 return 0; 1152 next_s: 1153 continue; 1154 }; 1155 return 1; 1156 } 1157 1158 /* this does not compare sources - only contexts ! */ 1159 1160 #ifdef __USE_PROTOS 1161 int MR_identicalContext(Predicate *p,Predicate *q) 1162 #else 1163 int MR_identicalContext(p,q) 1164 Predicate *p; 1165 Predicate *q; 1166 #endif 1167 { 1168 if (p->k != q->k) return 0; 1169 require ( (p->tcontext == NULL) == (q->tcontext == NULL), 1170 "tcontext inconsistent"); 1171 if (p->k == 1) { 1172 return set_equ(p->scontext[1],q->scontext[1]); 1173 } else { 1174 return MR_tree_equ(p->tcontext,q->tcontext); 1175 }; 1176 } 1177 1178 #ifdef __USE_PROTOS 1179 void MR_reportSetSuppression(int predDepth, 1180 set predSet,set plainSet,Junction *jPred,Junction *jPlain,Predicate *p) 1181 #else 1182 void MR_reportSetSuppression(predDepth,predSet,plainSet,jPred,jPlain,p) 1183 int predDepth; 1184 set predSet; 1185 set plainSet; 1186 Junction *jPred; 1187 Junction *jPlain; 1188 Predicate *p; 1189 #endif 1190 { 1191 if (InfoP) { 1192 fprintf(output,"\n#if 0\n\n"); 1193 fprintf(output,"Hoisting of predicate suppressed by alternative without predicate.\n"); 1194 fprintf(output,"The alt without the predicate includes all cases where the predicate is false.\n\n"); 1195 fprintf(output," WITH predicate: line %d %s\n",jPred->line,FileStr[jPred->file]); 1196 if (jPlain != NULL) { 1197 fprintf(output," WITHOUT predicate: line %d %s\n",jPlain->line,FileStr[jPlain->file]); 1198 } else { 1199 fprintf(output," WITHOUT predicate: all alternatives without predicates (combined)\n"); 1200 }; 1201 if (predDepth == 1) { 1202 fprintf(output,"\nThe context set for the predicate:\n"); 1203 MR_dumpTokenSet(output,1,predSet); 1204 }; 1205 fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n"); 1206 MR_dumpTokenSet(output,1,plainSet); 1207 fprintf(output,"\nThe predicate:\n\n"); 1208 MR_dumpPred1(1,p,1); 1209 fprintf(output,"Chain of referenced rules:\n\n"); 1210 MR_dumpPredRuleRefStack(output,4); 1211 fprintf(output,"\n#endif\n"); 1212 }; 1213 } 1214 1215 #ifdef __USE_PROTOS 1216 void MR_reportSetRestriction(int predDepth,set predSet,set plainSet, 1217 Junction *jPred,Junction *jPlain,Predicate *origPred,Predicate *newPred) 1218 #else 1219 void MR_reportSetRestriction(predDepth,predSet,plainSet,jPred,jPlain,origPred,newPred) 1220 int predDepth; 1221 set predSet; 1222 set plainSet; 1223 Junction *jPred; 1224 Junction *jPlain; 1225 Predicate *origPred; 1226 Predicate *newPred; 1227 #endif 1228 { 1229 set intersect; 1230 1231 intersect=empty; 1232 1233 if (! InfoP) return; 1234 fprintf(output,"\n#if 0\n\n"); 1235 fprintf(output,"Restricting the context of a predicate because of overlap in the lookahead set\n"); 1236 fprintf(output," between the alternative with the semantic predicate and one without\n"); 1237 fprintf(output,"Without this restriction the alternative without the predicate could not\n"); 1238 fprintf(output," be reached when input matched the context of the predicate and the predicate\n"); 1239 fprintf(output," was false.\n\n"); 1240 1241 fprintf(output," WITH predicate: line %d %s\n",jPred->line,FileStr[jPred->file]); 1242 if (jPlain != NULL) { 1243 fprintf(output," WITHOUT predicate: line %d %s\n",jPlain->line,FileStr[jPlain->file]); 1244 } else { 1245 fprintf(output," WITHOUT predicate: all alternatives without predicates (combined)\n"); 1246 }; 1247 if (predDepth == 1) { 1248 fprintf(output,"\nThe original context set for the predicate:\n"); 1249 MR_dumpTokenSet(output,1,predSet); 1250 }; 1251 fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n"); 1252 MR_dumpTokenSet(output,1,plainSet); 1253 if (predDepth == 1) { 1254 fprintf(output,"\nThe intersection of the two sets\n"); 1255 intersect=set_and(predSet,plainSet); 1256 MR_dumpTokenSet(output,1,intersect); 1257 set_free(intersect); 1258 }; 1259 fprintf(output,"\nThe original predicate:\n\n"); 1260 MR_dumpPred1(1,origPred,1); 1261 fprintf(output,"The new (modified) form of the predicate:\n\n"); 1262 MR_dumpPred1(1,newPred,1); 1263 fprintf(output,"#endif\n"); 1264 } 1265 1266 /* don't use Pass3 by itself unless you know that inverted is not important */ 1267 1268 #ifdef __USE_PROTOS 1269 Predicate * MR_removeRedundantPredPass3(Predicate *p) 1270 #else 1271 Predicate * MR_removeRedundantPredPass3(p) 1272 Predicate *p; 1273 #endif 1274 { 1275 Predicate *q; 1276 1277 if (p == NULL) return NULL; 1278 p->right=MR_removeRedundantPredPass3(p->right); 1279 p->down=MR_removeRedundantPredPass3(p->down); 1280 if (p->redundant) { 1281 q=p->right; 1282 p->right=NULL; 1283 predicate_free(p); 1284 return q; 1285 }; 1286 if (p->expr == PRED_AND_LIST || 1287 p->expr == PRED_OR_LIST) { 1288 if (p->down == NULL) { 1289 q=p->right; 1290 p->right=NULL; 1291 predicate_free(p); 1292 return q; 1293 }; 1294 if (p->down != NULL && p->down->right == NULL) { 1295 q=p->down; 1296 q->right=p->right; 1297 p->right=NULL; 1298 p->down=NULL; 1299 return q; 1300 }; 1301 }; 1302 return p; 1303 } 1304 1305 #ifdef __USE_PROTOS 1306 void MR_removeRedundantPredPass2(Predicate *p) 1307 #else 1308 void MR_removeRedundantPredPass2(p) 1309 Predicate *p; 1310 #endif 1311 { 1312 Predicate *q; 1313 1314 if (p == NULL) return; 1315 1316 if (p->expr == PRED_AND_LIST) { 1317 for (q=p->down ; q != NULL ; q=q->right) { 1318 MR_removeRedundantPredPass2(q); 1319 if (q->isConst) { 1320 if (q->constValue == 0) { 1321 p->isConst=1; 1322 p->constValue=0; 1323 return; 1324 } else { 1325 q->redundant=1; 1326 }; 1327 }; 1328 }; 1329 }; 1330 1331 if (p->expr == PRED_OR_LIST) { 1332 for (q=p->down ; q != NULL ; q=q->right) { 1333 MR_removeRedundantPredPass2(q); 1334 if (q->isConst) { 1335 if (q->constValue == 0) { 1336 q->redundant=1; 1337 } else { 1338 p->isConst=1; 1339 p->constValue=1; 1340 return; 1341 }; 1342 }; 1343 }; 1344 }; 1345 1346 return; 1347 } 1348 1349 #if 0 1350 this totally ignores the implications of guarded predicates 1351 in which the part after the guard could possibly cover a predicate. 1352 that would be much harder: 1353 1354 rule : (A)? => <<p>>? sub1; /* 1 */ 1355 | (B)? => <<r>>? sub2 /* 2 */ 1356 sub1 : (A)? => <<q>>? A B /* 3 */ 1357 | B /* 4 - suppresses line 2 */ 1358 ; 1359 #endif 1360 1361 #ifdef __USE_PROTOS 1362 void MR_apply_restriction1(Predicate *pred,set *plainSet,int *changed) 1363 #else 1364 void MR_apply_restriction1(pred,plainSet,changed) 1365 Predicate *pred; 1366 set *plainSet; 1367 int *changed; 1368 #endif 1369 { 1370 if (pred == NULL) return; 1371 MR_apply_restriction1(pred->right,plainSet,changed); 1372 if (pred->down != NULL) { 1373 MR_apply_restriction1(pred->down,plainSet,changed); 1374 } else { 1375 set t; 1376 if (pred->k == 1) { 1377 t=set_dif(pred->scontext[1],*plainSet); 1378 if (*changed == 0 && 1379 !set_equ(t,pred->scontext[1])) { 1380 *changed=1; 1381 }; 1382 if (set_nil(t)) { 1383 pred->redundant=1; 1384 }; 1385 set_free(pred->scontext[1]); 1386 pred->scontext[1]=t; 1387 }; 1388 }; 1389 } 1390 1391 #ifdef __USE_PROTOS 1392 void MR_orin_plainSet(Predicate *p,set plainSet) 1393 #else 1394 void MR_orin_plainSet(p,plainSet) 1395 Predicate *p; 1396 set plainSet; 1397 #endif 1398 { 1399 if (p == NULL) return; 1400 MR_orin_plainSet(p->down,plainSet); 1401 MR_orin_plainSet(p->right,plainSet); 1402 set_orin(&p->plainSet,plainSet); 1403 } 1404 1405 Predicate *PRED_SUPPRESS; 1406 1407 #ifdef __USE_PROTOS 1408 Predicate * MR_find_in_aSubBlk(Junction *alt) 1409 #else 1410 Predicate * MR_find_in_aSubBlk(alt) 1411 Junction *alt; 1412 #endif 1413 { 1414 Predicate *root=NULL; 1415 Predicate **tail=NULL; 1416 1417 Junction *p; 1418 1419 int nAlts=0; 1420 Junction **jList; 1421 Predicate **predList; 1422 int *matchList; 1423 set predSet; 1424 int i; 1425 int j; 1426 int m; 1427 int predDepth; 1428 set incomplete; 1429 set union_plainSet; 1430 set setChange; 1431 int changed; 1432 Predicate *newPred; 1433 set setDif; 1434 Predicate *origPred; 1435 int depth1=1; /* const int */ 1436 set *plainContext; 1437 set plainSet; 1438 1439 predSet=empty; 1440 incomplete=empty; 1441 union_plainSet=empty; 1442 setChange=empty; 1443 setDif=empty; 1444 plainSet=empty; 1445 1446 if (PRED_SUPPRESS == NULL) { 1447 PRED_SUPPRESS=new_pred(); 1448 PRED_SUPPRESS->expr="Predicate Suppressed"; 1449 }; 1450 1451 /* this section just counts the number of "interesting" alternatives */ 1452 /* in order to allocate arrays */ 1453 1454 for (p=alt; p!=NULL; p=(Junction *)p->p2) { 1455 /* ignore empty alts */ 1456 if ( p->p1->ntype != nJunction || 1457 ((Junction *)p->p1)->jtype != EndBlk ) { 1458 nAlts++; 1459 }; 1460 }; 1461 1462 /* if this is a (...)+ block then don't count the last alt because 1463 it can't be taken until at least one time through the block. 1464 In other words it isn't a real choice until the (...)+ is entered 1465 at which point the hoisting issue is moot. 1466 Maybe look at "ignore" instead ? 1467 */ 1468 1469 if (alt->jtype == aPlusBlk) { 1470 nAlts--; 1471 }; 1472 1473 jList=(Junction **)calloc(nAlts,sizeof(Junction *)); 1474 require(jList!=NULL,"cannot allocate MR_find_in_aSubBlk jList"); 1475 1476 plainContext=(set *)calloc(nAlts,sizeof(set)); 1477 require(plainContext!=NULL,"cannot allocate MR_find_in_aSubBlk plainContext"); 1478 for (m=0; m < nAlts; m++) plainContext[m]=empty; 1479 1480 predList=(Predicate **)calloc(nAlts,sizeof(Predicate *)); 1481 require(predList!=NULL,"cannot allocate MR_find_in_aSubBlk predList"); 1482 1483 matchList=(int *)calloc(nAlts,sizeof(int)); 1484 require(matchList!=NULL,"cannot allocate MR_find_in_aSubBlk matchList"); 1485 1486 /* this section just fills in the arrays previously allocated */ 1487 /* the most interesting one is matchList[] */ 1488 /* */ 1489 /* bit 0 => this alt has a semantic pred which is "covered" */ 1490 /* by an alt without a semantic pred. Don't hoist. */ 1491 1492 for (i=0,p=alt; 1493 p!=NULL && i<nAlts; 1494 i++,p=(Junction *)p->p2) { 1495 1496 /* ignore empty alts */ 1497 1498 if ( p->p1->ntype != nJunction || 1499 ((Junction *)p->p1)->jtype != EndBlk ) { 1500 jList[i]=MR_junctionWithoutP2(p); 1501 predList[i]=find_predicates(p->p1); /* should be jList ????? */ 1502 if (predList[i] != NULL) { 1503 MR_cleanup_pred_trees(predList[i]); /* flatten & left factor */ 1504 plainContext[i]=MR_union_plain_sets(predList[i]); 1505 } else { 1506 MR_set_reuse(&plainSet); 1507 MR_set_reuse(&incomplete); 1508 plainSet=MR_First(depth1,jList[i],&incomplete); 1509 MR_complete_set(depth1,&plainSet,&incomplete); 1510 require(set_nil(incomplete),"couldn't complete k=1"); 1511 plainContext[i]=plainSet; 1512 plainSet=empty; 1513 }; 1514 set_orin(&union_plainSet,plainContext[i]); 1515 }; 1516 }; 1517 1518 if (nAlts == 1) { 1519 goto EXIT_SIMPLE; 1520 }; 1521 1522 /* 1523 * Looking for cases where alt i has a semantic pred and alt j does not. 1524 * Don't care about cases where lookahead for semantic predicates overlap 1525 * because normal predicate hoisting does the correct thing automatically. 1526 * Don't care about cases where lookahead for alts without semantic predicates 1527 * overlap because normal prediction does the correct thing automatically. 1528 * 1529 * When we find such a case check for one of three subcases: 1530 * 1531 * 1. if lookahead for alt i is contained in the lookahead for any 1532 * alt j then ignore semantic predicate of alt i 1533 * 2. if lookahead for alt i is not contained in the lookahead for 1534 * any alt j then add add predicate i to the OR list to be hoisted 1535 * 3. if lookahead for alt i overlaps the lookahead for some alt j then 1536 * add a dummy semantic predicate for alt j 1537 * 1538 * There is an implicit assumption that the context of all alternatives following 1539 * the rule being processed here are identical (but may vary from hoist to 1540 * hoist depending on the place where the rule was invoked that led to hoisting 1541 * these predicates. In othere words in the fragment: 1542 * 1543 * ( <<a>>? a1 a2 a3 | <<b>>? b1 b2 b3 ) 1544 * 1545 * both a3 and b3 have the same follow sets because they are both at the end of 1546 * alternatives in the same block. 1547 */ 1548 1549 for (i=0; i < nAlts; i++) { 1550 if (jList[i] == NULL) continue; 1551 if (predList[i] == NULL) continue; 1552 1553 /* if the predicate depth turns out to be one token only */ 1554 /* then it is can be easily represented as a set and */ 1555 /* compared to the junction set create by MR_First() */ 1556 1557 predDepth=0; 1558 MR_pred_depth(predList[i],&predDepth); 1559 require (predDepth >= 1,"MR_find_in_aSubBlk: pred depth < 1"); 1560 require (predDepth <= CLL_k,"MR_find_in_aSubBlk: predDepth > CLL_k"); 1561 1562 /* complete predicates to predDepth 1563 If completed to depth=1 then the context would be incomplete. 1564 The context would be truncated and the predicate simplify routine 1565 would have incomplete information. It would lead to 1566 either false matches of failure to find true matches. 1567 */ 1568 1569 MR_complete_predicates(predDepth,predList[i]); 1570 1571 if (predList[i] != NULL) { 1572 MR_cleanup_pred_trees(predList[i]); /* flatten & left factor */ 1573 }; 1574 1575 /* If the predicate depth is 1 then it is possible to suppress 1576 a predicate completely using a single plain alt. Check for suppression 1577 by a single plain alt first because it gives better messages. If that 1578 fails try the union of all the plain alts. 1579 */ 1580 1581 if (predDepth == 1) { 1582 1583 MR_set_reuse(&predSet); 1584 predSet=MR_compute_pred_set(predList[i]); /* ignores k>1 predicates */ 1585 1586 for (j=0; j < nAlts; j++) { 1587 if (jList[j] == NULL) continue; 1588 if (j == i) continue; 1589 1590 MR_set_reuse(&setDif); 1591 setDif=set_dif(predSet,plainContext[j]); 1592 if (set_nil(setDif)) { 1593 matchList[i] |= 1; 1594 MR_reportSetSuppression(predDepth,predSet,plainContext[j],jList[i],jList[j],predList[i]); 1595 predicate_free(predList[i]); 1596 predList[i]=PRED_SUPPRESS; 1597 goto next_i; 1598 }; 1599 1600 }; /* end loop on j */ 1601 1602 changed=0; 1603 1604 /* predicate_dup is only to give good error messages */ 1605 /* remember to do a predicate_free() */ 1606 1607 origPred=predicate_dup(predList[i]); 1608 MR_apply_restriction1(predList[i],&union_plainSet,&changed); 1609 if (changed) { 1610 1611 /* don't use Pass3 by itself unless you know that inverted is not important */ 1612 1613 newPred=MR_removeRedundantPredPass3(predList[i]); 1614 newPred=MR_predSimplifyALL(newPred); 1615 if (newPred == NULL) { 1616 matchList[i] |= 1; 1617 MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i], 1618 NULL,origPred); 1619 predList[i]=PRED_SUPPRESS; 1620 } else { 1621 MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i], 1622 NULL,origPred,newPred); 1623 predList[i]=newPred; 1624 }; 1625 }; 1626 predicate_free(origPred); 1627 origPred=NULL; 1628 }; 1629 1630 /* 1631 If the predicate depth is > 1 then it can't be suppressed completely 1632 because the code doesn't support inspection of such things. They're 1633 much messier than k=1 sets. 1634 */ 1635 1636 if (predDepth > 1 ) { 1637 1638 changed=0; 1639 1640 /* predicate_dup is only to give good error messages */ 1641 /* remember to do a predicate_free() */ 1642 1643 origPred=predicate_dup(predList[i]); 1644 MR_apply_restriction1(predList[i],&union_plainSet,&changed); 1645 if (changed) { 1646 newPred=MR_removeRedundantPredPass3(predList[i]); 1647 newPred=MR_predSimplifyALL(newPred); 1648 if (newPred == NULL) { 1649 matchList[i] |= 1; 1650 MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i], 1651 NULL,origPred); 1652 predList[i]=PRED_SUPPRESS; 1653 } else { 1654 MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i], 1655 NULL,origPred,newPred); 1656 predList[i]=newPred; 1657 }; 1658 }; 1659 predicate_free(origPred); 1660 origPred=NULL; 1661 }; 1662 next_i: 1663 continue; 1664 }; 1665 1666 EXIT_SIMPLE: 1667 1668 root = new_pred(); 1669 root->expr=PRED_OR_LIST; 1670 tail = &(root->down); 1671 1672 for (i=0 ; i< nAlts ; i++) { 1673 if (jList[i] == NULL) continue; 1674 1675 if (predList[i] == NULL) { 1676 continue; 1677 } else if ( (matchList[i] & 1) != 0) { 1678 if (predList[i] != PRED_SUPPRESS) { 1679 predicate_free(predList[i]); 1680 }; 1681 continue; 1682 }; 1683 1684 /* make an OR list of predicates */ 1685 1686 *tail=predList[i]; 1687 tail=&(predList[i]->right); 1688 }; 1689 1690 /* if just one pred, remove OR root */ 1691 1692 if (root->down == NULL) { 1693 predicate_free(root); 1694 root=NULL; 1695 } else if (root->down->right == NULL) { 1696 Predicate *p=root->down; 1697 root->down=NULL; 1698 predicate_free(root); 1699 root=p; 1700 } 1701 1702 root=MR_predSimplifyALL(root); 1703 1704 MR_orin_plainSet(root,union_plainSet); 1705 1706 set_free(predSet); 1707 set_free(union_plainSet); 1708 set_free(incomplete); 1709 set_free(setChange); 1710 set_free(setDif); 1711 1712 for (m=0; m < nAlts; m++) set_free(plainContext[m]); 1713 1714 free ( (char *) jList); 1715 free ( (char *) predList); 1716 free ( (char *) matchList); 1717 free ( (char *) plainContext); 1718 1719 return root; 1720 } 1721 1722 #ifdef __USE_PROTOS 1723 void MR_predContextPresent(Predicate *p,int *allHaveContext,int *noneHaveContext) 1724 #else 1725 void MR_predContextPresent(p,allHaveContext,noneHaveContext) 1726 Predicate *p; 1727 int *allHaveContext; 1728 int *noneHaveContext; 1729 #endif 1730 { 1731 if (p == NULL) return; 1732 MR_predContextPresent(p->right,allHaveContext,noneHaveContext); 1733 if (p->expr != PRED_AND_LIST && 1734 p->expr != PRED_OR_LIST) { 1735 if (set_nil(p->scontext[1]) == 0 || 1736 (p->tcontext != NULL)) { 1737 *noneHaveContext=0; 1738 } else { 1739 *allHaveContext=0; 1740 }; 1741 }; 1742 MR_predContextPresent(p->down,allHaveContext,noneHaveContext); 1743 } 1744 1745 #ifdef __USE_PROTOS 1746 int MR_pointerStackPush(PointerStack *ps,void *dataPointer) 1747 #else 1748 int MR_pointerStackPush(ps,dataPointer) 1749 PointerStack *ps; 1750 void *dataPointer; 1751 #endif 1752 { 1753 void **newStack; 1754 int newSize; 1755 int i; 1756 1757 if (ps->count == ps->size) { 1758 newSize=20+ps->size*2; 1759 newStack=(void **)calloc(newSize,sizeof(void *)); 1760 require (newStack != NULL,"cannot allocate PointerStack"); 1761 for (i=0; i < ps->size; i++) { 1762 newStack[i]=ps->data[i]; 1763 }; 1764 if (ps->data != NULL) free( (char *) ps->data); 1765 ps->data=newStack; 1766 ps->size=newSize; 1767 }; 1768 ps->data[ps->count]=dataPointer; 1769 ps->count++; 1770 return ps->count-1; 1771 } 1772 1773 #ifdef __USE_PROTOS 1774 void * MR_pointerStackPop(PointerStack *ps) 1775 #else 1776 void * MR_pointerStackPop(ps) 1777 PointerStack *ps; 1778 #endif 1779 { 1780 void *dataPointer; 1781 1782 require(ps->count > 0,"MR_pointerStackPop underflow"); 1783 1784 dataPointer=ps->data[ps->count-1]; 1785 ps->data[ps->count-1]=NULL; 1786 (ps->count)--; 1787 return dataPointer; 1788 } 1789 1790 #ifdef __USE_PROTOS 1791 void * MR_pointerStackTop(PointerStack *ps) 1792 #else 1793 void * MR_pointerStackTop(ps) 1794 PointerStack *ps; 1795 #endif 1796 { 1797 require(ps->count > 0,"MR_pointerStackTop underflow"); 1798 return ps->data[ps->count-1]; 1799 } 1800 1801 #ifdef __USE_PROTOS 1802 void MR_pointerStackReset(PointerStack *ps) 1803 #else 1804 void MR_pointerStackReset(ps) 1805 PointerStack *ps; 1806 #endif 1807 { 1808 int i; 1809 if (ps->data != NULL) { 1810 for (i=0; i < ps->count ; i++) { 1811 ps->data[i]=NULL; 1812 }; 1813 }; 1814 ps->count=0; 1815 } 1816 1817 #ifdef __USE_PROTOS 1818 Junction *MR_nameToRuleBlk(char *name) 1819 #else 1820 Junction *MR_nameToRuleBlk(name) 1821 char *name; 1822 #endif 1823 { 1824 RuleEntry *q; 1825 1826 require (RulePtr != NULL,"MR_nameToRule: RulePtr not initialized"); 1827 1828 if (name == NULL) return NULL; 1829 1830 q = (RuleEntry *) hash_get(Rname,name); 1831 1832 if ( q == NULL ) { 1833 return NULL; 1834 } else { 1835 return RulePtr[q->rulenum]; 1836 }; 1837 } 1838 1839 #ifdef __USE_PROTOS 1840 Junction * MR_ruleReferenced(RuleRefNode *rrn) 1841 #else 1842 Junction * MR_ruleReferenced(rrn) 1843 RuleRefNode *rrn; 1844 #endif 1845 { 1846 return MR_nameToRuleBlk(rrn->text); 1847 } 1848 1849 #ifdef __USE_PROTOS 1850 void MR_comparePredLeaves(Predicate *me,Predicate *myParent,Predicate *him,Predicate *hisParent) 1851 #else 1852 void MR_comparePredLeaves(me,myParent,him,hisParent) 1853 Predicate *me; 1854 Predicate *myParent; 1855 Predicate *him; 1856 Predicate *hisParent; 1857 #endif 1858 { 1859 if (me == NULL) return; 1860 if (me == him) { 1861 MR_comparePredLeaves(me->right,myParent,him,hisParent); 1862 return; 1863 } else if (me->expr == PRED_AND_LIST || 1864 me->expr == PRED_OR_LIST) { 1865 MR_comparePredLeaves(me->down,me,him,hisParent); 1866 MR_comparePredLeaves(me->right,myParent,him,hisParent); 1867 return; 1868 } else { 1869 if (me->source != NULL) { 1870 1871 /* predicate->invert can be set only in the predEntry predicates */ 1872 /* thus they are only visible after the predEntry predicates have been "unfolded" */ 1873 1874 int sameSource=(me->source == him->source); 1875 int sameInvert=1 & 1876 (1 + me->inverted + him->inverted + me->source->inverted + him->source->inverted); 1877 int samePredEntry=(me->source->predEntry != NULL 1878 && him->source->predEntry != NULL 1879 && me->source->predEntry == him->source->predEntry); 1880 if (sameInvert && (sameSource || samePredEntry)) { 1881 if (MR_identicalContext(me,him)) { 1882 1883 /* identical predicates */ 1884 1885 if (hisParent->expr == PRED_OR_LIST && 1886 myParent->expr == PRED_OR_LIST) { 1887 me->redundant=1; 1888 } else if (hisParent->expr == PRED_AND_LIST && 1889 myParent->expr == PRED_AND_LIST) { 1890 me->redundant=1; 1891 } else if ( (hisParent->expr == PRED_OR_LIST && 1892 myParent->expr == PRED_AND_LIST) 1893 || 1894 (hisParent->expr == PRED_AND_LIST && 1895 myParent->expr == PRED_OR_LIST) 1896 ) { 1897 myParent->redundant=1; 1898 } else { 1899 require (0,"MR_comparePredLeaves: not both PRED_LIST"); 1900 }; 1901 }; 1902 }; /* end same source or same predEntrr with same invert sense */ 1903 1904 /* same predEntry but opposite invert sense */ 1905 1906 if (!sameInvert && (sameSource || samePredEntry)) { 1907 if (MR_identicalContext(me,him)) { 1908 if (hisParent->expr == PRED_OR_LIST && 1909 myParent->expr == PRED_OR_LIST) { 1910 myParent->isConst=1; 1911 myParent->constValue=1; 1912 } else if (hisParent->expr == PRED_AND_LIST && 1913 myParent->expr == PRED_AND_LIST) { 1914 myParent->isConst=1; 1915 myParent->constValue=0; 1916 } else if ( (hisParent->expr == PRED_OR_LIST && 1917 myParent->expr == PRED_AND_LIST) 1918 || 1919 (hisParent->expr == PRED_AND_LIST && 1920 myParent->expr == PRED_OR_LIST) 1921 ) { 1922 me->redundant=1; 1923 } else { 1924 require (0,"MR_comparePredLeaves: not both PRED_LIST"); 1925 }; 1926 }; 1927 }; /* end same predEntry with opposite invert sense */ 1928 }; 1929 1930 MR_comparePredLeaves(me->right,myParent,him,hisParent); 1931 return; 1932 }; 1933 } 1934 1935 #ifdef __USE_PROTOS 1936 void MR_removeRedundantPredPass1(Predicate *me,Predicate *myParent) 1937 #else 1938 void MR_removeRedundantPredPass1(me,myParent) 1939 Predicate *me; 1940 Predicate *myParent; 1941 #endif 1942 { 1943 if (me == NULL) return; 1944 if (me->redundant) { 1945 MR_removeRedundantPredPass1(me->right,myParent); 1946 return; 1947 }; 1948 if (me->expr == PRED_AND_LIST || 1949 me->expr == PRED_OR_LIST) { 1950 MR_removeRedundantPredPass1(me->down,me); 1951 MR_removeRedundantPredPass1(me->right,myParent); 1952 } else { 1953 require (me->source != NULL,"me->source == NULL"); 1954 if (myParent != NULL) { 1955 MR_comparePredLeaves(myParent->down,myParent,me,myParent); 1956 }; 1957 MR_removeRedundantPredPass1(me->right,myParent); 1958 }; 1959 } 1960 1961 /* pretty much ignores things with the inverted bit set */ 1962 1963 #ifdef __USE_PROTOS 1964 Predicate *MR_predFlatten(Predicate *p) 1965 #else 1966 Predicate *MR_predFlatten(p) 1967 Predicate *p; 1968 #endif 1969 { 1970 if (p == NULL) return NULL; 1971 if (p->expr == PRED_OR_LIST 1972 || p->expr == PRED_AND_LIST) { 1973 1974 Predicate *child; 1975 Predicate *gchild; 1976 Predicate **tail; 1977 Predicate *next; 1978 char *PRED_XXX_LIST=p->expr; 1979 1980 require (p->down != NULL,"MR_predFlatten AND/OR no child"); 1981 1982 1983 p->down=MR_predFlatten(p->down); 1984 p->right=MR_predFlatten(p->right); 1985 child=p->down; 1986 if (child->right == NULL) { 1987 child->right=p->right; 1988 p->right=NULL; 1989 p->down=NULL; 1990 if (p->inverted) child->inverted=!child->inverted; 1991 predicate_free(p); 1992 return child; 1993 }; 1994 1995 /* make a single list of all children and grandchildren */ 1996 1997 tail=&(p->down); 1998 for (child=p->down; child != NULL; child=next) { 1999 if (child->expr != PRED_XXX_LIST 2000 || child->inverted 2001 || child->predEntry != NULL) { 2002 *tail=child; 2003 tail=&(child->right); 2004 next=child->right; 2005 } else { 2006 for (gchild=child->down; 2007 gchild != NULL; 2008 gchild=gchild->right) { 2009 *tail=gchild; 2010 tail=&(gchild->right); 2011 }; 2012 next=child->right; 2013 child->right=NULL; 2014 child->down=NULL; 2015 predicate_free(child); 2016 }; 2017 }; 2018 *tail=NULL; 2019 return p; 2020 } else { 2021 p->right=MR_predFlatten(p->right); 2022 return p; 2023 }; 2024 } 2025 2026 static char *alwaysFalseWarning=NULL; 2027 2028 #ifdef __USE_PROTOS 2029 Predicate *checkPredicateConflict(Predicate *p) 2030 #else 2031 Predicate *checkPredicateConflict(p) 2032 Predicate *p; 2033 #endif 2034 { 2035 if (p->isConst) { 2036 if (p->constValue == 1) { 2037 predicate_free(p); 2038 return NULL; 2039 } else { 2040 if (InfoP && !p->conflictReported) { 2041 p->conflictReported=1; 2042 fprintf(output,"\n#if 0\n\n"); 2043 fprintf(output,"The following predicate expression will always be false:\n\n"); 2044 MR_dumpPred1(1,p,1); 2045 fprintf(output,"\n#endif\n"); 2046 }; 2047 2048 if (alwaysFalseWarning != CurRule) { 2049 alwaysFalseWarning=CurRule; 2050 if (InfoP) { 2051 warnNoFL(eMsg1("one (or more) predicate expression hoisted into rule \"%s\" are always false \ 2052 - see output file for more information",CurRule)); 2053 } else { 2054 warnNoFL(eMsg1("one (or more) predicate expressions hoisted into rule \"%s\" are always false \ 2055 - use \"-info p\" for more information",CurRule)); 2056 }; 2057 }; 2058 }; 2059 }; 2060 return p; 2061 } 2062 2063 2064 #ifdef __USE_PROTOS 2065 int MR_countPredNodes(Predicate *p) 2066 #else 2067 int MR_countPredNodes(p) 2068 Predicate *p; 2069 #endif 2070 { 2071 if (p == NULL) return 0; 2072 return 1 + MR_countPredNodes(p->down) + MR_countPredNodes(p->right); 2073 } 2074 2075 #ifdef __USE_PROTOS 2076 Predicate *MR_predSimplifyALLX(Predicate *p,int skipPass3) 2077 #else 2078 Predicate *MR_predSimplifyALLX(p,skipPass3) 2079 Predicate *p; 2080 int skipPass3; 2081 #endif 2082 { 2083 int countBefore; 2084 int countAfter; 2085 2086 countAfter=MR_countPredNodes(p); 2087 2088 do { 2089 if (p == NULL) return NULL; 2090 if (p->right == NULL && p->down == NULL) return p; 2091 countBefore=countAfter; 2092 MR_simplifyInverted(p,0); 2093 p=MR_predFlatten(p); 2094 MR_removeRedundantPredPass1(p,NULL); 2095 MR_removeRedundantPredPass2(p); 2096 if (! skipPass3) { 2097 p=checkPredicateConflict(p); 2098 p=MR_removeRedundantPredPass3(p); 2099 }; 2100 countAfter=MR_countPredNodes(p); 2101 } while (countBefore != countAfter); 2102 2103 return p; 2104 } 2105 2106 #ifdef __USE_PROTOS 2107 Predicate *MR_predSimplifyALL(Predicate *p) 2108 #else 2109 Predicate *MR_predSimplifyALL(p) 2110 Predicate *p; 2111 #endif 2112 { 2113 return MR_predSimplifyALLX(p,0); 2114 } 2115 2116 #ifdef __USE_PROTOS 2117 void MR_releaseResourcesUsedInRule(Node *n) 2118 #else 2119 void MR_releaseResourcesUsedInRule(n) 2120 Node *n; 2121 #endif 2122 { 2123 Node *next; 2124 Junction *j; 2125 int i; 2126 2127 if (n == NULL) return; 2128 if (n->ntype == nJunction) { 2129 j=(Junction *) n; 2130 2131 if (j->predicate != NULL) { 2132 predicate_free(j->predicate); 2133 j->predicate=NULL; 2134 }; 2135 for (i=0; i< CLL_k; i++) { 2136 set_free(j->fset[i]); 2137 j->fset[i]=empty; 2138 }; 2139 if (j->ftree != NULL) { 2140 Tfree(j->ftree); 2141 j->ftree=NULL; 2142 }; 2143 if (j->jtype == EndRule) return; 2144 if (j->jtype != RuleBlk && j->jtype != EndBlk) { 2145 if (j->p2 != NULL && !j->ignore) { /* MR11 */ 2146 MR_releaseResourcesUsedInRule(j->p2); 2147 }; 2148 }; 2149 }; 2150 next=MR_advance(n); 2151 MR_releaseResourcesUsedInRule(next); 2152 } 2153 2154 #ifdef __USE_PROTOS 2155 int MR_allPredLeaves(Predicate *p) 2156 #else 2157 int MR_allPredLeaves(p) 2158 Predicate *p; 2159 #endif 2160 { 2161 Predicate *q; 2162 2163 if (p == NULL) return 1; 2164 2165 for (q=p; q != NULL; q=q->right) { 2166 if (q->down != NULL) return 0; 2167 }; 2168 return 1; 2169 } 2170 2171 /* make sure it works for the last rule in a file */ 2172 2173 #ifdef __USE_PROTOS 2174 int MR_offsetFromRule(Node *n) 2175 #else 2176 int MR_offsetFromRule(n) 2177 Node *n; 2178 #endif 2179 { 2180 Junction *j; 2181 int offset=(-1); 2182 2183 for (j=SynDiag; j != NULL; j=(Junction *)j->p2) { 2184 2185 require (j->ntype == nJunction && j->jtype == RuleBlk,"Not a rule block"); 2186 2187 if (n->file < j->file) { 2188 return offset; 2189 }; 2190 if (n->file == j->file) { 2191 if (n->line < j->line) { 2192 return (offset < 0) ? 0 : offset; 2193 } else { 2194 offset=n->line - j->line; 2195 if (offset == 0) return 0; 2196 }; 2197 }; 2198 }; 2199 return offset; 2200 } 2201 2202 #define ruleNameMax 50 2203 2204 static char ruleNameStatic1[ruleNameMax]; 2205 static char ruleNameStatic2[ruleNameMax+10]; 2206 2207 #ifdef __USE_PROTOS 2208 char * MR_ruleNamePlusOffset(Node *n) 2209 #else 2210 char * MR_ruleNamePlusOffset(n) 2211 Node *n; 2212 #endif 2213 { 2214 int offset=MR_offsetFromRule(n); 2215 2216 strncpy(ruleNameStatic1,n->rname,ruleNameMax); 2217 if (offset < 0) { 2218 sprintf(ruleNameStatic2,"%s/?",ruleNameStatic1); 2219 } else { 2220 sprintf(ruleNameStatic2,"%s/%d",ruleNameStatic1,offset+1); 2221 }; 2222 return ruleNameStatic2; 2223 } 2224 2225 #ifdef __USE_PROTOS 2226 int MR_max_height_of_tree(Tree *t) 2227 #else 2228 int MR_max_height_of_tree(t) 2229 Tree *t; 2230 #endif 2231 { 2232 int h; 2233 int height=0; 2234 Tree *u; 2235 2236 if (t == NULL) return 0; 2237 2238 require (t->token != ALT && t->token != EpToken,"MR_max_height_of_tree ALT or EpToken"); 2239 2240 for (u=t; u != NULL; u=u->right) { 2241 h=MR_max_height_of_tree(u->down)+1; 2242 if (h > height) height=h; 2243 }; 2244 return height; 2245 } 2246 2247 #ifdef __USE_PROTOS 2248 int MR_all_leaves_same_height(Tree *t,int depth) 2249 #else 2250 int MR_all_leaves_same_height(t,depth) 2251 Tree *t; 2252 int depth; 2253 #endif 2254 { 2255 if (t == NULL) { 2256 return (depth==0); 2257 }; 2258 2259 require (t->token != ALT && t->token != EpToken,"MR_all_leaves_same_height ALT or EpToken"); 2260 2261 if (depth == 0) { 2262 return 0; 2263 } else { 2264 if ( ! MR_all_leaves_same_height(t->down,depth-1)) { 2265 return 0; 2266 }; 2267 if (t->right == NULL) { 2268 return 1; 2269 } else { 2270 return MR_all_leaves_same_height(t->right,depth); 2271 }; 2272 }; 2273 } 2274 2275 #ifdef __USE_PROTOS 2276 void MR_projectTreeOntoSet(Tree *tree,int ck,set *ckset) 2277 #else 2278 void MR_projectTreeOntoSet(tree,ck,ckset) 2279 Tree *tree; 2280 int ck; 2281 set *ckset; 2282 #endif 2283 { 2284 if (tree == NULL) return; 2285 2286 require(tree->token != EpToken,"MR_projectTreeOntoSet: EpToken unexpected\n"); 2287 2288 MR_projectTreeOntoSet(tree->right,ck,ckset); 2289 if (tree->token == ALT) { 2290 MR_projectTreeOntoSet(tree->down,ck,ckset); 2291 } else { 2292 if (ck > 1) { 2293 MR_projectTreeOntoSet(tree->down,ck-1,ckset); 2294 } else { 2295 set_orel(tree->token,ckset); 2296 }; 2297 }; 2298 } 2299 2300 #ifdef __USE_PROTOS 2301 int MR_comparePredicates(Predicate *a,Predicate *b) 2302 #else 2303 int MR_comparePredicates(a,b) 2304 Predicate *a; 2305 Predicate *b; 2306 #endif 2307 { 2308 Predicate *p; 2309 Predicate *q; 2310 2311 if (a == b) return 1; 2312 if (a == NULL || b == NULL ) return 0; 2313 if (a->down == NULL && b->down == NULL) { 2314 2315 /* predicate->invert can be set only in the predEntry predicates */ 2316 /* thus they are only visible after the predEntry predicates have been "unfolded" */ 2317 2318 int sameSource=(a->source == b->source); 2319 int sameInvert= 1 & (1 +a->inverted + b->inverted + 2320 a->source->inverted + b->source->inverted); 2321 int samePredEntry=(a->source->predEntry != NULL 2322 && b->source->predEntry != NULL 2323 && a->source->predEntry == b->source->predEntry); 2324 if (sameInvert && (sameSource || samePredEntry)) { 2325 if (MR_identicalContext(a,b)) { 2326 return 1; 2327 }; 2328 }; 2329 return 0; 2330 }; 2331 if (a->down == NULL || b->down == NULL) return 0; 2332 if (a->expr != b->expr) return 0; 2333 2334 for (p=a->down; p != NULL; p=p->right) { 2335 for (q=b->down; q != NULL; q=q->right) { 2336 if (MR_comparePredicates(p,q)) goto NEXT_P; 2337 }; 2338 return 0; 2339 NEXT_P: 2340 continue; 2341 }; 2342 return 1; 2343 } 2344 2345 /* 2346 * action->inverted can be set only when a predicate symbol appears in 2347 * a rule: "rule : <<!XXX>>? X". It cannot be set under any 2348 * other circumstances. In particular it cannot be set by 2349 * "#pred NotA !A" or by "#pred Nota <<!A>>?". The first case 2350 * creates a predEntry and the predicate expression of that predEntry 2351 * has inverted set. In the second case, the code for handling "!" 2352 * is only present in buildAction, which is not called by the #pred 2353 * semantic routines, only when a <<...>>? is recognized as part of 2354 * a rule definition. 2355 * 2356 * predicate->inverted can only be set by a predicate created by a #pred 2357 * expression, such as "#pred NotA !A" or "#pred NotXY ! (X && Y) or 2358 * "#pred XbarY !(X && Y)". In particular, it cannot be set by any 2359 * predicate expression occurring under any other circumstances. 2360 * The #pred predicate expresssions are stored with in predEntry->pred 2361 * and do not normally appear anywhere else until the predicates are 2362 * "unfolded" in order to recognize redundancies, conflicts, and 2363 * tautologies. 2364 * 2365 * The unfold routine expands all references to #pred expressions. 2366 * 2367 * The simplifyInvert goes through and propagates the invert bit so that 2368 * all OR and AND nodes are un-inverted. 2369 * 2370 * Note that !(A and B) => (!A or !B) 2371 * !(A or B) => (!A and !B) 2372 * 2373 * MR_unfold() is called to expand predicate symbols by replacing predicates 2374 * that reference predicate entries with the copies of the predicate entries. 2375 * Each reference receives a duplicate of the original. This is necessary 2376 * because the next phase involves simplification and removal of redundant 2377 * predicate nodes. Anyway, the point I'm making is that predicate->invert 2378 * should not be set in any predicate until it has been expanded. 2379 * 2380 * This is a recursive structure, but there is no need for "recursive expansion" 2381 * by which I mean a predicate symbol refers to other predicate symbols which 2382 * must also be expanded. 2383 * 2384 * Recursive expansion is *not* performed by this routine because it is not 2385 * necessary. Expansion of references is performed by predPrimary when 2386 * a new predicate symbol is created by referring to others in the pred expr. 2387 */ 2388 2389 #ifdef __USE_PROTOS 2390 Predicate *MR_unfold(Predicate *pred) 2391 #else 2392 Predicate *MR_unfold(pred) 2393 Predicate *pred; 2394 #endif 2395 { 2396 Predicate *result; 2397 2398 if (pred == NULL) return NULL; 2399 2400 pred->right=MR_unfold(pred->right); 2401 2402 if (pred->down == NULL) { 2403 if (pred->source->predEntry != NULL) { 2404 if (pred->source->predEntry->pred == NULL) { 2405 ; /* do nothing */ /* a reference to a literal #pred (perhaps with "!" */ 2406 } else { 2407 result=predicate_dup_without_context(pred->source->predEntry->pred); 2408 if (pred->inverted) { 2409 result->inverted=!result->inverted; 2410 }; 2411 if (pred->source->inverted) { 2412 result->inverted=!result->inverted; 2413 }; 2414 result->right=pred->right; 2415 pred->right=NULL; 2416 predicate_free(pred); 2417 /*** result=MR_unfold(result); *** not necessary */ /* recursive expansion */ 2418 return result; 2419 }; 2420 } else { 2421 ; /* do nothing */ /* an inline literal predicate */ 2422 }; 2423 } else { 2424 pred->down=MR_unfold(pred->down); 2425 }; 2426 return pred; 2427 } 2428 2429 /* this should be called immediately after MR_unfold() and 2430 at no other times 2431 */ 2432 2433 #ifdef __USE_PROTOS 2434 void MR_simplifyInverted(Predicate *pred,int inverted) 2435 #else 2436 void MR_simplifyInverted(pred,inverted) 2437 Predicate *pred; 2438 int inverted; 2439 #endif 2440 { 2441 int newInverted; 2442 2443 if (pred == NULL) return; 2444 2445 MR_simplifyInverted(pred->right,inverted); 2446 2447 newInverted= 1 & (inverted + pred->inverted); 2448 2449 if (pred->down == NULL) { 2450 pred->inverted=newInverted; 2451 } else { 2452 if (newInverted != 0) { 2453 if (pred->expr == PRED_AND_LIST) { 2454 pred->expr=PRED_OR_LIST; 2455 } else { 2456 pred->expr=PRED_AND_LIST; 2457 }; 2458 }; 2459 pred->inverted=0; 2460 MR_simplifyInverted(pred->down,newInverted); 2461 }; 2462 } 2463 2464 /* only remove it from AND and OR nodes, not leaves */ 2465 2466 #ifdef __USE_PROTOS 2467 void MR_clearPredEntry(Predicate *p) 2468 #else 2469 void MR_clearPredEntry(p) 2470 Predicate *p; 2471 #endif 2472 { 2473 if (p == NULL) return; 2474 MR_clearPredEntry(p->down); 2475 MR_clearPredEntry(p->right); 2476 if (p->down != NULL) p->predEntry=NULL; 2477 } 2478 2479 2480 #ifdef __USE_PROTOS 2481 void MR_orphanRules(FILE *f) 2482 #else 2483 void MR_orphanRules(f) 2484 FILE *f; 2485 #endif 2486 { 2487 set a; 2488 Junction *p; 2489 unsigned e; 2490 RuleEntry *re; 2491 2492 a=empty; 2493 2494 if (! InfoO) return; 2495 2496 for (p=SynDiag; p!=NULL; p = (Junction *)p->p2) { 2497 if ( (Junction *) (p->end)->p1 == NULL) { 2498 re=(RuleEntry *) hash_get(Rname,p->rname); 2499 require (re != NULL,"RuleEntry == NULL"); 2500 set_orel(re->rulenum, &a); 2501 } 2502 } 2503 2504 if (set_deg(a) > 1) { 2505 fprintf(f,"note: Start rules: {"); 2506 for (; !set_nil(a); set_rm(e,a)) { 2507 e=set_int(a); 2508 fprintf(f," %s",RulePtr[e]->rname); 2509 }; 2510 fprintf(f," }\n"); 2511 }; 2512 set_free( a ); 2513 } 2514 2515 /* merge (X Y) and (X) to create (X) */ 2516 2517 static int *mergeChain; 2518 static Tree *mergeTree; 2519 2520 #ifdef __USE_PROTOS 2521 Tree *MR_merge_tree_contexts_client(Tree *t,int chain[]) 2522 #else 2523 Tree *MR_merge_tree_contexts_client(t,chain) 2524 Tree *t; 2525 int chain[]; 2526 #endif 2527 { 2528 if (t == NULL) return NULL; 2529 if (chain[0] == 0) { 2530 Tree *u=t->right; 2531 t->right=NULL; 2532 Tfree(t); 2533 return MR_merge_tree_contexts_client(u,&chain[0]); 2534 } 2535 if (chain[0] == t->token) { 2536 t->down=MR_merge_tree_contexts_client(t->down,&chain[1]); 2537 }; 2538 t->right=MR_merge_tree_contexts_client(t->right,&chain[0]); 2539 return t; 2540 } 2541 2542 #ifdef __USE_PROTOS 2543 void MR_iterateOverTreeContexts(Tree *t,int chain[]) 2544 #else 2545 void MR_iterateOverTreeContexts(t,chain) 2546 Tree *t; 2547 int chain[]; 2548 #endif 2549 { 2550 if (t == NULL) return; 2551 chain[0]=t->token; 2552 if (t->down != NULL) { 2553 MR_iterateOverTreeContexts(t->down,&chain[1]); 2554 } else { 2555 MR_merge_tree_contexts_client(mergeTree,mergeChain); 2556 }; 2557 MR_iterateOverTreeContexts(t->right,&chain[0]); 2558 chain[0]=0; 2559 } 2560 2561 #ifdef __USE_PROTOS 2562 Tree *MR_merge_tree_contexts(Tree *t) 2563 #else 2564 Tree *MR_merge_tree_contexts(t) 2565 Tree *t; 2566 #endif 2567 { 2568 int h=MR_max_height_of_tree(t); 2569 2570 mergeTree=t; 2571 mergeChain=(int *) calloc(h+1,sizeof(int)); 2572 require (mergeChain != NULL,"MR_merge_tree_contexts: can't alloc chain"); 2573 MR_iterateOverTreeContexts(t,mergeChain); 2574 t=tshrink(t); 2575 t=tflatten(t); 2576 t=tleft_factor(t); 2577 free ( (char *) mergeChain); 2578 mergeChain=NULL; 2579 return t; 2580 } 2581 2582 #ifdef __USE_PROTOS 2583 Tree *MR_compute_pred_tree_context(Predicate *p) 2584 #else 2585 Tree *MR_compute_pred_tree_context(p) 2586 Predicate *p; 2587 #endif 2588 { 2589 Tree *t; 2590 2591 t=MR_compute_pred_tree_ctxXX(p); 2592 MR_merge_tree_contexts(t); 2593 return t; 2594 } 2595 2596 #ifdef __USE_PROTOS 2597 void MR_guardPred_plainSet(ActionNode *anode,Predicate *pred) 2598 #else 2599 void MR_guardPred_plainSet(anode,pred) 2600 ActionNode *anode; 2601 Predicate *pred; 2602 #endif 2603 { 2604 Junction *j; 2605 Predicate *workPred; 2606 set maskSet; 2607 2608 maskSet=empty; 2609 2610 if (!MRhoisting) return; 2611 2612 /* it doesn't really matter whether the predicate has 2613 depth k=1 or k>1 because we're not really looking 2614 at the predicate itself, just the stuff "behind" 2615 the predicate. 2616 */ 2617 2618 /* shouldn't have to worry about REACHing off the end 2619 of the rule containing the predicate because the 2620 Rule->end->halt should have been set already by the 2621 the code which handles RuleRef nodes. 2622 2623 We don't want to REACH off the end of the rule because 2624 this would give the "global" follow context rather than 2625 the "local" context. 2626 2627 r1a : (A)? => <<p>>? r2 (A|B) 2628 r1b : (A)? => <<p>>? r2 (A|C) 2629 r2 : (); 2630 2631 For r1a we want follow of predicate = {A B} 2632 we want plainSet = {B} 2633 For r1b we want follow of predicate = {A C} 2634 we want plainSet = {C} 2635 */ 2636 2637 require (anode->next->ntype == nJunction,"MR_guardpred_plainSet not Junction"); 2638 j=(Junction *)(anode->next); 2639 2640 workPred=predicate_dup_without_context(pred); 2641 workPred->k=1; 2642 workPred->scontext[1]=MR_First(1,j, &(workPred->completionSet) ); 2643 MR_complete_predicates(1,workPred); 2644 if (pred->k == 1) { 2645 maskSet=pred->scontext[1]; 2646 } else { 2647 MR_projectTreeOntoSet(pred->tcontext,1,&maskSet); 2648 } 2649 pred->plainSet=set_dif(workPred->scontext[1],maskSet); 2650 predicate_free(workPred); 2651 } 2652 2653 /*******************************************************************************/ 2654 2655 static Tree * suppressTree; 2656 static int * suppressChain; /* element 0 not used */ 2657 static set * suppressSets; 2658 static Node * suppressNode; 2659 static int suppressChainLength; 2660 int MR_SuppressSearch=0; 2661 static int suppressSucceeded; 2662 static Predicate * suppressPredicate; 2663 2664 #ifdef __USE_PROTOS 2665 int MR_isChain(Tree *t) 2666 #else 2667 int MR_isChain(t) 2668 Tree *t; 2669 #endif 2670 { 2671 Tree *u; 2672 2673 for (u=t; u != NULL; u=u->down) { 2674 if (u->right != NULL) return 0; 2675 } 2676 return 1; 2677 } 2678 2679 #ifdef __USE_PROTOS 2680 int MR_suppressK_client(Tree *tree,int tokensInChain[]) 2681 #else 2682 int MR_suppressK_client(tree,tokensInChain) 2683 Tree *tree; 2684 int tokensInChain[]; 2685 #endif 2686 { 2687 int i; 2688 set *save_fset; 2689 int save_ConstrainSearch; 2690 set incomplete; 2691 Tree *t; 2692 2693 suppressSucceeded=0; /* volatile */ 2694 2695 if (suppressSets == NULL) { 2696 suppressSets=(set *) calloc (CLL_k+1,sizeof(set)); 2697 require (suppressSets != NULL,"MR_suppressK_client: suppressSets alloc"); 2698 }; 2699 2700 for (suppressChainLength=1; 2701 tokensInChain[suppressChainLength+1] != 0; 2702 suppressChainLength++) {}; 2703 2704 require (suppressChainLength != 0,"MR_suppressK_client: chain empty"); 2705 2706 for (i=1 ; i <= suppressChainLength ; i++) { 2707 set_clr(suppressSets[i]); 2708 set_orel( (unsigned) tokensInChain[i], 2709 &suppressSets[i]); 2710 }; 2711 2712 save_fset=fset; 2713 save_ConstrainSearch=ConstrainSearch; 2714 2715 fset=suppressSets; 2716 2717 MR_SuppressSearch=1; 2718 MR_AmbSourceSearch=1; 2719 MR_MaintainBackTrace=1; 2720 ConstrainSearch=1; 2721 2722 maxk = suppressChainLength; 2723 2724 incomplete=empty; 2725 t=NULL; 2726 2727 /*** constrain = &(fset[1]); ***/ 2728 2729 MR_setConstrainPointer(&(fset[1])); /* MR18 */ 2730 2731 MR_pointerStackReset(&MR_BackTraceStack); 2732 2733 TRAV(suppressNode,maxk,&incomplete,t); 2734 2735 Tfree(t); 2736 2737 require (set_nil(incomplete),"MR_suppressK_client TRAV incomplete"); 2738 require (MR_BackTraceStack.count == 0, 2739 "MR_suppressK_client: MR_BackTraceStack.count != 0"); 2740 set_free(incomplete); 2741 2742 ConstrainSearch=save_ConstrainSearch; 2743 fset=save_fset; 2744 2745 MR_AmbSourceSearch=0; 2746 MR_MaintainBackTrace=0; 2747 MR_SuppressSearch=0; 2748 return suppressSucceeded; 2749 } 2750 2751 #ifdef __USE_PROTOS 2752 Tree * MR_iterateOverTreeSuppressK(Tree *t,int chain[]) 2753 #else 2754 Tree * MR_iterateOverTreeSuppressK(t,chain) 2755 Tree *t; 2756 int chain[]; 2757 #endif 2758 { 2759 if (t == NULL) return NULL; 2760 t->right=MR_iterateOverTreeSuppressK(t->right,&chain[0]); 2761 chain[0]=t->token; 2762 if (t->down != NULL) { 2763 t->down=MR_iterateOverTreeSuppressK(t->down,&chain[1]); 2764 if (t->down == NULL) { 2765 Tree *u=t->right; 2766 t->right=NULL; 2767 Tfree(t); 2768 chain[0]=0; 2769 return u; 2770 }; 2771 } else { 2772 MR_suppressK_client(suppressTree,suppressChain); 2773 if (suppressSucceeded) { 2774 Tree *u=t->right; 2775 t->right=NULL; 2776 Tfree(t); 2777 chain[0]=0; 2778 return u; 2779 }; 2780 }; 2781 chain[0]=0; 2782 return t; 2783 } 2784 2785 /* @@@ */ 2786 2787 #ifdef __USE_PROTOS 2788 Predicate * MR_suppressK(Node *j,Predicate *p) 2789 #else 2790 Predicate * MR_suppressK(j,p) 2791 Node *j; 2792 Predicate *p; 2793 #endif 2794 { 2795 Predicate *result; 2796 int guardPred=0; 2797 int ampersandPred=0; 2798 Node *nodePrime; 2799 2800 if (! MRhoistingk) { 2801 return p; 2802 } 2803 2804 if (! MRhoisting) return p; 2805 if (CLL_k == 1) return p; 2806 2807 if (suppressChain == NULL) { 2808 suppressChain=(int *) calloc(CLL_k+2,sizeof(int)); 2809 require (suppressChain != NULL,"MR_suppressK: can't allocate chain"); 2810 } 2811 2812 if (p == NULL) return NULL; 2813 2814 if (j->ntype == nJunction) { 2815 nodePrime=(Node *) MR_junctionWithoutP2( (Junction *) j); 2816 } else { 2817 nodePrime=j; 2818 }; 2819 2820 p->down=MR_suppressK(j,p->down); 2821 p->right=MR_suppressK(j,p->right); 2822 if (p->down != NULL) { 2823 result=p; 2824 goto EXIT; 2825 }; 2826 if (p->k == 1) { 2827 result=p; 2828 goto EXIT; 2829 }; 2830 2831 if (p->source != NULL) { 2832 if (p->source->guardpred != NULL) guardPred=1; 2833 if (p->source->ampersandPred != NULL) ampersandPred=1; 2834 } 2835 2836 suppressPredicate=p; 2837 suppressNode=nodePrime; /* was j*/ 2838 2839 suppressTree=p->tcontext; 2840 2841 if (guardPred || ampersandPred) { 2842 p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]); 2843 if (p->tcontext == NULL) { 2844 predicate_free(p); 2845 result=NULL; 2846 goto EXIT; 2847 }; 2848 } else { 2849 if (MR_isChain(p->tcontext)) { 2850 p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]); 2851 if (p->tcontext == NULL) { 2852 predicate_free(p); 2853 result=NULL; 2854 goto EXIT; 2855 }; 2856 } 2857 } 2858 result=p; 2859 EXIT: 2860 return result; 2861 } 2862 2863 #ifdef __USE_PROTOS 2864 void MR_suppressSearchReport(void) 2865 #else 2866 void MR_suppressSearchReport() 2867 #endif 2868 { 2869 int i; 2870 Node *p; 2871 TokNode *tn; 2872 int depth; 2873 set setAnd; 2874 2875 /* number of tokens in back trace stack matches length of chain */ 2876 2877 depth=0; 2878 for (i=0; i < MR_BackTraceStack.count ; i++) { 2879 p=(Node *) MR_BackTraceStack.data[i]; 2880 if (p->ntype == nToken) depth++; 2881 }; 2882 2883 require (depth == suppressChainLength,"depth > suppressChainLength"); 2884 2885 /* token codes match chain */ 2886 2887 depth=0; 2888 for (i=0; i < MR_BackTraceStack.count ; i++) { 2889 p=(Node *) MR_BackTraceStack.data[i]; 2890 if (p->ntype != nToken) continue; 2891 tn=(TokNode *) p; 2892 depth++; 2893 if (set_nil(tn->tset)) { 2894 require(set_el( (unsigned) tn->token,fset[depth]), 2895 "MR_suppressSearchReport: no match to #token in chain"); 2896 } else { 2897 setAnd=set_and(fset[depth],tn->tset); 2898 require(!set_nil(setAnd), 2899 "MR_suppressSearchReport: no match to #token set in chain"); 2900 set_free(setAnd); 2901 }; 2902 }; 2903 2904 /* have a match - now remove it from the predicate */ 2905 2906 suppressSucceeded=1; 2907 2908 if (suppressSucceeded) { 2909 fprintf(output,"\n"); 2910 fprintf(output,"#if 0\n"); 2911 fprintf(output,"\n"); 2912 fprintf(output,"Part (or all) of predicate with depth > 1 suppressed by "); 2913 fprintf(output,"alternative without predicate\n\n"); 2914 MR_dumpPred(suppressPredicate,1); 2915 fprintf(output,"The token sequence which is suppressed:"); 2916 fprintf(output," ("); 2917 for (i=1; i <= suppressChainLength; i++) { 2918 fprintf(output," %s",TerminalString(suppressChain[i])); 2919 }; 2920 fprintf(output," )\n"); 2921 fprintf(output,"The sequence of references which generate that sequence of tokens:\n\n"); 2922 2923 MR_backTraceDumpItemReset(); 2924 2925 for (i=0; i < MR_BackTraceStack.count ; i++) { 2926 MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]); 2927 }; 2928 fprintf(output,"\n"); 2929 fprintf(output,"#endif\n"); 2930 } 2931 } 2932 2933 #ifdef __USE_PROTOS 2934 void MR_markCompromisedRule(Node *n) 2935 #else 2936 void MR_markCompromisedRule(n) 2937 Node *n; 2938 #endif 2939 { 2940 RuleEntry *q; 2941 Node *mark=NULL; 2942 Junction *j; 2943 2944 if (n->ntype == nRuleRef) { 2945 mark=(Node *) MR_ruleReferenced( (RuleRefNode *) n); 2946 } else if (n->ntype == nToken) { 2947 mark=n; 2948 } else if (n->ntype == nJunction) { 2949 j=(Junction *)n; 2950 switch (j->jtype) { 2951 case aOptBlk: 2952 case aLoopBlk: 2953 case RuleBlk: 2954 case EndRule: 2955 case aPlusBlk: 2956 case aLoopBegin: 2957 mark=n; 2958 break; 2959 default: 2960 break; 2961 }; 2962 } 2963 2964 if (mark == NULL) return; 2965 2966 require (RulePtr != NULL,"RulePtr not initialized"); 2967 2968 q = (RuleEntry *) hash_get(Rname,mark->rname); 2969 require (q != NULL,"RuleEntry not found"); 2970 set_orel(q->rulenum,&MR_CompromisedRules); 2971 } 2972 2973 #ifdef __USE_PROTOS 2974 void MR_alphaBetaTraceReport(void) 2975 #else 2976 void MR_alphaBetaTraceReport() 2977 #endif 2978 { 2979 int i; 2980 2981 if (! AlphaBetaTrace) return; 2982 2983 MR_AlphaBetaMessageCount++; 2984 2985 fprintf(output,"\n"); 2986 fprintf(output,"#if 0\n"); 2987 fprintf(output,"\n"); 2988 fprintf(output,"Trace of references leading to attempt to compute the follow set of\n"); 2989 fprintf(output,"alpha in an \"(alpha)? beta\" block. It is not possible for antlr to\n"); 2990 fprintf(output,"compute this follow set because it is not known what part of beta has\n"); 2991 fprintf(output,"already been matched by alpha and what part remains to be matched.\n"); 2992 fprintf(output,"\n"); 2993 fprintf(output,"Rules which make use of the incorrect follow set will also be incorrect\n"); 2994 fprintf(output,"\n"); 2995 2996 MR_backTraceDumpItemReset(); 2997 2998 for (i=0; i < MR_BackTraceStack.count ; i++) { 2999 MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]); 3000 if (i < MR_BackTraceStack.count-1) { 3001 MR_markCompromisedRule( (Node *) MR_BackTraceStack.data[i]); 3002 }; 3003 }; 3004 fprintf(output,"\n"); 3005 fprintf(output,"#endif\n"); 3006 } 3007 3008 #ifdef __USE_PROTOS 3009 void MR_dumpRuleSet(set s) 3010 #else 3011 void MR_dumpRuleSet(s) 3012 set s; 3013 #endif 3014 { 3015 unsigned *cursor; 3016 unsigned *origin=set_pdq(s); 3017 3018 require(origin != NULL,"set_pdq failed"); 3019 3020 if (RulePtr == NULL) { 3021 fprintf(stderr,"RulePtr[] not yet initialized"); 3022 } else { 3023 for (cursor=origin; *cursor != nil ; cursor++) { 3024 /**** if (cursor != origin) fprintf(stderr,","); ****/ 3025 fprintf(stderr," %s",RulePtr[*cursor]->rname); 3026 fprintf(stderr,"\n"); 3027 }; 3028 free( (char *) origin); 3029 }; 3030 } 3031