The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

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

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*      $NetBSD: llparse.c,v 1.14 2009/03/18 10:22:44 cegger 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.14 2009/03/18 10:22:44 cegger 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(void)
   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(int term)
  175 {
  176         register int    ptr;
  177         register int    sym;
  178         register int    pact;
  179         register int    nomore;
  180         register int    rval;
  181 
  182         IFDEBUG(L)
  183                 printf("llepsilonok() enter\n");
  184         ENDDEBUG
  185         rval = true;
  186 
  187         ptr = llstackptr;
  188 
  189         do {
  190                 sym = llparsestack[ptr];
  191 
  192                 if(sym < 0) {
  193                         ptr--;
  194                         nomore = ptr == 0;
  195                         continue;
  196                 }
  197 
  198                 if(sym < llnterms) {
  199                         nomore = true;
  200                         rval = sym == term;
  201                         continue;
  202                 }
  203 
  204                 pact = llfindaction(sym, term);
  205 
  206                 if(pact == 0) {
  207                         nomore = true;
  208                         rval = false;
  209                         continue;
  210                 }
  211 
  212                 if(llepsilon[pact] == true) {
  213                         ptr--;
  214                         nomore = ptr == 0;
  215                 }
  216                 else {
  217                         nomore = true;
  218                 }
  219 
  220         } while(!nomore);
  221 
  222         return(rval);
  223 }
  224 
  225 
  226 short
  227 llfindaction(int sym, int term)
  228 {
  229         register int    index;
  230 
  231         IFDEBUG(L)
  232                 printf("llfindaction(sym=%d, term=%d) enter \n", sym, term);
  233         ENDDEBUG
  234         index = llparseindex[sym];
  235 
  236         while(llparsetable[index].llterm != 0) {
  237                 if(llparsetable[index].llterm == term) {
  238                         return(llparsetable[index].llprod);
  239                 }
  240                 index++;
  241         }
  242         return(0);
  243 }
  244 
  245 void
  246 llparsererror(LLtoken *token)
  247 {
  248         IFDEBUG(L)
  249                 fprintf(stderr,"llparsererror() enter\n");
  250                 prt_token(token);
  251         ENDDEBUG
  252 
  253         fprintf(stderr, "Syntax error: ");
  254         prt_token(token);
  255         dump_buffer();
  256         Exit(-1);
  257 }
  258 
  259 void
  260 llgettoken(LLtoken *token)
  261 {
  262         llscan(token);
  263         token->llstate = NORMAL;
  264         IFDEBUG(L)
  265                 printf("llgettoken(): ");
  266                 prt_token(token);
  267         ENDDEBUG
  268 }
  269 
  270 
  271 /******************************************************************************
  272 
  273         Attribute support routines
  274 
  275 ******************************************************************************/
  276 /*
  277 **      attribute stack
  278 **
  279 **      AttrStack =     stack of record
  280 **                              values : array of values;
  281 **                              ptr     : index;
  282 **      end;
  283 **
  284 */
  285 
  286 LLattrib        llattributes[LLMAXATTR];
  287 int             llattrtop = 0;
  288 
  289 struct llattr   llattrdesc[LLMAXDESC];
  290 
  291 int     lldescindex = 1;
  292 
  293 void
  294 llsetattr(int n)
  295 {
  296         register struct llattr *ptr;
  297 
  298         IFDEBUG(L)
  299                 printf("llsetattr(%d) enter\n",n);
  300         ENDDEBUG
  301         if(lldescindex >= LLMAXDESC) {
  302                 fprintf(stdout, "llattribute stack overflow: desc\n");
  303                 fprintf(stdout,
  304                         "lldescindex=0x%x, llattrtop=0x%x\n",lldescindex, llattrtop);
  305                 Exit(-1);
  306         }
  307         ptr = &llattrdesc[lldescindex];
  308         ptr->llabase = &llattributes[llattrtop];
  309         ptr->lloldtop = ++llattrtop;
  310         ptr->llaindex = 1;
  311         ptr->llacnt = n+1; /* the lhs ALWAYS uses an attr; it remains on the
  312                                                 stack when the production is recognized */
  313         lldescindex++;
  314 }
  315 
  316 void
  317 llpushattr(LLattrib attr)
  318 {
  319         struct llattr *a;
  320 
  321         IFDEBUG(L)
  322                 printf("llpushattr() enter\n");
  323         ENDDEBUG
  324         if(llattrtop + 1 > LLMAXATTR) {
  325                 fprintf(stderr, "ATTRIBUTE STACK OVERFLOW!\n");
  326                 Exit(-1);
  327         }
  328         a = &llattrdesc[lldescindex-1];
  329         llattributes[llattrtop++] = attr;
  330         a->llaindex++; /* inc count of attrs on the stack for this prod */
  331 }
  332 
  333 void
  334 llfinprod(void)
  335 {
  336         IFDEBUG(L)
  337                 printf("llfinprod() enter\n");
  338         ENDDEBUG
  339         lldescindex--;
  340         llattrtop = llattrdesc[lldescindex].lloldtop;
  341         llattrdesc[lldescindex-1].llaindex++; /* lhs-of-prod.attr stays on
  342                 the stack; it is now one of the rhs attrs of the now-top production
  343                 on the stack */
  344 }
  345 
  346 #ifndef LINT
  347 #ifdef DEBUG
  348 void
  349 dump_parse_stack(void)
  350 {
  351         int ind;
  352 
  353         printf("PARSE STACK:\n");
  354         for(ind=llstackptr; ind>=0; ind--) {
  355                 printf("%d\t%d\t%s\n",
  356                 ind, llparsestack[ind],
  357                 llparsestack[ind]<0? "Action symbol" : llstrings[llparsestack[ind]]);
  358         }
  359 }
  360 
  361 #endif /* DEBUG */
  362 #endif /* !LINT */
  363 
  364 void
  365 prt_token(LLtoken *t)
  366 {
  367         fprintf(stdout, "t at %p\n", t);
  368         fprintf(stdout, "t->llterm=0x%x\n", t->llterm); (void) fflush(stdout);
  369         fprintf(stdout, "TOK: %s\n", llstrings[t->llterm]);
  370         (void) fflush(stdout);
  371 #ifdef LINT
  372         /* to make lint shut up */
  373         fprintf(stdout, "", llnterms, llnsyms, llnprods, llinfinite);
  374 #endif /* LINT */
  375 }

Cache object: d03edfbd24a2e7cb296b56b5298ea8e3


[ 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.