+++ /dev/null
-/*\r
- * fset2.c\r
- *\r
- * Compute FIRST sets for full LL(k)\r
- *\r
- * SOFTWARE RIGHTS\r
- *\r
- * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
- * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
- * company may do whatever they wish with source code distributed with\r
- * PCCTS or the code generated by PCCTS, including the incorporation of\r
- * PCCTS, or its output, into commerical software.\r
- *\r
- * We encourage users to develop software with PCCTS. However, we do ask\r
- * that credit is given to us for developing PCCTS. By "credit",\r
- * we mean that if you incorporate our source code into one of your\r
- * programs (commercial product, research project, or otherwise) that you\r
- * acknowledge this fact somewhere in the documentation, research report,\r
- * etc... If you like PCCTS and have developed a nice tool with the\r
- * output, please mention that you developed it using PCCTS. In\r
- * addition, we ask that this header remain intact in our source code.\r
- * As long as these guidelines are kept, we expect to continue enhancing\r
- * this system and expect to make other tools available as they are\r
- * completed.\r
- *\r
- * ANTLR 1.33\r
- * Terence Parr\r
- * Parr Research Corporation\r
- * with Purdue University and AHPCRC, University of Minnesota\r
- * 1989-2001\r
- */\r
-\r
-#include <stdio.h>\r
-#include "pcctscfg.h"\r
-#include <stdlib.h>\r
-\r
-#ifdef PCCTS_USE_STDARG\r
-#include <stdarg.h>\r
-#else\r
-#include <varargs.h>\r
-#endif\r
-\r
-#include "set.h"\r
-#include "syn.h"\r
-#include "hash.h"\r
-#include "generic.h"\r
-#include "dlgdef.h"\r
-\r
-/* ick! globals. Used by permute() to track which elements of a set have been used */\r
-\r
-static int *findex;\r
-set *fset; /* MR11 make global */\r
-static unsigned **ftbl;\r
-static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */\r
-int ConstrainSearch;\r
-int maxk; /* set to initial k upon tree construction request */\r
- /* MR11 make global */\r
-static Tree *FreeList = NULL;\r
-\r
-#ifdef __USE_PROTOS\r
-static int tmember_of_context(Tree *, Predicate *);\r
-#else\r
-static int tmember_of_context();\r
-#endif\r
-\r
-#if TREE_DEBUG\r
-set set_of_tnodes_in_use;\r
-int stop_on_tnode_seq_number=(-1); /* (-1) to disable */\r
-#endif\r
-\r
-/* Do root\r
- * Then each sibling\r
- */\r
-\r
-void\r
-#ifdef __USE_PROTOS\r
-preorder( Tree *tree )\r
-#else\r
-preorder( tree )\r
-Tree *tree;\r
-#endif\r
-{\r
- if ( tree == NULL ) return;\r
- if ( tree->down != NULL ) fprintf(stderr, " (");\r
- if ( tree->token == ALT ) fprintf(stderr, " ALT");\r
- else fprintf(stderr, " %s", TerminalString(tree->token));\r
- if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);\r
- preorder(tree->down);\r
- if ( tree->down != NULL ) fprintf(stderr, " )");\r
- preorder(tree->right);\r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-int MR_tree_matches_constraints(int k,set * constrain,Tree *t)\r
-#else\r
-int MR_tree_matches_constraints(k,constrain,t)\r
- int k;\r
- set * constrain;\r
- Tree * t;\r
-#endif\r
-{\r
- int i;\r
- Tree *u;\r
-\r
- if (k == 0) return 1;\r
-\r
- /* for testing guard predicates: if the guard tree is shorter\r
- than the constraint then it is a match. The reason is that\r
- a guard of (A B) should be equivalent to a guard of (A B . . .)\r
- where "." matches every token. Thus a match which runs out\r
- of tree before constraint is a match.\r
- */\r
-\r
- if (t == NULL) return 1;\r
- require (set_deg(constrain[0]) == 1,\r
- "MR_tree_matches_constraints: set_deg != 1");\r
- i=set_int(constrain[0]);\r
- if (t->token != i) return 0;\r
- if (k-1 == 0) return 1;\r
- for (u=t->down; u != NULL; u=u->right) {\r
- if (MR_tree_matches_constraints(k-1,&constrain[1],u)) {\r
- return 1;\r
- };\r
- };\r
- return 0;\r
-}\r
-\r
-/* check the depth of each primary sibling to see that it is exactly\r
- * k deep. e.g.;\r
- *\r
- * ALT\r
- * |\r
- * A ------- B\r
- * | |\r
- * C -- D E\r
- *\r
- * Remove all branches <= k deep.\r
- *\r
- * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work.\r
- */\r
-\r
-static int pruneCount=0;\r
-static int prunePeak=200;\r
-\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-prune( Tree *t, int k )\r
-#else\r
-prune( t, k )\r
-Tree *t;\r
-int k;\r
-#endif\r
-{\r
- pruneCount++;\r
- if (pruneCount > prunePeak+100) {\r
- prunePeak=pruneCount;\r
-#if 0\r
-*** fprintf(stderr,"pruneCount=%d\n",pruneCount);\r
-/*** preorder(t); ***/\r
-*** fprintf(stderr,"\n",pruneCount);\r
-#endif\r
- };\r
- if ( t == NULL ) {\r
- pruneCount--;\r
- return NULL;\r
- };\r
- if ( t->token == ALT ) fatal_internal("prune: ALT node in FIRST tree");\r
- if ( t->right!=NULL ) t->right = prune(t->right, k);\r
- if ( k>1 )\r
- {\r
- if ( t->down!=NULL ) t->down = prune(t->down, k-1);\r
- if ( t->down == NULL )\r
- {\r
- Tree *r = t->right;\r
- t->right = NULL;\r
- Tfree(t);\r
- pruneCount--;\r
- return r;\r
- }\r
- }\r
- pruneCount--;\r
- return t;\r
-}\r
-\r
-/* build a tree (root child1 child2 ... NULL) */\r
-#ifdef PCCTS_USE_STDARG\r
-Tree *tmake(Tree *root, ...)\r
-#else\r
-Tree *tmake(va_alist)\r
-va_dcl\r
-#endif\r
-{\r
- Tree *w;\r
- va_list ap;\r
- Tree *child, *sibling=NULL, *tail=NULL;\r
-#ifndef PCCTS_USE_STDARG\r
- Tree *root;\r
-#endif\r
-\r
-#ifdef PCCTS_USE_STDARG\r
- va_start(ap, root);\r
-#else\r
- va_start(ap);\r
- root = va_arg(ap, Tree *);\r
-#endif\r
- child = va_arg(ap, Tree *);\r
- while ( child != NULL )\r
- {\r
-#ifdef DUM\r
- /* added "find end of child" thing TJP March 1994 */\r
- for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */\r
-#else\r
- w = child;\r
-#endif\r
-\r
- if ( sibling == NULL ) {sibling = child; tail = w;}\r
- else {tail->right = child; tail = w;}\r
- child = va_arg(ap, Tree *);\r
- }\r
-\r
- /* was "root->down = sibling;" */\r
- if ( root==NULL ) root = sibling;\r
- else root->down = sibling;\r
-\r
- va_end(ap);\r
- return root;\r
-}\r
-\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tnode( int tok )\r
-#else\r
-tnode( tok )\r
-int tok;\r
-#endif\r
-{\r
- Tree *p, *newblk;\r
- static int n=0;\r
- \r
- if ( FreeList == NULL )\r
- {\r
- /*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/\r
- if ( TreeResourceLimit > 0 )\r
- {\r
- if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )\r
- {\r
- fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);\r
- fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n",\r
- CurAmbigAlt1,\r
- CurAmbigAlt2,\r
- CurAmbigbtype);\r
- exit(PCCTS_EXIT_FAILURE);\r
- }\r
- }\r
- newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));\r
- if ( newblk == NULL )\r
- {\r
- fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);\r
- fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n",\r
- CurAmbigAlt1,\r
- CurAmbigAlt2,\r
- CurAmbigbtype);\r
- exit(PCCTS_EXIT_FAILURE);\r
- }\r
- n += TreeBlockAllocSize;\r
- for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)\r
- {\r
- p->right = FreeList; /* add all new Tree nodes to Free List */\r
- FreeList = p;\r
- }\r
- }\r
- p = FreeList;\r
- FreeList = FreeList->right; /* remove a tree node */\r
- p->right = NULL; /* zero out ptrs */\r
- p->down = NULL;\r
- p->token = tok;\r
-\r
- TnodesAllocated++; /* MR10 */\r
- TnodesInUse++; /* MR10 */\r
- if (TnodesInUse > TnodesPeak) TnodesPeak=TnodesInUse; /* MR10 */\r
-\r
-#ifdef TREE_DEBUG\r
- require(!p->in_use, "tnode: node in use!");\r
- p->in_use = 1;\r
- p->seq=TnodesAllocated;\r
- set_orel( (unsigned) TnodesAllocated,&set_of_tnodes_in_use);\r
- if (stop_on_tnode_seq_number == p->seq) {\r
- fprintf(stderr,"\n*** just allocated tnode #%d ***\n",\r
- stop_on_tnode_seq_number);\r
- };\r
-#endif\r
- return p;\r
-}\r
-\r
-static Tree *\r
-#ifdef __USE_PROTOS\r
-eofnode( int k )\r
-#else\r
-eofnode( k )\r
-int k;\r
-#endif\r
-{\r
- Tree *t=NULL;\r
- int i;\r
-\r
- for (i=1; i<=k; i++)\r
- {\r
- t = tmake(tnode((TokenInd!=NULL?TokenInd[EofToken]:EofToken)), t, NULL);\r
- }\r
- return t;\r
-}\r
-\r
-\r
-\r
-void\r
-#ifdef __USE_PROTOS\r
-_Tfree( Tree *t )\r
-#else\r
-_Tfree( t )\r
-Tree *t;\r
-#endif\r
-{\r
- if ( t!=NULL )\r
- {\r
-#ifdef TREE_DEBUG\r
- if (t->seq == stop_on_tnode_seq_number) {\r
- fprintf(stderr,"\n*** just freed tnode #%d ***\n",t->seq);\r
- };\r
- require(t->in_use, "_Tfree: node not in use!");\r
- t->in_use = 0;\r
- set_rm( (unsigned) t->seq,set_of_tnodes_in_use);\r
-#endif\r
- t->right = FreeList;\r
- FreeList = t;\r
- TnodesInUse--; /* MR10 */\r
- }\r
-}\r
-\r
-/* tree duplicate */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tdup( Tree *t )\r
-#else\r
-tdup( t )\r
-Tree *t;\r
-#endif\r
-{\r
- Tree *u;\r
- \r
- if ( t == NULL ) return NULL;\r
- u = tnode(t->token);\r
- u->v.rk = t->v.rk;\r
- u->right = tdup(t->right);\r
- u->down = tdup(t->down);\r
- return u;\r
-}\r
-\r
-/* tree duplicate (assume tree is a chain downwards) */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tdup_chain( Tree *t )\r
-#else\r
-tdup_chain( t )\r
-Tree *t;\r
-#endif\r
-{\r
- Tree *u;\r
- \r
- if ( t == NULL ) return NULL;\r
- u = tnode(t->token);\r
- u->v.rk = t->v.rk;\r
- u->down = tdup(t->down);\r
- return u;\r
-}\r
-\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tappend( Tree *t, Tree *u )\r
-#else\r
-tappend( t, u )\r
-Tree *t;\r
-Tree *u;\r
-#endif\r
-{\r
- Tree *w;\r
-\r
-/*** fprintf(stderr, "tappend(");\r
- *** preorder(t); fprintf(stderr, ",");\r
- *** preorder(u); fprintf(stderr, " )\n");\r
-*/\r
- if ( t == NULL ) return u;\r
- if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);\r
- for (w=t; w->right!=NULL; w=w->right) {;}\r
- w->right = u;\r
- return t;\r
-}\r
-\r
-/* dealloc all nodes in a tree */\r
-void\r
-#ifdef __USE_PROTOS\r
-Tfree( Tree *t )\r
-#else\r
-Tfree( t )\r
-Tree *t;\r
-#endif\r
-{\r
- if ( t == NULL ) return;\r
- Tfree( t->down );\r
- Tfree( t->right );\r
- _Tfree( t );\r
-}\r
-\r
-/* find all children (alts) of t that require remaining_k nodes to be LL_k\r
- * tokens long.\r
- *\r
- * t-->o\r
- * |\r
- * a1--a2--...--an <-- LL(1) tokens\r
- * | | |\r
- * b1 b2 ... bn <-- LL(2) tokens\r
- * | | |\r
- * . . .\r
- * . . .\r
- * z1 z2 ... zn <-- LL(LL_k) tokens\r
- *\r
- * We look for all [Ep] needing remaining_k nodes and replace with u.\r
- * u is not destroyed or actually used by the tree (a copy is made).\r
- */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tlink( Tree *t, Tree *u, int remaining_k )\r
-#else\r
-tlink( t, u, remaining_k )\r
-Tree *t;\r
-Tree *u;\r
-int remaining_k;\r
-#endif\r
-{\r
- Tree *p;\r
- require(remaining_k!=0, "tlink: bad tree");\r
-\r
- if ( t==NULL ) return NULL;\r
- /*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/\r
- if ( t->token == EpToken && t->v.rk == remaining_k )\r
- {\r
- require(t->down==NULL, "tlink: invalid tree");\r
- if ( u == NULL ) {\r
-/* MR10 */ Tree *tt=t->right;\r
-/* MR10 */ _Tfree(t);\r
-/* MR10 */ return tt;\r
- };\r
- p = tdup( u );\r
- p->right = t->right;\r
- _Tfree( t );\r
- return p;\r
- }\r
- t->down = tlink(t->down, u, remaining_k);\r
- t->right = tlink(t->right, u, remaining_k);\r
- return t;\r
-}\r
-\r
-/* remove as many ALT nodes as possible while still maintaining semantics */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tshrink( Tree *t )\r
-#else\r
-tshrink( t )\r
-Tree *t;\r
-#endif\r
-{\r
- if ( t == NULL ) return NULL;\r
- t->down = tshrink( t->down );\r
- t->right = tshrink( t->right );\r
- if ( t->down == NULL )\r
- {\r
- if ( t->token == ALT )\r
- {\r
- Tree *u = t->right;\r
- _Tfree(t);\r
- return u; /* remove useless alts */\r
- }\r
- return t;\r
- }\r
-\r
- /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */\r
- if ( t->token == ALT && t->down->right == NULL)\r
- {\r
- Tree *u = t->down;\r
- u->right = t->right;\r
- _Tfree( t );\r
- return u;\r
- }\r
- /* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */\r
- if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )\r
- {\r
- Tree *u = t->down->down;\r
- _Tfree( t->down );\r
- t->down = u;\r
- return t;\r
- }\r
- return t;\r
-}\r
-\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tflatten( Tree *t )\r
-#else\r
-tflatten( t )\r
-Tree *t;\r
-#endif\r
-{\r
- if ( t == NULL ) return NULL;\r
- t->down = tflatten( t->down );\r
- t->right = tflatten( t->right );\r
- if ( t->down == NULL ) return t;\r
- \r
- if ( t->token == ALT )\r
- {\r
- Tree *u;\r
- /* find tail of children */\r
- for (u=t->down; u->right!=NULL; u=u->right) {;}\r
- u->right = t->right;\r
- u = t->down;\r
- _Tfree( t );\r
- return u;\r
- }\r
- return t;\r
-}\r
-\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tJunc( Junction *p, int k, set *rk )\r
-#else\r
-tJunc( p, k, rk )\r
-Junction *p;\r
-int k;\r
-set *rk;\r
-#endif\r
-{\r
- Tree *t=NULL, *u=NULL;\r
- Junction *alt;\r
- Tree *tail=NULL, *r;\r
-\r
-#ifdef DBG_TRAV\r
- fprintf(stderr, "tJunc(%d): %s in rule %s\n", k,\r
- decodeJType[p->jtype], ((Junction *)p)->rname);\r
-#endif\r
-\r
-/* MR14 */ if (AlphaBetaTrace && p->alpha_beta_guess_end) {\r
-/* MR14 */ warnFL(\r
-/* MR14 */ "not possible to compute follow set for alpha in an \"(alpha)? beta\" block. ",\r
-/* MR14 */ FileStr[p->file],p->line);\r
-/* MR14 */ MR_alphaBetaTraceReport();\r
-/* MR14 */ };\r
-\r
-/* MR14 */ if (p->alpha_beta_guess_end) {\r
-/* MR14 */ return NULL;\r
-/* MR14 */ }\r
-\r
- if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||\r
- p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )\r
- {\r
- if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {\r
- require(p->lock!=NULL, "rJunc: lock array is NULL");\r
- if ( p->lock[k] ) return NULL;\r
- p->lock[k] = TRUE;\r
- }\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);\r
-/* MR10 */ };\r
-\r
- TRAV(p->p1, k, rk, tail);\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);\r
-/* MR10 */ };\r
-\r
- if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}\r
- r = tmake(tnode(ALT), tail, NULL);\r
- for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)\r
- {\r
- /* if this is one of the added optional alts for (...)+ then break */\r
- if ( alt->ignore ) break;\r
-\r
- if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}\r
- else\r
- {\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);\r
-/* MR10 */ };\r
-\r
- TRAV(alt->p1, k, rk, tail->right);\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);\r
-/* MR10 */ };\r
- if ( tail->right != NULL ) tail = tail->right;\r
- }\r
- }\r
- if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;\r
-#ifdef DBG_TREES\r
- fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n");\r
-#endif\r
- if ( r->down == NULL ) {_Tfree(r); return NULL;}\r
- return r;\r
- }\r
-\r
- if ( p->jtype==EndRule )\r
- {\r
- if ( p->halt ) /* don't want FOLLOW here? */\r
- {\r
-/**** if ( ContextGuardTRAV ) return NULL; ****/\r
- set_orel( (unsigned) k, rk); /* indicate this k value needed */ /* MR10 cast */\r
- t = tnode(EpToken);\r
- t->v.rk = k;\r
- return t;\r
- }\r
- require(p->lock!=NULL, "rJunc: lock array is NULL");\r
- if ( p->lock[k] ) return NULL;\r
- /* if no FOLLOW assume k EOF's */\r
- if ( p->p1 == NULL ) return eofnode(k);\r
- p->lock[k] = TRUE;\r
- }\r
-\r
-/* MR14 */ if (p->p1 != NULL && p->guess && p->guess_analysis_point == NULL) {\r
-/* MR14 */ Node * guess_point;\r
-/* MR14 */ guess_point=(Node *)analysis_point(p);\r
-/* MR14 */ if (guess_point == (Node *)p) {\r
-/* MR14 */ guess_point=p->p1;\r
-/* MR14 */ }\r
-/* MR14 */ p->guess_analysis_point=guess_point;\r
-/* MR14 */ } \r
-\r
- if ( p->p2 == NULL )\r
- {\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);\r
-/* MR10 */ };\r
-\r
-/* M14 */ if (p->guess_analysis_point != NULL) {\r
-/* M14 */ TRAV(p->guess_analysis_point, k, rk,t);\r
-/* M14 */ } else {\r
- TRAV(p->p1, k, rk,t);\r
-/* M14 */ }\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);\r
-/* MR10 */ };\r
-\r
- if ( p->jtype==EndRule ) p->lock[k]=FALSE;\r
- return t;\r
- }\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);\r
-/* MR10 */ };\r
-\r
-/* M14 */ if (p->guess_analysis_point != NULL) {\r
-/* M14 */ TRAV(p->guess_analysis_point, k, rk,t);\r
-/* M14 */ } else {\r
- TRAV(p->p1, k, rk,t);\r
-/* M14 */ }\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);\r
-/* MR10 */ };\r
-\r
- if ( p->jtype!=RuleBlk && /* MR14 */ !p->guess) TRAV(p->p2, k, rk, u);\r
-\r
- if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */\r
-\r
- if ( t==NULL ) return tmake(tnode(ALT), u, NULL);\r
- return tmake(tnode(ALT), t, u, NULL);\r
-}\r
-\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tRuleRef( RuleRefNode *p, int k, set *rk_out )\r
-#else\r
-tRuleRef( p, k, rk_out )\r
-RuleRefNode *p;\r
-int k;\r
-set *rk_out;\r
-#endif\r
-{\r
- int k2;\r
- Tree *t=NULL, *u=NULL;\r
- Junction *r;\r
- set rk, rk2;\r
- int save_halt;\r
- RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);\r
- \r
-#ifdef DBG_TRAV\r
- fprintf(stderr, "tRuleRef: %s\n", p->text);\r
-#endif\r
- if ( q == NULL )\r
- {\r
- TRAV(p->next, k, rk_out, t);/* ignore undefined rules */\r
- return t;\r
- }\r
- rk = rk2 = empty;\r
- if (RulePtr == NULL) fatal("RulePtr==NULL");\r
- r = RulePtr[q->rulenum];\r
- if ( r->lock[k] ) return NULL;\r
- save_halt = r->end->halt;\r
- r->end->halt = TRUE; /* don't let reach fall off end of rule here */\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p);\r
-/* MR10 */ };\r
-\r
- TRAV(r, k, &rk, t);\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ MR_pointerStackPop(&MR_BackTraceStack);\r
-/* MR10 */ };\r
-\r
- r->end->halt = save_halt;\r
-#ifdef DBG_TREES\r
- fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n");\r
-#endif\r
- t = tshrink( t );\r
- while ( !set_nil(rk) ) { /* any k left to do? if so, link onto tree */\r
- k2 = set_int(rk);\r
- set_rm(k2, rk);\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p);\r
-/* MR10 */ };\r
-\r
- TRAV(p->next, k2, &rk2, u);\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ MR_pointerStackPop(&MR_BackTraceStack);\r
-/* MR10 */ };\r
-\r
- t = tlink(t, u, k2); /* any alts missing k2 toks, add u onto end */\r
- Tfree(u); /* MR10 */\r
- }\r
- set_free(rk); /* rk is empty, but free it's memory */\r
- set_orin(rk_out, rk2); /* remember what we couldn't do */\r
- set_free(rk2);\r
- return t;\r
-}\r
-\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tToken( TokNode *p, int k, set *rk )\r
-#else\r
-tToken( p, k, rk )\r
-TokNode *p;\r
-int k;\r
-set *rk;\r
-#endif\r
-{\r
- Tree *t=NULL, *tset=NULL, *u;\r
-\r
- if (ConstrainSearch) {\r
- if (MR_AmbSourceSearch) {\r
- require(constrain>=fset&&constrain<=&(fset[CLL_k]),"tToken: constrain is not a valid set");\r
- } else {\r
- require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");\r
- };\r
- constrain = &fset[maxk-k+1];\r
- }\r
-\r
-#ifdef DBG_TRAV\r
- fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token));\r
- if ( ConstrainSearch ) {\r
- fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n");\r
- }\r
-#endif\r
-\r
- /* is it a meta token (set of tokens)? */\r
-\r
- if ( !set_nil(p->tset) )\r
- {\r
- unsigned e=0;\r
- set a;\r
- Tree *n, *tail = NULL;\r
-\r
- if ( ConstrainSearch ) {\r
- a = set_and(p->tset, *constrain);\r
- if (set_nil(a)) { /* MR10 */\r
- set_free(a); /* MR11 */\r
- return NULL; /* MR10 */\r
- }; /* MR10 */\r
- } else {\r
- a = set_dup(p->tset);\r
- };\r
-\r
- for (; !set_nil(a); set_rm(e, a))\r
- {\r
- e = set_int(a);\r
- n = tnode(e);\r
- if ( tset==NULL ) { tset = n; tail = n; }\r
- else { tail->right = n; tail = n; }\r
- }\r
- set_free( a );\r
- }\r
- else if ( ConstrainSearch && !set_el(p->token, *constrain) )\r
- {\r
-/* fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),\r
- k);*/\r
- return NULL;\r
- }\r
- else {\r
- tset = tnode( p->token );\r
- };\r
-\r
-/* MR10 */ if (MR_MaintainBackTrace) {\r
-/* MR10 */ if (k == 1) {\r
-/* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p);\r
-/* MR13 */ if (MR_SuppressSearch) {\r
-/* MR13 */ MR_suppressSearchReport();\r
-/* MR13 */ } else {\r
-/* MR10 */ MR_backTraceReport();\r
-/* MR13 */ };\r
-/* MR10 */ MR_pointerStackPop(&MR_BackTraceStack);\r
-/* MR11 */ Tfree(tset);\r
-/* MR11 */ return NULL;\r
-/* MR10 */ };\r
-/* MR10 */ };\r
-\r
- if ( k == 1 ) return tset;\r
-\r
- if (MR_MaintainBackTrace) {\r
- MR_pointerStackPush(&MR_BackTraceStack,p);\r
- };\r
-\r
- TRAV(p->next, k-1, rk, t);\r
-\r
- if (MR_MaintainBackTrace) {\r
- Tfree(t);\r
- Tfree(tset);\r
- MR_pointerStackPop(&MR_BackTraceStack);\r
- return NULL;\r
- };\r
-\r
- /* here, we are positive that, at least, this tree will not contribute\r
- * to the LL(2) tree since it will be too shallow, IF t==NULL.\r
- * If doing a context guard walk, then don't prune.\r
- */\r
- if ( t == NULL && !ContextGuardTRAV ) /* tree will be too shallow */\r
- {\r
- if ( tset!=NULL ) Tfree( tset );\r
- return NULL;\r
- }\r
-#ifdef DBG_TREES\r
- fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n");\r
-#endif\r
-\r
- /* if single token root, then just make new tree and return */\r
- /* MR10 - set_nil(p->tset) isn't a good test because of ConstraintSearch */\r
-\r
- if (tset->right == NULL) return tmake(tset, t, NULL); /* MR10 */\r
-\r
- /* here we must make a copy of t as a child of each element of the tset;\r
- * e.g., "T1..T3 A" would yield ( nil ( T1 A ) ( T2 A ) ( T3 A ) )\r
- */\r
- for (u=tset; u!=NULL; u=u->right)\r
- {\r
- /* make a copy of t and hook it onto bottom of u */\r
- u->down = tdup(t);\r
- }\r
- Tfree( t );\r
-#ifdef DBG_TREES\r
- fprintf(stderr, "range is:"); preorder(tset); fprintf(stderr, "\n");\r
-#endif\r
- return tset;\r
-}\r
-\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tAction( ActionNode *p, int k, set *rk )\r
-#else\r
-tAction( p, k, rk )\r
-ActionNode *p;\r
-int k;\r
-set *rk;\r
-#endif\r
-{\r
- Tree *t=NULL;\r
- set *save_fset=NULL;\r
- int i;\r
-\r
- /* fprintf(stderr, "tAction\n"); */\r
-\r
-/* An MR_SuppressSearch is looking for things that can be\r
- reached even when the predicate is false.\r
-\r
- There are three kinds of predicates:\r
- plain: r1: <<p>>? r2\r
- guarded: r1: (A)? => <<p>>? r2\r
- ampersand style: r1: (A)? && <<p>>? r2\r
-\r
- Of the three kinds of predicates, only a guard predicate\r
- has things which are reachable even when the predicate\r
- is false. To be reachable the constraint must *not*\r
- match the guard.\r
-\r
-*/\r
-\r
- if (p->is_predicate && MR_SuppressSearch) {\r
-\r
- Predicate *pred=p->guardpred;\r
-\r
- if (pred == NULL) {\r
- t=NULL;\r
- goto EXIT;\r
- };\r
- constrain = &fset[maxk-k+1];\r
- if (pred->k == 1) {\r
- set dif;\r
- dif=set_dif(*constrain,pred->scontext[1]);\r
- if (set_nil(dif)) {\r
- set_free(dif);\r
- t=NULL;\r
- goto EXIT;\r
- };\r
- set_free(dif);\r
- } else {\r
- if (MR_tree_matches_constraints(k,constrain,pred->tcontext)) {\r
- t=NULL;\r
- goto EXIT;\r
- };\r
- }\r
- };\r
-\r
- /* The ampersand predicate differs from the\r
- other predicates because its first set\r
- is a subset of the first set behind the predicate\r
-\r
- r1: (A)? && <<p>>? r2 ;\r
- r2: A | B;\r
-\r
- In this case first[1] of r1 is A, even\r
- though first[1] of r2 is {A B}.\r
- */\r
-\r
- if (p->is_predicate && p->ampersandPred != NULL) {\r
-\r
- Predicate *pred=p->ampersandPred;\r
- Tree *tAND;\r
- Tree *tset;\r
-\r
- if (k <= pred->k) {\r
- if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);\r
- TRAV(p->guardNodes,k,rk,t);\r
- if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);\r
- return t;\r
- } else {\r
- require (k>1,"tAction for ampersandpred: k <= 1");\r
- if (ConstrainSearch) {\r
- if (MR_AmbSourceSearch) {\r
- require(constrain>=fset&&constrain<=&(fset[CLL_k]),\r
- "tToken: constrain is not a valid set");\r
- } else {\r
- require(constrain>=fset&&constrain<=&(fset[LL_k]),\r
- "tToken: constrain is not a valid set");\r
- };\r
- save_fset=(set *) calloc (CLL_k+1,sizeof(set));\r
- require (save_fset != NULL,"tAction save_fset alloc");\r
- for (i=1; i <= CLL_k ; i++) {\r
- save_fset[i]=set_dup(fset[i]);\r
- };\r
- if (pred->k == 1) {\r
- constrain = &fset[maxk-k+1];\r
- set_andin(constrain,pred->scontext[1]);\r
- if (set_nil(*constrain)) {\r
- t=NULL;\r
- goto EXIT;\r
- };\r
- } else {\r
- constrain = &fset[maxk-k+1];\r
- if (! MR_tree_matches_constraints(pred->k,constrain,pred->tcontext)) {\r
- t=NULL;\r
- goto EXIT;\r
- }; /* end loop on i */\r
- }; /* end loop on pred scontext/tcontext */\r
- }; /* end if on k > pred->k */\r
- }; /* end if on constrain search */\r
-\r
- TRAV(p->next,k,rk,t);\r
-\r
- if (t != NULL) {\r
- t=tshrink(t);\r
- t=tflatten(t);\r
- t=tleft_factor(t);\r
- if (pred->tcontext != NULL) {\r
- tAND=MR_computeTreeAND(t,pred->tcontext);\r
- } else {\r
- tset=MR_make_tree_from_set(pred->scontext[1]);\r
- tAND=MR_computeTreeAND(t,tset);\r
- Tfree(tset);\r
- };\r
- Tfree(t);\r
- t=tAND;\r
- };\r
- goto EXIT;\r
-\r
- }; /* end if on ampersand predicate */\r
-\r
- TRAV(p->next,k,rk,t);\r
-\r
-EXIT:\r
- if (save_fset != NULL) {\r
- for (i=1 ; i <= CLL_k ; i++) {\r
- set_free(fset[i]);\r
- fset[i]=save_fset[i];\r
- };\r
- free ( (char *) save_fset);\r
- };\r
- return t;\r
-}\r
-\r
-/* see if e exists in s as a possible input permutation (e is always a chain) */\r
-\r
-int\r
-#ifdef __USE_PROTOS\r
-tmember( Tree *e, Tree *s )\r
-#else\r
-tmember( e, s )\r
-Tree *e;\r
-Tree *s;\r
-#endif\r
-{\r
- if ( e==NULL||s==NULL ) return 0;\r
-/** fprintf(stderr, "tmember(");\r
-*** preorder(e); fprintf(stderr, ",");\r
-*** preorder(s); fprintf(stderr, " )\n");\r
-*/\r
- if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);\r
- if ( e->token!=s->token )\r
- {\r
- if ( s->right==NULL ) return 0;\r
- return tmember(e, s->right);\r
- }\r
- if ( e->down==NULL && s->down == NULL ) return 1;\r
- if ( tmember(e->down, s->down) ) return 1;\r
- if ( s->right==NULL ) return 0;\r
- return tmember(e, s->right);\r
-}\r
-\r
-/* see if e exists in s as a possible input permutation (e is always a chain);\r
- * Only check s to the depth of e. In other words, 'e' can be a shorter\r
- * sequence than s.\r
- */\r
-int\r
-#ifdef __USE_PROTOS\r
-tmember_constrained( Tree *e, Tree *s)\r
-#else\r
-tmember_constrained( e, s )\r
-Tree *e;\r
-Tree *s;\r
-#endif\r
-{\r
- if ( e==NULL||s==NULL ) return 0;\r
-/** fprintf(stderr, "tmember_constrained(");\r
-*** preorder(e); fprintf(stderr, ",");\r
-*** preorder(s); fprintf(stderr, " )\n");\r
-**/\r
- if ( s->token == ALT && s->right == NULL )\r
- return tmember_constrained(e, s->down);\r
- if ( e->token!=s->token )\r
- {\r
- if ( s->right==NULL ) return 0;\r
- return tmember_constrained(e, s->right);\r
- }\r
- if ( e->down == NULL ) return 1; /* if s is matched to depth of e return */\r
- if ( tmember_constrained(e->down, s->down) ) return 1;\r
- if ( s->right==NULL ) return 0;\r
- return tmember_constrained(e, s->right);\r
-}\r
-\r
-/* combine (? (A t) ... (A u) ...) into (? (A t u)) */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tleft_factor( Tree *t )\r
-#else\r
-tleft_factor( t )\r
-Tree *t;\r
-#endif\r
-{\r
- Tree *u, *v, *trail, *w;\r
-\r
- /* left-factor what is at this level */\r
- if ( t == NULL ) return NULL;\r
- for (u=t; u!=NULL; u=u->right)\r
- {\r
- trail = u;\r
- v=u->right;\r
- while ( v!=NULL )\r
- {\r
- if ( u->token == v->token )\r
- {\r
- if ( u->down!=NULL )\r
- {\r
- for (w=u->down; w->right!=NULL; w=w->right) {;}\r
- w->right = v->down; /* link children together */\r
- }\r
- else u->down = v->down;\r
- trail->right = v->right; /* unlink factored node */\r
- _Tfree( v );\r
- v = trail->right;\r
- }\r
- else {trail = v; v=v->right;}\r
- }\r
- }\r
- /* left-factor what is below */\r
- for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );\r
- return t;\r
-}\r
-\r
-/* remove the permutation p from t if present */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-trm_perm( Tree *t, Tree *p )\r
-#else\r
-trm_perm( t, p )\r
-Tree *t;\r
-Tree *p;\r
-#endif\r
-{\r
- /*\r
- fprintf(stderr, "trm_perm(");\r
- preorder(t); fprintf(stderr, ",");\r
- preorder(p); fprintf(stderr, " )\n");\r
- */\r
- if ( t == NULL || p == NULL ) return NULL;\r
- if ( t->token == ALT )\r
- {\r
- t->down = trm_perm(t->down, p);\r
- if ( t->down == NULL ) /* nothing left below, rm cur node */\r
- {\r
- Tree *u = t->right;\r
- _Tfree( t );\r
- return trm_perm(u, p);\r
- }\r
- t->right = trm_perm(t->right, p); /* look for more instances of p */\r
- return t;\r
- }\r
- if ( p->token != t->token ) /* not found, try a sibling */\r
- {\r
- t->right = trm_perm(t->right, p);\r
- return t;\r
- }\r
- t->down = trm_perm(t->down, p->down);\r
- if ( t->down == NULL ) /* nothing left below, rm cur node */\r
- {\r
- Tree *u = t->right;\r
- _Tfree( t );\r
- return trm_perm(u, p);\r
- }\r
- t->right = trm_perm(t->right, p); /* look for more instances of p */\r
- return t;\r
-}\r
-\r
-/* add the permutation 'perm' to the LL_k sets in 'fset' */\r
-void\r
-#ifdef __USE_PROTOS\r
-tcvt( set *fset, Tree *perm )\r
-#else\r
-tcvt( fset, perm )\r
-set *fset;\r
-Tree *perm;\r
-#endif\r
-{\r
- if ( perm==NULL ) return;\r
- set_orel(perm->token, fset);\r
- tcvt(fset+1, perm->down);\r
-}\r
-\r
-/* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])\r
- * as a child.\r
- */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-permute( int k, int max_k )\r
-#else\r
-permute( k, max_k )\r
-int k, max_k;\r
-#endif\r
-{\r
- Tree *t, *u;\r
- \r
- if ( k>max_k ) return NULL;\r
- if ( ftbl[k][findex[k]] == nil ) return NULL;\r
- t = permute(k+1, max_k);\r
- if ( t==NULL&&k<max_k ) /* no permutation left below for k+1 tokens? */\r
- {\r
- findex[k+1] = 0;\r
- (findex[k])++; /* try next token at this k */\r
- return permute(k, max_k);\r
- }\r
- \r
- u = tmake(tnode(ftbl[k][findex[k]]), t, NULL);\r
- if ( k == max_k ) (findex[k])++;\r
- return u;\r
-}\r
-\r
-/* Compute LL(k) trees for alts alt1 and alt2 of p.\r
- * function result is tree of ambiguous input permutations\r
- *\r
- * ALGORITHM may change to look for something other than LL_k size\r
- * trees ==> maxk will have to change.\r
- */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig )\r
-#else\r
-VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig )\r
-Junction *alt1;\r
-Junction *alt2;\r
-unsigned **ft;\r
-set *fs;\r
-Tree **t;\r
-Tree **u;\r
-int *numAmbig;\r
-#endif\r
-{\r
- set rk;\r
- Tree *perm, *ambig=NULL;\r
- Junction *p;\r
- int k;\r
- int tnodes_at_start=TnodesAllocated;\r
- int tnodes_at_end;\r
- int tnodes_used;\r
- set *save_fs;\r
- int j;\r
-\r
- save_fs=(set *) calloc(CLL_k+1,sizeof(set));\r
- require(save_fs != NULL,"save_fs calloc");\r
-\r
- for (j=0; j <= CLL_k ; j++) save_fs[j]=set_dup(fs[j]);\r
-\r
- maxk = LL_k; /* NOTE: for now, we look for LL_k */\r
- ftbl = ft;\r
- fset = fs;\r
- constrain = &(fset[1]);\r
- findex = (int *) calloc(LL_k+1, sizeof(int));\r
- if ( findex == NULL )\r
- {\r
- fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);\r
- fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n",\r
- CurAmbigAlt1,\r
- CurAmbigAlt2,\r
- CurAmbigbtype);\r
- exit(PCCTS_EXIT_FAILURE);\r
- }\r
- for (k=1; k<=LL_k; k++) findex[k] = 0;\r
-\r
- rk = empty;\r
- ConstrainSearch = 1; /* consider only tokens in ambig sets */\r
-\r
- p = analysis_point((Junction *)alt1->p1);\r
- TRAV(p, LL_k, &rk, *t);\r
- *t = tshrink( *t );\r
- *t = tflatten( *t );\r
- *t = tleft_factor( *t ); /* MR10 */\r
- *t = prune(*t, LL_k);\r
- *t = tleft_factor( *t );\r
-\r
-/*** fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/\r
- if ( *t == NULL )\r
- {\r
-/*** fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/\r
- Tfree( *t ); /* kill if impossible to have ambig */\r
- *t = NULL;\r
- }\r
-\r
- p = analysis_point((Junction *)alt2->p1);\r
-\r
- TRAV(p, LL_k, &rk, *u);\r
- *u = tshrink( *u );\r
- *u = tflatten( *u );\r
- *t = tleft_factor( *t ); /* MR10 */\r
- *u = prune(*u, LL_k);\r
- *u = tleft_factor( *u );\r
-/* fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/\r
- if ( *u == NULL )\r
- {\r
-/* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/\r
- Tfree( *u );\r
- *u = NULL;\r
- }\r
-\r
- for (k=1; k<=LL_k; k++) set_clr( fs[k] );\r
-\r
- ambig = tnode(ALT);\r
- k = 0;\r
- if ( *t!=NULL && *u!=NULL )\r
- {\r
- while ( (perm=permute(1,LL_k))!=NULL )\r
- {\r
-/* fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/\r
- if ( tmember(perm, *t) && tmember(perm, *u) )\r
- {\r
-/* fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/\r
-\r
- k++;\r
- perm->right = ambig->down;\r
- ambig->down = perm;\r
- tcvt(&(fs[1]), perm);\r
- }\r
- else Tfree( perm );\r
- }\r
- }\r
-\r
- for (j=0; j <= CLL_k ; j++) fs[j]=save_fs[j];\r
- free( (char *) save_fs);\r
-\r
- tnodes_at_end=TnodesAllocated;\r
- tnodes_used=tnodes_at_end - tnodes_at_start;\r
-\r
- if (TnodesReportThreshold > 0 && tnodes_used > TnodesReportThreshold) {\r
- fprintf(stdout,"There were %d tuples whose ambiguity could not be resolved by full lookahead\n",k);\r
- fprintf(stdout,"There were %d tnodes created to resolve ambiguity between:\n\n",tnodes_used);\r
- fprintf(stdout," Choice 1: %s line %d file %s\n",\r
- MR_ruleNamePlusOffset( (Node *) alt1),alt1->line,FileStr[alt1->file]);\r
- fprintf(stdout," Choice 2: %s line %d file %s\n",\r
- MR_ruleNamePlusOffset( (Node *) alt2),alt2->line,FileStr[alt2->file]);\r
- for (j=1; j <= CLL_k ; j++) {\r
- fprintf(stdout,"\n Intersection of lookahead[%d] sets:\n",j);\r
- MR_dumpTokenSet(stdout,2,fs[j]);\r
- };\r
- fprintf(stdout,"\n");\r
- };\r
-\r
- *numAmbig = k;\r
- if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;}\r
- free( (char *)findex );\r
-/* fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/\r
- return ambig;\r
-}\r
-\r
-static Tree *\r
-#ifdef __USE_PROTOS\r
-bottom_of_chain( Tree *t )\r
-#else\r
-bottom_of_chain( t )\r
-Tree *t;\r
-#endif\r
-{\r
- if ( t==NULL ) return NULL;\r
- for (; t->down != NULL; t=t->down) {;}\r
- return t;\r
-}\r
-\r
-/*\r
- * Make a tree from k sets where the degree of the first k-1 sets is 1.\r
- */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-make_tree_from_sets( set *fset1, set *fset2 )\r
-#else\r
-make_tree_from_sets( fset1, fset2 )\r
-set *fset1;\r
-set *fset2;\r
-#endif\r
-{\r
- set inter;\r
- int i;\r
- Tree *t=NULL, *n, *u;\r
- unsigned *p,*q;\r
- require(LL_k>1, "make_tree_from_sets: LL_k must be > 1");\r
-\r
- /* do the degree 1 sets first */\r
- for (i=1; i<=LL_k-1; i++)\r
- {\r
- inter = set_and(fset1[i], fset2[i]);\r
- require(set_deg(inter)==1, "invalid set to tree conversion");\r
- n = tnode(set_int(inter));\r
- if (t==NULL) t=n; else tmake(t, n, NULL);\r
- set_free(inter);\r
- }\r
-\r
- /* now add the chain of tokens at depth k */\r
- u = bottom_of_chain(t);\r
- inter = set_and(fset1[LL_k], fset2[LL_k]);\r
- if ( (q=p=set_pdq(inter)) == NULL ) fatal_internal("Can't alloc space for set_pdq");\r
- /* first one is linked to bottom, then others are sibling linked */\r
- n = tnode(*p++);\r
- u->down = n;\r
- u = u->down;\r
- while ( *p != nil )\r
- {\r
- n = tnode(*p);\r
- u->right = n;\r
- u = u->right;\r
- p++;\r
- }\r
- free((char *)q);\r
-\r
- return t;\r
-}\r
-\r
-/* create and return the tree of lookahead k-sequences that are in t, but not\r
- * in the context of predicates in predicate list p.\r
- */\r
-Tree *\r
-#ifdef __USE_PROTOS\r
-tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 )\r
-#else\r
-tdif( ambig_tuples, p, fset1, fset2 )\r
-Tree *ambig_tuples;\r
-Predicate *p;\r
-set *fset1;\r
-set *fset2;\r
-#endif\r
-{\r
- unsigned **ft;\r
- Tree *dif=NULL;\r
- Tree *perm;\r
- set b;\r
- int i,k;\r
-\r
- if ( p == NULL ) return tdup(ambig_tuples);\r
-\r
- ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));\r
- require(ft!=NULL, "cannot allocate ft");\r
- for (i=1; i<=CLL_k; i++)\r
- {\r
- b = set_and(fset1[i], fset2[i]);\r
- ft[i] = set_pdq(b);\r
- set_free(b);\r
- }\r
- findex = (int *) calloc(LL_k+1, sizeof(int));\r
- if ( findex == NULL )\r
- {\r
- fatal_internal("out of memory in tdif while checking predicates");\r
- }\r
- for (k=1; k<=LL_k; k++) findex[k] = 0;\r
-\r
-#ifdef DBG_TRAV\r
- fprintf(stderr, "tdif_%d[", p->k);\r
- preorder(ambig_tuples);\r
- fprintf(stderr, ",");\r
- preorder(p->tcontext);\r
- fprintf(stderr, "] =");\r
-#endif\r
-\r
- ftbl = ft;\r
- while ( (perm=permute(1,p->k))!=NULL )\r
- {\r
-#ifdef DBG_TRAV\r
- fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "\n");\r
-#endif\r
- if ( tmember_constrained(perm, ambig_tuples) &&\r
- !tmember_of_context(perm, p) )\r
- {\r
-#ifdef DBG_TRAV\r
- fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "\n");\r
-#endif\r
- k++;\r
- if ( dif==NULL ) dif = perm;\r
- else\r
- {\r
- perm->right = dif;\r
- dif = perm;\r
- }\r
- }\r
- else Tfree( perm );\r
- }\r
-\r
-#ifdef DBG_TRAV\r
- preorder(dif);\r
- fprintf(stderr, "\n");\r
-#endif\r
-\r
- for (i=1; i<=CLL_k; i++) free( (char *)ft[i] );\r
- free((char *)ft);\r
- free((char *)findex);\r
-\r
- return dif;\r
-}\r
-\r
-/* is lookahead sequence t a member of any context tree for any\r
- * predicate in p?\r
- */\r
-static int\r
-#ifdef __USE_PROTOS\r
-tmember_of_context( Tree *t, Predicate *p )\r
-#else\r
-tmember_of_context( t, p )\r
-Tree *t;\r
-Predicate *p;\r
-#endif\r
-{\r
- for (; p!=NULL; p=p->right)\r
- {\r
- if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST )\r
- return tmember_of_context(t, p->down);\r
- if ( tmember_constrained(t, p->tcontext) ) return 1;\r
- if ( tmember_of_context(t, p->down) ) return 1;\r
- }\r
- return 0;\r
-}\r
-\r
-int\r
-#ifdef __USE_PROTOS\r
-is_single_tuple( Tree *t )\r
-#else\r
-is_single_tuple( t )\r
-Tree *t;\r
-#endif\r
-{\r
- if ( t == NULL ) return 0;\r
- if ( t->right != NULL ) return 0;\r
- if ( t->down == NULL ) return 1;\r
- return is_single_tuple(t->down);\r
-}\r
-\r
-\r
-/* MR10 Check that a context guard contains only allowed things */\r
-/* MR10 (mainly token references). */\r
-\r
-#ifdef __USE_PROTOS\r
-int contextGuardOK(Node *p,int h,int *hmax)\r
-#else\r
-int contextGuardOK(p,h,hmax)\r
- Node *p;\r
- int h;\r
- int *hmax;\r
-#endif\r
-{\r
- Junction *j;\r
- TokNode *tn;\r
-\r
- if (p == NULL) return 1;\r
- if (p->ntype == nToken) {\r
- h++;\r
- if (h > *hmax) *hmax=h;\r
- tn=(TokNode *)p;\r
- if (tn->el_label != NULL) {\r
- warnFL(eMsg1("a label (\"%s\") for a context guard element is meaningless",tn->el_label),\r
- FileStr[p->file],p->line);\r
- };\r
- return contextGuardOK( ( (TokNode *) p)->next,h,hmax);\r
- } else if (p->ntype == nAction) {\r
- goto Fail;\r
- } else if (p->ntype == nRuleRef) {\r
- goto Fail;\r
- } else {\r
- require (p->ntype == nJunction,"Unexpected ntype");\r
- j=(Junction *) p;\r
- if (j->jtype != Generic &&\r
- j->jtype != aSubBlk && /* pretty sure this one is allowed */\r
-/**** j->jtype != aOptBlk && ****/ /* pretty sure this one is allowed */ /* MR11 not any more ! */\r
- j->jtype != EndBlk) {\r
- errFL("A context guard may not contain an option block: {...} or looping block: (...)* or (...)+",\r
- FileStr[p->file],p->line);\r
- contextGuardOK(j->p1,h,hmax);\r
- return 0;\r
- };\r
- /* do both p1 and p2 so use | rather than || */\r
- return contextGuardOK(j->p2,h,hmax) | contextGuardOK(j->p1,h,hmax);\r
- };\r
-Fail:\r
- errFL("A context guard may contain only Token references - guard will be ignored",\r
- FileStr[p->file],p->line);\r
- contextGuardOK( ( (ActionNode *) p)->next,h,hmax);\r
- return 0;\r
-}\r
-\r
-/*\r
- * Look at a (...)? generalized-predicate context-guard and compute\r
- * either a lookahead set (k==1) or a lookahead tree for k>1. The\r
- * k level is determined by the guard itself rather than the LL_k\r
- * variable. For example, ( A B )? is an LL(2) guard and ( ID )?\r
- * is an LL(1) guard. For the moment, you can only have a single\r
- * tuple in the guard. Physically, the block must look like this\r
- * --o-->TOKEN-->o-->o-->TOKEN-->o-- ... -->o-->TOKEN-->o--\r
- * An error is printed for any other type.\r
- */\r
-Predicate *\r
-#ifdef __USE_PROTOS\r
-computePredFromContextGuard(Graph blk,int *msgDone) /* MR10 */\r
-#else\r
-computePredFromContextGuard(blk,msgDone) /* MR10 */\r
- Graph blk;\r
- int *msgDone; /* MR10 */\r
-#endif\r
-{\r
- Junction *junc = (Junction *)blk.left, *p;\r
- Tree *t=NULL;\r
- Predicate *pred = NULL;\r
- set scontext, rk;\r
- int ok;\r
- int hmax=0;\r
-\r
- require(junc!=NULL && junc->ntype == nJunction, "bad context guard");\r
-\r
-/* MR10 Check for anything other than Tokens and generic junctions */\r
-\r
- *msgDone=0; /* MR10 */\r
- ok=contextGuardOK( (Node *)junc,0,&hmax); /* MR10 */\r
- if (! ok) { /* MR10 */\r
- *msgDone=1; /* MR10 */\r
- return NULL; /* MR10 */\r
- }; /* MR10 */\r
- if (hmax == 0) {\r
-errFL("guard is 0 tokens long",FileStr[junc->file],junc->line); /* MR11 */\r
- *msgDone=1;\r
- return NULL;\r
- };\r
- if (hmax > CLL_k) { /* MR10 */\r
-errFL(eMsgd2("guard is %d tokens long - lookahead is limited to max(k,ck)==%d", /* MR10 */\r
- hmax,CLL_k), /* MR10 */\r
- FileStr[junc->file],junc->line); /* MR10 */\r
- *msgDone=1; /* MR10 */\r
- return NULL; /* MR10 */\r
- }; /* MR10 */\r
-\r
- rk = empty;\r
- p = junc;\r
- pred = new_pred();\r
- pred->k = hmax; /* MR10 should be CLL_k, not LLK ? */\r
- if (hmax > 1 ) /* MR10 was LL_k */\r
- {\r
- ConstrainSearch = 0;\r
- ContextGuardTRAV = 1;\r
- TRAV(p, hmax, &rk, t); /* MR10 was LL_k */\r
- ContextGuardTRAV = 0;\r
- set_free(rk);\r
- t = tshrink( t );\r
- t = tflatten( t );\r
- t = tleft_factor( t );\r
-/*\r
- fprintf(stderr, "ctx guard:");\r
- preorder(t);\r
- fprintf(stderr, "\n");\r
-*/\r
- pred->tcontext = t;\r
- }\r
- else\r
- {\r
- REACH(p, 1, &rk, scontext);\r
- require(set_nil(rk), "rk != nil");\r
- set_free(rk);\r
-/*\r
- fprintf(stderr, "LL(1) ctx guard is:");\r
- s_fprT(stderr, scontext);\r
- fprintf(stderr, "\n");\r
-*/\r
- pred->scontext[1] = scontext;\r
- }\r
-\r
- list_add(&ContextGuardPredicateList,pred); /* MR13 */\r
-\r
- return pred;\r
-}\r
-\r
-/* MR13\r
- When the context guard is originally computed the\r
- meta-tokens are not known.\r
-*/\r
-\r
-#ifdef __USE_PROTOS\r
-void recomputeContextGuard(Predicate *pred)\r
-#else\r
-void recomputeContextGuard(pred)\r
- Predicate *pred;\r
-#endif\r
-{\r
- Tree * t=NULL;\r
- set scontext;\r
- set rk;\r
- ActionNode * actionNode;\r
- Junction * p;\r
-\r
- actionNode=pred->source;\r
- require (actionNode != NULL,"context predicate's source == NULL");\r
-\r
- p=actionNode->guardNodes;\r
- require (p != NULL,"context predicate's guardNodes == NULL");\r
-\r
- rk = empty;\r
- if (pred->k > 1 )\r
- {\r
- ConstrainSearch = 0;\r
- ContextGuardTRAV = 1;\r
- TRAV(p, pred->k, &rk, t);\r
- ContextGuardTRAV = 0;\r
- set_free(rk);\r
- t = tshrink( t );\r
- t = tflatten( t );\r
- t = tleft_factor( t );\r
- Tfree(pred->tcontext);\r
- pred->tcontext = t;\r
- }\r
- else\r
- {\r
- REACH(p, 1, &rk, scontext);\r
- require(set_nil(rk), "rk != nil");\r
- set_free(rk);\r
- set_free(pred->scontext[1]);\r
- pred->scontext[1] = scontext;\r
- }\r
-}\r
-\r
-/* MR11 - had enough of flags yet ? */\r
-\r
-int MR_AmbSourceSearch=0;\r
-int MR_AmbSourceSearchGroup=0;\r
-int MR_AmbSourceSearchChoice=0;\r
-int MR_AmbSourceSearchLimit=0;\r
-int MR_matched_AmbAidRule=0;\r
-\r
-static set *matchSets[2]={NULL,NULL};\r
-static int *tokensInChain=NULL;\r
-static Junction *MR_AmbSourceSearchJ[2];\r
-\r
-void MR_traceAmbSourceKclient()\r
-{\r
- int i;\r
- set *save_fset;\r
- int save_ConstrainSearch;\r
- set incomplete;\r
- Tree *t;\r
-\r
- if (matchSets[0] == NULL) {\r
- matchSets[0]=(set *) calloc (CLL_k+1,sizeof(set));\r
- require (matchSets[0] != NULL,"matchSets[0] alloc");\r
- matchSets[1]=(set *) calloc (CLL_k+1,sizeof(set));\r
- require (matchSets[1] != NULL,"matchSets[1] alloc");\r
- };\r
-\r
- for (i=1 ; i <= MR_AmbSourceSearchLimit ; i++) {\r
- set_clr(matchSets[0][i]);\r
- set_orel( (unsigned) tokensInChain[i],\r
- &matchSets[0][i]);\r
- set_clr(matchSets[1][i]);\r
- set_orel( (unsigned) tokensInChain[i],\r
- &matchSets[1][i]);\r
- };\r
-\r
- save_fset=fset;\r
- save_ConstrainSearch=ConstrainSearch;\r
-\r
-\r
-\r
- for (i=0 ; i < 2 ; i++) {\r
-\r
-#if 0\r
-** fprintf(stdout," Choice:%d Depth:%d ",i+1,MR_AmbSourceSearchLimit);\r
-** fprintf(stdout,"(");\r
-** for (j=1 ; j <= MR_AmbSourceSearchLimit ; j++) {\r
-** if (j != 1) fprintf(stdout," ");\r
-** fprintf(stdout,"%s",TerminalString(tokensInChain[j]));\r
-** };\r
-** fprintf(stdout,")\n\n");\r
-#endif\r
-\r
- fset=matchSets[i];\r
-\r
- MR_AmbSourceSearch=1;\r
- MR_MaintainBackTrace=1;\r
- MR_AmbSourceSearchChoice=i;\r
- ConstrainSearch=1;\r
-\r
- maxk = MR_AmbSourceSearchLimit;\r
-\r
- incomplete=empty;\r
- t=NULL;\r
-\r
- constrain = &(fset[1]);\r
- MR_pointerStackReset(&MR_BackTraceStack);\r
-\r
- TRAV(MR_AmbSourceSearchJ[i],maxk,&incomplete,t);\r
-\r
- Tfree(t);\r
-\r
- require (set_nil(incomplete),"MR_traceAmbSourceK TRAV incomplete");\r
- require (MR_BackTraceStack.count == 0,"K: MR_BackTraceStack.count != 0");\r
-\r
- set_free(incomplete);\r
- };\r
-\r
- ConstrainSearch=save_ConstrainSearch;\r
- fset=save_fset;\r
- MR_AmbSourceSearch=0;\r
- MR_MaintainBackTrace=0;\r
- MR_AmbSourceSearchChoice=0;\r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-Tree *tTrunc(Tree *t,int depth)\r
-#else\r
-Tree *tTrunc(t,depth)\r
- Tree *t;\r
-#endif\r
-{\r
- Tree *u;\r
-\r
- require ( ! (t == NULL && depth > 0),"tree too short");\r
-\r
- if (depth == 0) return NULL;\r
-\r
- if (t->token == ALT) {\r
- u=tTrunc(t->down,depth);\r
- } else {\r
- u=tnode(t->token);\r
- u->down=tTrunc(t->down,depth-1);\r
- };\r
- if (t->right != NULL) u->right=tTrunc(t->right,depth);\r
- return u;\r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-void MR_iterateOverTree(Tree *t,int chain[])\r
-#else\r
-void MR_iterateOverTree(t,chain)\r
- Tree *t;\r
- int chain[];\r
-#endif\r
-{\r
- if (t == NULL) return;\r
- chain[0]=t->token;\r
- if (t->down != NULL) {\r
- MR_iterateOverTree(t->down,&chain[1]);\r
- } else {\r
- MR_traceAmbSourceKclient();\r
- };\r
- MR_iterateOverTree(t->right,&chain[0]);\r
- chain[0]=0;\r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-void MR_traceAmbSourceK(Tree *t,Junction *alt1,Junction *alt2)\r
-#else\r
-void MR_traceAmbSourceK(t,alt1,alt2)\r
- Tree *t;\r
- Junction *alt1;\r
- Junction *alt2;\r
-#endif\r
-{\r
- int i;\r
- int depth;\r
- int maxDepth;\r
- Tree *truncatedTree;\r
-\r
- if (MR_AmbAidRule == NULL) return;\r
-\r
- if ( ! (\r
- strcmp(MR_AmbAidRule,alt1->rname) == 0 ||\r
- strcmp(MR_AmbAidRule,alt2->rname) == 0 ||\r
- MR_AmbAidLine==alt1->line ||\r
- MR_AmbAidLine==alt2->line\r
- )\r
- ) return;\r
-\r
- MR_matched_AmbAidRule++;\r
-\r
- /* there are no token sets in trees, only in TokNodes */\r
-\r
- MR_AmbSourceSearchJ[0]=analysis_point( (Junction *) alt1->p1);\r
- MR_AmbSourceSearchJ[1]=analysis_point( (Junction *) alt2->p1);\r
-\r
- if (tokensInChain == NULL) {\r
- tokensInChain=(int *) calloc (CLL_k+1,sizeof(int));\r
- require (tokensInChain != NULL,"tokensInChain alloc");\r
- };\r
-\r
- MR_AmbSourceSearchGroup=0;\r
-\r
- fprintf(stdout,"\n");\r
- fprintf(stdout," Ambiguity Aid ");\r
- fprintf(stdout,\r
- (MR_AmbAidDepth <= LL_k ?\r
- "(-k %d -aa %s %s -aad %d)\n\n" :\r
- "(-k %d -aa %s %s [-k value limits -aad %d])\n\n"),\r
- LL_k,\r
- MR_AmbAidRule,\r
- (MR_AmbAidMultiple ? "-aam" : ""),\r
- MR_AmbAidDepth);\r
-\r
- for (i=0 ; i < 2 ; i++) {\r
- fprintf(stdout," Choice %d: %-25s line %d file %s\n",\r
- (i+1),\r
- MR_ruleNamePlusOffset( (Node *) MR_AmbSourceSearchJ[i]),\r
- MR_AmbSourceSearchJ[i]->line,\r
- FileStr[MR_AmbSourceSearchJ[i]->file]);\r
- };\r
-\r
- fprintf(stdout,"\n");\r
-\r
- if (MR_AmbAidDepth < LL_k) {\r
- maxDepth=MR_AmbAidDepth;\r
- } else {\r
- maxDepth=LL_k;\r
- };\r
-\r
- for (depth=1 ; depth <= maxDepth; depth++) {\r
- MR_AmbSourceSearchLimit=depth;\r
- if (depth < LL_k) {\r
- truncatedTree=tTrunc(t,depth);\r
- truncatedTree=tleft_factor(truncatedTree);\r
- MR_iterateOverTree(truncatedTree,&tokensInChain[1]); /* <===== */\r
- Tfree(truncatedTree);\r
- } else {\r
- MR_iterateOverTree(t,tokensInChain); /* <===== */\r
- };\r
- fflush(stdout);\r
- fflush(stderr);\r
- };\r
-\r
- fprintf(stdout,"\n");\r
- MR_AmbSourceSearch=0;\r
- MR_MaintainBackTrace=0;\r
- MR_AmbSourceSearchGroup=0;\r
- MR_AmbSourceSearchChoice=0;\r
- MR_AmbSourceSearchLimit=0;\r
-\r
-}\r
-\r
-\r
-/* this if for k=1 grammars only\r
-\r
- this is approximate only because of the limitations of linear\r
- approximation lookahead. Don't want to do a k=3 search when\r
- the user only specified a ck=3 grammar\r
-*/\r
-\r
-#ifdef __USE_PROTOS\r
-void MR_traceAmbSource(set *matchSets,Junction *alt1, Junction *alt2)\r
-#else\r
-void MR_traceAmbSource(matchSets,alt1,alt2)\r
- set *matchSets;\r
- Junction *alt1;\r
- Junction *alt2;\r
-#endif\r
-{\r
- set *save_fset;\r
- Junction *p[2];\r
- int i;\r
- int j;\r
- set *dup_matchSets;\r
- set intersection;\r
- set incomplete;\r
- set tokensUsed;\r
- int depth;\r
-\r
- if (MR_AmbAidRule == NULL) return;\r
- if ( ! (\r
- strcmp(MR_AmbAidRule,alt1->rname) == 0 ||\r
- strcmp(MR_AmbAidRule,alt2->rname) == 0 ||\r
- MR_AmbAidLine==alt1->line ||\r
- MR_AmbAidLine==alt2->line\r
- )\r
- ) return;\r
-\r
- MR_matched_AmbAidRule++;\r
-\r
- save_fset=fset;\r
-\r
- dup_matchSets=(set *) calloc(CLL_k+1,sizeof(set));\r
- require (dup_matchSets != NULL,"Can't allocate dup_matchSets");\r
-\r
- p[0]=analysis_point( (Junction *) alt1->p1);\r
- p[1]=analysis_point( (Junction *) alt2->p1);\r
-\r
- fprintf(stdout,"\n");\r
-\r
- fprintf(stdout," Ambiguity Aid ");\r
- fprintf(stdout,\r
- (MR_AmbAidDepth <= CLL_k ?\r
- "(-ck %d -aa %s %s -aad %d)\n\n" :\r
- "(-ck %d -aa %s %s [-ck value limits -aad %d])\n\n"),\r
- CLL_k,\r
- MR_AmbAidRule,\r
- (MR_AmbAidMultiple ? "-aam" : ""),\r
- MR_AmbAidDepth);\r
-\r
- for (i=0 ; i < 2 ; i++) {\r
- fprintf(stdout," Choice %d: %-25s line %d file %s\n",\r
- (i+1),\r
- MR_ruleNamePlusOffset( (Node *) p[i]),\r
- p[i]->line,FileStr[p[i]->file]);\r
- };\r
-\r
- for (j=1; j <= CLL_k ; j++) {\r
- fprintf(stdout,"\n Intersection of lookahead[%d] sets:\n",j);\r
- intersection=set_and(alt1->fset[j],alt2->fset[j]);\r
- MR_dumpTokenSet(stdout,2,intersection);\r
- set_free(intersection);\r
- };\r
-\r
- fprintf(stdout,"\n");\r
-\r
- require (1 <= MR_AmbAidDepth && MR_AmbAidDepth <= CLL_k,\r
- "illegal MR_AmbAidDepth");\r
-\r
- MR_AmbSourceSearchGroup=0;\r
- for (depth=1; depth <= MR_AmbAidDepth; depth++) {\r
- MR_AmbSourceSearchLimit=depth;\r
- for (i=0 ; i < 2 ; i++) {\r
-\r
-/*** fprintf(stdout," Choice:%d Depth:%d\n\n",i+1,depth); ***/\r
-\r
- for (j=0 ; j <= CLL_k ; j++) { dup_matchSets[j]=set_dup(matchSets[j]); };\r
- fset=dup_matchSets;\r
-\r
- fflush(output);\r
- fflush(stdout);\r
-\r
- MR_AmbSourceSearch=1;\r
- MR_MaintainBackTrace=1;\r
- MR_AmbSourceSearchChoice=i;\r
-\r
- maxk = depth;\r
- tokensUsed=empty;\r
- incomplete=empty;\r
-\r
- constrain = &(fset[1]);\r
- MR_pointerStackReset(&MR_BackTraceStack);\r
-\r
- REACH(p[i],depth,&incomplete,tokensUsed);\r
-\r
- fflush(output);\r
- fflush(stdout);\r
-\r
- require (set_nil(incomplete),"MR_traceAmbSource REACH incomplete");\r
- require (MR_BackTraceStack.count == 0,"1: MR_BackTraceStack.count != 0");\r
-\r
- set_free(incomplete);\r
- set_free(tokensUsed);\r
-\r
- for (j=0 ; j <= CLL_k ; j++) { set_free(dup_matchSets[j]); };\r
- };\r
- };\r
-\r
- fprintf(stdout,"\n");\r
-\r
- MR_AmbSourceSearch=0;\r
- MR_MaintainBackTrace=0;\r
- MR_AmbSourceSearchGroup=0;\r
- MR_AmbSourceSearchChoice=0;\r
- MR_AmbSourceSearchLimit=0;\r
-\r
- fset=save_fset;\r
- free ( (char *) dup_matchSets);\r
-}\r
-\r
-static int itemCount;\r
-\r
-void MR_backTraceDumpItemReset() {\r
- itemCount=0;\r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-void MR_backTraceDumpItem(FILE *f,int skip,Node *n)\r
-#else\r
-void MR_backTraceDumpItem(f,skip,n)\r
- FILE *f;\r
- int skip;\r
- Node *n;\r
-#endif\r
-{\r
- TokNode *tn;\r
- RuleRefNode *rrn;\r
- Junction *j;\r
- ActionNode *a;\r
-\r
- switch (n->ntype) {\r
- case nToken:\r
- itemCount++; if (skip) goto EXIT;\r
- tn=(TokNode *)n;\r
- if (set_nil(tn->tset)) {\r
- fprintf(f," %2d #token %-23s",itemCount,TerminalString(tn->token));\r
- } else {\r
- fprintf(f," %2d #tokclass %-20s",itemCount,TerminalString(tn->token));\r
- };\r
- break;\r
- case nRuleRef:\r
- itemCount++; if (skip) goto EXIT;\r
- rrn=(RuleRefNode *)n;\r
- fprintf(f," %2d to %-27s",itemCount,rrn->text);\r
- break;\r
- case nAction:\r
- a=(ActionNode *)n;\r
- goto EXIT;\r
- case nJunction:\r
-\r
- j=(Junction *)n;\r
-\r
- switch (j->jtype) {\r
- case aSubBlk:\r
- if (j->guess) {\r
- itemCount++; if (skip) goto EXIT;\r
- fprintf(f," %2d %-30s",itemCount,"in (...)? block at");\r
- break;\r
- };\r
-/****** fprintf(f," %2d %-32s",itemCount,"in (...) block at"); *******/\r
-/****** break; *******/\r
- goto EXIT;\r
- case aOptBlk:\r
- itemCount++; if (skip) goto EXIT;\r
- fprintf(f," %2d %-30s",itemCount,"in {...} block");\r
- break;\r
- case aLoopBlk:\r
- itemCount++; if (skip) goto EXIT;\r
- fprintf(f," %2d %-30s",itemCount,"in (...)* block");\r
- break;\r
- case EndBlk:\r
- if (j->alpha_beta_guess_end) {\r
- itemCount++; if (skip) goto EXIT;\r
- fprintf(f," %2d %-30s",itemCount,"end (...)? block at");\r
- break;\r
- };\r
- goto EXIT;\r
-/****** fprintf(f," %2d %-32s",itemCount,"end of a block at"); *****/\r
-/****** break; *****/\r
- case RuleBlk:\r
- itemCount++; if (skip) goto EXIT;\r
- fprintf(f," %2d %-30s",itemCount,j->rname);\r
- break;\r
- case Generic:\r
- goto EXIT;\r
- case EndRule:\r
- itemCount++; if (skip) goto EXIT;\r
- fprintf (f," %2d end %-26s",itemCount,j->rname);\r
- break;\r
- case aPlusBlk:\r
- itemCount++; if (skip) goto EXIT;\r
- fprintf(f," %2d %-30s",itemCount,"in (...)+ block");\r
- break;\r
- case aLoopBegin:\r
- goto EXIT;\r
- };\r
- break;\r
- };\r
- fprintf(f," %-23s line %-4d %s\n",MR_ruleNamePlusOffset(n),n->line,FileStr[n->file]);\r
-EXIT:\r
- return;\r
-}\r
-\r
-\r
-static PointerStack previousBackTrace={0,0,NULL};\r
-\r
-#ifdef __USE_PROTOS\r
-void MR_backTraceReport(void)\r
-#else\r
-void MR_backTraceReport()\r
-#endif\r
-{\r
- int i;\r
- int match = 0;\r
- int limitMatch;\r
-\r
- Node *p;\r
- TokNode *tn;\r
- set remainder;\r
- int depth;\r
-\r
- /* Even when doing a k=2 search this routine can get\r
- called when there is only 1 token on the stack.\r
- This is because something like rRuleRef can change\r
- the search value of k from 2 to 1 temporarily.\r
- It does this because the it wants to know the k=1\r
- first set before it does a k=2 search\r
- */\r
-\r
- depth=0;\r
- for (i=0; i < MR_BackTraceStack.count ; i++) {\r
- p=(Node *) MR_BackTraceStack.data[i];\r
- if (p->ntype == nToken) depth++;\r
- };\r
-\r
-/* MR14 */ if (MR_AmbSourceSearch) {\r
-/* MR14 */ require (depth <= MR_AmbSourceSearchLimit,"depth > MR_AmbSourceSearchLimit");\r
-/* MR14 */ }\r
-\r
- /* MR23 THM - Traceback report was being called at the wrong time for -alpha reports */\r
- /* Reported by Arpad Beszedes (beszedes@inf.u-szeged.hu) */\r
-\r
- if (MR_AmbSourceSearchLimit == 0 || depth < MR_AmbSourceSearchLimit) {\r
- return;\r
- };\r
-\r
- MR_backTraceDumpItemReset();\r
-\r
- limitMatch=MR_BackTraceStack.count;\r
- if (limitMatch > previousBackTrace.count) {\r
- limitMatch=previousBackTrace.count;\r
- };\r
-\r
- for (match=0; match < limitMatch; match++) {\r
- if (MR_BackTraceStack.data[match] !=\r
- previousBackTrace.data[match]) {\r
- break;\r
- };\r
- };\r
-\r
- /* not sure at the moment why there would be duplicates */\r
-\r
- if (match != MR_BackTraceStack.count) {\r
-\r
- fprintf(stdout," Choice:%d Depth:%d Group:%d",\r
- (MR_AmbSourceSearchChoice+1),\r
- MR_AmbSourceSearchLimit,\r
- ++MR_AmbSourceSearchGroup);\r
-\r
- depth=0;\r
- fprintf(stdout," (");\r
- for (i=0; i < MR_BackTraceStack.count ; i++) {\r
- p=(Node *) MR_BackTraceStack.data[i];\r
- if (p->ntype != nToken) continue;\r
- tn=(TokNode *)p;\r
- if (depth != 0) fprintf(stdout," ");\r
- fprintf(stdout,TerminalString(tn->token));\r
- depth++;\r
- if (! MR_AmbAidMultiple) {\r
- if (set_nil(tn->tset)) {\r
- set_rm( (unsigned) tn->token,fset[depth]);\r
- } else {\r
- remainder=set_dif(fset[depth],tn->tset);\r
- set_free(fset[depth]);\r
- fset[depth]=remainder;\r
- };\r
- };\r
- };\r
- fprintf(stdout,")\n");\r
-\r
- for (i=0; i < MR_BackTraceStack.count ; i++) {\r
- MR_backTraceDumpItem(stdout, (i<match) ,(Node *) MR_BackTraceStack.data[i]);\r
- };\r
- fprintf(stdout,"\n");\r
- fflush(stdout);\r
-\r
- MR_pointerStackReset(&previousBackTrace);\r
-\r
- for (i=0; i < MR_BackTraceStack.count ; i++) {\r
- MR_pointerStackPush(&previousBackTrace,MR_BackTraceStack.data[i]);\r
- };\r
-\r
- };\r
-}\r
-\r
-#ifdef __USE_PROTOS\r
-void MR_setConstrainPointer(set * newConstrainValue)\r
-#else\r
-void MR_setConstrainPointer(newConstrainValue)\r
- set * newConstrainValue;\r
-#endif\r
-{\r
- constrain=newConstrainValue;\r
-}\r
projects / mirror_edk2.git / blobdiff