util/LLgen/src/check.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  * check.c
  16  * Several routines to perform checks and printouts
  17  */
  18
  19 # include "types.h"
  20 # include "extern.h"
  21 # include "io.h"
  22 # include "sets.h"
  23 # include "assert.h"
  24
  25 # ifndef NORCSID
  26 static string rcsid1 = "$Id: check.c,v 2.14 1997/02/21 11:27:45 ceriel Exp $";
  27 # endif
  28
  29 static string   c_first = "> firstset   ";
  30 static string   c_contains = "> containset ";
  31 static string   c_follow = "> followset  ";
  32 p_set           setalloc();
  33 static int      level;
  34
  35 /* In this file are defined : */
  36 extern conflchecks();
  37 STATIC prline();
  38 STATIC printset();
  39 STATIC int check();
  40 STATIC moreverbose();
  41 STATIC prrule();
  42 STATIC cfcheck();
  43 STATIC resolve();
  44 STATIC propagate();
  45 STATIC spaces();
  46
  47 conflchecks() {
  48         /*
  49          * Check for conflicts, that is,
  50          * in a repeating term, the FIRST and FOLLOW must be disjunct,
  51          * unless there is a disambiguating condition.
  52          * in an alternation, the sets that determine the direction to take,
  53          * must be disjunct.
  54          */
  55         register p_nont p;
  56         register int s;
  57         p_file          x = files;
  58
  59         f_input = x->f_name;
  60         if (verbose >= 3) {
  61                 for (p = nonterms; p < maxnt; p++) p->n_flags |= VERBOSE;
  62         }
  63         if (verbose) {
  64                 if ((fout = fopen(f_out,"w")) == NULL) fatal(1,e_noopen,f_out);
  65         }
  66         /*
  67          * Check the rules in the order in which they are declared,
  68          * and input file by input file, to give proper error messages
  69          */
  70         for (; x < maxfiles; x++) {
  71             f_input = x->f_name;
  72             for (s = x->f_nonterminals; s != -1; s = p->n_next) {
  73                 p = &nonterms[s];
  74                 if (check(p->n_rule)) p->n_flags |= VERBOSE;
  75             }
  76         }
  77         for (x = files; x < maxfiles; x++) {
  78             f_input = x->f_name;
  79             for (s = x->f_nonterminals; s != -1; s = p->n_next) {
  80                 p = &nonterms[s];
  81                 if (p->n_flags & RECURSIVE) {
  82                         error(p->n_lineno,
  83                                 "Recursion in default for nonterminal %s",
  84                                 p->n_name);
  85                 }
  86                 /*
  87                  * If a printout is needed for this rule in
  88                  * LL.output, just do it
  89                  */
  90                 if (verbose && (p->n_flags & VERBOSE)) {
  91                         fprintf(fout,"\n%s :\n",p->n_name);
  92                         printset(p->n_first,c_first);
  93                         printset(p->n_contains,c_contains);
  94                         printset(p->n_follow,c_follow);
  95                         fprintf(fout,"> rule%s\n\t",
  96                                 p->n_flags&EMPTY ? "\t(EMPTY producing)" : "");
  97                         level = 8;
  98                         prrule(p->n_rule);
  99                         level = 0;
 100                         prline("\n");
 101                 }
 102                 /*
 103                  * Now, the conflicts may be resolved
 104                  */
 105                 resolve(p->n_rule);
 106             }
 107         }
 108         if (verbose) fclose(fout);
 109 }
 110
 111 STATIC
 112 prline(s) char *s; {
 113         fputs(s, fout);
 114         spaces();
 115 }
 116
 117 STATIC
 118 printset(p,s) register p_set p; string s; {
 119         /*
 120          * Print the elements of a set
 121          */
 122         register int    i;
 123         register int    j;
 124         register p_token pt;
 125         string          name;
 126         int             k;
 127         int             hulp;
 128
 129         k = strlen(s) + 2 + level;
 130         /*
 131          * k contains relative level of indentation
 132          */
 133         fprintf(fout,"%s{ ",s);
 134         j = k;
 135         /*
 136          * j will gather the total length of the line
 137          */
 138         for (i = 0, pt = tokens; i < ntokens; i++,pt++) {
 139                 if (IN(p,i)) {
 140                         hulp = strlen(pt->t_string)+1;
 141                         if (pt->t_tokno < 0400) hulp += 2;
 142                         if ((j += hulp) >= 78) {
 143                                 /*
 144                                  * Line becoming too long
 145                                  */
 146                                 j = k+hulp;
 147                                 prline("\n");
 148                                 fprintf(fout,">%*c",k - level - 1,' ');
 149                         }
 150                         fprintf(fout, pt->t_tokno<0400 ? "'%s' " : "%s ",pt->t_string);
 151                 }
 152         }
 153         if (ntprint) for (i = 0; i < nnonterms; i++) {
 154                 /*
 155                  * Nonterminals in the set must also be printed
 156                  */
 157                 if (NTIN(p,i)) {
 158                         name = nonterms[i].n_name;
 159                         hulp = strlen(name) + 3;
 160                         if ((j += hulp) >= 78) {
 161                                 j = k + hulp;
 162                                 prline("\n");
 163                                 fprintf(fout,">%*c",k - level - 1,' ');
 164                         }
 165                         fprintf(fout,"<%s> ",name);
 166                 }
 167         }
 168         prline("}\n");
 169 }
 170
 171 STATIC int
 172 check(p) register p_gram p; {
 173         /*
 174          * Search for conflicts in a grammar rule.
 175          */
 176         register p_set  temp;
 177         register int retval;
 178
 179         retval = 0;
 180         for (;;) {
 181                 switch (g_gettype(p)) {
 182                   case EORULE :
 183                         return retval;
 184                   case NONTERM : {
 185                         register p_nont n;
 186
 187                         n = &nonterms[g_getcont(p)];
 188                         if (g_getnpar(p) != getntparams(n)) {
 189                             error(p->g_lineno,
 190                                 "Call of %s: parameter count mismatch",
 191                                 n->n_name);
 192                         }
 193                         break; }
 194                   case TERM : {
 195                         register p_term q;
 196
 197                         q = g_getterm(p);
 198                         retval |= check(q->t_rule);
 199                         if (r_getkind(q) == FIXED) break;
 200                         if (setempty(q->t_first)) {
 201                                 q->t_flags |= EMPTYFIRST;
 202                                 retval = 1;
 203                                 error(p->g_lineno, "No symbols in term");
 204                         }
 205                         if (empty(q->t_rule)) {
 206                                 q->t_flags |= EMPTYTERM;
 207                                 retval = 1;
 208                                 error(p->g_lineno, "Term with variable repetition count produces empty");
 209                         }
 210                         temp = setalloc();
 211                         setunion(temp,q->t_first);
 212                         if (!setintersect(temp,q->t_follow)) {
 213                                 /*
 214                                  * q->t_first * q->t_follow != EMPTY
 215                                  */
 216                                 if (!(q->t_flags & RESOLVER)) {
 217                                         /*
 218                                          * No conflict resolver
 219                                          */
 220                                         error(p->g_lineno,
 221                                                 "Repetition conflict");
 222                                         retval = 1;
 223                                         moreverbose(temp);
 224                                 }
 225                         }
 226                         else {
 227                                 if (q->t_flags & RESOLVER) {
 228                                         q->t_flags |= NOCONF;
 229                                         warning(p->g_lineno,
 230                                                 "%%while without conflict");
 231                                 }
 232                         }
 233                         free((p_mem) temp);
 234                         break; }
 235                   case ALTERNATION : {
 236                         register p_link l;
 237
 238                         l = g_getlink(p);
 239                         temp = setalloc();
 240                         setunion(temp,l->l_symbs);
 241                         if(!setintersect(temp,l->l_others)) {
 242                                 /*
 243                                  * temp now contains the conflicting
 244                                  * symbols
 245                                  */
 246                                 if (!(l->l_flag & (COND|PREFERING|AVOIDING))) {
 247                                         error(p->g_lineno,
 248 "Alternation conflict");
 249                                         retval = 1;
 250                                         moreverbose(temp);
 251                                 }
 252                         } else {
 253                                 if (l->l_flag & (COND|PREFERING|AVOIDING)) {
 254                                         l->l_flag |= NOCONF;
 255                                         warning(p->g_lineno,
 256 "Conflict resolver without conflict");
 257                                 }
 258                         }
 259                         free( (p_mem) temp);
 260                         if (l->l_flag & PREFERING) propagate(l->l_symbs,p+1);
 261                         retval |= check(l->l_rule);
 262                         break; }
 263                 }
 264                 p++;
 265         }
 266 }
 267
 268 STATIC
 269 moreverbose(t) register p_set t; {
 270         /*
 271          * t points to a set containing conflicting symbols and pssibly
 272          * also containing nonterminals.
 273          * Take care that a printout will be prepared for these nonterminals
 274          */
 275         register int i;
 276         register p_nont p;
 277
 278         if (verbose == 2) for (i = 0, p = nonterms; i < nnonterms; i++, p++) {
 279                 if (NTIN(t,i)) p->n_flags |= VERBOSE;
 280         }
 281 }
 282
 283 STATIC
 284 prrule(p) register p_gram p; {
 285         /*
 286          * Create a verbose printout of grammar rule p
 287          */
 288         register FILE   *f;
 289         int             present = 0;
 290         int             firstalt = 1;
 291
 292         f = fout;
 293         for (;;) {
 294                 switch (g_gettype(p)) {
 295                   case EORULE :
 296                         fputs("\n",f);
 297                         return;
 298                   case TERM : {
 299                         register p_term q;
 300                         register int    c;
 301
 302                         q = g_getterm(p);
 303                         if (present) prline("\n");
 304                         fputs("[   ",f);
 305                         level += 4;
 306                         if (q->t_flags & RESOLVER) {
 307                                 prline("%while (..)\n");
 308                         }
 309                         if (q->t_flags & PERSISTENT) {
 310                                 prline("%persistent\n");
 311                         }
 312                         if (r_getkind(q) != FIXED) {
 313                                 if (!(q->t_flags & PERSISTENT)) {
 314                                     prline("> continue repetition on the\n");
 315                                 }
 316                                 printset(q->t_first, c_first);
 317                                 if (q->t_flags & PERSISTENT) {
 318                                     prline("> continue repetition on the\n");
 319                                 }
 320                                 printset(q->t_contains, c_contains);
 321                                 prline("> terminate repetition on the\n");
 322                                 printset(q->t_follow,c_follow);
 323                                 if (q->t_flags & EMPTYFIRST) {
 324                                     prline(">>> empty first\n");
 325                                 }
 326                                 if (q->t_flags & EMPTYTERM) {
 327                                     prline(">>> term produces empty\n");
 328                                 }
 329                                 cfcheck(q->t_first,q->t_follow,
 330                                         q->t_flags & RESOLVER);
 331                         }
 332                         prrule(q->t_rule);
 333                         level -= 4;
 334                         spaces();
 335                         c = r_getkind(q);
 336                         fputs(c == STAR ? "]*" : c == PLUS ? "]+" :
 337                               c == OPT ? "]?" : "]", f);
 338                         if (c = r_getnum(q)) {
 339                                 fprintf(f,"%d",c);
 340                         }
 341                         prline("\n");
 342                         break; }
 343                   case ACTION :
 344                         fputs("{..} ",f);
 345                         break;
 346                   case ALTERNATION : {
 347                         register p_link l;
 348
 349                         l = g_getlink(p);
 350                         if (firstalt) {
 351                                 firstalt = 0;
 352                         }
 353                         else    prline("|\n");
 354                         printset(l->l_symbs,"> alternative on ");
 355                         cfcheck(l->l_symbs,
 356                                 l->l_others,
 357                                 (int)(l->l_flag&(COND|PREFERING|AVOIDING)));
 358                         fputs("    ",f);
 359                         level += 4;
 360                         if (l->l_flag & DEF) {
 361                                 prline("%default\n");
 362                         }
 363                         if (l->l_flag & AVOIDING) {
 364                                 prline("%avoid\n");
 365                         }
 366                         if (l->l_flag & PREFERING) {
 367                                 prline("%prefer\n");
 368                         }
 369                         if (l->l_flag & COND) {
 370                                 prline("%if ( ... )\n");
 371                         }
 372                         prrule(l->l_rule);
 373                         level -= 4;
 374                         if (g_gettype(p+1) == EORULE) {
 375                                 return;
 376                         }
 377                         spaces();
 378                         p++; continue; }
 379                   case LITERAL :
 380                   case TERMINAL : {
 381                         register p_token pt = &tokens[g_getcont(p)];
 382
 383                         fprintf(f,pt->t_tokno<0400 ?
 384                                   "'%s' " : "%s ", pt->t_string);
 385                         break; }
 386                   case NONTERM :
 387                         fprintf(f,"%s ",nonterms[g_getcont(p)].n_name);
 388                         break;
 389                 }
 390                 p++;
 391                 present = 1;
 392         }
 393 }
 394
 395 STATIC
 396 cfcheck(s1,s2,flag) p_set s1,s2; {
 397         /*
 398          * Check if s1 and s2 have elements in common.
 399          * If so, flag must be non-zero, indicating that there is a
 400          * conflict resolver, otherwise, flag must be zero, indicating
 401          * that there is not.
 402          */
 403         register p_set temp;
 404
 405         temp = setalloc();
 406         setunion(temp,s1);
 407         if (!setintersect(temp,s2)) {
 408                 if (! flag) {
 409                         printset(temp,">>> conflict on ");
 410                         prline("\n");
 411                 }
 412         } else {
 413                 if (flag) {
 414                         prline(">>> %if/%while, no conflict\n");
 415                 }
 416         }
 417         free((p_mem) temp);
 418 }
 419
 420 STATIC
 421 resolve(p) register p_gram p; {
 422         /*
 423          * resolve conflicts, as specified by the user
 424          */
 425         for (;;) {
 426                 switch (g_gettype(p)) {
 427                   case EORULE :
 428                         return;
 429                   case TERM :
 430                         resolve(g_getterm(p)->t_rule);
 431                         break;
 432                   case ALTERNATION : {
 433                         register p_link l;
 434
 435                         l = g_getlink(p);
 436                         if (l->l_flag & AVOIDING) {
 437                                 /*
 438                                  * On conflicting symbols, this rule
 439                                  * is never chosen
 440                                  */
 441                                 setminus(l->l_symbs,l->l_others);
 442                         }
 443                         if (setempty(l->l_symbs)) {
 444                                 /*
 445                                  * This may be caused by the statement above
 446                                  */
 447                                 error(p->g_lineno,"Alternative never chosen");
 448                         }
 449                         resolve(l->l_rule);
 450                         break; }
 451                 }
 452                 p++;
 453         }
 454 }
 455
 456 STATIC
 457 propagate(set,p) p_set set; register p_gram p; {
 458         /*
 459          * Propagate the fact that on the elements of set the grammar rule
 460          * p will not be chosen.
 461          */
 462         while (g_gettype(p) != EORULE) {
 463                 setminus(g_getlink(p)->l_symbs,set);
 464                 p++;
 465         }
 466 }
 467
 468 STATIC
 469 spaces() {
 470
 471         if (level > 0) fprintf(fout,"%*c",level,' ');
 472 }