util/LLgen/src/savegram.c

   1 /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
   2  * All rights reserved.
   3  */
   4
   5 #ifdef NON_CORRECTING
   6
   7 /*
   8  *  L L G E N
   9  *
  10  *  An Extended LL(1) Parser Generator
  11  *
  12  *  Author : Ceriel J.H. Jacobs
  13  */
  14
  15 /*
  16  * savegram.c
  17  * Save the input grammar for non-correcting error recovery
  18  *
  19  * Grammar rules are `flattened' by introducing anonymous nonterminals.
  20  * [B]? becomes X; X: B | {empty}
  21  * [B]+ becomes X: B Y; Y: X | {empty}
  22  * [B]* becomes X; X: B X | {empty}
  23  * [B | C] becomes X; X: B | C
  24  * [B | C]* becomes X; X: B X | C X | {empty}  etc.
  25  */
  26
  27
  28 # include "types.h"
  29 # include "extern.h"
  30 # include "io.h"
  31 # include "assert.h"
  32 # include "sets.h"
  33
  34 #define LLALT 9999
  35
  36 static int nt_highest;
  37 extern int nbytes;
  38 extern p_mem alloc();
  39 extern p_set start_firsts;
  40 extern p_set setalloc();
  41 extern p_gram search();
  42
  43 STATIC save_rule();
  44 STATIC save_set();
  45
  46 /* t_list will contain terms to be `flattened' */
  47 static struct t_list {
  48         p_term term;
  49         int t_nt_num;
  50 } *t_list;
  51
  52 /* Subparse list will contain symbols in %substart */
  53 static struct subparse_list {
  54         p_gram sub_action;
  55         int sub_nt_num;
  56 } *sub_list;
  57
  58 /* Index in t_list */
  59 static int t_list_index;
  60
  61 /* Index in subparse_list */
  62 static int sub_list_index;
  63
  64 /* File to save grammar to */
  65 static FILE *fgram;
  66
  67 /* Nonterminal number to simulate parsers that get called in actions
  68    used when LLgen called with -n -s options */
  69 int act_nt;
  70
  71 save_grammar(f) FILE *f; {
  72         /*
  73          * Save the grammar
  74          */
  75         register p_nont         p;
  76         register p_start        st;
  77         register int            nt_nr;
  78
  79         fgram = f;
  80
  81         /* Compute highest nonterminal nr. */
  82         nt_highest = nnonterms + assval - 1;
  83
  84
  85         /* Generate some constants in the grammar file */
  86
  87         /* Allocate terms list */
  88         t_list = (struct t_list *) alloc((unsigned) nterms * sizeof(struct t_list));
  89         t_list_index = 0;
  90
  91         sub_list = (struct subparse_list *) alloc(nsubstarts * sizeof(struct subparse_list));
  92
  93         fputs("static ", fgram);
  94         fputs((prefix ? prefix : "LL"), fgram);
  95         fputs("grammar[] = {\n", fgram);
  96
  97         /* Check if -n -s option is on */
  98         if (subpars_sim) {
  99
 100                 /* Allocate action simulation nt */
 101
 102                 act_nt = ++nt_highest;
 103
 104                 /* write simualtion rule */
 105                 fprintf(fgram, "/* Simulation rule */\n");
 106                 fprintf(fgram, "%d,\n", act_nt);
 107
 108                 /* Put a firstset and a fake followset */
 109                 /* Followset optimization is not implemented for
 110                    -s because it would be hard, and does not
 111                    bring enough improvement to jutify the effort
 112                  */
 113                 save_set(start_firsts);
 114                 save_set(start_firsts);
 115                 /* Simulation rule procudes empty */
 116                 fprintf(fgram, "%d,\n", 1);
 117                 for (st = start; st; st = st->ff_next)
 118                 {
 119                         fprintf(fgram, "%d, %d, %d, \n", st->ff_nont + assval,
 120                                                                 act_nt, LLALT);
 121                 }
 122                 fprintf(fgram, "%d, \n", 0);
 123
 124         }
 125
 126         /* Now process all rules */
 127         for (p = nonterms, nt_nr = assval; p < maxnt; p++, nt_nr++) {
 128                 fprintf(fgram, "/* nr. %d %s */\n", nt_nr, p->n_name);
 129                 fprintf(fgram, "%d, ",nt_nr);
 130                 if (! p->n_rule) {      /* undefined */
 131                         f_input = p->n_string;
 132                         error(p->n_lineno,"Nonterminal %s not defined",
 133                                 p->n_name);
 134                 }
 135
 136                 /* Save the first_set and follow set */
 137                 save_set(p->n_nc_first);
 138                 save_set(p->n_nc_follow);
 139
 140                 if (p->n_flags & EMPTY)
 141                         fprintf(fgram, "%d,\n", 1);
 142                 else
 143                         fprintf(fgram, "%d,\n", 0);
 144
 145                 save_rule(p->n_rule, 0);
 146
 147                 fprintf(fgram, "%d,\n", 0);
 148         }
 149
 150         /* Resolve terms, they are on t_list */
 151
 152         fprintf(fgram, "/* Fresh nonterminals */\n");
 153
 154         { int i;
 155         for (i = 0; i < t_list_index; i++)
 156         {
 157
 158         /* Terms of the form [] without + ? * or number produce
 159          a NIL pointer in the term-list */
 160                 if ((t_list + i)->term == (struct term *) 0) {
 161                         continue;
 162                 }
 163
 164                 fprintf(fgram, "%d, ", (t_list + i)->t_nt_num);
 165
 166                 /* Save the first and follow sets */
 167
 168                 save_set((t_list + i)->term->t_nc_first);
 169                 save_set((t_list + i)->term->t_nc_follow);
 170
 171                 /* NOTE: A VARIABLE REPETITION COUNT TERMS RULE IS NOT
 172                    ALLOWED TO PRODUCE EMPTY IN LLGEN
 173                  */
 174
 175                 switch(r_getkind((t_list + i)->term)) {
 176                 case FIXED:
 177                 /* Already done by repeating new nonterminal */
 178
 179                         /* FIXED term-rule may produce empty */
 180                         if (empty((t_list +i)->term->t_rule))
 181                                 fprintf(fgram, "%d,\n", 1);
 182                         else
 183                                 fprintf(fgram, "%d,\n", 0);
 184
 185                         save_rule((t_list + i)->term->t_rule, 0);
 186                         fprintf(fgram, "%d,\n", 0);
 187                         break;
 188                 case STAR:
 189                 /* Save the rule, appending the new lhs for this rule */
 190
 191                         /* Star rules always produce empty */
 192                         fprintf(fgram, "1,\n");
 193
 194                         save_rule((t_list + i)->term->t_rule,
 195                                                 (t_list + i)->t_nt_num);
 196                         fprintf(fgram, "%d,\n%d,\n", LLALT, 0);
 197                         /* ALT EMPTY*/
 198                         break;
 199                 case PLUS:
 200                 /* Save the rule appending a fresh nonterminal */
 201
 202                         fprintf(fgram, "%d,\n", 0);
 203
 204                         save_rule((t_list + i)->term->t_rule, ++nt_highest);
 205                         fprintf(fgram, "%d,\n", 0); /* EOR */
 206                         fprintf(fgram, "%d, ", nt_highest);
 207                         /* First set of the extra nonterm is same as
 208                            for the term */
 209                         /* Except that the new nonterm also produces empty ! */
 210                         save_set((t_list + i)->term->t_nc_first);
 211                         save_set((t_list + i)->term->t_nc_follow);
 212                         fprintf(fgram, "1,\n");
 213                         fprintf(fgram, "%d, ", (t_list+i)->t_nt_num);
 214                         fprintf(fgram, "%d,\n%d,\n", LLALT, 0); /* ALT EMPTY */
 215                         break;
 216                 case OPT:
 217                         fprintf(fgram, "1,\n");
 218                         save_rule((t_list + i)->term->t_rule, 0);
 219                         fprintf(fgram, "%d,\n%d,\n", LLALT, 0); /* ALT EMPTY */
 220                         break;
 221                 }
 222         }
 223         }
 224
 225         /* Resolve %substarts */
 226         if (!subpars_sim) {
 227                 int i,s,check;
 228                 p_start ff, gg;
 229                 p_set temp_set;
 230
 231                 for (i = 0; i < sub_list_index; i++) {
 232                         fprintf(fgram, "%d, ", (sub_list + i)->sub_nt_num);
 233                         /* Compute the first set */
 234                         temp_set = setalloc();
 235                         for (ff = g_getsubparse((sub_list + i)->sub_action);
 236                                                         ff; ff = ff->ff_next){
 237                         s = setunion(temp_set,
 238                                         (&nonterms[ff->ff_nont])->n_first);
 239                         check = 0;
 240                         for (gg =start; gg; gg = gg->ff_next)
 241                                 if (ff->ff_nont == gg->ff_nont)
 242                                         check = 1;
 243                         if (check == 0)
 244                         warning((sub_list + i)->sub_action->g_lineno,
 245                                         "\"%s\" is not a startsymbol",
 246                                         (&nonterms[ff->ff_nont])->n_name);
 247                 }
 248                 save_set(temp_set);
 249                 save_set(temp_set);
 250                 free(temp_set);
 251
 252                 /* Produces empty */
 253                 fprintf(fgram, "1,\n");
 254
 255                 ff = g_getsubparse((sub_list + i)->sub_action);
 256
 257                 for (; ff; ff = ff->ff_next)
 258                         fprintf(fgram, "%d, %d, %d, \n", ff->ff_nont + assval,
 259                                                 (sub_list + i)->sub_nt_num,
 260                                                                         LLALT);
 261                 fprintf(fgram, "%d, \n", 0);
 262                 }
 263         }
 264
 265         fprintf(fgram, "%d\n};\n", 0);
 266         fprintf(fgram, "#define LLNNONTERMINALS %d\n", nt_highest - assval + 1);
 267 }
 268
 269 STATIC
 270 save_rule(p, tail) register p_gram p; int tail; {
 271 /*
 272  Walk through rule p, saving it. The non-terminal tail is
 273  appended to the rule. It needs to be appended in this function
 274  to process alt-rules correctly. Tail == 0 means don't append.
 275  */
 276
 277         int in_alt;
 278         int illegal_num;
 279         /* Processing an alt needs some special care. When processing the
 280            first alternative, we don't want to write the alt-code;
 281            When appending something to the alt, it needs to be appended to
 282            every alternative and not at the end of the rule.
 283         */
 284
 285         /* Look up the ILLEGAL token number */
 286         illegal_num = tokens[g_getcont(illegal_gram)].t_tokno;
 287
 288         in_alt = 0;
 289         for (;;) {
 290                 switch(g_gettype(p)) {
 291                 case ALTERNATION :
 292                         if (in_alt)
 293                                 fprintf(fgram, "%d,\n", LLALT);
 294                         else
 295                                 in_alt = 1;
 296                         save_rule(g_getlink(p)->l_rule, tail);
 297                         break;
 298                 case TERM :
 299                         /* Make entry in term list */
 300                         (t_list + t_list_index)->term = g_getterm(p);
 301                         /* Test for [] without specifier */
 302                         if (g_getterm(p) == (struct term *) 0) {
 303                                 t_list_index++;
 304                                 break;
 305                         }
 306                         (t_list + t_list_index++)->t_nt_num = ++nt_highest;
 307                         fprintf(fgram, "%d, ", nt_highest);
 308                         /* Check if repetition,  if so handle here */
 309                         if (r_getkind(g_getterm(p)) == FIXED)
 310                         {
 311                                 int k;
 312                                 for (k = 1; k < r_getnum(g_getterm(p)); k++)
 313                                         fprintf(fgram, "%d, ", nt_highest);
 314                         }
 315                         break;
 316                 case NONTERM :
 317                         fprintf(fgram, "%d, ", g_getcont(p) + assval);
 318                         break;
 319                 case TERMINAL:
 320                         if (g_getcont(p) == g_getcont(illegal_gram)) {
 321                                 /* %illegal. Ignore. */
 322                                 break;
 323                         }
 324                         if (p->g_erroneous)
 325                                 fprintf(fgram, "%d, ", illegal_num);
 326                         else
 327                                 fprintf(fgram, "%d, ",
 328                                                 tokens[g_getcont(p)].t_tokno);
 329                         break;
 330                 case LITERAL:
 331                         if (p->g_erroneous)
 332                                 fprintf(fgram, "%d, ", illegal_num);
 333                         else
 334                                 fprintf(fgram, "%d, ",
 335                                                 tokens[g_getcont(p)].t_tokno);
 336                         break;
 337                 case ACTION:
 338                         if (subpars_sim) {
 339                                 fprintf(fgram, "%d, ", act_nt);
 340                         }
 341                         else if (g_getsubparse(p)) {
 342                                 /* Allocate nonterminal that will simulate
 343                                    subparser
 344                                  */
 345                                 (sub_list + sub_list_index)->sub_nt_num =
 346                                                                 ++nt_highest;
 347                                 (sub_list + sub_list_index++)->sub_action = p;
 348
 349                                 fprintf(fgram, "%d, ", nt_highest);
 350                         }
 351                         break;
 352                 case EORULE :
 353                         if ((! in_alt) && tail )
 354                         /* If this rule is not an alt, append tail now.
 355                            If it is an alt, the recursive call of this function
 356                            has appended tail to each alternative
 357                          */
 358                         fprintf(fgram, "%d, ", tail);
 359                         return;
 360                 }
 361                 p++;
 362         }
 363 }
 364
 365 STATIC
 366 save_set(p) p_set p; {
 367         register int k;
 368         register unsigned i;
 369         int j;
 370
 371         j = nbytes;
 372         for (;;) {
 373                 i = (unsigned) *p++;
 374                 for (k = 0; k < sizeof(int); k++) {
 375                         fprintf(fgram,"0%o,",(int)(i & 0377));
 376                         i >>= 8;
 377                         if (--j == 0) {
 378                                 fputs("\n",fgram);
 379                                 return;
 380                         }
 381                 }
 382         }
 383         /* NOTREACHED */
 384 }
 385 #endif