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