home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / sys / netiso / xebec / llparse.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-03  |  7.1 KB  |  367 lines
  1. /* $Header: llparse.c,v 2.2 88/09/19 12:54:59 nhall Exp $ */
  2. /* $Source: /var/home/tadl/src/argo/xebec/RCS/llparse.c,v $ */
  3. /*
  4.  * ************************* NOTICE *******************************
  5.  * This code is in the public domain.  It cannot be copyrighted.
  6.  * This ll parser was originally written by Keith Thompson for the 
  7.  * University of Wisconsin Crystal project.
  8.  * It was based on an FMQ lr parser written by Jon Mauney at the
  9.  * University of Wisconsin.
  10.  * It was subsequently modified very slightly by Nancy Hall at the 
  11.  * University of Wisconsin for the Crystal project.
  12.  * ****************************************************************
  13.  */
  14. #include "xebec.h"
  15. #include "llparse.h"
  16. #include "main.h"
  17. #include <stdio.h>
  18.  
  19. #include "debug.h"
  20.  
  21. #define LLMINACTION -LLINF
  22.  
  23. short        llparsestack[STACKSIZE];
  24. short        llstackptr = 0;
  25. LLtoken        lltoken;
  26.  
  27. llparse()
  28. {
  29.     register        havetoken = FALSE;
  30.     register        sym;
  31.     register LLtoken    *t = &lltoken;
  32.     register        parseaction;
  33.     register        accepted = FALSE;
  34.  
  35.     llpushprod(llnprods-1); /* $$$ ::= <start symbol>  */
  36.  
  37.     do {
  38.         sym = llparsestack[llstackptr];
  39.     IFDEBUG(L)
  40.         printf("llparse() top of loop, llstackptr=%d, sym=%d\n",
  41.             llstackptr, sym);
  42.     ENDDEBUG
  43.  
  44.         if(sym < 0) {
  45.             /* action symbol */
  46.             if(sym <= LLMINACTION) {
  47.                 for(;sym<=LLMINACTION;sym++) {
  48.                     llaction(1, t); /* calls llfinprod */
  49.                 }
  50.                 llstackptr--;
  51.                 continue;
  52.             } else { llaction(-sym, t);
  53.                 llstackptr--;
  54.                 continue;
  55.             }
  56.         }
  57.  
  58.         if(sym < llnterms) {
  59.  
  60.             /* it's a terminal symbol */
  61.  
  62.             if(!havetoken) {
  63.                 llgettoken(t);
  64.                 havetoken = TRUE;
  65.             }
  66.  
  67.             if(sym == t->llterm) {
  68.                 llpushattr(t->llattrib);
  69.                 llaccept(t);
  70.                 llstackptr--; /* pop terminal */
  71.                 if(t->llterm == llnterms-1) { /* end symbol $$$ */
  72.                     accepted = TRUE;
  73.                 } else {
  74.                     havetoken = FALSE;
  75.                 }
  76.             } else {
  77.                 llparsererror(t); /* wrong terminal on input */
  78.                 havetoken = FALSE;
  79.             }
  80.             continue;
  81.         }
  82.  
  83.         /* non terminal */
  84.  
  85.         if(!havetoken) {
  86.             llgettoken(t);
  87.             havetoken = TRUE;
  88.         }
  89.  
  90.         /* consult parse table  for new production */
  91.         parseaction = llfindaction(sym, t->llterm);
  92.  
  93.         if(parseaction == 0) {
  94.             /* error entry */
  95.             llparsererror(t);
  96.             havetoken = FALSE;
  97.             continue;
  98.         }
  99.  
  100.         if(llepsilon[parseaction]) {
  101.             /* epsilon production */
  102.             if(llepsilonok(t->llterm)) {
  103.                 llstackptr--; /* pop nonterminal */
  104.                 llpushprod(parseaction); /* push rhs of production */
  105.             } else {
  106.                 llparsererror(t);
  107.                 havetoken = FALSE;
  108.             }
  109.         } else {
  110.             llstackptr--; /* pop nonterminal */
  111.             llpushprod(parseaction); /* push rhs of production */
  112.         }
  113.     } while(!accepted);
  114.  
  115.     return(0);
  116. }
  117.  
  118. llpushprod(prod)     /* recognize production prod - push rhs on stack */
  119. short prod;
  120. {
  121.     register    start;
  122.     register    length;
  123.     register    count;
  124.  
  125.     start = llprodindex[prod].llprodstart;
  126.     length = llprodindex[prod].llprodlength;
  127.  
  128.     IFDEBUG(L)
  129.         printf("llpushprod(%d) llstackptr=0x%x(%d), length = 0x%x(%d)\n",
  130.         prod, llstackptr, llstackptr, length , length);
  131.         /*
  132.         dump_parse_stack();
  133.         */
  134.     ENDDEBUG
  135.     if(llstackptr+length >= STACKSIZE) {
  136.         fprintf(stderr,"Parse stack overflow. llstackptr=0x%x, length=0x%x\n",
  137.         llstackptr, length);
  138.         Exit(-1);
  139.     }
  140.  
  141.  
  142.     llsetattr(llprodindex[prod].llprodtlen);
  143.  
  144.     /* put a marker on the stack to mark beginning of production */
  145.     if(llparsestack[llstackptr] <= LLMINACTION) {
  146.         (llparsestack[llstackptr]) --; /* if there's already one there, don't
  147.                                 put another on; just let it represent all of
  148.                                 the adjacent markers */
  149.     }
  150.     else {
  151.         llstackptr++;
  152.         llparsestack[llstackptr] = LLMINACTION;
  153.     }
  154.  
  155.     for(count=0; count<length; count++) {
  156.         llstackptr++;
  157.         llparsestack[llstackptr] = llproductions[start++];
  158.     }
  159.     if(llstackptr > STACKSIZE) {
  160.         fprintf(stderr, "PARSE STACK OVERFLOW! \n"); Exit(-1);
  161.         Exit(-1);
  162.     }
  163. }
  164.  
  165.  
  166. llepsilonok(term)
  167. {
  168.     register    ptr;
  169.     register    sym;
  170.     register    pact;
  171.     register    nomore;
  172.     register    rval;
  173.  
  174.     IFDEBUG(L)
  175.         printf("llepsilonok() enter\n");
  176.     ENDDEBUG
  177.     rval = TRUE;
  178.  
  179.     ptr = llstackptr;
  180.  
  181.     do {
  182.         sym = llparsestack[ptr];
  183.  
  184.         if(sym < 0) {
  185.             ptr--;
  186.             nomore = ptr == 0;
  187.             continue;
  188.         }
  189.  
  190.         if(sym < llnterms) {
  191.             nomore = TRUE;
  192.             rval = sym == term;
  193.             continue;
  194.         }
  195.  
  196.         pact = llfindaction(sym, term);
  197.  
  198.         if(pact == 0) {
  199.             nomore = TRUE;
  200.             rval = FALSE;
  201.             continue;
  202.         }
  203.  
  204.         if(llepsilon[pact] == TRUE) {
  205.             ptr--;
  206.             nomore = ptr == 0;
  207.         }
  208.         else {
  209.             nomore = TRUE;
  210.         }
  211.  
  212.     } while(!nomore);
  213.  
  214.     return(rval);
  215. }
  216.  
  217.  
  218. short llfindaction(sym, term)
  219. {
  220.     register    index;
  221.  
  222.     IFDEBUG(L)
  223.         printf("llfindaction(sym=%d, term=%d) enter \n", sym, term);
  224.     ENDDEBUG
  225.     index = llparseindex[sym];
  226.  
  227.     while(llparsetable[index].llterm != 0) {
  228.         if(llparsetable[index].llterm == term) {
  229.             return(llparsetable[index].llprod);
  230.         }
  231.         index++;
  232.     }
  233.     return(0);
  234. }
  235.  
  236.  
  237. llparsererror(token)
  238. LLtoken *token;
  239. {
  240.     IFDEBUG(L)
  241.         fprintf(stderr,"llparsererror() enter\n");
  242.         prt_token(token);
  243.     ENDDEBUG
  244.  
  245.     fprintf(stderr, "Syntax error: ");
  246.     prt_token(token);
  247.     dump_buffer();
  248.     Exit(-1);
  249. }
  250.  
  251.  
  252. llgettoken(token)
  253. LLtoken *token;
  254. {
  255.     llscan(token);
  256.     token->llstate = NORMAL;
  257.     IFDEBUG(L)
  258.         printf("llgettoken(): ");
  259.         prt_token(token);
  260.     ENDDEBUG
  261. }
  262.  
  263.  
  264. /******************************************************************************
  265.  
  266.     Attribute support routines
  267.  
  268. ******************************************************************************/
  269. /*
  270. **    attribute stack
  271. **
  272. **    AttrStack =    stack of record
  273. **                values : array of values;
  274. **                ptr    : index;
  275. **    end;
  276. **
  277. */
  278.  
  279. LLattrib    llattributes[LLMAXATTR];
  280. int        llattrtop = 0;
  281.  
  282. struct llattr    llattrdesc[LLMAXDESC];
  283.  
  284. int    lldescindex = 1;
  285.  
  286.  
  287. llsetattr(n)
  288. {
  289.     register struct llattr *ptr;
  290.  
  291.     IFDEBUG(L)
  292.         printf("llsetattr(%d) enter\n",n);
  293.     ENDDEBUG
  294.     if(lldescindex >= LLMAXDESC) {
  295.         fprintf(stdout, "llattribute stack overflow: desc\n");
  296.         fprintf(stdout, 
  297.             "lldescindex=0x%x, llattrtop=0x%x\n",lldescindex, llattrtop);
  298.         Exit(-1);
  299.     }
  300.     ptr = &llattrdesc[lldescindex];
  301.     ptr->llabase = &llattributes[llattrtop];
  302.     ptr->lloldtop = ++llattrtop; 
  303.     ptr->llaindex = 1;
  304.     ptr->llacnt = n+1; /* the lhs ALWAYS uses an attr; it remains on the
  305.                         stack when the production is recognized */
  306.     lldescindex++;
  307. }
  308.  
  309. llpushattr(attr)
  310. LLattrib attr;
  311. {
  312.     struct llattr *a;
  313.  
  314.     IFDEBUG(L)
  315.         printf("llpushattr() enter\n");
  316.     ENDDEBUG
  317.     if(llattrtop + 1 > LLMAXATTR) {
  318.         fprintf(stderr, "ATTRIBUTE STACK OVERFLOW!\n");
  319.         Exit(-1);
  320.     }
  321.     a = &llattrdesc[lldescindex-1];
  322.     llattributes[llattrtop++] = attr;
  323.     a->llaindex++; /* inc count of attrs on the stack for this prod */
  324. }
  325.  
  326. llfinprod()
  327. {
  328.     IFDEBUG(L)
  329.         printf("llfinprod() enter\n");
  330.     ENDDEBUG
  331.     lldescindex--;
  332.     llattrtop = llattrdesc[lldescindex].lloldtop;
  333.     llattrdesc[lldescindex-1].llaindex++; /* lhs-of-prod.attr stays on
  334.         the stack; it is now one of the rhs attrs of the now-top production
  335.         on the stack */
  336. }
  337.  
  338. #ifndef LINT
  339. #ifdef DEBUG
  340. dump_parse_stack()
  341. {
  342.     int ind;
  343.  
  344.     printf("PARSE STACK:\n");
  345.     for(ind=llstackptr; ind>=0; ind--) {
  346.         printf("%d\t%d\t%s\n",
  347.         ind, llparsestack[ind],
  348.         llparsestack[ind]<0? "Action symbol" : llstrings[llparsestack[ind]]);
  349.     }
  350. }
  351.  
  352. #endif DEBUG
  353. #endif LINT
  354.  
  355. prt_token(t)
  356. LLtoken *t;
  357. {
  358.     fprintf(stdout, "t at 0x%x\n", t);
  359.     fprintf(stdout, "t->llterm=0x%x\n", t->llterm); (void) fflush(stdout);
  360.     fprintf(stdout, "TOK: %s\n", llstrings[t->llterm]);
  361.     (void) fflush(stdout);
  362. #ifdef LINT
  363.     /* to make lint shut up */
  364.     fprintf(stdout, "", llnterms, llnsyms, llnprods, llinfinite);
  365. #endif LINT
  366. }
  367.