util/LLgen/src/gencode.c

   1 /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
   2  * For full copyright and restrictions on use see the file COPYING in the top
   3  * level of the LLgen tree.
   4  */
   5
   6 /*
   7  *  L L G E N
   8  *
   9  *  An Extended LL(1) Parser Generator
  10  *
  11  *  Author : Ceriel J.H. Jacobs
  12  */
  13
  14 /*
  15  * gencode.c
  16  * Defines the routine "gencode", which generates the parser
  17  * we wanted so badly.
  18  * This file is a mess, it should be cleaned up some time.
  19  */
  20
  21 # include "types.h"
  22 # include "io.h"
  23 # include "extern.h"
  24 # include "sets.h"
  25 # include "assert.h"
  26 # include "cclass.h"
  27
  28 # ifndef NORCSID
  29 static string rcsid3 = "$Id: gencode.c,v 2.45 2002/04/04 12:33:15 ceriel Exp $";
  30 #endif /* NORCSID */
  31
  32 /*
  33  * Some codestrings used more than once
  34  */
  35
  36 static string   c_arrend =      "0 };\n";
  37 static string   c_close =       "}\n";
  38 static string   c_break =       "break;\n";
  39 static string   c_read =        "LLread();\n";
  40
  41 /* Some constants used for reading from the action file */
  42 # define ENDDECL        0400
  43 # define IDENT          0401
  44
  45 static int nlabel;              /* count for the generation of labels */
  46 static int firsts;              /* are there any? */
  47 static int listcount;
  48
  49 /* In this file the following routines are defined: */
  50 extern          gencode();
  51 STATIC          opentemp();
  52 STATIC          geninclude();
  53 STATIC          genrecovery();
  54 #ifdef NON_CORRECTING
  55 STATIC          genncrecovery();
  56 #endif
  57 STATIC string   genname();
  58 STATIC          generate();
  59 STATIC          prset();
  60 STATIC          macro();
  61 STATIC          controlline();
  62 STATIC          getparams();
  63 STATIC          getansiparams();
  64 STATIC          genprototypes();
  65 STATIC          gettok();
  66 STATIC          rulecode();
  67 STATIC int *    dopush();
  68 STATIC int *    mk_tokenlist();
  69 STATIC          getaction();
  70 STATIC          alternation();
  71 STATIC          codeforterm();
  72 STATIC          genswhead();
  73 STATIC          gencases();
  74 STATIC          genpush();
  75 STATIC          genpop();
  76 STATIC          genincrdecr();
  77 STATIC          add_cases();
  78 STATIC int      analyze_switch();
  79 STATIC          out_list();
  80 STATIC          genextname();
  81 STATIC          correct_prefix();
  82
  83 # define NOPOP          -20000
  84
  85 p_mem alloc(), ralloc();
  86
  87 doclose(f)
  88         FILE *f;
  89 {
  90         if (ferror(f) != 0) {
  91                 fatal(0,"Write error on temporary");
  92         }
  93         fclose(f);
  94 }
  95
  96 STATIC int *
  97 mk_tokenlist()
  98 {
  99         register int i = ntokens;
 100         register int *p = (int *)alloc((unsigned)(i * sizeof(int))) + i;
 101
 102         while (i--) *--p = -1;
 103
 104         return p;
 105 }
 106
 107 STATIC
 108 genhdr()
 109 {
 110         if (!firsts) fputs("#define LLNOFIRSTS\n", fpars);
 111         if (ansi_c) fputs("#define LL_ANSI_C 1\n", fpars);
 112         else {
 113                 fputs("#if __STDC__ || __cplusplus\n#define LL_ANSI_C 1\n#endif\n", fpars);
 114         }
 115 #ifdef NON_CORRECTING
 116         if (non_corr) fputs("#define LL_NON_CORR 1\n", fpars);
 117 #endif
 118         fprintf(fpars, "#define LL_LEXI %s\n", lexical);
 119         copyfile(incl_file);
 120 }
 121
 122 gencode(argc) {
 123         register p_file p = files;
 124
 125         /* Set up for code generation */
 126         if ((fact = fopen(f_temp,"r")) == NULL) {
 127                 fatal(0,e_noopen,f_temp);
 128         }
 129
 130 #ifdef NON_CORRECTING
 131         /* The non-correcting error recovery must be generated BEFORE
 132            parser code is generated!!!! In case of conflict resolvers,
 133            the code-generation process will delete conflicting symbols
 134            from first and followsets, making them UNUSABLE for the
 135            non-correcting error recovery code.
 136          */
 137         if (non_corr)
 138             genncrecovery();
 139 #endif
 140         /* For every source file .... */
 141         while (argc--) {
 142                 /* Open temporary */
 143                 f_input = p->f_name;
 144                 opentemp(f_input);
 145                 correct_prefix();
 146                 /* generate code ... */
 147                 generate(p);
 148                 getaction(2);
 149                 doclose(fpars);
 150                 /* And install */
 151                 install(genname(p->f_name),p->f_name);
 152                 p++;
 153         }
 154         geninclude();
 155         genrecovery();
 156
 157         fclose(fact);
 158 }
 159
 160 STATIC
 161 opentemp(str) string str; {
 162
 163         if ((fpars = fopen(f_pars,"w")) == NULL) {
 164                 fatal(0,e_noopen,f_pars);
 165         }
 166         if (!str) str = ".";
 167         fprintf(fpars,LLgenid,str);
 168 }
 169
 170 STATIC
 171 geninclude() {
 172         register p_token p;
 173         int maxno = 0;
 174
 175         opentemp((string) 0);
 176         for (p = tokens; p < maxt; p++) {
 177                 if (p->t_tokno > maxno) maxno = p->t_tokno;
 178                 if (p->t_tokno >= 0400) {
 179                         fprintf(fpars,"#define %s %d\n",
 180                                   p->t_string,
 181                                   p->t_tokno);
 182                 }
 183         }
 184         fprintf(fpars, "#define %s_MAXTOKNO %d\n", prefix ? prefix : "LL",
 185                 maxno);
 186 #ifdef NON_CORRECTING
 187         if (non_corr) {
 188                 fprintf(fpars, "#define %sNONCORR\n", prefix ? prefix : "LL");
 189         }
 190 #endif
 191         doclose(fpars);
 192         install(f_include, ".");
 193 }
 194
 195 STATIC
 196 genrecovery() {
 197         register FILE   *f;
 198         register p_token t;
 199         register int    *q;
 200         register p_nont p;
 201         register p_set  *psetl;
 202         int             *index;
 203         int             i;
 204         register p_start st;
 205
 206         opentemp((string) 0);
 207         f = fpars;
 208         correct_prefix();
 209         genhdr();
 210         for (st = start; st; st = st->ff_next) {
 211                 /* Make sure that every set the parser needs is in the list
 212                  * before generating a define of the number of them!
 213                  */
 214                 p = &nonterms[st->ff_nont];
 215                 if (g_gettype(p->n_rule) == ALTERNATION) {
 216                         findindex(p->n_contains);
 217                 }
 218         }
 219         i = maxptr - setptr;
 220         fprintf(f,
 221 "#define LL_SSIZE %d\n#define LL_NSETS %d\n#define LL_NTERMINALS %d\n",
 222                   nbytes,
 223                   i > 0 ? i : 1,
 224                   ntokens);
 225         if (onerror) fprintf(f,"#define LL_USERHOOK %s\n", onerror);
 226 #ifdef NON_CORRECTING
 227         if (non_corr) {
 228             fputs("static int nc_done = 0;\n", f);
 229             fputs("static int err_seen = 0;\n", f);
 230         }
 231 #endif
 232         /* Now generate the routines that call the startsymbols */
 233         fputs("#if LL_ANSI_C\n", f);
 234         for (st = start; st; st = st->ff_next) {
 235                 p = &nonterms[st->ff_nont];
 236                 fputs("void ", f);
 237                 genextname(st->ff_nont, p->n_name, f);
 238                 fputs("(void);\n", f);
 239         }
 240         fputs("#endif\n", f);
 241         for (st = start; st; st = st->ff_next) {
 242                 fprintf(f, "#if LL_ANSI_C\nvoid %s(void)\n#else\n%s()\n#endif\n", st->ff_name, st->ff_name);
 243                 p = &nonterms[st->ff_nont];
 244                 fputs(" {\n\tunsigned int s[LL_NTERMINALS+LL_NSETS+2];", f);
 245 #ifdef NON_CORRECTING
 246                 if (non_corr) {
 247                     fputs(" \n\tint oldstartsymb;", f);
 248                     fputs(" \n\tint oldncflag;", f);
 249                     fputs(" \n\toldstartsymb = LLstartsymb;", f);
 250                     fputs(" \n\toldncflag = nc_done;", f);
 251                     fputs(" \n\tnc_done = 0;", f);
 252                     fprintf(f, "\n\tLLstartsymb = %d;", st->ff_nont + assval);
 253                 }
 254 #endif
 255                 fputs("\n\tLLnewlevel(s);\n\tLLread();\n", f);
 256                 if (g_gettype(p->n_rule) == ALTERNATION) {
 257                         genpush(findindex(p->n_contains));
 258                 }
 259                 genextname(st->ff_nont, p->n_name, f);
 260                 fputs("();\n", f);
 261                 if (getntout(p) == NOSCANDONE) {
 262                         fputs("\tLL_NOSCANDONE(EOFILE);\n",f);
 263                 }
 264                 else    fputs("\tLL_SCANDONE(EOFILE);\n",f);
 265                 fputs("\tLLoldlevel(s);\n",f);
 266 #ifdef NON_CORRECTING
 267                 if (non_corr) {
 268                     fputs("\tLLstartsymb = oldstartsymb;\n", f);
 269                     fputs("\tif (nc_done == 1) { \n", f);
 270                     fputs("\t\terr_seen = 1;\n", f);
 271                     fputs("\tnc_done = oldncflag;\n", f);
 272                     fputs("\t}\n", f);
 273                 }
 274 #endif
 275                 fputs("}\n", f);
 276
 277         }
 278         /* Now generate the sets */
 279         fputs("static char LLsets[] = {\n",f);
 280         for (psetl = setptr; psetl < maxptr; psetl++) prset(*psetl);
 281         fputs(c_arrend, f);
 282         index = (int *) alloc((unsigned) (assval * sizeof(int)));
 283         for (q = index; q < &index[assval];) *q++ = -1;
 284         for (t = tokens; t < maxt; t++) {
 285                 index[t->t_tokno] = t - tokens;
 286         }
 287         fputs("#define LLindex (LL_index+1)\nstatic short LL_index[] = {0,0,\n",f);
 288         for (q = index+1; q < &index[assval]; q++) {
 289                 fprintf(f, "%d,\n", *q);
 290         }
 291         fputs(c_arrend, f);
 292         free((p_mem) index);
 293         if (onerror) {
 294                 fputs("static short LLtok[] = {\n", f);
 295                 for (t = tokens; t < maxt; t++) {
 296                         fprintf(f, t->t_tokno<0400 ? "'%s',\n" : "%s,\n",t->t_string);
 297                 }
 298                 fputs(c_arrend, f);
 299         }
 300         fputs("#define LL_NEWMESS\n", f);
 301         copyfile(rec_file);
 302         doclose(f);
 303         install(f_rec, ".");
 304 }
 305
 306 #ifdef NON_CORRECTING
 307 STATIC
 308 genncrecovery() {
 309     register FILE    *f;
 310     register p_token  t;
 311     register int     *q;
 312     int              *index;
 313
 314     /* Generate the non-correcting error recovery file */
 315
 316     opentemp((string) 0);
 317     f = fpars;
 318
 319     genhdr();
 320     correct_prefix();
 321     save_grammar(f);
 322
 323     fprintf(f, "#define LLFIRST_NT %d\n", assval);
 324     fprintf(f, "#define LLSETSIZE %d\n", nbytes);
 325
 326     index = (int *) alloc((unsigned) (assval * sizeof(int)));
 327     for (q = index; q < &index[assval];) *q++ = -1;
 328     for (t = tokens; t < maxt; t++) {
 329         index[t->t_tokno] = t - tokens;
 330     }
 331     fputs("#define LLindex (LL_index+1)\nstatic short LL_index[] = {0,0,\n",f);
 332     for (q = index+1; q < &index[assval]; q++) {
 333         fprintf(f, "%d,\n", *q);
 334     }
 335     fputs(c_arrend, f);
 336     free((p_mem) index);
 337
 338     copyfile(nc_incl_file);
 339     copyfile(nc_rec_file);
 340
 341     doclose(f);
 342     install(f_nc, ".");
 343 }
 344 #endif
 345
 346 STATIC
 347 generate(f) p_file f; {
 348         /*
 349          * Generates a parsing routine for every nonterminal
 350          */
 351         register int s;
 352         register p_nont p;
 353         int i;
 354         register p_first ff;
 355         int mustpop;
 356         int is_first = 1;
 357
 358         fprintf(fpars, "#define LL_LEXI %s\n", lexical);
 359         listcount = 0;
 360         /* Generate first sets */
 361         for (ff = f->f_firsts; ff; ff = ff->ff_next) {
 362                 macro(ff->ff_name,&nonterms[ff->ff_nont]);
 363         }
 364
 365         genhdr();
 366
 367         /* For every nonterminal generate a function */
 368         for (s = f->f_nonterminals; s != -1; s = p->n_next) {
 369                 p = &nonterms[s];
 370                 /* Generate functions in the order in which the nonterminals
 371                  * were defined in the grammar. This is important, because
 372                  * of synchronisation with the action file
 373                  */
 374                 while (p->n_count--) getaction(1);
 375                 if (g_gettype(p->n_rule) == EORULE &&
 376                     getntparams(p) == 0) {
 377                         continue;
 378                 }
 379                 if (is_first) genprototypes(f);
 380                 is_first = 0;
 381                 if (p->n_flags & GENSTATIC) fputs("static\n", fpars);
 382                 fputs("#if LL_ANSI_C\nvoid\n#endif\n", fpars);
 383                 genextname(s, p->n_name, fpars);
 384                 if (p->n_flags & PARAMS) {
 385                         long off = ftell(fact);
 386                         fputs("(\n#if LL_ANSI_C\n", fpars);
 387                         controlline();
 388                         getansiparams(1);
 389                         fseek(fact, off, 0);
 390                         fputs("#else\n", fpars);
 391                         controlline();
 392                         getparams();
 393                         fputs("#endif\n{\n", fpars);
 394                 }
 395                 else fputs("(\n#if LL_ANSI_C\nvoid\n#endif\n) {\n", fpars);
 396                 if (p->n_flags & LOCALS) getaction(1);
 397                 i = getntsafe(p);
 398                 mustpop = NOPOP;
 399                 if (g_gettype(p->n_rule) == ALTERNATION &&
 400                     i > SAFESCANDONE) {
 401                         mustpop = findindex(p->n_contains);
 402                         if (i == NOSCANDONE) {
 403                                 fputs(c_read, fpars);
 404                                 i = SCANDONE;
 405                         }
 406                 }
 407                 nlabel = 1;
 408                 rulecode(p->n_rule,
 409                          i,
 410                          getntout(p) != NOSCANDONE,
 411                          mustpop);
 412                 fputs(c_close, fpars);
 413         }
 414 }
 415
 416 STATIC
 417 prset(p) p_set p; {
 418         register int k;
 419         register unsigned i;
 420         int j;
 421
 422         j = nbytes;
 423         for (;;) {
 424                 i = (unsigned) *p++;
 425                 for (k = 0; k < sizeof(int); k++) {
 426                         fprintf(fpars,"'\\%o',",(int)(i & 0377));
 427                         i >>= 8;
 428                         if (--j == 0) {
 429                                 fputs("\n",fpars);
 430                                 return;
 431                         }
 432                 }
 433         }
 434         /* NOTREACHED */
 435 }
 436
 437 STATIC
 438 macro(s,n) string s; p_nont n; {
 439         int i;
 440
 441         i = findindex(n->n_first);
 442         if (i < 0) {
 443                 fprintf(fpars, "#define %s(x) ((x) == %d)\n",
 444                         s,
 445                         tokens[-(i+1)].t_tokno);
 446                 return;
 447         }
 448         firsts = 1;
 449         fprintf(fpars,"#define %s(x) LLfirst((x), %d)\n", s, i);
 450 }
 451
 452 STATIC
 453 controlline() {
 454         /* Copy a compiler control line */
 455         register int l;
 456         register FILE *f1,*f2;
 457
 458         f1 = fact; f2 = fpars;
 459         l = getc(f1);
 460         assert(l == '\0');
 461         do {
 462                 l = getc(f1);
 463                 if (l == EOF) fatal(0, "temp file mangled");
 464                 putc(l,f2);
 465         } while ( l != '\n' ) ;
 466 }
 467
 468 STATIC
 469 getparams() {
 470         /* getparams is called if a nonterminal has parameters. The names
 471          * of the parameters have to be found, and they should be declared
 472          */
 473         long off;
 474         register int l;
 475         long ftell();
 476         char first;
 477         char add_semi = ' ';
 478
 479         first = ' ';
 480         /* save offset in file to be able to copy the declaration later */
 481         off = ftell(fact);
 482         /* First pass through declaration, find the parameter names */
 483         ltext[0] = '\0';
 484         while ((l = gettok()) != ENDDECL) {
 485                 if ((l == ';' || l == ',') && ltext[0] != '\0') {
 486                         /*
 487                          * The last identifier found before a ';' or a ','
 488                          * must be a parameter
 489                          */
 490                         fprintf(fpars,"%c%s", first, ltext);
 491                         first = ',';
 492                         ltext[0] = '\0';
 493                 }
 494         }
 495         if (ltext[0] != '\0') {
 496                 fprintf(fpars, "%c%s", first, ltext);
 497                 add_semi = ';';
 498         }
 499         fputs(") ",fpars);
 500         /*
 501          * Now copy the declarations
 502          */
 503         l = getc(fact);         /* patch: some implementations of fseek
 504                                    do not work properly after "ungetc"
 505                                 */
 506         fseek(fact,off,0);
 507         getaction(0);
 508         fprintf(fpars, "%c\n",add_semi);
 509 }
 510
 511 STATIC
 512 genprototypes(f)
 513         register p_file f;
 514 {
 515         /*
 516          * Generate prototypes for all nonterminals
 517          */
 518         register int i;
 519         register p_nont p;
 520         long    off = ftell(fact);
 521
 522         fputs("#if LL_ANSI_C\n", fpars);
 523         for (i = 0; i < nnonterms; i++) {
 524                 if (! IN(f->f_used, i)) continue;
 525                 p = &nonterms[i];
 526                 if (g_gettype(p->n_rule) == EORULE &&
 527                     getntparams(p) == 0) {
 528                         continue;
 529                 }
 530                 if (p->n_flags & GENSTATIC) fputs("static ", fpars);
 531                 fputs("void ", fpars);
 532                 genextname(i, p->n_name, fpars);
 533                 if (p->n_flags & PARAMS) {
 534                         fputs("(\n", fpars);
 535                         fseek(fact, p->n_off, 0);
 536                         controlline();
 537                         getansiparams(0);
 538                 }
 539                 else fputs("(void);\n", fpars);
 540         }
 541         fseek(fact, off, 0);
 542         fputs("#else\n", fpars);
 543         for (i = 0; i < nnonterms; i++) {
 544                 if (! IN(f->f_used, i)) continue;
 545                 p = &nonterms[i];
 546                 if (!(p->n_flags & GENSTATIC)) continue;
 547                 if (g_gettype(p->n_rule) == EORULE &&
 548                     getntparams(p) == 0) {
 549                         continue;
 550                 }
 551                 fputs("static ", fpars);
 552                 genextname(i, p->n_name, fpars);
 553                 fputs("();\n", fpars);
 554         }
 555         fputs("#endif\n", fpars);
 556 }
 557
 558 STATIC
 559 getansiparams(mkdef) {
 560         /* getansiparams is called if a nonterminal has parameters
 561          * and an ANSI C function definition/declaration has to be produced.
 562          * If a definition has to be produced, "mkdef" is set to 1.
 563          */
 564         register int l;
 565         int delayed = 0;
 566
 567         ltext[0] = '\0';
 568         while ((l = gettok()) != ENDDECL) {
 569                 if (l > 0177 || c_class[l] != ISSPA) {
 570                         if (delayed) {
 571                                 fputc(',', fpars);
 572                                 delayed = 0;
 573                         }
 574                 }
 575                 if ((l == ';' || l == ',') && ltext[0] != '\0') {
 576                         /*
 577                          * The last identifier found before a ';' or a ','
 578                          * must be a parameter
 579                          */
 580                         delayed = 1;
 581                         ltext[0] = '\0';
 582                 }
 583                 else if (l == IDENT) fprintf(fpars, "%s", ltext);
 584                 else fputc(l, fpars);
 585         }
 586         fprintf(fpars, ") %c\n", mkdef ? ' ' : ';');
 587 }
 588
 589 STATIC
 590 gettok() {
 591         /* Read from the action file. */
 592         register int ch;
 593         register string c;
 594         register FILE *f;
 595
 596         f = fact;
 597         ch = getc(f);
 598         switch(ch) {
 599                 case '\n':
 600                         ch = getc(f);
 601                         if (ch != EOF) {
 602                                 ungetc(ch,f);
 603                                 if (ch != '\0') return '\n';
 604                         }
 605                         return ENDDECL;
 606                 case '\0':
 607                         ungetc(ch,f);
 608                         /* Fall through */
 609                 case EOF :
 610                         return ENDDECL;
 611                 default :
 612                         if (c_class[ch] == ISLET) {
 613                                 c = ltext;
 614                                 do {
 615                                         *c++ = ch;
 616                                         if (c-ltext >= LTEXTSZ) --c;
 617                                         ch = getc(f);
 618                                 } while (c_class[ch] == ISLET || c_class[ch] == ISDIG);
 619                                 if (ch != EOF) ungetc(ch,f);
 620                                 *c = '\0';
 621                                 return IDENT;
 622                         }
 623                         return ch;
 624         }
 625 }
 626
 627 STATIC
 628 rulecode(p,safety,mustscan,mustpop) register p_gram p; {
 629         /*
 630          * Code for a production rule.
 631          */
 632
 633         register int    toplevel = 1;
 634         register FILE   *f;
 635         register int    *ppu;
 636         int             *pushlist;
 637         int             *ppushlist;
 638
 639         /*
 640          * First generate code to push the contains sets of this rule
 641          * on a stack
 642          */
 643         ppushlist = dopush(p,safety,1, &pushlist);
 644         if (mustpop != NOPOP) for (ppu = pushlist; ppu < ppushlist; ppu++) {
 645                 if (*ppu == mustpop) {
 646                         *ppu = mustpop = NOPOP;
 647                         break;
 648                 }
 649         }
 650         if (g_gettype(p) != ALTERNATION) {
 651                 genpop(mustpop);
 652                 mustpop = NOPOP;
 653         }
 654         for (ppu = pushlist; ppu < ppushlist; ppu++) genpush(*ppu);
 655         free((p_mem) pushlist);
 656         f = fpars;
 657         for (;;) {
 658                 switch (g_gettype(p)) {
 659                   case EORULE :
 660                         if (mustscan && safety == NOSCANDONE) {
 661                                 fputs(c_read,f);
 662                         }
 663                         return;
 664                   case LITERAL :
 665                   case TERMINAL : {
 666                         register p_token t;
 667                         string s;
 668
 669                         t = &tokens[g_getcont(p)];
 670                         if (toplevel == 0) {
 671                                 fprintf(f,"LLtdecr(%d);\n", g_getcont(p));
 672                         }
 673                         if (safety == SAFE) {
 674                                 fputs("LL_SAFE(",f);
 675                         }
 676                         else if (safety == SAFESCANDONE) {
 677                                 fputs("LL_SSCANDONE(",f);
 678                         }
 679                         else if (safety == SCANDONE) {
 680                                 fputs("LL_SCANDONE(",f);
 681                         }
 682                         else /* if (safety == NOSCANDONE) */ {
 683                                 fputs("LL_NOSCANDONE(", f);
 684                         }
 685                         if (t->t_tokno < 0400) s = "'%s');\n";
 686                         else    s = "%s);\n";
 687                         fprintf(f,s,t->t_string);
 688                         if (safety <= SAFESCANDONE && toplevel > 0) {
 689                                 safety = NOSCANDONE;
 690                                 toplevel = -1;
 691                                 p++;
 692                                 continue;
 693                         }
 694                         safety = NOSCANDONE;
 695                         break; }
 696                   case NONTERM : {
 697                         register p_nont n = &nonterms[g_getcont(p)];
 698
 699                         if (safety == NOSCANDONE &&
 700                             getntsafe(n) < NOSCANDONE) {
 701                                 safety = getntsafe(n);
 702                                 fputs(c_read, f);
 703                         }
 704                         if (toplevel == 0 &&
 705                             (g_gettype(n->n_rule) != ALTERNATION ||
 706                              getntsafe(n) <= SAFESCANDONE)) {
 707                                 genpop(findindex(n->n_contains));
 708                         }
 709                         genextname(g_getcont(p), n->n_name, f);
 710                         if (g_getnpar(p)) {
 711                                 fputs("(\n", f);
 712                                 controlline();
 713                                 getaction(0);
 714                                 fputs(");\n",f);
 715                         }
 716                         else    fputs("();\n", f);
 717                         safety = getntout(n);
 718                         break; }
 719                   case TERM :
 720                         safety = codeforterm(g_getterm(p),
 721                                                 safety,
 722                                                 toplevel);
 723                         break;
 724                   case ACTION :
 725                         getaction(1);
 726                         p++;
 727                         continue;
 728                   case ALTERNATION :
 729                         alternation(p, safety, mustscan, mustpop, 0);
 730                         return;
 731                 }
 732                 p++;
 733                 toplevel = 0;
 734         }
 735 }
 736
 737 STATIC
 738 alternation(pp, safety, mustscan, mustpop, lb)
 739         p_gram pp;
 740 {
 741         register p_gram p = pp;
 742         register FILE   *f = fpars;
 743         register p_link l;
 744         int             hulp, hulp1,hulp2;
 745         int             haddefault = 0;
 746         int             nsafe;
 747         p_set           set;
 748         p_set           setalloc();
 749         int             *tokenlist = mk_tokenlist();
 750         int             casecnt = 0;
 751         int             compacted;
 752         int             unsafe;
 753
 754         assert(safety < NOSCANDONE);
 755         hulp = nlabel++;
 756         hulp1 = nlabel++;
 757         hulp2 = nlabel++;
 758         if (!lb) lb = hulp1;
 759         unsafe = onerror || safety > SAFESCANDONE;
 760         if (!unsafe) {
 761                 genpop(mustpop);
 762                 mustpop = NOPOP;
 763         }
 764         if (unsafe && hulp1 == lb) {
 765                 fprintf(f,"goto L_%d; /* so that the label is used for certain */\nL_%d: ;\n", hulp1, hulp1);
 766         }
 767         if (safety == SAFE) {
 768                 /* check if we can avoid to generate the switch */
 769                 for (;;) {
 770                         if (g_gettype(p) == EORULE) return;
 771                         l = g_getlink(p);
 772                         if (l->l_flag & COND) break;
 773                         if ((g_gettype(l->l_rule) != TERMINAL &&
 774                              g_gettype(l->l_rule) != LITERAL) ||
 775                             g_gettype(l->l_rule+1) != EORULE) break;
 776                         p++;
 777                 }
 778                 p = pp;
 779         }
 780         while (g_gettype(p) != EORULE) {
 781                 set = 0;
 782                 l = g_getlink(p);
 783                 if (l->l_flag & COND) {
 784                         if (!(l->l_flag & NOCONF)) {
 785                                 set = setalloc();
 786                                 setunion(set, l->l_others);
 787                                 setintersect(set, l->l_symbs);
 788                                 setminus(l->l_symbs, set);
 789                                 setminus(l->l_others, set);
 790                                 add_cases(set, tokenlist, casecnt++);
 791                         }
 792                 }
 793                 if (!unsafe && (l->l_flag & DEF)) {
 794                         haddefault = 1;
 795                 }
 796                 else    add_cases(l->l_symbs, tokenlist, casecnt++);
 797                 if (l->l_flag & DEF) {
 798                         haddefault = 1;
 799                 }
 800                 if ((l->l_flag & COND) && !(l->l_flag & NOCONF)) {
 801                         p++;
 802                         if (g_gettype(p+1) == EORULE) {
 803                                 setminus(g_getlink(p)->l_symbs, set);
 804                                 free((p_mem) set);
 805                                 continue;
 806                         }
 807                         free((p_mem) set);
 808                         if (!haddefault) {
 809                         }
 810                         else {
 811                                 add_cases(l->l_others, tokenlist, casecnt++);
 812                                 unsafe = 0;
 813                         }
 814                         break;
 815                 }
 816                 p++;
 817         }
 818
 819         unsafe = onerror || safety > SAFESCANDONE;
 820         p = pp;
 821         haddefault = 0;
 822         compacted = analyze_switch(tokenlist);
 823         if (compacted) {
 824                 fputs("{", f);
 825                 out_list(tokenlist, listcount++, casecnt);
 826         }
 827         else    fputs("switch(LLcsymb) {\n", f);
 828         casecnt = 0;
 829
 830         while (g_gettype(p) != EORULE) {
 831                 l = g_getlink(p);
 832                 if (l->l_flag & COND) {
 833                         if (l->l_flag & NOCONF) {
 834                                 fputs("#ifdef ___NOCONFLICT___\n", f);
 835                         }
 836                         else gencases(tokenlist, casecnt++, compacted);
 837                         controlline();
 838                         fputs("if (!",f);
 839                         getaction(0);
 840                         fprintf(f,") goto L_%d;\n", hulp);
 841                         if (l->l_flag & NOCONF) {
 842                                 fputs("#endif\n", f);
 843                         }
 844                 }
 845                 if (!unsafe && (l->l_flag & DEF)) {
 846                         haddefault = 1;
 847                         fputs("default:\n", f);
 848                 }
 849                 else    gencases(tokenlist, casecnt++, compacted);
 850                 nsafe = SAFE;
 851                 if (l->l_flag & DEF) {
 852                         if (unsafe) {
 853                                 fprintf(f,"goto L_%d;\nL_%d: ;\n", hulp2, hulp2);
 854                         }
 855                         if (safety != SAFE) nsafe = SAFESCANDONE;
 856                 }
 857                 rulecode(l->l_rule, nsafe, mustscan, mustpop);
 858                 fputs(c_break,f);
 859                 if (unsafe && (l->l_flag & DEF)) {
 860                         haddefault = 1;
 861                         fprintf(f,
 862 "default: if (LLskip()) goto L_%d;\ngoto L_%d;\n",
 863                         lb, hulp2);
 864                 }
 865                 if ((l->l_flag & COND) && !(l->l_flag & NOCONF)) {
 866                         p++;
 867                         fprintf(f,"goto L_%d;\nL_%d : ;\n", hulp, hulp);
 868                         if (g_gettype(p+1) == EORULE) {
 869                                 continue;
 870                         }
 871                         if (!haddefault) {
 872                                 fputs("default:\n", f);
 873                         }
 874                         else {
 875                                 gencases(tokenlist, casecnt++, compacted);
 876                                 safety = SAFE;
 877                                 unsafe = 0;
 878                         }
 879                         if (! unsafe) {
 880                                 genpop(mustpop);
 881                                 mustpop = NOPOP;
 882                         }
 883                         alternation(p,safety,mustscan,mustpop,lb);
 884                         break;
 885                 }
 886                 p++;
 887         }
 888         if (compacted) fputs(c_close, f);
 889         fputs(c_close, f);
 890         free((p_mem) tokenlist);
 891 }
 892
 893 STATIC int *
 894 dopush(p,safety,toplevel,pp) register p_gram p; int **pp; {
 895         /*
 896          * The safety only matters if toplevel != 0
 897          */
 898         unsigned int i = 100;
 899         register int *ip = (int *) alloc(100 * sizeof(int));
 900
 901         *pp = ip;
 902
 903         for (;;) {
 904                 if (ip - *pp >= i) {
 905                         *pp = (int *)
 906                                 ralloc((p_mem) (*pp), (i + 100) * sizeof(int));
 907                         ip = *pp + i;
 908                         i += 100;
 909                 }
 910                 switch(g_gettype(p)) {
 911                   case EORULE :
 912                   case ALTERNATION :
 913                         return ip;
 914                   case TERM : {
 915                         register p_term q;
 916                         int rep_kind, rep_count;
 917
 918                         q = g_getterm(p);
 919                         rep_kind = r_getkind(q);
 920                         rep_count = r_getnum(q);
 921                         if (!(toplevel > 0 && safety <= SAFESCANDONE &&
 922                             (rep_kind == OPT || (rep_kind == FIXED && rep_count == 0)))) {
 923                                 *ip++ = findindex(q->t_contains);
 924                         }
 925                         break; }
 926                   case LITERAL :
 927                   case TERMINAL :
 928                         if (toplevel > 0 && safety <= SAFESCANDONE) {
 929                                 toplevel = -1;
 930                                 p++;
 931                                 safety = NOSCANDONE;
 932                                 continue;
 933                         }
 934                         if (toplevel == 0) *ip++ = -(g_getcont(p)+1);
 935                         break;
 936                   case NONTERM : {
 937                         register p_nont n;
 938
 939                         n = &nonterms[g_getcont(p)];
 940                         if (toplevel == 0 ||
 941                             (g_gettype(n->n_rule) == ALTERNATION &&
 942                              getntsafe(n) > SAFESCANDONE)) {
 943                                 *ip++ = findindex(n->n_contains);
 944                         }
 945                         break; }
 946                   case ACTION :
 947                         p++;
 948                         continue;
 949                 }
 950                 toplevel = 0;
 951                 safety = NOSCANDONE;
 952                 p++;
 953         }
 954 }
 955
 956 # define max(a,b) ((a) < (b) ? (b) : (a))
 957
 958 STATIC
 959 getaction(flag) {
 960         /* Read an action from the action file.
 961          * flag = 1 if it is an action,
 962          * 0 when reading parameters
 963          */
 964         register int ch;
 965         register FILE *f;
 966         int mark = 0;
 967
 968         if (flag == 1) {
 969                 controlline();
 970         }
 971         f = fpars;
 972         for (;;) {
 973                 ch = gettok();
 974                 switch(ch) {
 975                   case ENDDECL:
 976                         if (flag != 2) break;
 977                         ch = getc(fact);
 978                         assert(ch == '\0');
 979                         fputs("\n",f);
 980                         if (mark) return;
 981                         mark = 1;
 982                         continue;
 983                   case IDENT :
 984                         fputs(ltext,f);
 985                         continue;
 986                 }
 987                 mark = 0;
 988                 if (ch == ENDDECL) break;
 989                 putc(ch,f);
 990         }
 991         if (flag) fputs("\n",f);
 992 }
 993
 994 STATIC
 995 codeforterm(q,safety,toplevel) register p_term q; {
 996         /*
 997          * Generate code for a term
 998          */
 999         register FILE   *f = fpars;
1000         register int    rep_count = r_getnum(q);
1001         register int    rep_kind = r_getkind(q);
1002         int             term_is_persistent = (q->t_flags & PERSISTENT);
1003         int             ispushed = NOPOP;
1004
1005         if (!(toplevel > 0 &&
1006               (safety == 0 || (!onerror && safety <= SAFESCANDONE)) &&
1007             (rep_kind == OPT || (rep_kind == FIXED && rep_count == 0)))) {
1008                 ispushed = findindex(q->t_contains);
1009         }
1010         if (safety == NOSCANDONE && (rep_kind != FIXED || rep_count == 0 ||
1011             gettout(q) != NOSCANDONE)) {
1012                 fputs(c_read, f);
1013                 safety = SCANDONE;
1014         }
1015         if (rep_kind == PLUS && !term_is_persistent) {
1016                 int temp;
1017
1018                 temp = findindex(q->t_first);
1019                 if (temp != ispushed) {
1020                         genpop(ispushed);
1021                         ispushed = temp;
1022                         genpush(temp);
1023                 }
1024         }
1025         if (rep_count) {
1026                 /* N > 0, so generate fixed forloop */
1027                 fputs("{\nregister LL_i;\n", f);
1028                 assert(ispushed != NOPOP);
1029                 fprintf(f, "for (LL_i = %d; LL_i >= 0; LL_i--) {\n", rep_count - 1);
1030                 if (rep_kind == FIXED) {
1031                         fputs("if (!LL_i) ", f);
1032                         genpop(ispushed);
1033                         genpush(ispushed);
1034                         if (safety == NOSCANDONE) {
1035                                 assert(gettout(q) == NOSCANDONE);
1036                                 fputs(c_read, f);
1037                         }
1038                 }
1039         }
1040         else if (rep_kind != OPT && rep_kind != FIXED) {
1041                 /* '+' or '*', so generate infinite loop */
1042                 fputs("for (;;) {\n",f);
1043         }
1044         else if (rep_kind == OPT &&
1045                  (safety == 0 || (!onerror && safety <= SAFESCANDONE))) {
1046                 genpop(ispushed);
1047                 ispushed = NOPOP;
1048         }
1049         if (rep_kind == STAR || rep_kind == OPT) {
1050                 genswhead(q, rep_kind, rep_count, safety, ispushed);
1051         }
1052         rulecode(q->t_rule,
1053                  t_safety(rep_kind,rep_count,term_is_persistent,safety),
1054                  gettout(q) != NOSCANDONE,
1055                  rep_kind == FIXED ? ispushed : NOPOP);
1056         if (gettout(q) == NOSCANDONE && rep_kind != FIXED) {
1057                 fputs(c_read, f);
1058         }
1059         /* in the case of '+', the if is after the code for the rule */
1060         if (rep_kind == PLUS) {
1061                 if (rep_count) {
1062                         fputs("if (!LL_i) break;\n", f);
1063                 }
1064                 genswhead(q, rep_kind, rep_count, safety, ispushed);
1065         }
1066         if (rep_kind != OPT && rep_kind != FIXED) fputs("continue;\n", f);
1067         if (rep_kind != FIXED) {
1068                 fputs(c_close, f); /* Close switch */
1069                 fputs(c_close, f);
1070                 if (rep_kind != OPT) {
1071                         genpop(ispushed);
1072                         fputs(c_break, f);
1073                 }
1074         }
1075         if (rep_kind != OPT && (rep_kind != FIXED || rep_count > 0)) {
1076                 fputs(c_close, f);      /* Close for */
1077                 if (rep_count > 0) {
1078                         fputs(c_close, f);/* Close Register ... */
1079                 }
1080         }
1081         return t_after(rep_kind, rep_count, gettout(q));
1082 }
1083
1084 STATIC
1085 genswhead(q, rep_kind, rep_count, safety, ispushed) register p_term q; {
1086         /*
1087          * Generate switch statement for term q
1088          */
1089         register FILE   *f = fpars;
1090         p_set           p1;
1091         p_set           setalloc();
1092         int             hulp1 = 0, hulp2;
1093         int             safeterm;
1094         int             termissafe = 0;
1095         int             casecnt = 0;
1096         int             *tokenlist = mk_tokenlist();
1097         int             compacted;
1098
1099         if (rep_kind == PLUS) safeterm = gettout(q);
1100         else if (rep_kind == OPT) safeterm = safety;
1101         else /* if (rep_kind == STAR) */ safeterm = max(safety, gettout(q));
1102         hulp2 = nlabel++;
1103         fprintf(f, "goto L_%d;\nL_%d : ", hulp2, hulp2);
1104         if (q->t_flags & RESOLVER) {
1105                 hulp1 = nlabel++;
1106                 if (! (q->t_flags & NOCONF)) {
1107                         p1 = setalloc();
1108                         setunion(p1,q->t_first);
1109                         setintersect(p1,q->t_follow);
1110                         /*
1111                          * p1 now points to a set containing the conflicting
1112                          * symbols
1113                          */
1114                         setminus(q->t_first, p1);
1115                         setminus(q->t_follow, p1);
1116                         setminus(q->t_contains, p1);
1117                         add_cases(p1, tokenlist, casecnt++);
1118                         free((p_mem) p1);
1119                 }
1120         }
1121         if (safeterm == 0 || (!onerror && safeterm <= SAFESCANDONE)) {
1122                 termissafe = 1;
1123         }
1124         else    add_cases(q->t_follow, tokenlist, casecnt++);
1125         if (!onerror && (q->t_flags & PERSISTENT) && safeterm != SAFE) {
1126                 add_cases(q->t_contains, tokenlist, casecnt);
1127         }
1128         else    add_cases(q->t_first, tokenlist, casecnt);
1129         compacted = analyze_switch(tokenlist);
1130         fputs("{", f);
1131         if (compacted) {
1132                 out_list(tokenlist, listcount++, casecnt);
1133         }
1134         else    fputs("switch(LLcsymb) {\n", f);
1135         casecnt = 0;
1136         if (q->t_flags & RESOLVER) {
1137                 if (q->t_flags & NOCONF) {
1138                         fputs("#ifdef ___NOCONFLICT___\n", f);
1139                 }
1140                 else gencases(tokenlist, casecnt++, compacted);
1141                 controlline();
1142                 fputs("if (", f);
1143                 getaction(0);
1144                 fprintf(f, ") goto L_%d;\n", hulp1);
1145                 if (q->t_flags & NOCONF) {
1146                         fputs("#endif /* ___NOCONFLICT___ */\n", f);
1147                 }
1148         }
1149         if (safeterm == 0 || (!onerror && safeterm <= SAFESCANDONE)) {
1150                 fputs("default:\n", f);
1151         }
1152         else    gencases(tokenlist, casecnt++, compacted);
1153         if (rep_kind == OPT) genpop(ispushed);
1154         fputs(c_break, f);
1155         if (! termissafe) {
1156                 int i;
1157                 static int nvar;
1158
1159                 assert(ispushed != NOPOP);
1160                 if (ispushed >= 0) i = -ispushed;
1161                 else i = tokens[-(ispushed+1)].t_tokno;
1162                 ++nvar;
1163                 fprintf(f,"default:{int LL_%d=LLnext(%d);\n;if (!LL_%d) {\n",
1164                         nvar, i, nvar);
1165                 if (rep_kind == OPT) genpop(ispushed);
1166                 fputs(c_break, f);
1167                 fputs(c_close, f);
1168                 fprintf(f,"else if (LL_%d & 1) goto L_%d;}\n",nvar, hulp2);
1169         }
1170         gencases(tokenlist, casecnt, compacted);
1171         if (q->t_flags & RESOLVER) {
1172                 fprintf(f, "goto L_%d;\nL_%d : ;\n", hulp1, hulp1);
1173         }
1174         if (rep_kind == OPT) genpop(ispushed);
1175         if (rep_count > 0) {
1176                 assert(ispushed != NOPOP);
1177                 fputs(rep_kind == STAR ? "if (!LL_i) " : "if (LL_i == 1) ", f);
1178                 genpop(ispushed);
1179         }
1180         free((p_mem) tokenlist);
1181 }
1182
1183 STATIC
1184 gencases(tokenlist, caseno, compacted)
1185         int     *tokenlist;
1186 {
1187         /*
1188          * setp points to a bitset indicating which cases must
1189          * be generated.
1190          * YECH, the PCC compiler does not accept many cases without
1191          * statements in between, so after every case label an empty
1192          * statement is generated.
1193          * The C-grammar used by PCC is really stupid on this point :
1194          * it contains the rule
1195          *      statement : label statement
1196          * which is right-recursive, and as is well known, LALR parsers don't
1197          * handle these things very well.
1198          * The grammar should have been written :
1199          *      labeledstatement : labels statement ;
1200          *      labels : labels label | ;
1201          */
1202         register p_token p;
1203         register int i;
1204
1205         if (compacted) fprintf(fpars, "case %d :\n", caseno);
1206         for (i = 0, p = tokens; i < ntokens; i++, p++) {
1207                 if (tokenlist[i] == caseno) {
1208                         fprintf(fpars,
1209                                 compacted ?
1210                                    (p->t_tokno < 0400 ? "/* case '%s' */\n" :
1211                                                         "/* case %s */\n") :
1212                                    p->t_tokno<0400 ? "case /* '%s' */ %d : ;\n"
1213                                                 : "case /*  %s  */ %d : ;\n",
1214                                 p->t_string, i);
1215                 }
1216         }
1217 }
1218
1219 static char namebuf[20];
1220
1221 STATIC string
1222 genname(s) string s; {
1223         /*
1224          * Generate a target file name from the
1225          * source file name s.
1226          */
1227         register string c,d;
1228
1229         c = namebuf;
1230         while (*s) {
1231                 if (*s == '/') {
1232                         while (*s == '/') s++;
1233                         if (*s) c = namebuf;
1234                         else break;
1235                 }
1236                 *c++ = *s++;
1237         }
1238         for (d = c; --d > namebuf;) if (*d == '.') break;
1239         if (d == namebuf) d = c;
1240         if (d >= &namebuf[12]) {
1241                 fatal(0,"%s : filename too long",namebuf);
1242         }
1243         *d++ = '.';
1244         *d++ = 'c';
1245         *d = '\0';
1246         return namebuf;
1247 }
1248
1249 STATIC
1250 genpush(d) {
1251         genincrdecr("incr", d);
1252 }
1253
1254 STATIC
1255 genincrdecr(s, d) string s; {
1256         if (d == NOPOP) return;
1257         if (d >= 0) {
1258                 fprintf(fpars, "LLs%s(%d);\n", s,  d / nbytes);
1259                 return;
1260         }
1261         fprintf(fpars, "LLt%s(%d);\n", s, -(d + 1));
1262 }
1263
1264 STATIC
1265 genpop(d) {
1266         genincrdecr("decr", d);
1267 }
1268
1269 STATIC int
1270 analyze_switch(tokenlist)
1271         int     *tokenlist;
1272 {
1273         register int i;
1274         int ncases = 0;
1275         int percentage;
1276         int maxcase = 0, mincase = 0;
1277
1278         if (! jmptable_option) return 0;
1279         for (i = 0; i < ntokens; i++) {
1280                 if (tokenlist[i] >= 0) {
1281                         ncases++;
1282                         if (! mincase) mincase = i + 1;
1283                         maxcase = i + 1;
1284                 }
1285         }
1286
1287         if (ncases < min_cases_for_jmptable) return 0;
1288         percentage = ncases * 100 / (maxcase - mincase);
1289         fprintf(fpars, "/* percentage is %d */\n", percentage);
1290         return percentage >= low_percentage && percentage <= high_percentage;
1291 }
1292
1293 STATIC
1294 add_cases(s, tokenlist, caseno)
1295         p_set   s;
1296         int     *tokenlist;
1297 {
1298         register int i;
1299
1300         for (i = 0; i < ntokens; i++) {
1301                 if (IN(s, i)) {
1302                         tokenlist[i] = caseno;
1303                 }
1304         }
1305 }
1306
1307 STATIC
1308 out_list(tokenlist, listno, casecnt)
1309         int     *tokenlist;
1310 {
1311         register int i;
1312         register FILE *f = fpars;
1313
1314         fprintf(f, "static %s LL%d_tklist[] = {",
1315                 casecnt <= 127 ? "char" : "short",
1316                 listno);
1317
1318         for (i = 0; i < ntokens; i++) {
1319                 fprintf(f, "%c%d,", i % 10 == 0 ? '\n': ' ', tokenlist[i]);
1320         }
1321         fputs(c_arrend, f);
1322         fprintf(f, "switch(LL%d_tklist[LLcsymb]) {\n", listno);
1323 }
1324
1325 STATIC
1326 genextname(d, s, f)
1327         char *s;
1328         FILE *f;
1329 {
1330         fprintf(f, "%s%d_%s", prefix ? prefix : "LL", d, s);
1331 }
1332
1333 STATIC
1334 correct_prefix()
1335 {
1336         register FILE *f = fpars;
1337         register char *s = prefix;
1338
1339         if (s) {
1340                 fprintf(f, "#define LLsymb %ssymb\n", s);
1341                 fprintf(f, "#define LLerror %serror\n", s);
1342                 fprintf(f, "#define LLsafeerror %ssafeerror\n", s);
1343                 fprintf(f, "#ifndef LL_FASTER\n#define LLscan %sscan\n#endif\n", s);
1344                 fprintf(f, "#define LLscnt %sscnt\n", s);
1345                 fprintf(f, "#define LLtcnt %stcnt\n", s);
1346                 fprintf(f, "#define LLcsymb %scsymb\n", s);
1347                 fprintf(f, "#define LLread %sread\n", s);
1348                 fprintf(f, "#define LLskip %sskip\n", s);
1349                 fprintf(f, "#define LLnext %snext\n", s);
1350                 fprintf(f, "#define LLfirst %sfirst\n", s);
1351                 fprintf(f, "#define LLnewlevel %snewlevel\n", s);
1352                 fprintf(f, "#define LLoldlevel %soldlevel\n", s);
1353                 fprintf(f, "#define LLmessage %smessage\n", s);
1354 #ifdef NON_CORRECTING
1355                 fprintf(f, "#define LLnc_recovery %sncrecovery\n", s);
1356                 fprintf(f, "#define LLstartsymb %sstartsymb\n", s);
1357 #endif
1358         }
1359         fprintf(f, "#include \"%s\"\n", f_include);
1360 }