sys/netiso/xebec/llparse.c

   1 /*      $NetBSD: llparse.c,v 1.13 2009/03/14 15:36:24 dsl 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.13 2009/03/14 15:36:24 dsl 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 }