home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / pascal / src / yyrecover.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-16  |  21.7 KB  |  903 lines
  1. /*-
  2.  * Copyright (c) 1980 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #ifndef lint
  35. static char sccsid[] = "@(#)yyrecover.c    5.2 (Berkeley) 4/16/91";
  36. #endif /* not lint */
  37.  
  38. #include "whoami.h"
  39. #include "0.h"
  40. #include "tree_ty.h"    /* must be included for yy.h */
  41. #include "yy.h"
  42.  
  43. /*
  44.  * Very simplified version of Graham-Rhodes error recovery
  45.  * method for LALR parsers.  Backward move is embodied in
  46.  * default reductions of the yacc parser until an error condition
  47.  * is reached.  Forward move is over a small number of input tokens
  48.  * and cannot "condense".  The basic corrections are:
  49.  *
  50.  *    1) Delete the input token.
  51.  *
  52.  *    2) Replace the current input with a legal input.
  53.  *
  54.  *    3) Insert a legal token.
  55.  *
  56.  * All corrections are weighted, considered only if they allow
  57.  * at least two shifts, and the cost of a correction increases if
  58.  * it allows shifting over only a part of the lookahead.
  59.  *
  60.  * Another error situation is that which occurs when an identifier "fails"
  61.  * a reduction because it is not the required "class".
  62.  * In this case, we also consider replacing this identifier, which has
  63.  * already been shifted over, with an identifier of the correct class.
  64.  *
  65.  * Another correction performed here is unique symbol insertion.
  66.  * If the current state admits only one input, and no other alternative
  67.  * correction presents itself, then that symbol will be inserted.
  68.  * There is a danger in this of looping, and it is handled
  69.  * by counting true shifts over input (see below).
  70.  *
  71.  *
  72.  * A final class of corrections, considered only when the error
  73.  * occurred immediately after a shift over a terminal, involves
  74.  * the three basic corrections above, but with the point of error
  75.  * considered to be before this terminal was shifted over, effectively
  76.  * "unreading" this terminal.  This is a feeble attempt at elimination
  77.  * of the left-right bias and because "if" has a low weight and some
  78.  * statements are quite simple i.e.
  79.  *
  80.  *    cse ch of ...
  81.  *
  82.  * we can get a small number of errors.  The major deficiency of
  83.  * this is that we back up only one token, and that the forward
  84.  * move is over a small number of tokens, often not enough to really
  85.  * tell what the input should be, e.g. in
  86.  *
  87.  *    a[i] > a[i - 1] ...
  88.  *
  89.  * In such cases a bad identifier (misspelled keyword) or omitted
  90.  * keyword will be change or inserted as "if" as it has the lowest cost.
  91.  * This is not terribly bad, as "if"s are most common.
  92.  * This also allows the correction of other errors.
  93.  *
  94.  * This recovery depends on the default reductions which delay
  95.  * noticing the error until the parse reaches a state where the
  96.  * relevant "alternatives" are visible.  Note that it does not
  97.  * consider tokens which will cause reductions before being
  98.  * shifted over.  This requires the grammar to be written in a
  99.  * certain way for the recovery to work correctly.
  100.  * In some sense, also, the recovery suffers because we have
  101.  * LALR(1) tables rather than LR(1) tables, e.g. in
  102.  *
  103.  *    if rec.field < rec2,field2 then
  104.  */
  105.  
  106. /*
  107.  * Definitions of possible corrective actions
  108.  */
  109. #define    CPANIC        0
  110. #define    CDELETE        1
  111. #define    CREPLACE    2
  112. #define    CINSERT        3
  113. #define    CUNIQUE        4
  114. #define    CCHIDENT    5
  115.  
  116. /*
  117.  * Multiplicative cost factors for corrective actions.
  118.  *
  119.  * When an error occurs we take YCSIZ - 1 look-ahead tokens.
  120.  * If a correction being considered will shift over only part of
  121.  * that look-ahead, it is not completely discarded, but rather
  122.  * "weighted", its cost being multiplied by a weighting factor.
  123.  * For a correction to be considered its weighted cost must be less
  124.  * than CLIMIT.
  125.  *
  126.  * Non-weighted costs are considered:
  127.  *
  128.  *    LOW    <= 3
  129.  *    MEDIUM    4,5
  130.  *    HIGH    >= 6
  131.  *
  132.  * CURRENT WEIGHTING STRATEGY: Aug 20, 1977
  133.  *
  134.  * For all kinds of corrections we demand shifts over two symbols.
  135.  * Corrections have high weight even after two symbol
  136.  * shifts because the costs for deleting and inserting symbols are actually
  137.  * quite low; we do not want to change weighty symbols 
  138.  * on inconclusive evidence.
  139.  *
  140.  * The weights are the same after the third look ahead.
  141.  * This prevents later, unrelated errors from causing "funny"
  142.  * biases of the weights toward one type of correction.
  143.  *
  144.  * Current look ahead is 5 symbols.
  145.  */
  146.  
  147. /*** CLIMIT is defined in yy.h for yycosts ***/
  148. #define    CPRLIMIT    50
  149. #define    CCHIDCOST    3
  150.  
  151. char    insmult[8]    = {INFINITY, INFINITY, INFINITY, 15, 8, 6, 3, 1};
  152. char    repmult[7]    = {INFINITY, INFINITY, INFINITY, 8, 6, 3, 1};
  153. char    delmult[6]    = {INFINITY, INFINITY, INFINITY, 6, 3, 1};
  154.  
  155. #define    NOCHAR    -1
  156.  
  157. #define    Eprintf    if (errtrace) printf
  158. #define    Tprintf    if (testtrace) printf
  159.  
  160. /*
  161.  * Action arrays of the parser needed here
  162.  */
  163. union semstack *yypv;
  164. int        yyact[], yypact[];
  165.  
  166. /*
  167.  * Yytips is the tip of the stack when using
  168.  * the function loccor to check for local
  169.  * syntactic correctness. As we don't want
  170.  * to copy the whole parser stack, but want
  171.  * to simulate parser moves, we "split"
  172.  * the parser stack and keep the tip here.
  173.  */
  174. #define    YYTIPSIZ 16
  175. int    yytips[YYTIPSIZ], yytipct;
  176. int    yytipv[YYTIPSIZ];
  177.  
  178. /*
  179.  * The array YC saves the lookahead tokens for the
  180.  * forward moves.
  181.  * Yccnt is the number of tokens in the YC array.
  182.  */
  183. #define    YCSIZ    6
  184.  
  185. int    yCcnt;
  186. struct    yytok YC0[YCSIZ + 1];
  187. struct    yytok *YC;
  188.  
  189. /*
  190.  * YCps gives the top of stack at
  191.  * the point of error.
  192.  */
  193.  
  194. bool    yyunique = TRUE;
  195.  
  196. STATIC    unsigned yyTshifts;
  197.  
  198. /*
  199.  * Cact is the corrective action we have decided on
  200.  * so far, ccost its cost, and cchar the associated token.
  201.  * Cflag tells if the correction is over the previous input token.
  202.  */
  203. int    cact, ccost, cchar, cflag;
  204.  
  205. /*
  206.  * ACtok holds the token under
  207.  * consideration when examining
  208.  * the lookaheads in a state.
  209.  */
  210. struct    yytok ACtok;
  211.  
  212. #define acchar    ACtok.Yychar
  213. #define aclval    ACtok.Yylval
  214.  
  215. /*
  216.  * Make a correction to the current stack which has
  217.  * top of stack pointer Ps.
  218.  */
  219. yyrecover(Ps0, idfail)
  220.     int *Ps0, idfail;
  221. {
  222.     register int c, i;
  223.     int yyrwant, yyrhave;
  224.  
  225. #ifdef PI
  226.     Recovery = TRUE;
  227. #endif
  228.  
  229.     YC = &YC0[1];
  230. #ifdef DEBUG
  231.     if (errtrace) {
  232.         setpfx('p');
  233.         yerror("Point of error");
  234.         printf("States %d %d ...", Ps0[0], Ps0[-1]);
  235.         if (idfail)
  236.             printf(" [Idfail]");
  237. #ifdef PXP
  238.         putchar('\n');
  239. #else
  240.         pchr('\n');
  241. #endif
  242.         printf("Input %s%s", tokname(&Y , 0)
  243.                    , tokname(&Y , 1));
  244.     }
  245.  
  246. #endif
  247.     /*
  248.      * We first save the current input token
  249.      * and its associated semantic information.
  250.      */
  251.     if (yychar < 0)
  252.         yychar = yylex();
  253.     copy((char *) (&YC[0]), (char *) (&Y), sizeof Y);
  254.  
  255.     /*
  256.      * Set the default action and cost
  257.      */
  258.     cact = CPANIC, ccost = CLIMIT, cflag = 0;
  259.  
  260.     /*
  261.      * Peek ahead
  262.      */
  263.     for (yCcnt = 1; yCcnt < YCSIZ; yCcnt++) {
  264.         yychar = yylex();
  265.         copy((char *) (&YC[yCcnt]), (char *) (&Y), sizeof YC[0]);
  266. #ifdef DEBUG
  267.         Eprintf(" | %s%s", tokname(&YC[yCcnt] , 0 )
  268.                  , tokname(&YC[yCcnt] , 1 ));
  269. #endif
  270.     }
  271. #ifdef DEBUG
  272.     Eprintf("\n");
  273. #endif
  274.  
  275.     /*
  276.      * If we are here because a reduction failed, try
  277.      * correcting that.
  278.      */
  279.     if (idfail) {
  280.         /*
  281.          * Save the particulars about
  282.          * the kind of identifier we want/have.
  283.          */
  284.         yyrwant = yyidwant;
  285.         yyrhave = yyidhave;
  286. #ifdef DEBUG
  287.         Tprintf("  Try Replace %s identifier with %s identifier cost=%d\n",
  288.             classes[yyidhave], classes[yyidwant], CCHIDCOST);
  289. #endif
  290.  
  291.         /*
  292.          * Save the semantics of the ID on the
  293.          * stack, and null them out to free
  294.          * up the reduction in question.
  295.          */
  296.         i = yypv[0].i_entry;
  297.         yypv[0].i_entry = nullsem(YID);
  298.         c = correct(NOCHAR, 0, CCHIDCOST, &repmult[2], Ps0,
  299.                 (int *) yypv);
  300.         yypv[0].i_entry = i;
  301. #ifdef DEBUG
  302.         if (c < CPRLIMIT || fulltrace)
  303.             Eprintf("Cost %2d Replace %s identifier with %s identifier\n", c, classes[yyrhave], classes[yyrwant]);
  304. #endif
  305.         if (c < ccost)
  306.             cact = CCHIDENT, ccost = c, cchar = YID;
  307.     }
  308.  
  309.     /*
  310.      * First try correcting the state we are in
  311.      */
  312.     trystate(Ps0, (int *) yypv, 0, &insmult[1], &delmult[1], &repmult[1]);
  313.  
  314.     /*
  315.      * Now, if we just shifted over a terminal, try
  316.      * correcting it.
  317.      */
  318.     if (OY.Yychar != -1 && OY.Yylval != nullsem(OY.Yychar)) {
  319.         YC--;
  320.         copy((char *) (&YC[0]), (char *) (&OY), sizeof YC[0]);
  321.         trystate(Ps0 - 1, (int *) (yypv - 1), 1, insmult, delmult,
  322.                 repmult);
  323.         if (cflag == 0)
  324.             YC++;
  325.         else {
  326.             yypv--;
  327. #ifdef PXP
  328.             yypw--;
  329. #endif
  330.             Ps0--;
  331.             yCcnt++;
  332.         }
  333.     }
  334.  
  335.     /*
  336.      * Restoring the first look ahead into
  337.      * the scanner token allows the error message
  338.      * routine to print the error message with the text
  339.      * of the correct line.
  340.      */
  341.     copy((char *) (&Y), (char *) (&YC[0]), sizeof Y);
  342.  
  343.     /*
  344.      * Unique symbol insertion.
  345.      *
  346.      * If there was no reasonable correction found,
  347.      * but only one input to the parser is acceptable
  348.      * we report that, and try it.
  349.      *
  350.      * Special precautions here to prevent looping.
  351.      * The number of true inputs shifted over at the point
  352.      * of the last unique insertion is recorded in the
  353.      * variable yyTshifts.  If this is not less than
  354.      * the current number in yytshifts, we do not insert.
  355.      * Thus, after one unique insertion, no more unique
  356.      * insertions will be made until an input is shifted
  357.      * over.  This guarantees termination.
  358.      */
  359.     if (cact == CPANIC && !idfail) {
  360.         register int *ap;
  361.  
  362.         ap = &yyact[yypact[*Ps0 + 1]];
  363.         if (*ap == -ERROR)
  364.             ap += 2;
  365.         if (ap[0] <= 0 && ap[2] > 0) {
  366.             cchar = -ap[0];
  367.             if (cchar == YEOF)
  368.                 yyexeof();
  369.             if (cchar != ERROR && yyTshifts < yytshifts) {
  370.                 cact = CUNIQUE;
  371. #ifdef DEBUG
  372.                 Eprintf("Unique symbol %s%s\n"
  373.                     , charname(cchar , 0 )
  374.                     , charname(cchar , 1 ));
  375. #endif
  376.                 /*
  377.                  * Note that the inserted symbol
  378.                  * will not be counted as a true input
  379.                  * (i.e. the "yytshifts--" below)
  380.                  * so that a true shift will be needed
  381.                  * to make yytshifts > yyTshifts.
  382.                  */
  383.                 yyTshifts = yytshifts;
  384.             }
  385.         }
  386.     }
  387.  
  388.     /*
  389.      * Set up to perform the correction.
  390.      * Build a token appropriate for replacement
  391.      * or insertion in the yytok structure ACchar
  392.      * having the attributes of the input at the
  393.      * point of error.
  394.      */
  395.     copy((char *) (&ACtok), (char *) (&YC[0]), sizeof ACtok);
  396.     acchar = cchar;
  397.     aclval = nullsem(acchar);
  398.     if (aclval != NIL)
  399.         recovered();
  400.     switch (cact) {
  401.         /*
  402.          * Panic, just restore the
  403.          * lookahead and return.
  404.          */
  405.         case CPANIC:
  406.             setpfx('E');
  407.             if (idfail) {
  408.                 copy((char *) (&Y), (char *) (&OY), sizeof Y);
  409.                 if (yyrhave == NIL) {
  410. #ifdef PI
  411.                     if (yybaduse(yypv[0].cptr, yyeline, ISUNDEF) == NIL)
  412. #endif
  413.                         yerror("Undefined identifier");
  414.                 } else {
  415.                     yerror("Improper %s identifier", classes[yyrhave]);
  416. #ifdef PI
  417.                     (void) yybaduse(yypv[0].cptr, yyeline, NIL);
  418. #endif
  419.                 }
  420.                 /*
  421.                  * Suppress message from panic routine
  422.                  */
  423.                 yyshifts = 1;
  424.             }
  425.             i = 0;
  426.             /* Note that on one path we dont touch yyshifts ! */
  427.             break;
  428.         /*
  429.          * Delete the input.
  430.          * Mark this as a shift over true input.
  431.          * Restore the lookahead starting at
  432.          * the second token.
  433.          */
  434.         case CDELETE:
  435.             if (ccost != 0)
  436.                 yerror("Deleted %s%s", tokname(&YC[0] , 0 )
  437.                              , tokname(&YC[0] , 1 ));
  438.             yytshifts++;
  439.             i = 1;
  440.             yyshifts = 0;
  441.             break;
  442.         /*
  443.          * Replace the input with a new token.
  444.          */
  445.         case CREPLACE:
  446.             if (acchar == YEOF)
  447.                 yyexeof();
  448.             if (acchar == YEND)
  449.                 aclval = NIL;
  450.             yerror("Replaced %s%s with a %s%s",
  451.                 tokname(&YC[0] , 0 ),
  452.                 tokname(&YC[0] , 1 ),
  453.                 tokname(&ACtok , 0 ),
  454.                 tokname(&ACtok , 1 ));
  455.             copy((char *) (&YC[0]), (char *) (&ACtok), sizeof YC[0]);
  456.             i = 0;
  457.             yyshifts = 0;
  458.             break;
  459.         /*
  460.          * Insert a token.
  461.          * Don't count this token as a true input shift.
  462.          * For inserted "end"s pas.y is responsible
  463.          * for the error message later so suppress it.
  464.          * Restore all the lookahead.
  465.          */
  466.         case CINSERT:
  467.             if (acchar == YEOF)
  468.                 yyexeof();
  469.             if (acchar != YEND)
  470.                 yerror("Inserted %s%s",
  471.                     tokname(&ACtok , 0 ),
  472.                     tokname(&ACtok , 1 ));
  473.             yytshifts--;
  474.             i = 0;
  475.             yyshifts = 0;
  476.             break;
  477.         /*
  478.          * Make a unique symbol correction.
  479.          * Like an insertion but a different message.
  480.          */
  481.         case CUNIQUE:
  482.             setpfx('E');
  483.             yerror("Expected %s%s",
  484.                 tokname(&ACtok , 0 ),
  485.                 tokname(&ACtok , 1 ));
  486.             yytshifts--;
  487.             i = 0;
  488.             if (ccost == 0 || yyunique)
  489.                 yyshifts = 0;
  490.             else
  491.                 yyshifts = -1;
  492.             break;
  493.         /*
  494.          * Change an identifier's type
  495.          * to make it work.
  496.          */
  497.         case CCHIDENT:
  498.             copy((char *) (&Y), (char *) (&OY), sizeof Y);
  499. #ifdef PI
  500.             i = 1 << yyrwant;
  501. #endif
  502.             if (yyrhave == NIL) {
  503.                 yerror("Undefined %s", classes[yyrwant]);
  504. #ifdef PI
  505.                 i |= ISUNDEF;
  506. #endif
  507.             } else
  508.                 yerror("Replaced %s id with a %s id", classes[yyrhave], classes[yyrwant]);
  509. #ifdef PI
  510.             (void) yybaduse(yypv[0].cptr, yyeline, i);
  511. #endif
  512.             yypv[0].i_entry = nullsem(YID);
  513.             i = 0;
  514.             yyshifts = 0;
  515.             break;
  516.     }
  517.  
  518.     /*
  519.      * Restore the desired portion of the lookahead,
  520.      * and possibly the inserted or unique inserted token.
  521.      */
  522.     for (yCcnt--; yCcnt >= i; yCcnt--)
  523.         unyylex(&YC[yCcnt]);
  524.     if (cact == CINSERT || cact == CUNIQUE)
  525.         unyylex(&ACtok);
  526.  
  527.     /*
  528.      * Put the scanner back in sync.
  529.      */
  530.     yychar = yylex();
  531.  
  532.     /*
  533.      * We succeeded if we didn't "panic".
  534.      */
  535.     Recovery = FALSE;
  536.     Ps = Ps0;
  537.     return (cact != CPANIC);
  538. }
  539.  
  540. yyexeof()
  541. {
  542.  
  543.     yerror("End-of-file expected - QUIT");
  544.     pexit(ERRS);
  545. }
  546.  
  547. yyunexeof()
  548. {
  549.  
  550.     yerror("Unexpected end-of-file - QUIT");
  551.     pexit(ERRS);
  552. }
  553.  
  554. /*
  555.  * Try corrections with the state at Ps0.
  556.  * Flag is 0 if this is the top of stack state,
  557.  * 1 if it is the state below.
  558.  */
  559. trystate(Ps0, Pv0, flag, insmult, delmult, repmult)
  560.     int *Ps0, *Pv0, flag;
  561.     char *insmult, *delmult, *repmult;
  562. {
  563.     /*
  564.      * C is a working cost, ap a pointer into the action
  565.      * table for looking at feasible alternatives.
  566.      */
  567.     register int c, *ap;
  568.  
  569. #ifdef DEBUG
  570.     Eprintf("Trying state %d\n", *Ps0);
  571. #endif
  572.     /*
  573.      * Try deletion.
  574.      * Correct returns a cost.
  575.      */
  576. #ifdef DEBUG
  577.     Tprintf("  Try Delete %s%s cost=%d\n",
  578.         tokname(&YC[0] , 0 ),
  579.         tokname(&YC[0] , 1 ),
  580.         delcost(YC[0].Yychar));
  581. #endif
  582.     c = delcost(YC[0].Yychar);
  583. #ifndef DEBUG
  584.     if (c < ccost) {
  585. #endif
  586.         c = correct(NOCHAR, 1, c, delmult, Ps0, Pv0);
  587. #ifdef DEBUG
  588.         if (c < CPRLIMIT || fulltrace)
  589.             Eprintf("Cost %2d Delete %s%s\n", c,
  590.                 tokname(&YC[0] , 0 ),
  591.                 tokname(&YC[0] , 1 ));
  592. #endif
  593.         if (c < ccost)
  594.             cact = CDELETE, ccost = c, cflag = flag;
  595. #ifndef DEBUG
  596.     }
  597. #endif
  598.  
  599.     /*
  600.      * Look at the inputs to this state
  601.      * which will cause parse action shift.
  602.      */
  603.     aclval = NIL;
  604.     ap = &yyact[yypact[*Ps0 + 1]];
  605.  
  606.     /*
  607.      * Skip action on error to
  608.      * detect true unique inputs.
  609.      * Error action is always first.
  610.      */
  611.     if (*ap == -ERROR) 
  612.         ap += 2;
  613.  
  614.     /*
  615.      * Loop through the test actions
  616.      * for this state.
  617.      */
  618.     for (; *ap <= 0; ap += 2) {
  619.         /*
  620.          * Extract the token of this action
  621.          */
  622.         acchar = -*ap;
  623.  
  624.         /*
  625.          * Try insertion
  626.          */
  627. #ifdef DEBUG
  628.         Tprintf("  Try Insert %s%s cost=%d\n"
  629.             , charname(acchar , 0 )
  630.             , charname(acchar , 1 )
  631.             , inscost(acchar, YC[0].Yychar));
  632. #endif
  633.         c = inscost(acchar, YC[0].Yychar);
  634. #ifndef DEBUG
  635.         if (c < ccost) {
  636. #endif
  637.             if (c == 0) {
  638.                 c = correct(acchar, 0, 1, insmult + 1, Ps0, Pv0);
  639. #ifdef DEBUG
  640.                 Eprintf("Cost %2d Freebie %s%s\n", c
  641.                     , charname(acchar , 0 )
  642.                     , charname(acchar , 1 ));
  643. #endif
  644.                 if (c < ccost)
  645.                     cact = CUNIQUE, ccost = 0, cchar = acchar, cflag = flag;
  646.             } else {
  647.                 c = correct(acchar, 0, c, insmult, Ps0, Pv0);
  648. #ifdef DEBUG
  649.                 if (c < CPRLIMIT || fulltrace)
  650.                     Eprintf("Cost %2d Insert %s%s\n", c
  651.                         , charname(acchar , 0 )
  652.                         , charname(acchar , 1 ));
  653. #endif
  654.                 if (c < ccost)
  655.                     cact = CINSERT, ccost = c, cchar = acchar, cflag = flag;
  656.             }
  657. #ifndef DEBUG
  658.         }
  659. #endif
  660.  
  661.         /*
  662.          * Try replacement
  663.          */
  664. #ifdef DEBUG
  665.         Tprintf("  Try Replace %s%s with %s%s cost=%d\n",
  666.             tokname(&YC[0] , 0 ),
  667.             tokname(&YC[0] , 1 ),
  668.             charname(acchar , 0 ),
  669.             charname(acchar , 1 ),
  670.             repcost(YC[0].Yychar, acchar));
  671. #endif
  672.         c = repcost(YC[0].Yychar, acchar);
  673. #ifndef DEBUG
  674.         if (c < ccost) {
  675. #endif
  676.             c = correct(acchar, 1, repcost(YC[0].Yychar, acchar), repmult, Ps0, Pv0);
  677. #ifdef DEBUG
  678.             if (c < CPRLIMIT || fulltrace)
  679.                 Eprintf("Cost %2d Replace %s%s with %s%s\n",
  680.                     c,
  681.                     tokname(&YC[0] , 0 ),
  682.                     tokname(&YC[0] , 1 ),
  683.                     tokname(&ACtok , 0 ),
  684.                     tokname(&ACtok , 1 ));
  685. #endif
  686.             if (c < ccost)
  687.                 cact = CREPLACE, ccost = c, cchar = acchar, cflag = flag;
  688. #ifndef DEBUG
  689.         }
  690. #endif
  691.     }
  692. }
  693.  
  694. int    *yCpv;
  695. char    yyredfail;
  696.  
  697. /*
  698.  * The ntok structure is used to build a
  699.  * scanner structure for tokens inserted
  700.  * from the argument "fchar" to "correct" below.
  701.  */
  702. static    struct yytok ntok;
  703.  
  704. /*
  705.  * Compute the cost of a correction
  706.  * C is the base cost for it.
  707.  * Fchar is the first input character from
  708.  * the current state, NOCHAR if none.
  709.  * The rest of the inputs come from the array
  710.  * YC, starting at origin and continuing to the
  711.  * last character there, YC[yCcnt - 1].Yychar.
  712.  *
  713.  * The cost returned is INFINITE if this correction
  714.  * allows no shifts, otherwise is weighted based
  715.  * on the number of shifts this allows against the
  716.  * maximum number possible with the available lookahead.
  717.  */
  718. correct(fchar, origin, c, multvec, Ps0, Pv0)
  719.     register int fchar, c;
  720.     int origin;
  721.     char *multvec;
  722.     int *Ps0, *Pv0;
  723. {
  724.     register char *mv;
  725.     extern int *loccor();
  726.  
  727.     /*
  728.      * Ps is the top of the parse stack after the most
  729.      * recent local correctness check.  Loccor returns
  730.      * NIL when we cannot shift.
  731.      */
  732.     register int *ps;
  733.  
  734.     yyredfail = 0;
  735.     /*
  736.      * Initialize the tip parse and semantic stacks.
  737.      */
  738.     ps = Ps0;
  739.     yytips[0] = *ps;
  740.     ps--;
  741.     yytipv[0] = Pv0[0];
  742.     yCpv = Pv0 - 1;
  743.     yytipct = 1;
  744.  
  745.     /*
  746.      * Shift while possible.
  747.      * Adjust cost as necessary.
  748.      */
  749.     mv = multvec;
  750.     do {
  751.         if (fchar != NOCHAR) {
  752.             copy((char *) (&ntok), (char *) (&YC[0]), sizeof ntok);
  753.             ntok.Yychar = fchar, ntok.Yylval = nullsem(fchar);
  754.             fchar = NOCHAR;
  755.             ps = loccor(ps, &ntok);
  756.         } else
  757.             ps = loccor(ps, &YC[origin++]);
  758.         if (ps == NIL) {
  759.             if (yyredfail && mv > multvec)
  760.                 mv--;
  761.             c *= *mv;
  762.             break;
  763.         }
  764.         mv++;
  765.     } while (*mv != 1);
  766.     return (c);
  767. }
  768.  
  769. extern    int yygo[], yypgo[], yyr1[], yyr2[];
  770. /*
  771.  * Local syntactic correctness check.
  772.  * The arguments to this routine are a
  773.  * top of stack pointer, ps, and an input
  774.  * token tok.  Also, implicitly, the contents
  775.  * of the yytips array which contains the tip
  776.  * of the stack, and into which the new top
  777.  * state on the stack will be placed if we shift.
  778.  *
  779.  * If we succeed, we return a new top of stack
  780.  * pointer, else we return NIL.
  781.  */
  782. int *
  783. loccor(ps, ntok)
  784.     int *ps;
  785.     struct yytok *ntok;
  786. {
  787.     register int *p, n;
  788.     register int nchar;
  789.     int i;
  790.  
  791.     if (ps == NIL)
  792.         return (NIL);
  793.     nchar = ntok->Yychar;
  794.     yyeline = ntok->Yyeline;
  795. #ifdef DEBUG
  796.     Tprintf("    Stack ");
  797.     for (i = yytipct - 1; i >= 0; i--)
  798.         Tprintf("%d ", yytips[i]);
  799.     Tprintf("| %d, Input %s%s\n", *ps
  800.         , charname(nchar , 0 )
  801.         , charname(nchar , 1 ));
  802. #endif
  803.     /*
  804.      * As in the yacc parser yyparse,
  805.      * p traces through the action list
  806.      * and "n" is the information associated
  807.      * with the action.
  808.      */
  809. newstate:
  810.     p = &yyact[ yypact[yytips[yytipct - 1]+1] ];
  811.  
  812.     /*
  813.      * Search the parse actions table
  814.      * for something useful to do.
  815.      * While n is non-positive, it is the
  816.      * arithmetic inverse of the token to be tested.
  817.      * This allows a fast check.
  818.      */
  819.     while ((n = *p++) <= 0)
  820.         if ((n += nchar) != 0)
  821.             p++;
  822.     switch (n >> 12) {
  823.         /*
  824.          * SHIFT
  825.          */
  826.         default:
  827.             panic("loccor");
  828.         case 2:
  829.             n &= 07777;
  830.             yyredfail = 0;
  831.             if (nchar == YID)
  832.                 yyredfail++;
  833.             if (yytipct == YYTIPSIZ) {
  834. tipover:
  835. #ifdef DEBUG
  836.                 Tprintf("\tTIP OVFLO\n");
  837. #endif
  838.                 return (NIL);
  839.             }
  840.             yytips[yytipct] = n;
  841.             yytipv[yytipct] = ntok->Yylval;
  842.             yytipct++;
  843. #ifdef DEBUG
  844.             Tprintf("\tShift to state %d\n", n);
  845. #endif
  846.             return (ps);
  847.         /*
  848.          * REDUCE
  849.          */
  850.         case 3:
  851.             n &= 07777;
  852.             if (yyEactr(n, (char *) yytipv[yytipct - 1]) == 0) {
  853. #ifdef DEBUG
  854.                 Tprintf("\tYyEactr objects: have %s id, want %s id\n", classes[yyidhave], classes[yyidwant]);
  855. #endif
  856.                 return (NIL);
  857.             }
  858.             yyredfail = 0;
  859.             i = yyr2[n];
  860. #ifdef DEBUG
  861.             Tprintf("\tReduce, length %d,", i);
  862. #endif
  863.             if (i > yytipct) {
  864.                 i -= yytipct;
  865.                 yytipct = 0;
  866.                 ps -= i;
  867.                 yCpv -= i;
  868.             } else
  869.                 yytipct -= i;
  870.             if (yytipct >= YYTIPSIZ)
  871.                 goto tipover;
  872.             /*
  873.              * Use goto table to find next state
  874.              */
  875.             p = &yygo[yypgo[yyr1[n]]];
  876.             i = yytipct ? yytips[yytipct - 1] : *ps;
  877.             while (*p != i && *p >= 0)
  878.                 p += 2;
  879. #ifdef DEBUG
  880.             Tprintf(" new state %d\n", p[1]);
  881. #endif
  882.             yytips[yytipct] = p[1];
  883.             yytipct++;
  884.             goto newstate;
  885.         /*
  886.          * ACCEPT
  887.          */
  888.         case 4:
  889. #ifdef DEBUG
  890.             Tprintf("\tAccept\n");
  891. #endif
  892.             return (ps);
  893.         /*
  894.          * ERROR
  895.          */
  896.         case 1:
  897. #ifdef DEBUG
  898.             Tprintf("\tError\n");
  899. #endif
  900.             return (0);
  901.     }
  902. }
  903.