home *** CD-ROM | disk | FTP | other *** search
/ The Education Master 1994 (4th Edition) / EDUCATIONS_MASTER_4TH_EDITION.bin / files / progmisc / qparser2 / cskels / pars.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-07  |  9.5 KB  |  352 lines
  1. /* pars.c
  2.  
  3.    Parser and error recovery functions.
  4.    This file should be run through lr1p to activate or suppress
  5.      parser debugging features.
  6.  
  7.    */
  8.  
  9.  
  10. #include <stdio.h>
  11. #include <ctype.h>
  12. #include "decl.h"
  13.  
  14. int cstate;
  15. int stack[STACKSIZE+1];  /* the state stack */
  16.  
  17. int stackx= 0;
  18. semrectype *semstack[STACKSIZE+1];
  19. static char errsym[9]= "ErrSymAA";
  20.  
  21. /* .................... */
  22. static void copy_stack(mstack, mstackx, mcstate,
  23.                     stack, stackx, cstate, jstx)
  24.   int mstack[], mstackx, mcstate,
  25.       stack[], *stackx, *cstate, jstx;
  26. {
  27.   if ((jstx<0) || (jstx>mstackx)) abort_trap("ERROR RECOVERY BUG");
  28.   memcpy((char *) stack, (char *) mstack, (jstx+1)*sizeof(int));
  29.   *stackx = jstx;
  30.   *cstate = (jstx == mstackx) ?  mcstate : mstack[jstx+1];
  31.   }
  32.  
  33. /*......................*/
  34. static void err_pushread(cstate, stack, stackx)
  35.   int cstate, stack[], *stackx;
  36.   /* do the push part of a READSTATE. */
  37. {
  38.   (*stackx)++;
  39.   if (*stackx>STACKSIZE)
  40.     abort_trap("stack overflow");
  41.   stack[*stackx] = cstate;
  42.   }
  43.  
  44. /*...............*/
  45. static int trial_parse(cstate, stack, stackx)
  46.   int *cstate, stack[], stackx;
  47.   /* parses from current read state through the inserted and the
  48.     error token; if successful, returns 1. */
  49. {
  50.   int rx;
  51.   int trial= 1;
  52.  
  53.   while (*cstate!=0) {
  54. #if DEBUG == 1
  55.     stack[stackx+1]= *cstate;
  56. #endif
  57.     if (*cstate < READSTATE) {
  58.       /* a reduce state */
  59.  
  60. #if DEBUG == 1
  61.       if (debug_level > 3)
  62.         stk_dump("E*Reduce", stack, stackx, debug_level);
  63. #endif
  64.       if (popno[*cstate] == 0) {
  65.         /* empty production */
  66.         err_pushread(stk_state[statex[*cstate]], stack, &stackx);
  67.         *cstate = stk_tostate[statex[*cstate]];
  68.         }
  69.       else {
  70.         /* non-empty production */
  71.         stackx = stackx - popno[*cstate] + 1;
  72.         rx = statex[*cstate];   /* compute the GOTO state */
  73.         *cstate = stack[stackx];
  74.         while ((stk_state[rx]!=*cstate) &&
  75.                (stk_state[rx]!=0)) rx++;
  76.         *cstate = stk_tostate[rx];
  77.         }
  78.       }
  79.     else if (*cstate < LOOKSTATE) {
  80.       /* a read state */
  81.       next_token();  /* need a token now */
  82. #if DEBUG == 1
  83.       if (debug_level > 3)
  84.         stk_dump("E*Read", stack, stackx, debug_level);
  85. #endif
  86.       rx = statex[*cstate];
  87.       while (toknum[rx] &&
  88.              toknum[rx]!=token) rx++;
  89.       if (toknum[rx]) {
  90.         /* did read something */
  91.         err_pushread(*cstate, stack, &stackx);
  92.         *cstate = tostate[rx];
  93.         tokenread();  /* scan the token */
  94.         if (tokenx>1) return trial;   /* successful */
  95.         }
  96.       else return 0;  /* failure */
  97.       }
  98.     else {
  99.       /* lookahead state */
  100.       next_token();  /* need a token now */
  101. #if DEBUG == 1
  102.       if (debug_level > 3)
  103.         stk_dump("E*Look", stack, stackx, debug_level);
  104. #endif
  105.       rx = statex[*cstate];
  106.       while (toknum[rx] &&
  107.              toknum[rx]!=token) rx++;
  108.       *cstate = tostate[rx];
  109.       }
  110.     }
  111.   return(trial);
  112.   }
  113.  
  114. /*.................*/
  115. static void incr_errsym()
  116.   /* Note that this procedure assumes ASCII. */
  117. { int slen= strlen(errsym);
  118.  
  119.   if (errsym[slen-1] >= 'Z') {
  120.     errsym[slen-2]++;       /* incrementing a char */
  121.     errsym[slen-1]= 'A';
  122.     }
  123.   else
  124.     errsym[slen-1]++;
  125.   }
  126.  
  127. /*.................*/
  128. static semrectype *make_default(tokx)
  129.   int tokx;
  130.   /* creates a default token semantics data structure */
  131. { semrectype *tsemp;
  132.  
  133.   switch (tokx) {
  134.     case IDENT_TOKX:
  135.       tsemp= new_sem(IDENT, USER);
  136.       tsemp->usem.symp = makesym(errsym, SYMERR);
  137.       incr_errsym();
  138.       break;
  139.     case INT_TOKX:
  140.       tsemp= new_sem(FIXED, INTVAR);
  141.       tsemp->usem.numval = 1;
  142.       break;
  143.     case REAL_TOKX:
  144.       tsemp= new_sem(FLOAT, REALVAR);
  145.       tsemp->usem.rval = 1.0;
  146.       break;
  147.     case STR_TOKX:
  148.       tsemp= new_sem(STRNG, STRVAR);
  149.       tsemp->usem.strx = "ERROR";
  150.       break;
  151.     default:
  152.       tsemp= new_sem(OTHER, SYMERR);
  153.       break;
  154.     } /* switch tokx */
  155.   return tsemp;
  156.   }
  157.  
  158. /* .............. */
  159. static int error_recovery(mstack, mstackx, mcstate)
  160.   int mstack[], *mstackx, mcstate;
  161. { int stack[STACKSIZE+1],  /* local copy of stack */
  162.      stackx,              /* local stack pointer */
  163.      cstate,              /* local state */
  164.      jstx,                /* temporary stack limit */
  165.      rx;                  /* index into TOKNUM table */
  166.  
  167. #if DEBUG == 1
  168.   if (debug_level > 3) printf("Going into ERROR RECOVERY\n");
  169. #endif
  170.   while (1) {
  171.     jstx = *mstackx;
  172.     while (jstx>=0) {
  173.       copy_stack(mstack, *mstackx, mcstate,
  174.                  stack, &stackx, &cstate, jstx);
  175.       rx = statex[cstate];
  176.       while (toknum[rx]) {
  177.         /* scan through legal next tokens */
  178. #if DEBUG == 1
  179.         if (debug_level > 3) printf("...starting trial parse\n");
  180. #endif
  181.         tokary[0] = toknum[rx];  /* the insertion */
  182.         tokenx = 0;
  183.         if (trial_parse(&cstate, stack, stackx))
  184.           goto got_it;  /* it clicked! */
  185.         rx++;
  186.         if (toknum[rx])
  187.           copy_stack(mstack, *mstackx, mcstate,
  188.                      stack, &stackx, &cstate, jstx);
  189.         }
  190.       jstx--;  /* reduce stack */
  191.       }
  192.     if (token == STOP_TOKX) {
  193.       /* empty stack, no more tokens */
  194.       cstate = 0;  /* halt state */
  195.       tokenx = 2;
  196.       jstx = 0;  /* bottom of stack */
  197.       goto finish;
  198.       }
  199.     tokenx = 2;
  200.     next_token();
  201.     }
  202.   got_it:  /* found a solution */
  203.   copy_stack(mstack, *mstackx, mcstate,
  204.              stack, &stackx, &cstate, jstx);
  205.   lsempary[0]= make_default(tokary[0]);
  206.   tokenx = 0;  /* forces a `real' rescan of the insertion */
  207.   if (jstx<*mstackx)
  208.     cstate = stack[jstx+1];
  209.   else
  210.     cstate = mcstate;  /* cstate returned */
  211.   finish:
  212.   *mstackx = jstx;
  213. #if DEBUG == 1
  214.   if (debug_level > 3) printf("Ending error recovery\n");
  215. #endif
  216.   return(cstate);
  217.   }
  218.  
  219. #define MSG2 ", expecting:"
  220. #define MSG1 "Found "
  221.  
  222. /*.....................*/
  223. static void show_expecting(cstate)
  224. { int len, rx;
  225.  
  226.   printf(MSG1);
  227.  
  228.   if (token == IDENT_TOKX &&
  229.       lsemp->usem.symp)
  230.     printf("%s", lsemp->usem.symp->sym);
  231.   else printf("%s", tokstring[token]);
  232.  
  233.   printf(MSG2);
  234.   len= strlen(MSG2);
  235.   rx=statex[cstate];
  236.   while(toknum[rx] && len < 50) {
  237.     printf(" %s", tokstring[toknum[rx]]);
  238.     len += 1+ strlen(tokstring[toknum[rx]]);
  239.     rx++;
  240.     }
  241.  
  242.   if (toknum[rx]) printf("...\n");
  243.   else printf("\n");
  244.   }
  245.  
  246. /*......................*/
  247. static void parse_pushread(cstate, semp)
  248.   int cstate;
  249.   semrectype *semp;
  250.   /* do the push part of a READSTATE. */
  251. {
  252.   stackx++;
  253.   if (stackx>STACKSIZE)
  254.     abort_trap("stack overflow");
  255.   semstack[stackx] = semp;
  256.   stack[stackx] = cstate;
  257.   }
  258.  
  259. /* .............. */
  260. void parser()      /* Carries out a complete parse, until
  261.     the halt state is seen -- same as empty stack */
  262. { int rx;
  263.   semrectype *tsemp;
  264.   void init_sem(), end_sem();
  265.  
  266.   init_sem();
  267.   cstate = START_STATE;
  268.   stackx = -1;
  269.   tsemp=NULL;
  270.   parse_pushread(ISTK_STATE, tsemp);
  271.   while (cstate!=0) {
  272. #if DEBUG == 1
  273.     stack[stackx+1]= cstate;
  274. #endif
  275.     if (cstate < READSTATE) {
  276.       /* a reduce state */
  277. #if DEBUG == 1
  278.       if (debug_level > 0)
  279.         stk_dump("Reduce", stack, stackx, debug_level);
  280.       else if (prodtrap && set_member(cstate, prodtrap))
  281.         stk_dump("Reduce", stack, stackx, 2);
  282. #endif
  283.       tsemp= apply(cstate);  /* the semantics action */
  284.       if (popno[cstate]) {
  285.         /* non-empty production:
  286.             semantics is preserved on a unit production A --> w,
  287.             where |w| = 1, unless something is in TSEMP.  Note that
  288.             if w is nonterminal, the production may be bypassed. */
  289.         if (popno[cstate]==1) {
  290.           if (tsemp) semstack[stackx]= tsemp;
  291.           }
  292.         else {
  293.           stackx += 1-popno[cstate];
  294.           semstack[stackx] = tsemp;
  295.           }
  296.         /* compute the GOTO state */
  297.         rx = statex[cstate];
  298.         cstate = stack[stackx];
  299.         while (stk_state[rx]!=cstate && stk_state[rx]) rx++;
  300.         cstate = stk_tostate[rx];
  301.         }
  302.       else {  /* empty production */
  303.         parse_pushread(stk_state[statex[cstate]], tsemp);
  304.         cstate = stk_tostate[statex[cstate]];
  305.         }
  306.       }
  307.     else if (cstate < LOOKSTATE) {
  308.       /* a read state */
  309.       next_token();  /* need next token now */
  310. #if DEBUG == 1
  311.       if (debug_level > 2)
  312.         stk_dump("Read", stack, stackx, debug_level);
  313. #endif
  314.       rx = statex[cstate];
  315.       while (toknum[rx] && toknum[rx]!=token) rx++;
  316.       if (toknum[rx]) {  /* found the token */
  317.         parse_pushread(cstate, lsemp);
  318.         cstate = tostate[rx];
  319.         tokenread();  /* token has been scanned */
  320.         }
  321.       else {
  322.         if (err_count<=0) {
  323.           error("syntax error");
  324.           show_expecting(cstate);
  325.           err_count= 3;  /* don't report errors for a few tokens */
  326.              /* lex.c is supposed to decrement err_count if > 0, once
  327.                  for each token */
  328.           }
  329.         cstate = error_recovery(stack, &stackx, cstate);
  330.         }
  331.       }
  332.     else {
  333.       /* lookahead state */
  334.       next_token();  /* need another token now */
  335. #if DEBUG == 1
  336.       if (debug_level > 2)
  337.         stk_dump("Look", stack, stackx, debug_level);
  338. #endif
  339.       rx = statex[cstate];
  340.       while (toknum[rx] && toknum[rx]!=token) rx++;
  341.       cstate = tostate[rx];
  342.       }
  343.     }
  344.   next_token();
  345.   if (token != STOP_TOKX) {
  346.     err_count= 0;
  347.     error("No end-of-file seen with HALT state");
  348.     }
  349.   end_sem();
  350.   }
  351.  
  352.