/* Version of 8 September, 1995 */ /* Version id for Kimwitu: $Id: bisonsim.rec,v 1.1 1996/10/29 17:53:51 belinfan Rel $ */ /***************************************************************************** * * * BFS USING INSERTION/ADVANCED DELETION WITH COSTS ERROR RECOVERY * * Corey Yeatman, Bruce McKenzie, Lorraine de Vere. * * Initial coding: Version 1.0, 12/10/92 * * * * Method: * * Works 'across' each state, finding shifts on symbols, and trying each * * path from the state the error occurred in. It also follows 'chains' of * * reductions order to keep all paths on the same level. Inserts symbols * * and deletes symbols based on total cost. Considers to have recovered * * the moment it finds `lookahead' symbols that can be parsed without * * error. * *****************************************************************************/ #include #include /* -*-C-*- Note some compilers choke on comments on `#line' lines. */ /* Skeleton output parser for bison, Copyright (C) 1984, 1989, 1990 Bob Corbett and Richard Stallman This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 1, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #ifndef alloca #ifdef __GNUC__ #define alloca __builtin_alloca #else /* Not GNU C. */ #if (!defined (__STDC__) && defined (sparc)) || defined (__sparc__) #include #else /* Not sparc */ #ifdef __MSDOS__ #include #endif /* MSDOS */ #endif /* Not sparc. */ #endif /* Not GNU C. */ #endif /* alloca not defined. */ #include /* This is the parser code that is written into each bison parser when the %semantic_parser declaration is not specified in the grammar. It was written by Richard Stallman by simplifying the hairy parser used when %semantic_parser is specified. */ /* Note: there must be only one dollar sign in this file. It is replaced by the list of actions, each action as one case of the switch. */ #define yyclearin (yychar = YYEMPTY) #define YYEMPTY -2 #define YYEOF 0 /************* For Error recovery *******************************************/ #define YYACCEPT error_statistics(0); return(0); #define YYABORT error_statistics(0); return(1); #ifndef YYERRCOUNTLIMIT #define YYERRCOUNTLIMIT 1000 #endif int yyerrcountlimit = YYERRCOUNTLIMIT; /* ## needed to implement n-Lookahead */ #ifndef LOOKAHEAD #define LOOKAHEAD 3 #endif int yylookahead = LOOKAHEAD; #ifndef DELARRAYSIZE #define DELARRAYSIZE 100 #endif int yydelarraysize = DELARRAYSIZE; /***************************************************************************/ #define YYERROR goto yyerrlab1 /* Like YYERROR except do call yyerror. This remains here temporarily to ease the transition to the new meaning of YYERROR, for GCC. Once GCC version 2 has supplanted version 1, this can go. */ #define YYFAIL goto yyerrlab #define YYBACKUP(token, value) \ do \ if (yychar == YYEMPTY && yylen == 1) \ { yychar = (token), yylval = (value); \ yychar1 = YYTRANSLATE (yychar); \ YYPOPSTACK; \ goto yybackup; \ } \ else \ { yyerror ("syntax error: cannot back up"); YYERROR; } \ while (0) #define YYTERROR 1 #define YYERRCODE 256 #ifndef YYPURE #define YYLEX yylex() #endif #ifdef YYPURE #ifdef YYLSP_NEEDED #define YYLEX yylex(&yylval, &yylloc) #else #define YYLEX yylex(&yylval) #endif #endif /* If nonreentrant, generate the variables here */ #ifndef YYPURE int yychar; /* the lookahead symbol */ YYSTYPE yylval; /* the semantic value of the */ /* lookahead symbol */ #ifdef YYLSP_NEEDED YYLTYPE yylloc; /* location data for the lookahead */ /* symbol */ #endif int yynerrs; /* number of parse errors so far */ #endif /* not YYPURE */ #if YYDEBUG != 0 int yydebug; /* nonzero means print parse trace */ int yydebugerror; /* nonzero means print parse trace on error* / /* Since this is uninitialized, it does not stop multiple parsers from coexisting. */ #endif /* YYINITDEPTH indicates the initial size of the parser's stacks */ #ifndef YYINITDEPTH #define YYINITDEPTH 200 #endif /* YYMAXDEPTH is the maximum size the stacks can grow to (effective only if the built-in stack extension method is used). */ #if YYMAXDEPTH == 0 #undef YYMAXDEPTH #endif #ifndef YYMAXDEPTH #define YYMAXDEPTH 10000 #endif #ifndef __cplusplus /* This is the most reliable way to avoid incompatibilities in available built-in functions on various systems. */ static void __yy_bcopy (from, to, count) char *from; char *to; int count; { register char *f = from; register char *t = to; register int i = count; while (i-- > 0) *t++ = *f++; } #else /* __cplusplus */ /* This is the most reliable way to avoid incompatibilities in available built-in functions on various systems. */ static void __yy_bcopy (char *from, char *to, int count) { register char *f = from; register char *t = to; register int i = count; while (i-- > 0) *t++ = *f++; } #endif /************* For Error recovery ******************************************* * GLOBAL VARIABLES: * * The global variables necessary are a structure to hold a queue of * * stacks, and another structure to hold debugging information for later * * analysis if YYERRDEBUG is defined. As before, we have pointers to these* * structures, etc. errloc_ptr marks the error position in the state * * stack; is used when we check for loops. Also, a 'switch' yyerrorinfo * * is defined. This gives one of three levels of information error * * recovery : * * 0 : No error recovery information is printed. Only basic facts are * * reported. * * 1 : Gives a summary at the end of the parse as to the error(s) that * * occurred, the symbols inserted, etc. * * 2 : Gives even more elaborate information about the error recovery * * while it is happening. * ****************************************************************************/ /* Bit manipulation macros to look for reentered states - for each state */ /* we have a BITTYPE which will be used to record that we have */ /* investigated this state. Bit `n' will be used to indicate we have seen */ /* state `n` before. A new bitmap is allocated each time the stack drops */ /* below the level at which the bitmap was created or there is a futher */ /* symbol deleted. */ #define BITTYPE short #define BITSPERBYTE 8 #define BITTYPESIZE (sizeof(BITTYPE)*BITSPERBYTE) #define BITARRAY BITTYPE * #define BITSNEEDED (((YYFINAL+1)/BITTYPESIZE)+1) #define MAKEBITS (BITARRAY) calloc(BITSNEEDED,(sizeof(BITTYPE))) #define GETBIT(a,s) (a[s/BITTYPESIZE] & (1<<(s%BITTYPESIZE))) #define TSTBIT(a,s) testbit(a,s) typedef struct stkqueue *stack_queue; #define TOKENTYPE int struct stkqueue { short *stk_ptr; TOKENTYPE *inserted; TOKENTYPE *deleted; int totcost; #ifdef BITMAP short depth; /* depth of stack when bitmap created */ BITARRAY seenstate; #endif stack_queue next; }; stack_queue front, currstk, del_stack; short err_fixed, *TOS_ptr, errloc_ptr; int *ins_costs, *del_costs; int q_length = 0, max_length = 0; TOKENTYPE *syms; short num_read = 0, syms_remaining = 0; char *yymsg = NULL,*yymsgp; int yymsgleft; /* variables for use in implementing N-Lookahead */ int yyerrstatus = 0; /* the number of tokens we have to successfully */ /* parse before another error */ int yyerrorigstatus = 0; /* the number of tokens we have to successfully */ /* parse before another error in original method */ int err_sym = -1; /* the location of the token in error */ #if YYERRDEBUG != 0 int yytokencount; float yyparsetime; typedef struct debuginfo *debug_ptr; struct debuginfo { int errorstate, errorsymbol; int recoverstate, numstvisited, mq_length; int numqueued, numstudied; float start_time, tot_time; TOKENTYPE *inssymbols, *delsymbols; int cost; #ifdef BITMAP int seenbitscreated,seenbitstested,seenbitsalreadyset; #endif debug_ptr next; }; debug_ptr db_base = NULL, db_last = NULL; debug_ptr db_ptr; int yydumpstats = 0; int num_errs = 0; int yyerrorinfo = 0; int states_visited[YYFINAL+1]; int overall_visits[YYFINAL+1]; #endif stack_queue create_stack(); void destroy_stack(); void destroy_queue(); stack_queue copy_stack(); void handle_reduction(); void handle_shift(); void queue_shift(); void queue_shift_on_reduction(); void link_in(); int check_loop(); void move_symbols(); void read_a_symbol(); void queue_deletion(); #if YYERRDEBUG !=0 void printqueue(); #endif void error_statistics(); float get_time(); void yymsginit(); void yymsgcpy(); void yymsgfree(); int yyerrcount = 0; /***************************************************************************/ int yyparse() { register int yystate; register int yyn; register short *yyssp; register YYSTYPE *yyvsp; int yychar1; /* lookahead token as an internal (translated) token number */ short yyssa[YYINITDEPTH]; /* the state stack */ YYSTYPE yyvsa[YYINITDEPTH]; /* the semantic value stack */ short *yyss = yyssa; /* refer to the stacks thru separate pointers */ YYSTYPE *yyvs = yyvsa; /* to allow yyoverflow to reallocate them elsewhere */ #ifdef YYLSP_NEEDED YYLTYPE *yyls = yylsa; YYLTYPE *yylsp; YYLTYPE yylsa[YYINITDEPTH]; /* the location stack */ #define YYPOPSTACK (yyvsp--, yysp--, yylsp--) #else #define YYPOPSTACK (yyvsp--, yysp--) #endif int yystacksize = YYINITDEPTH; #ifdef YYPURE int yychar; YYSTYPE yylval; int yynerrs; #ifdef YYLSP_NEEDED YYLTYPE yylloc; #endif #endif YYSTYPE yyval; /* the variable used to return */ /* semantic values from the action */ /* routines */ int yylen; /************* For Error recovery ******************************************* * LOCAL VARIABLES: * * Only those variables which it is necessary to keep local are in here. * * Others are global for easy access from other functions. Here we define * * pointers to the error stack, the debug information nodes, etc. * ****************************************************************************/ int stack_size, errstk_size, recover_ss = 0, i, j; short *errstk_base, *tmp_ptr, *recover_stk, tmp = 0, recover_flag = 0; float yyrectime; char yychartime[28]; recover_stk = (short *) malloc(yystacksize * sizeof(*yyssp)); ins_costs = (int *) malloc(YYNTBASE * sizeof(int)); del_costs = (int *) malloc(YYNTBASE * sizeof(int)); syms = (TOKENTYPE *) malloc(yydelarraysize * sizeof(TOKENTYPE)); for (i=3; i1) { for (i=3; i= yyss + yystacksize - 1) { /* Give user a chance to reallocate the stack */ /* Use copies of these so that the &'s don't force the real ones into memory. */ YYSTYPE *yyvs1 = yyvs; short *yyss1 = yyss; #ifdef YYLSP_NEEDED YYLTYPE *yyls1 = yyls; #endif /* Get the current used size of the three stacks, in elements. */ int size = yyssp - yyss + 1; #ifdef yyoverflow /* Each stack pointer address is followed by the size of the data in use in that stack, in bytes. */ yyoverflow("parser stack overflow", &yyss1, size * sizeof (*yyssp), &yyvs1, size * sizeof (*yyvsp), #ifdef YYLSP_NEEDED &yyls1, size * sizeof (*yylsp), #endif &yystacksize); yyss = yyss1; yyvs = yyvs1; #ifdef YYLSP_NEEDED yyls = yyls1; #endif #else /* no yyoverflow */ /* Extend the stack our own way. */ if (yystacksize >= YYMAXDEPTH) { yyerror("parser stack overflow"); return 2; } yystacksize *= 2; if (yystacksize > YYMAXDEPTH) yystacksize = YYMAXDEPTH; yyss = (short *) alloca (yystacksize * sizeof (*yyssp)); __yy_bcopy ((char *)yyss1, (char *)yyss, size * sizeof (*yyssp)); yyvs = (YYSTYPE *) alloca (yystacksize * sizeof (*yyvsp)); __yy_bcopy ((char *)yyvs1, (char *)yyvs, size * sizeof (*yyvsp)); #ifdef YYLSP_NEEDED yyls = (YYLTYPE *) alloca (yystacksize * sizeof (*yylsp)); __yy_bcopy ((char *)yyls1, (char *)yyls, size * sizeof (*yylsp)); #endif #endif /* no yyoverflow */ yyssp = yyss + size - 1; yyvsp = yyvs + size - 1; #ifdef YYLSP_NEEDED yylsp = yyls + size - 1; #endif #if YYDEBUG != 0 if (yydebug) fprintf(stderr, "Stack size increased to %d\n", yystacksize); #endif if (yyssp >= yyss + yystacksize - 1) { YYABORT; } /************* For Error recovery *******************************************/ free(recover_stk); recover_stk = (short *) malloc(yystacksize * sizeof(*yyssp)); /***************************************************************************/ } #if YYDEBUG != 0 if (yydebug) fprintf(stderr, "Entering state %d\n", yystate); #endif yybackup: /* Do appropriate processing given the current state. */ /* Read a lookahead token if we need one and don't already have one. */ /* yyresume: */ /* First try to decide what to do without reference to lookahead token. */ yyn = yypact[yystate]; if (yyn == YYFLAG) goto yydefault; /* Not known => get a lookahead token if don't already have one. */ /* yychar is either YYEMPTY or YYEOF or a valid token in external form. */ if (yychar == YYEMPTY) { /************* For Error recovery ***********************************/ /* force the parser to read input symbols from the lookahead */ /* buffer rather than from input */ if (syms_remaining) { yychar = syms[num_read - syms_remaining]; #if YYDERREBUG != 0 if (yydebug) fprintf(stderr, "Reusing a token %d from those saved during error recovery in syms[%d]: ", yychar, num_read-syms_remaining); #endif } else { /*******************************************************************/ #if YYDEBUG != 0 if (yydebug) fprintf(stderr, "Reading a token: "); #endif #if YYERRDEBUG != 0 if (yydumpstats) yytokencount++; #endif if (yyerrstatus) { read_a_symbol(); yychar = syms[num_read - syms_remaining]; #if YYERRDEBUG != 0 if (yydebug) fprintf(stderr, "Forced read ahead of token %d and saved in syms[%d]: ", yychar, num_read-syms_remaining); #endif } else yychar = YYLEX; } } /* Convert token to internal form (in yychar1) for indexing tables with */ if (yychar <= 0) /* This means end of input. */ { yychar1 = 0; yychar = YYEOF; /* Don't call YYLEX any more */ #if YYDEBUG != 0 if (yydebug) fprintf(stderr, "Now at end of input.\n"); #endif } else { yychar1 = YYTRANSLATE(yychar); #if YYDEBUG != 0 if (yydebug) fprintf(stderr, "Next token is %d (%s)\n", yychar, yytname[yychar1]); #endif } yyn += yychar1; if (yyn < 0 || yyn > YYLAST || yycheck[yyn] != yychar1) { goto yydefault; } yyn = yytable[yyn]; /* yyn is what to do for this token type in this state. Negative => reduce, -yyn is rule number. Positive => shift, yyn is new state. New state is final state => don't bother to shift, just return success. 0, or most negative number => error. */ if (yyn < 0) { if (yyn == YYFLAG) goto yyerrlab; yyn = -yyn; goto yyreduce; } else if (yyn == 0) goto yyerrlab; if (yyn == YYFINAL) { /************* For Error recovery *******************************************/ if (yyerrstatus) { #if YYERRDEBUG != 0 if (yydebug) fprintf(stderr, "Recoved from error by acepting input (yyerrorstate=%d)\nWith message %s\n", yyerrstatus,yymsg); #endif yyrecovermsg(yymsg); } /***************************************************************************/ YYACCEPT; } /* Shift the lookahead token. */ #if YYDEBUG != 0 if (yydebug) fprintf(stderr, "Shifting token %d (%s), ", yychar, yytname[yychar1]); #endif /* Discard the token being shifted unless it is eof. */ if (yychar != YYEOF) yychar = YYEMPTY; *++yyvsp = yylval; #ifdef YYLSP_NEEDED *++yylsp = yylloc; #endif /* count tokens shifted since error; after three, turn off error status. */ yystate = yyn; /************* For Error recovery *******************************************/ recover_flag = 0; #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr,"Reset recover_flag\n"); #endif if (syms_remaining) syms_remaining--; /* we have successfully read another symbol */ if (yyerrstatus) { if(! --yyerrstatus) { yyerrcount = 0; yyrecovermsg(yymsg); yyerrorigstatus = 0; #if YYERRDEBUG != 0 if (yyerrstatus) fprintf(stderr, "Set yyerrcount to zero\n"); if (yydebug && yyerrstatus) fprintf(stderr, "have read the required %d symbols after error\n", yylookahead); #endif } #if YYERRDEBUG != 0 else { if (yydebug && yyerrstatus) fprintf(stderr, "have to successfully read %d more symbols before another error\n", yyerrstatus); } #endif } /***************************************************************************/ goto yynewstate; /* Do the default action for the current state. */ yydefault: yyn = yydefact[yystate]; if (yyn == 0) goto yyerrlab; /************* For Error recovery *******************************************/ if (!recover_flag) { recover_ss = yyssp - yyss + 1; __yy_bcopy((char *)yyss, (char *)recover_stk, recover_ss * sizeof(*yyssp)); #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr,"Saved recover_stk and set recover_flag\n"); #endif recover_flag = 1; } /***************************************************************************/ /* Do a reduction. yyn is the number of a rule to reduce with. */ yyreduce: yylen = yyr2[yyn]; yyval = yyvsp[1-yylen]; /* implement default value of the action */ #if YYDEBUG != 0 if (yydebug) { int i; fprintf (stderr, "Reducing via rule %d (line %d), ", yyn, yyrline[yyn]); /* Print the symboles being reduced, and their result. */ for (i = yyprhs[yyn]; yyrhs[i] > 0; i++) fprintf (stderr, "%s ", yytname[yyrhs[i]]); fprintf (stderr, " -> %s\n", yytname[yyr1[yyn]]); } #endif $ /* the action file gets copied in in place of this dollarsign */ yyvsp -= yylen; yyssp -= yylen; #ifdef YYLSP_NEEDED yylsp -= yylen; #endif #if YYDEBUG != 0 if (yydebug) { short *ssp1 = yyss - 1; fprintf (stderr, "state stack now"); while (ssp1 != yyssp) fprintf (stderr, " %d", *++ssp1); fprintf (stderr, "\n"); } #endif *++yyvsp = yyval; #ifdef YYLSP_NEEDED yylsp++; if (yylen == 0) { yylsp->first_line = yylloc.first_line; yylsp->first_column = yylloc.first_column; yylsp->last_line = (yylsp-1)->last_line; yylsp->last_column = (yylsp-1)->last_column; yylsp->text = 0; } else { yylsp->last_line = (yylsp+yylen-1)->last_line; yylsp->last_column = (yylsp+yylen-1)->last_column; } #endif /* Now "shift" the result of the reduction. Determine what state that goes to, based on the state we popped back to and the rule number reduced by. */ yyn = yyr1[yyn]; yystate = yypgoto[yyn - YYNTBASE] + *yyssp; if (yystate >= 0 && yystate <= YYLAST && yycheck[yystate] == *yyssp) yystate = yytable[yystate]; else yystate = yydefgoto[yyn - YYNTBASE]; goto yynewstate; /************* For Error recovery ******************************************* * ERROR RECOVERY: This is the section that implements the BFS recovery * * with insert/delete with costs. Firstly, we rreport an error has * * occurred, and increase num_errs. If YYERRDEBUG is on, we print an error* * message. err_fixed is set to zero to show we haven't recovered yet. * * Then we allocate space for the error state stack (equal to the size of * * the current main state stack). Finally, move any `deleted' symbols * * remaining from the last error and save the current symbols. * ****************************************************************************/ yyerrlab: if (yyerrorigstatus) goto yyerroriglab1; #ifdef YYERRDEBUG if (yydebugerror) yydebug = 1; #endif if (! yyerrstatus) /* If not already recovering from an error, report this error. */ { yyerrcount = 0; #ifdef YYERRDEBUG if (yyerrorinfo) fprintf(stderr, "Set yyerrcount to zero\n"); #endif ++yynerrs; yyrectime = get_time(); yymsginit(); yymsgcpy("Parse error on "); yymsgcpy(yytname[yychar1]); #ifdef YYERROR_VERBOSE yyn = yypact[yystate]; if (yyn > YYFLAG && yyn < YYLAST) { int x, count; count = 0; for (x = 0; x < (sizeof(yytname) / sizeof(char *)); x++) if (yycheck[x + yyn] == x) count++; if (count < 5) { count = 0; for (x = 0; x < (sizeof(yytname) / sizeof(char *)); x++) if (yycheck[x + yyn] == x) { yymsgcpy(count == 0 ? ", expecting `" : " or `"); yymsgcpy(yytname[x]); yymsgcpy("'"); count++; } } } #endif /* YYERROR_VERBOSE */ yyerror(yymsg); yymsgfree(); } /************* For Error recovery *******************************************/ #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "\nError - on token %s has occurred in state %d\n", yytname[yychar1], *yyssp); num_errs++; #endif err_fixed = 0; errstk_base = (short *) malloc(yystacksize * sizeof (*yyssp)); errstk_size = yystacksize; if (yyerrstatus) { #if YYERRDEBUG != 0 if (yydebug) fprintf(stderr, "Another error occurred within %d symbols.\n", yylookahead); free(db_ptr->inssymbols); free(db_ptr->delsymbols); db_ptr->inssymbols = db_ptr->delsymbols = NULL; num_errs--; #endif /* revert back to the situation that we had when the original */ /* error occurred */ yyerrstatus = yylookahead; #if YYERRDEBUG != 0 if (yydebug) fprintf(stderr, "now need to read %d symbols\n", yyerrstatus); #endif yychar = syms[err_sym]; yychar1 = ((syms[err_sym] <= 0) ? 0 : YYTRANSLATE(syms[err_sym])); #if YYERRDEBUG != 0 if (yydebug) fprintf(stderr, "The symbol in error is %s found in sysms[%d]\n", yytname[yychar1], err_sym); #endif goto yymainloop; } /* we only want to alter the input array if we have a new error */ /* ie: we don't want to revert back to an error that occurred earlier */ move_symbols(yychar); /* need to successfully parse this many tokens after recovering from */ /* this error */ yyerrstatus = yylookahead; /* Next, we set our states_visited[] array to 0, and create a new */ /* 'node' in the debugging info linked-list. We also create a */ /* stack-queue structure containing the whole state stack. Then we */ /* go into the main loop. */ #if YYERRDEBUG != 0 for (i=0; ierrorstate = *yyssp; db_ptr->errorsymbol = yychar1; db_ptr->numstvisited = 0; db_ptr->numqueued = 0; db_ptr->numstudied = 0; db_ptr->start_time = get_time(); db_ptr->cost = 0; #ifdef BITMAP db_ptr->seenbitscreated = 0; db_ptr->seenbitstested = 0; db_ptr->seenbitsalreadyset = 0; #endif db_ptr->next = NULL; db_ptr->inssymbols = db_ptr->delsymbols = NULL; if (db_base == NULL) db_base = db_last = db_ptr; else { db_last->next = db_ptr; db_last = db_last->next; } if (yyerrorinfo >= 2) { fprintf(stderr, "Creating a complete copy of the stack for the queue.\n"); if (recover_flag) fprintf(stderr, "This will be before the chain of default reductions was followed.\n"); } #endif stack_size = (recover_flag ? recover_ss : (yyssp - yyss + 1)); /* destroy the queue if it is non empty so that we can build a new one */ /* to recover from this error */ if (front != NULL) destroy_queue(front); front = create_stack(stack_size, 0, 0); #ifdef BITMAP front->depth = stack_size; /* construct a new seen state bits array */ front->seenstate = MAKEBITS; #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "\nCreated seenstate bits\n"); #endif #endif q_length = max_length = 1; if (recover_flag) __yy_bcopy((char *)recover_stk, (char *)&front->stk_ptr[1], stack_size * sizeof(*yyssp)); else __yy_bcopy((char *)yyss, (char *)&front->stk_ptr[1], stack_size * sizeof(*yyssp)); errloc_ptr = front->stk_ptr[0]; recover_flag = 0; #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr,"Reset recover_flag\n"); #endif /* Now we enter the main loop. The first thing to check is to see if */ /* there is nothing in the queue, in which case we cannot recover from */ /* this error. Otherwise, we copy the first stack in the queue to our */ /* error stack (adjusting the error stack size if it is full). Then, we */ /* print info about the states pushed on the stack. */ yymainloop: if (front == NULL) { #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "Unable to insert string to recover. revert to PANIC mode\n"); #endif goto yyerroriglab; } currstk = front; front = front->next; q_length--; if ((stack_size = currstk->stk_ptr[0]) >= (errstk_size - 20)) { if ((errstk_size *= 2) >= YYMAXDEPTH) { yyerror("Error stack overflow"); YYABORT; } errstk_base = (short *) realloc(errstk_base, errstk_size); #if YYERRDEBUG != 0 fprintf(stderr, "Error stack size was increased to %d elements\n", errstk_size); #endif } __yy_bcopy((char *)&currstk->stk_ptr[1], (char *)errstk_base, stack_size * sizeof(*yyssp)); TOS_ptr = errstk_base + stack_size - 1; #ifdef BITMAP if (TSTBIT(currstk->seenstate,*TOS_ptr)) { #else #ifdef NOLOOPCHECK if (0) { #else if (check_loop(*TOS_ptr)) { #endif #endif #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "State %d at front of queue already tested so skip\n", *TOS_ptr); #endif goto yymainloop; } #ifdef YYERRDEBUG if (yyerrorinfo) fprintf(stderr, "Tested yyerrcount = %d\n", yyerrcount); #endif if (yyerrcount > yyerrcountlimit) { #ifdef YYERRDEBUG if (yyerrorinfo) { fprintf(stderr, "Error recovery limit exceeded - unable to recover"); fprintf(stderr, "Time spent on recovery %5.2f seconds (%d Qed) \n", get_time()-yyrectime, yyerrcount); } #endif goto yyerroriglab; } #if YYERRDEBUG != 0 db_ptr->numstudied++; if (yyerrorinfo >= 2) { fprintf(stderr, "\nResulting state stack from first in queue : "); for (tmp_ptr = errstk_base; tmp_ptr <= TOS_ptr; tmp_ptr++) fprintf(stderr, "%d ", *tmp_ptr); fprintf(stderr, "\n\n"); } #endif /* If there is a default reduction from the TOS state, we call */ /* handle_reduction to follow the 'chain' of reductions to a state with */ /* shifts - *then* from there we call handle_shifts to add them to the */ /* queue. A reduction should NEVER be enqueued by itself - it must have */ /* a shift at the end of it. (Note that we first make a copy of the state */ /* stack so we can add a further deletion). */ del_stack = copy_stack(currstk, currstk->stk_ptr[0], 0, 0, 1); if (yypact[*TOS_ptr] == YYFLAG) { #if YYERRDEBUG !=0 if (yyerrorinfo >= 2) fprintf(stderr, "Default reduction possible in this state.\n"); #endif handle_reduction(yydefact[*TOS_ptr]); goto yycontinue; } /* The other possibility is to scan through yytable[] and find what */ /* shifts can be done from this state. This is done by handle_shift, */ /* which adds new stack items to the rear of the queue. Then add a */ /* further deletion to the node that was copied earlier. */ handle_shift(yypact[*TOS_ptr]); yycontinue: queue_deletion(del_stack); /* If handle_reduction or handle_shift found a shift on the current */ /* symbol in error from the TOS state, we consider that we have */ /* recovered. We copy the state stack back, adjust pointers, and record */ /* debugging info if necessary. Otherwise, we go back to the beginning of */ /* our main loop. */ if (err_fixed) { #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) { fprintf(stderr, "\nResulting state stack from first in queue : "); for (tmp = 1; tmp <= currstk->stk_ptr[0]; tmp++) fprintf(stderr, "%d ", currstk->stk_ptr[tmp]); fprintf(stderr, "\n\n"); fprintf(stderr, "error stack size is %d\n", currstk->stk_ptr[0]); } #endif yymsginit(); sprintf(yychartime,"(%5.2f)[%d][%d] ",get_time()-yyrectime,currstk->totcost,yyerrcount); yymsgcpy(yychartime); yymsgcpy("Inserted "); if (!currstk->inserted[0]) yymsgcpy("nothing "); else for (i=1; i <= currstk->inserted[0]; i++) { yymsgcpy(yytname[currstk->inserted[i]]); yymsgcpy(" "); } yymsgcpy("and deleted "); if (!currstk->deleted[0]) yymsgcpy("nothing."); else for (i=1; i <= currstk->deleted[0]; i++) { yymsgcpy(yytname[currstk->deleted[i]]); yymsgcpy(" "); } #if YYERRDEBUG != 0 if (yydebug && yyerrorinfo) { fprintf(stderr, "\nBuilt up error message <%s>\n",yymsg); } #endif if (errstk_size != yystacksize) { yystacksize = errstk_size; #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "Size of state stack increased to %d elements\n", yystacksize); #endif yyss = (short *) alloca (yystacksize * sizeof (*yyssp)); yyvs = (YYSTYPE *) alloca (yystacksize * sizeof (*yyssp)); } stack_size = currstk->stk_ptr[0]; __yy_bcopy((char *)&currstk->stk_ptr[1], (char *)yyss, stack_size * sizeof(*TOS_ptr)); yyssp = yyss + stack_size - 1; yyvsp = yyvs + stack_size - 1; yystate = *yyssp; #if YYERRDEBUG != 0 db_ptr->recoverstate = yystate; db_ptr->numstvisited = 0; for (i=0; inumstvisited++; db_ptr->inssymbols = (TOKENTYPE *) malloc((currstk->inserted[0] + 1) * sizeof(TOKENTYPE)); db_ptr->delsymbols = (TOKENTYPE *) malloc((currstk->deleted[0] + 1) * sizeof(TOKENTYPE)); __yy_bcopy((char *)currstk->inserted, (char *)db_ptr->inssymbols, (currstk->inserted[0] + 1) * sizeof(TOKENTYPE)); __yy_bcopy((char *)currstk->deleted, (char *)db_ptr->delsymbols, (currstk->deleted[0] + 1) * sizeof(TOKENTYPE)); db_ptr->tot_time = get_time() - db_ptr->start_time; db_ptr->cost = currstk->totcost; db_ptr->mq_length = max_length; #endif syms_remaining = num_read - currstk->deleted[0]; yychar = syms[currstk->deleted[0]]; yychar1 = (yychar == 0 ? 0 : YYTRANSLATE(yychar)); #ifdef YYERRDEBUG if (yyerrorinfo) fprintf(stderr,"Getting char=%d from syms[%d]: syms_remaing=%d num_read=%d\n", yychar, currstk->deleted[0], syms_remaining, num_read); #endif /* destroy_queue(front); we do not want to destroy the queue */ /* in case another error occurs within the lookahead period */ destroy_stack(currstk); free(errstk_base); goto yybackup; } #if YYERRDEBUG != 0 if (yyerrorinfo >= 3) printqueue(); #endif destroy_stack(currstk); goto yymainloop; yyerroriglab: /* here on detecting error that can not be repaired */ /* revert back to the situation that we had when the original */ /* error occurred */ yymsginit(); sprintf(yychartime,"(%5.2f)[>%d][%d] ",get_time()-yyrectime,currstk->totcost,yyerrcount); yymsgcpy(yychartime); yymsgcpy("PANIC MODE - Discarded "); yychar = syms[err_sym]; yychar1 = ((syms[err_sym] <= 0) ? 0 : YYTRANSLATE(syms[err_sym])); __yy_bcopy((char *)recover_stk, (char *)yyss, recover_ss * sizeof(*yyssp)); yyerrstatus = yylookahead; syms_remaining = num_read; #if YYERRDEBUG != 0 free(db_ptr->inssymbols); free(db_ptr->delsymbols); db_ptr->inssymbols = db_ptr->delsymbols = NULL; #endif yyerroriglab1: /* here when returning again without enough correct shifts */ if (yyerrorigstatus == 3) { /* if just tried and failed to reuse lookahead token after an error, discard it. */ /* return failure if at end of input */ if (yychar == YYEOF) { yyerror("Encountered end of input while in PANIC mode"); yyrecovermsg(yymsg); YYABORT; } yymsgcpy(" "); yymsgcpy(yytname[yychar1]); #if YYDEBUG != 0 if (yydebug) fprintf(stderr, "Discarding token %d (%s).\n", yychar, yytname[yychar1]); #endif if (syms_remaining) syms_remaining--; yychar = YYEMPTY; } /* Else will try to reuse lookahead token after shifting the error token. */ yyerrorigstatus = 3; /* Each real token shifted decrements this */ goto yyerrorighandle; yyerrorigdefault: /* current state does not do anything special for the error token. */ yyerrorigpop: /* pop the current state because it cannot handle the error token */ if (yyssp == yyss) { yyerror("Encountered bottom of stack while in PANIC mode"); yyrecovermsg(yymsg); YYABORT; } yyvsp--; yystate = *--yyssp; #ifdef YYLSP_NEEDED yylsp--; #endif #if YYDEBUG != 0 if (yydebug) { short *ssp1 = yyss - 1; fprintf (stderr, "Error: state stack now"); while (ssp1 != yyssp) fprintf (stderr, " %d", *++ssp1); fprintf (stderr, "\n"); } #endif yyerrorighandle: yyn = yypact[yystate]; if (yyn == YYFLAG) goto yyerrorigdefault; yyn += YYTERROR; if (yyn < 0 || yyn > YYLAST || yycheck[yyn] != YYTERROR) goto yyerrorigdefault; yyn = yytable[yyn]; if (yyn < 0) { if (yyn == YYFLAG) goto yyerrorigpop; yyn = -yyn; goto yyreduce; } else if (yyn == 0) goto yyerrorigpop; if (yyn == YYFINAL) { YYACCEPT; } #if YYDEBUG != 0 if (yydebug) fprintf(stderr, "Shifting error token, "); #endif *++yyvsp = yylval; #ifdef YYLSP_NEEDED *++yylsp = yylloc; #endif yystate = yyn; goto yynewstate; } /* create_stack : This creates a stack node for the queue of stacks to be */ /* checked. It allocates enough space to store the 'size' stack elements */ /* and 'ins_size' inserted symbol elements, and 'del_size' deleted symbol */ /* elements. We place these sizes into the first location in the allocated */ /* memory. A pointer to the node is returned. */ stack_queue create_stack(size, ins_size, del_size) int size, ins_size, del_size; { stack_queue qnode_ptr = (stack_queue) malloc(sizeof(struct stkqueue)); qnode_ptr->stk_ptr = (short *) malloc((size + 1) * sizeof(short)); qnode_ptr->stk_ptr[0] = size; qnode_ptr->inserted = (TOKENTYPE *) malloc((ins_size + 1) * sizeof(TOKENTYPE)); qnode_ptr->inserted[0]= ins_size; qnode_ptr->deleted = (TOKENTYPE *) malloc((del_size + 1) * sizeof(TOKENTYPE)); qnode_ptr->deleted[0] = del_size; qnode_ptr->totcost = 0; qnode_ptr->next = NULL; return qnode_ptr; } /* destroy_stack : Gets rid of an unwanted stack (queue) node. Requires */ /* a pointer to the node to be passed. */ void destroy_stack(node_ptr) stack_queue node_ptr; { free(node_ptr->stk_ptr); free(node_ptr->inserted); free(node_ptr->deleted); free(node_ptr); } /* destroy_queue : Disposes of a whole queue of stacks. Performed when */ /* we exit the error recovery loop. */ void destroy_queue(head_ptr) stack_queue head_ptr; { stack_queue temp_ptr = head_ptr; while (head_ptr != NULL) { head_ptr = head_ptr->next; destroy_stack(temp_ptr); temp_ptr = head_ptr; } } /* copy_stack : Makes a copy of the state stack and symbol stack in a */ /* new queue-stack node, with additional space (as specified) for new */ /* stack/symbol items. The base_size is needed for when we have just */ /* performed a reduction, and we only want to copy part of the */ /* resulting state stack. Leave the seenbits array and depth the same.*/ stack_queue copy_stack(original, base_size, size_inc, ins_inc, del_inc) stack_queue original; int base_size, size_inc, ins_inc, del_inc; { stack_queue qnode_ptr = create_stack(base_size + size_inc, original->inserted[0] + ins_inc, original->deleted[0] + del_inc); __yy_bcopy((char *)&original->stk_ptr[1], (char *)&qnode_ptr->stk_ptr[1], (base_size * sizeof(short))); __yy_bcopy((char *)&original->inserted[1], (char *)&qnode_ptr->inserted[1], (original->inserted[0] * sizeof(TOKENTYPE))); __yy_bcopy((char *)&original->deleted[1], (char *)&qnode_ptr->deleted[1], (original->deleted[0] * sizeof(TOKENTYPE))); qnode_ptr->totcost = original->totcost; #ifdef BITMAP qnode_ptr->depth = original->depth; qnode_ptr->seenstate = original->seenstate; #endif qnode_ptr->next = NULL; return qnode_ptr; } /* handle_reduction : This function follows 'chains' of reductions to a */ /* state that contains shifts. Only shifts are ever enqueued. It is */ /* recursive, and it updates a global stack node called 'currstk' and */ /* adjusts the top-of-stack via TOS_ptr. The only exit from this function */ /* is to call handle_shifts. */ void handle_reduction(rule_number) short rule_number; { short lhs_nt, length_rhs, shift; stack_queue newstk; short newstacklen; lhs_nt = yyr1[rule_number]; length_rhs = yyr2[rule_number]; #if YYERRDEBUG != 0 states_visited[*TOS_ptr] = overall_visits[*TOS_ptr] = 1; #endif shift = yypgoto[lhs_nt - YYNTBASE] + *(TOS_ptr -= length_rhs); if ((shift >= 0) && (shift <= YYLAST) && (yycheck[shift] == *TOS_ptr)) shift = yytable[shift]; else shift = yydefgoto[lhs_nt - YYNTBASE]; newstacklen = currstk->stk_ptr[0]-length_rhs; #ifdef BITMAP if (newstacklen < currstk->depth) { /* stack dropped below level when seenstate bitmap */ /* created - replace with new array */ currstk->depth = newstacklen; currstk->seenstate = MAKEBITS; #if YYERRDEBUG != 0 db_ptr->seenbitscreated++; if (yyerrorinfo >= 2) fprintf(stderr, "Recreated seenbits on reduction\n"); #endif } if (!check_loop(shift)) #endif { *++TOS_ptr = shift; newstk = copy_stack(currstk, newstacklen, 1, 0, 0); newstk->stk_ptr[newstacklen + 1] = shift; destroy_stack(currstk); currstk = newstk; handle_shift(yypact[shift]); } #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "At end of handle reduction\n"); #endif } /* handle_shift : Deals with shifts from a state, enqueue-ing a new stack */ /* item for each one found. For reductions we call handle_reduction() and */ /* follow any chain of reductions that may follow to a state with shifts. */ /* This way only shifts on *real* symbols get put into the queue. Also, */ /* if this current stack includes any 'deletes', we don't try to enqueue */ /* any further shifts. */ void handle_shift(base) short base; { int offset, translated_sym; /** temp variable for testing **/ stack_queue actualstk; short *top_ptr, tmp_ptr; int found_soln; /* indicate whether we have found a valid */ /* recovery from the error */ found_soln = 0; /* initialise so that recursive calls to */ /* handle_shift and handle_reduction */ /* don't upset things */ translated_sym = (syms[currstk->deleted[0]] == 0 ? 0 : YYTRANSLATE(syms[currstk->deleted[0]])); #ifdef YYERRDEBUG if (yyerrorinfo) fprintf(stderr,"Getting translated_char=%d from syms[%d]: syms_remaing=%d num_read=%d\n", translated_sym, currstk->deleted[0], syms_remaining, num_read); states_visited[*TOS_ptr] = overall_visits[*TOS_ptr] = 1; #endif if ((base + translated_sym) >= 0 && yycheck[base + translated_sym] == translated_sym) { err_fixed = 1; found_soln = 1; top_ptr = (short *)malloc(sizeof(short)); *top_ptr = *TOS_ptr; actualstk = copy_stack(currstk, currstk->stk_ptr[0], 0, 0, 0); #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) { fprintf(stderr, "We have found a recovery\n"); fprintf(stderr, "Top of stack state is %d\n", *TOS_ptr); } #endif } #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "Can't recover on a %s from the current state %d...\n\n", yytname[translated_sym], *TOS_ptr); #endif if (currstk->deleted[0] == 0) { /* start loop at 2 to avoid shifts on `error' token */ for (offset = ((base < 0) ? abs(base) : 2); offset <= ((YYLAST - base) < (YYNTBASE - 1) ? YYLAST - base : (YYNTBASE - 1)); offset++) if (yycheck[base + offset] == offset) { int yyn = yytable[base + offset]; if ( (yyn < 0) && (yyn != YYFLAG)) { #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "Reduction possible on a %s\n", yytname[offset]); #endif queue_shift_on_reduction(-yyn, offset); } else if ( (yyn == 0) || (yyn == YYFLAG)) { #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "Error possible on a %s\n", yytname[offset]); #endif } else { #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "Shift possible on a %s\n", yytname[offset]); #endif queue_shift(yyn, offset); } } } if (yydefact[*TOS_ptr]) handle_reduction(yydefact[*TOS_ptr]); if (found_soln == 1) { destroy_stack(currstk); currstk = actualstk; *TOS_ptr = *top_ptr; #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) { fprintf(stderr, "Top of stack state is %d\n", *TOS_ptr); printqueue(); } #endif } #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "At end of handle_shift\n"); #endif } /* queue_shift : This creates a stack specifically for a shift from a */ /* state, and links it to the queue. */ void queue_shift(shift, symbol) short shift; TOKENTYPE symbol; { stack_queue newstk; if (!check_loop(shift)) { newstk = copy_stack(currstk, currstk->stk_ptr[0], 1, 1, 0); newstk->stk_ptr[currstk->stk_ptr[0] + 1] = shift; newstk->inserted[currstk->inserted[0] + 1] = symbol; newstk->totcost += ins_costs[symbol]; #ifdef YYERRDEBUG if ((yyerrorinfo >= 1) && (symbol==0)) fprintf(stderr,"Used ins_costs of EOF\n"); #endif link_in(newstk); } } /* queue_shift_on_reduction : This is a special case of a shift. We must */ /* make a copy of the stack and find out which state to shift to after */ /* the reduction, and place the symbol into the string of recovery */ /* symbols. */ void queue_shift_on_reduction(rule_number, symbol) short rule_number; TOKENTYPE symbol; { short lhs_nt, length_rhs, shift, newshift, exposedstate; short origstacklen, newstacklen; stack_queue newstk; /* Need to copy stack even if we eventually find a loop as the stack * can grow as a result of empty RHS productions. Make the initial * assumption that the stack doesn't grow more than 5 states. * This corresponds to an four initial empty RHS productions. * Allow stack to grow only if necessary. * At end dont worry about cutting back to final size. */ #if YYERRDEBUG != 0 if (yyerrorinfo >=4) fprintf(stderr,"queue_shift_on_reduction: rule_number=%d, symbol=%s\n", rule_number,yytname[symbol]); #endif origstacklen = newstacklen = currstk->stk_ptr[0]; newstk = copy_stack(currstk, currstk->stk_ptr[0], 5, 1, 0); newstk->inserted[currstk->inserted[0] + 1] = symbol; newstk->totcost += ins_costs[symbol]; yydoreduce: lhs_nt = yyr1[rule_number]; length_rhs = yyr2[rule_number]; newstacklen -= length_rhs; exposedstate = newstk->stk_ptr[newstacklen]; shift = yypgoto[lhs_nt - YYNTBASE] + exposedstate; if ((shift >= 0) && (shift <= YYLAST) && (yycheck[shift] == exposedstate)) shift = yytable[shift]; else shift = yydefgoto[lhs_nt - YYNTBASE]; #if YYERRDEBUG != 0 if (yyerrorinfo >=4) { int i; fprintf(stderr,"\trule_number=%d, symbol=%s origstacklen=%d, newstacklen=%d,\n\tlhs_nt=%d, length_rhs=%d exposedstate=%d, shift=%d\n\tRule:", rule_number,yytname[symbol],origstacklen,newstacklen,lhs_nt,length_rhs,exposedstate,shift); for (i = yyprhs[rule_number]; yyrhs[i] > 0; i++) fprintf (stderr, "%s ", yytname[yyrhs[i]]); fprintf (stderr, " -> %s\n\tstack =", yytname[yyr1[rule_number]]); for (i= 1; i<= newstacklen; i++) fprintf (stderr, "%d ", newstk->stk_ptr[i]); fprintf (stderr, "||| "); for (i= newstacklen+1; i<= newstacklen+length_rhs; i++) fprintf (stderr, "%d ", newstk->stk_ptr[i]); fprintf (stderr, "\n"); } #endif /********* STACK COULD OVERFLOW *********/ newstacklen++; if (newstacklen > newstk->stk_ptr[0]) { fprintf (stderr, "queue_shift_on_reduction: FATAL STACK OVERFLOW\n"); } newstk->stk_ptr[newstacklen] = shift; newshift = yypact[shift]; if (newshift == YYFLAG) { rule_number = yydefact[shift]; #if YYERRDEBUG != 0 if (yyerrorinfo >=4) fprintf(stderr, "Encountered default reduction(%d) in queue_shift_on_reduction.symbol=%d shift=%d\n", rule_number,symbol,shift); #endif goto yydoreduce; } newshift += symbol; if (newshift < 0 || newshift > YYLAST || yycheck[newshift] != symbol) { #if YYERRDEBUG != 0 if (yyerrorinfo >=4) fprintf(stderr,"\tFATAL MISMATCH for newshift=%d yycheck=%d\n",newshift, yycheck[newshift]); #endif destroy_stack(newstk); return; } newshift = yytable[newshift]; /********* NEED TO CHECK THIS IS OK ********/ #if YYERRDEBUG != 0 if (yyerrorinfo >=4) fprintf(stderr,"\tnewshift=%d\n", newshift); #endif if (newshift < 0) { rule_number = - newshift; #if YYERRDEBUG != 0 if (yyerrorinfo >=4) fprintf(stderr,"\trepeat for rule=%d\n\n", rule_number); #endif goto yydoreduce; } if (newshift == 0) { #if YYERRDEBUG != 0 if (yyerrorinfo >= 4) fprintf(stderr, "Encountered error in queue_shift_on_reduction.symbol=%d shift=%d\n", rule_number,symbol,shift); #endif destroy_stack(newstk); return; } /********* STACK COULD OVERFLOW *********/ newstacklen++; if (newstacklen > newstk->stk_ptr[0]) { fprintf (stderr, "queue_shift_on_reduction: FATAL STACK OVERFLOW\n"); } newstk->stk_ptr[newstacklen] = newshift; newstk->stk_ptr[0]=newstacklen; #if YYERRDEBUG != 0 if (yyerrorinfo >= 4) fprintf(stderr,"\tfinal shift newshift=%d\n", newshift); #endif #ifdef BITMAP if (newstacklen < origstacklen) { /* stack dropped below level when seenstate bitmap */ /* created - replace with new array */ newstk->depth = newstacklen; newstk->seenstate = MAKEBITS; #if YYERRDEBUG != 0 db_ptr->seenbitscreated++; if (yyerrorinfo >= 2) fprintf(stderr, "Recreated seenbits on reduction\n"); #endif } if (check_loop(shift)) { destroy_stack(newstk); } else #endif { link_in(newstk); } } #ifdef SAMEELEM int SAME_ELEM(p1,p2) stack_queue p1,p2; { int i; if (p1->totcost != p2->totcost) return(0); if (p1->stk_ptr[0] != p2->stk_ptr[0]) return(0); for(i=1;i<=(p1->stk_ptr[0]);i++) if (p1->stk_ptr[i] != p2->stk_ptr[i]) return(0); if (p1->inserted[0] != p2->inserted[0]) return(0); for(i=1;i<=(p1->inserted[0]);i++) if (p1->inserted[i] != p2->inserted[i]) return(0); if (p1->deleted[0] != p2->deleted[0]) return(0); for(i=1;i<=(p1->deleted[0]);i++) if (p1->deleted[i] != p2->deleted[i]) return(0); return(1); } #endif /* link_in : Inserts a new stack item to the queue based on cost of the */ /* symbols to be inserted and deleted. */ void link_in(newstk) stack_queue newstk; { stack_queue tmp_ptr = front; int placefound = 0; yyerrcount++; if (front == NULL) front = newstk; else if (newstk->totcost < front->totcost) { newstk->next = front; front = newstk; } else { while ((tmp_ptr->next != NULL) && (!placefound)) { #ifdef SAMEELEM if (SAME_ELEM(newstk, tmp_ptr)) { fprintf(stderr, "Found identical elements\n"); return; } #endif if (newstk->totcost >= tmp_ptr->next->totcost) tmp_ptr = tmp_ptr->next; else placefound = 1; } newstk->next = tmp_ptr->next; tmp_ptr->next = newstk; } q_length++; if (q_length > max_length) max_length = q_length; #if YYERRDEBUG != 0 db_ptr->numqueued++; #endif } /* check_loop : Checks to see if adding the given new state to the stack */ /* will create a loop - if so, we won't create a stack item to hold it. */ /* We don't want to be jammed in infinite loops! For this version, since */ /* we are copying the whole stack at a time, we use errloc_ptr so we only */ /* go back as far in the stack as where the error occurred to check for */ /* loops. In fact any reentering of the state means we have already */ /* investigated that state and do not need to add it to the queue again. */ #ifdef BITMAP int testbit(seenstate,state) BITARRAY seenstate; { /* set the `state'th bit of seenstate and return its */ /* previous setting */ BITARRAY p = &seenstate[state / BITTYPESIZE]; int mask = 1<<(state % BITTYPESIZE); int oldval = (*p) & mask; (*p) |= mask; #if YYERRDEBUG != 0 db_ptr->seenbitstested++; if (oldval) db_ptr->seenbitsalreadyset++; #endif return(oldval); } #endif int check_loop(state) short state; { int loop; #ifdef BITMAP int ndel = currstk->deleted[0]; #if YYERRDEBUG != 0 db_ptr->seenbitstested++; #endif if (GETBIT(currstk->seenstate,state)) { #if YYERRDEBUG != 0 db_ptr->seenbitsalreadyset++; if (yyerrorinfo >= 2) fprintf(stderr, "State %d already tested so don't add to queue\n", state); #endif return 1; } /* The following tests is not needed now that seenstate detect loops */ return 0; #else #ifdef NOLOOPCHECK return 0; #else for (loop = errloc_ptr+1; loop <= currstk->stk_ptr[0]; loop++) if (currstk->stk_ptr[loop] == state) { #if YYERRDEBUG != 0 if (yyerrorinfo >= 2) fprintf(stderr, "Loop detected in state %d so don't add to queue\n", state); #endif return 1; } return 0; #endif #endif } /* move_symbols : This is called when we enter the error recovery */ /* routines. If there are symbols remaining in the syms array it moves */ /* them to the front otherwise the current char is placed at the */ /* beginning of the array. */ void move_symbols(thischar) int thischar; { int i; #ifdef YYERRDEBUG if (yyerrorinfo) fprintf(stderr,"In move_symbols with thischar=%d, syms_remaining=%d and num_read=%d\n", thischar, syms_remaining,num_read); #endif if (syms_remaining) { #ifdef YYERRDEBUG if (yyerrorinfo) fprintf(stderr,"Moved %d symbols\n", syms_remaining); #endif for (i=(num_read - syms_remaining); ideleted[0]; if (i == num_read) read_a_symbol(); if ((syms[i - 1] != YYEOF) && (i != num_read)) { delstk->deleted[i] = (syms[i - 1] < 0 ? 0 : YYTRANSLATE(syms[i - 1])); delstk->totcost += del_costs[delstk->deleted[i]]; #ifdef YYERRDEBUG if ((yyerrorinfo >= 1) && (delstk->deleted[i]==0)) fprintf(stderr,"Used del_costs of EOF\n"); #endif #ifdef BITMAP delstk->depth = delstk->stk_ptr[0]; delstk->seenstate = MAKEBITS; #ifdef YYERRDEBUG db_ptr->seenbitscreated++; #endif #endif link_in(delstk); } } /* printqueue : Prints out the state/symbol stacks stored in the queue - */ /* part of the debugging information. */ #if YYERRDEBUG !=0 void printqueue() { stack_queue tmp_ptr = front; int i; if (tmp_ptr == NULL) fprintf(stderr, "\nFor the next iteration: The queue is empty.\n\n"); else { fprintf(stderr, "\nFor the next iteration: The queue is:\n\n"); while (tmp_ptr != NULL) { fprintf(stderr, "States : "); for (i=1; i<= tmp_ptr->stk_ptr[0]; i++) fprintf(stderr, "%2d ", tmp_ptr->stk_ptr[i]); fprintf(stderr, "\nInserted: "); for (i=1; i<= tmp_ptr->inserted[0]; i++) fprintf(stderr, "%s ", yytname[tmp_ptr->inserted[i]]); fprintf(stderr, "\nDeleted : "); for (i=1; i<= tmp_ptr->deleted[0]; i++) fprintf(stderr, "%s ", yytname[tmp_ptr->deleted[i]]); fprintf(stderr, "\nCost : %d\n\n", tmp_ptr->totcost); tmp_ptr = tmp_ptr->next; } fprintf(stderr, "\n"); } } #endif /* error_statistics : Gives info about errors recovered from, and what */ /* symbols were inserted to do this. */ void error_statistics(didnt_recover) int didnt_recover; { #if YYERRDEBUG != 0 debug_ptr db_ptr = db_base; int printsyms, err_count = 1, i, overall = 0; FILE *fptr; if (yydumpstats) { yyparsetime = get_time() - yyparsetime; fprintf(stderr, "Shifted %d tokens in %6.3f seconds", yytokencount, yyparsetime); fprintf(stderr, " (%6.1f tokens per second)\n", (yytokencount / yyparsetime)); } if (yydumpstats && num_errs) { if (didnt_recover) { fprintf(stderr, "Unable to recover.\n"); if (--num_errs) fprintf(stderr, "However, we recovered from %d error%sthat occurred beforehand.\n\n", num_errs, (num_errs == 1) ? " " : "s "); } else fprintf(stderr, "We recovered from %d error%c\n\n", num_errs, (num_errs == 1) ? ' ' : 's'); printf("# Symbols\tNumber_States_Visited\t\tTime\tNumber\tMax Q"); #ifdef BITMAP printf("\tSeen_State_Bitmap"); #endif printf("\nInsert\tDelete\tStudied\tVisited\tTotal\tPerc\t(secs)\tQueued\tLength"); #ifdef BITMAP printf("\tCreate\tTest\tSet"); #endif printf("\tCost\n"); while (num_errs--) { if (db_ptr->inssymbols && db_ptr->delsymbols) printf("%d\t%d\t", db_ptr->inssymbols[0],db_ptr->delsymbols[0]); else printf("PANIC\t"); printf("%d\t%d\t%d\t",db_ptr->numstudied, db_ptr->numstvisited - 1, YYFINAL + 1); printf("%5.1f%%\t", ((double) (db_ptr->numstvisited - 1) / (YYFINAL + 1)) * 100); printf("%6.3f\t", db_ptr->tot_time); printf("%d\t", db_ptr->numqueued); printf("%d\t", db_ptr->mq_length); #ifdef BITMAP printf("%d\t%d\t%d\t", db_ptr->seenbitscreated, db_ptr->seenbitstested, db_ptr->seenbitsalreadyset); #endif printf("%d\n", db_ptr->cost); if (db_ptr->inssymbols && db_ptr->inssymbols[0] > 0) { printf("\tIns: "); for (printsyms = 1; printsyms <= db_ptr->inssymbols[0]; printsyms++) printf("%s ", yytname[db_ptr->inssymbols[printsyms]]); } if (db_ptr->delsymbols && db_ptr->delsymbols[0] > 0) { printf("\n\tDel: "); for (printsyms = 1; printsyms <= db_ptr->delsymbols[0]; printsyms++) printf("%s ", yytname[db_ptr->delsymbols[printsyms]]); } printf("\n"); db_ptr = db_ptr->next; } printf("\n"); } #endif } float get_time() { struct rusage rusage; getrusage(RUSAGE_SELF, &rusage); return(rusage.ru_utime.tv_sec + rusage.ru_utime.tv_usec / 1000000.0 + rusage.ru_stime.tv_sec + rusage.ru_stime.tv_usec / 1000000.0); } /* Routines to build up a message */ void yymsginit() { yymsgleft = 128; if(yymsg!=NULL) free(yymsg); yymsgp = yymsg = malloc(yymsgleft+1); *yymsgp = '\0'; } void yymsgcpy(s) char *s; { while(yymsgleft && *s) { yymsgleft--; *yymsgp++ = *s++; } *yymsgp = '\0'; if (*s) { /* need to increase length */ int currlen = yymsgp - yymsg; yymsg = realloc(yymsg,2*currlen+1); yymsgleft += currlen; yymsgp = yymsg + currlen; yymsgcpy(s); } } void yymsgfree() { free(yymsg); yymsg = NULL; }