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-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.7 2002/05/16 19:30:41 wiz 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.7 2002/05/16 19:30:41 wiz 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 {
  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(sym, 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(token)
  247 LLtoken *token;
  248 {
  249         IFDEBUG(L)
  250                 fprintf(stderr,"llparsererror() enter\n");
  251                 prt_token(token);
  252         ENDDEBUG
  253 
  254         fprintf(stderr, "Syntax error: ");
  255         prt_token(token);
  256         dump_buffer();
  257         Exit(-1);
  258 }
  259 
  260 void
  261 llgettoken(token)
  262         LLtoken *token;
  263 {
  264         llscan(token);
  265         token->llstate = NORMAL;
  266         IFDEBUG(L)
  267                 printf("llgettoken(): ");
  268                 prt_token(token);
  269         ENDDEBUG
  270 }
  271 
  272 
  273 /******************************************************************************
  274 
  275         Attribute support routines
  276 
  277 ******************************************************************************/
  278 /*
  279 **      attribute stack
  280 **
  281 **      AttrStack =     stack of record
  282 **                              values : array of values;
  283 **                              ptr     : index;
  284 **      end;
  285 **
  286 */
  287 
  288 LLattrib        llattributes[LLMAXATTR];
  289 int             llattrtop = 0;
  290 
  291 struct llattr   llattrdesc[LLMAXDESC];
  292 
  293 int     lldescindex = 1;
  294 
  295 void
  296 llsetattr(n)
  297         int n;
  298 {
  299         register struct llattr *ptr;
  300 
  301         IFDEBUG(L)
  302                 printf("llsetattr(%d) enter\n",n);
  303         ENDDEBUG
  304         if(lldescindex >= LLMAXDESC) {
  305                 fprintf(stdout, "llattribute stack overflow: desc\n");
  306                 fprintf(stdout, 
  307                         "lldescindex=0x%x, llattrtop=0x%x\n",lldescindex, llattrtop);
  308                 Exit(-1);
  309         }
  310         ptr = &llattrdesc[lldescindex];
  311         ptr->llabase = &llattributes[llattrtop];
  312         ptr->lloldtop = ++llattrtop; 
  313         ptr->llaindex = 1;
  314         ptr->llacnt = n+1; /* the lhs ALWAYS uses an attr; it remains on the
  315                                                 stack when the production is recognized */
  316         lldescindex++;
  317 }
  318 
  319 void
  320 llpushattr(attr)
  321         LLattrib attr;
  322 {
  323         struct llattr *a;
  324 
  325         IFDEBUG(L)
  326                 printf("llpushattr() enter\n");
  327         ENDDEBUG
  328         if(llattrtop + 1 > LLMAXATTR) {
  329                 fprintf(stderr, "ATTRIBUTE STACK OVERFLOW!\n");
  330                 Exit(-1);
  331         }
  332         a = &llattrdesc[lldescindex-1];
  333         llattributes[llattrtop++] = attr;
  334         a->llaindex++; /* inc count of attrs on the stack for this prod */
  335 }
  336 
  337 void
  338 llfinprod()
  339 {
  340         IFDEBUG(L)
  341                 printf("llfinprod() enter\n");
  342         ENDDEBUG
  343         lldescindex--;
  344         llattrtop = llattrdesc[lldescindex].lloldtop;
  345         llattrdesc[lldescindex-1].llaindex++; /* lhs-of-prod.attr stays on
  346                 the stack; it is now one of the rhs attrs of the now-top production
  347                 on the stack */
  348 }
  349 
  350 #ifndef LINT
  351 #ifdef DEBUG
  352 void
  353 dump_parse_stack()
  354 {
  355         int ind;
  356 
  357         printf("PARSE STACK:\n");
  358         for(ind=llstackptr; ind>=0; ind--) {
  359                 printf("%d\t%d\t%s\n",
  360                 ind, llparsestack[ind],
  361                 llparsestack[ind]<0? "Action symbol" : llstrings[llparsestack[ind]]);
  362         }
  363 }
  364 
  365 #endif /* DEBUG */
  366 #endif /* !LINT */
  367 
  368 void
  369 prt_token(t)
  370         LLtoken *t;
  371 {
  372         fprintf(stdout, "t at 0x%p\n", t);
  373         fprintf(stdout, "t->llterm=0x%x\n", t->llterm); (void) fflush(stdout);
  374         fprintf(stdout, "TOK: %s\n", llstrings[t->llterm]);
  375         (void) fflush(stdout);
  376 #ifdef LINT
  377         /* to make lint shut up */
  378         fprintf(stdout, "", llnterms, llnsyms, llnprods, llinfinite);
  379 #endif /* LINT */
  380 }

Cache object: bd3821d48e9ceddbac66302cc3190368


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