llparse.c

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

FreeBSD/Linux Kernel Cross Reference
sys/netiso/xebec/llparse.c
