Parser/pgen.c

   1
   2 /* Parser generator */
   3 /* XXX This file is not yet fully PROTOized */
   4
   5 /* For a description, see the comments at end of this file */
   6
   7 #include "pgenheaders.h"
   8 #include "assert.h"
   9 #include "token.h"
  10 #include "node.h"
  11 #include "grammar.h"
  12 #include "metagrammar.h"
  13 #include "pgen.h"
  14
  15 extern int Py_DebugFlag;
  16
  17
  18 /* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */
  19
  20 typedef struct _nfaarc {
  21         int     ar_label;
  22         int     ar_arrow;
  23 } nfaarc;
  24
  25 typedef struct _nfastate {
  26         int     st_narcs;
  27         nfaarc  *st_arc;
  28 } nfastate;
  29
  30 typedef struct _nfa {
  31         int             nf_type;
  32         char            *nf_name;
  33         int             nf_nstates;
  34         nfastate        *nf_state;
  35         int             nf_start, nf_finish;
  36 } nfa;
  37
  38 /* Forward */
  39 static void compile_rhs(labellist *ll,
  40                         nfa *nf, node *n, int *pa, int *pb);
  41 static void compile_alt(labellist *ll,
  42                         nfa *nf, node *n, int *pa, int *pb);
  43 static void compile_item(labellist *ll,
  44                          nfa *nf, node *n, int *pa, int *pb);
  45 static void compile_atom(labellist *ll,
  46                          nfa *nf, node *n, int *pa, int *pb);
  47
  48 static int
  49 addnfastate(nfa *nf)
  50 {
  51         nfastate *st;
  52
  53         PyMem_RESIZE(nf->nf_state, nfastate, nf->nf_nstates + 1);
  54         if (nf->nf_state == NULL)
  55                 Py_FatalError("out of mem");
  56         st = &nf->nf_state[nf->nf_nstates++];
  57         st->st_narcs = 0;
  58         st->st_arc = NULL;
  59         return st - nf->nf_state;
  60 }
  61
  62 static void
  63 addnfaarc(nfa *nf, int from, int to, int lbl)
  64 {
  65         nfastate *st;
  66         nfaarc *ar;
  67
  68         st = &nf->nf_state[from];
  69         PyMem_RESIZE(st->st_arc, nfaarc, st->st_narcs + 1);
  70         if (st->st_arc == NULL)
  71                 Py_FatalError("out of mem");
  72         ar = &st->st_arc[st->st_narcs++];
  73         ar->ar_label = lbl;
  74         ar->ar_arrow = to;
  75 }
  76
  77 static nfa *
  78 newnfa(char *name)
  79 {
  80         nfa *nf;
  81         static int type = NT_OFFSET; /* All types will be disjunct */
  82
  83         nf = PyMem_NEW(nfa, 1);
  84         if (nf == NULL)
  85                 Py_FatalError("no mem for new nfa");
  86         nf->nf_type = type++;
  87         nf->nf_name = name; /* XXX strdup(name) ??? */
  88         nf->nf_nstates = 0;
  89         nf->nf_state = NULL;
  90         nf->nf_start = nf->nf_finish = -1;
  91         return nf;
  92 }
  93
  94 typedef struct _nfagrammar {
  95         int             gr_nnfas;
  96         nfa             **gr_nfa;
  97         labellist       gr_ll;
  98 } nfagrammar;
  99
 100 /* Forward */
 101 static void compile_rule(nfagrammar *gr, node *n);
 102
 103 static nfagrammar *
 104 newnfagrammar(void)
 105 {
 106         nfagrammar *gr;
 107
 108         gr = PyMem_NEW(nfagrammar, 1);
 109         if (gr == NULL)
 110                 Py_FatalError("no mem for new nfa grammar");
 111         gr->gr_nnfas = 0;
 112         gr->gr_nfa = NULL;
 113         gr->gr_ll.ll_nlabels = 0;
 114         gr->gr_ll.ll_label = NULL;
 115         addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");
 116         return gr;
 117 }
 118
 119 static nfa *
 120 addnfa(nfagrammar *gr, char *name)
 121 {
 122         nfa *nf;
 123
 124         nf = newnfa(name);
 125         PyMem_RESIZE(gr->gr_nfa, nfa *, gr->gr_nnfas + 1);
 126         if (gr->gr_nfa == NULL)
 127                 Py_FatalError("out of mem");
 128         gr->gr_nfa[gr->gr_nnfas++] = nf;
 129         addlabel(&gr->gr_ll, NAME, nf->nf_name);
 130         return nf;
 131 }
 132
 133 #ifdef Py_DEBUG
 134
 135 static char REQNFMT[] = "metacompile: less than %d children\n";
 136
 137 #define REQN(i, count) \
 138         if (i < count) { \
 139                 fprintf(stderr, REQNFMT, count); \
 140                 Py_FatalError("REQN"); \
 141         } else
 142
 143 #else
 144 #define REQN(i, count)  /* empty */
 145 #endif
 146
 147 static nfagrammar *
 148 metacompile(node *n)
 149 {
 150         nfagrammar *gr;
 151         int i;
 152
 153         printf("Compiling (meta-) parse tree into NFA grammar\n");
 154         gr = newnfagrammar();
 155         REQ(n, MSTART);
 156         i = n->n_nchildren - 1; /* Last child is ENDMARKER */
 157         n = n->n_child;
 158         for (; --i >= 0; n++) {
 159                 if (n->n_type != NEWLINE)
 160                         compile_rule(gr, n);
 161         }
 162         return gr;
 163 }
 164
 165 static void
 166 compile_rule(nfagrammar *gr, node *n)
 167 {
 168         nfa *nf;
 169
 170         REQ(n, RULE);
 171         REQN(n->n_nchildren, 4);
 172         n = n->n_child;
 173         REQ(n, NAME);
 174         nf = addnfa(gr, n->n_str);
 175         n++;
 176         REQ(n, COLON);
 177         n++;
 178         REQ(n, RHS);
 179         compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
 180         n++;
 181         REQ(n, NEWLINE);
 182 }
 183
 184 static void
 185 compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
 186 {
 187         int i;
 188         int a, b;
 189
 190         REQ(n, RHS);
 191         i = n->n_nchildren;
 192         REQN(i, 1);
 193         n = n->n_child;
 194         REQ(n, ALT);
 195         compile_alt(ll, nf, n, pa, pb);
 196         if (--i <= 0)
 197                 return;
 198         n++;
 199         a = *pa;
 200         b = *pb;
 201         *pa = addnfastate(nf);
 202         *pb = addnfastate(nf);
 203         addnfaarc(nf, *pa, a, EMPTY);
 204         addnfaarc(nf, b, *pb, EMPTY);
 205         for (; --i >= 0; n++) {
 206                 REQ(n, VBAR);
 207                 REQN(i, 1);
 208                 --i;
 209                 n++;
 210                 REQ(n, ALT);
 211                 compile_alt(ll, nf, n, &a, &b);
 212                 addnfaarc(nf, *pa, a, EMPTY);
 213                 addnfaarc(nf, b, *pb, EMPTY);
 214         }
 215 }
 216
 217 static void
 218 compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
 219 {
 220         int i;
 221         int a, b;
 222
 223         REQ(n, ALT);
 224         i = n->n_nchildren;
 225         REQN(i, 1);
 226         n = n->n_child;
 227         REQ(n, ITEM);
 228         compile_item(ll, nf, n, pa, pb);
 229         --i;
 230         n++;
 231         for (; --i >= 0; n++) {
 232                 if (n->n_type == COMMA) { /* XXX Temporary */
 233                         REQN(i, 1);
 234                         --i;
 235                         n++;
 236                 }
 237                 REQ(n, ITEM);
 238                 compile_item(ll, nf, n, &a, &b);
 239                 addnfaarc(nf, *pb, a, EMPTY);
 240                 *pb = b;
 241         }
 242 }
 243
 244 static void
 245 compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
 246 {
 247         int i;
 248         int a, b;
 249
 250         REQ(n, ITEM);
 251         i = n->n_nchildren;
 252         REQN(i, 1);
 253         n = n->n_child;
 254         if (n->n_type == LSQB) {
 255                 REQN(i, 3);
 256                 n++;
 257                 REQ(n, RHS);
 258                 *pa = addnfastate(nf);
 259                 *pb = addnfastate(nf);
 260                 addnfaarc(nf, *pa, *pb, EMPTY);
 261                 compile_rhs(ll, nf, n, &a, &b);
 262                 addnfaarc(nf, *pa, a, EMPTY);
 263                 addnfaarc(nf, b, *pb, EMPTY);
 264                 REQN(i, 1);
 265                 n++;
 266                 REQ(n, RSQB);
 267         }
 268         else {
 269                 compile_atom(ll, nf, n, pa, pb);
 270                 if (--i <= 0)
 271                         return;
 272                 n++;
 273                 addnfaarc(nf, *pb, *pa, EMPTY);
 274                 if (n->n_type == STAR)
 275                         *pb = *pa;
 276                 else
 277                         REQ(n, PLUS);
 278         }
 279 }
 280
 281 static void
 282 compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
 283 {
 284         int i;
 285
 286         REQ(n, ATOM);
 287         i = n->n_nchildren;
 288         REQN(i, 1);
 289         n = n->n_child;
 290         if (n->n_type == LPAR) {
 291                 REQN(i, 3);
 292                 n++;
 293                 REQ(n, RHS);
 294                 compile_rhs(ll, nf, n, pa, pb);
 295                 n++;
 296                 REQ(n, RPAR);
 297         }
 298         else if (n->n_type == NAME || n->n_type == STRING) {
 299                 *pa = addnfastate(nf);
 300                 *pb = addnfastate(nf);
 301                 addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));
 302         }
 303         else
 304                 REQ(n, NAME);
 305 }
 306
 307 static void
 308 dumpstate(labellist *ll, nfa *nf, int istate)
 309 {
 310         nfastate *st;
 311         int i;
 312         nfaarc *ar;
 313
 314         printf("%c%2d%c",
 315                 istate == nf->nf_start ? '*' : ' ',
 316                 istate,
 317                 istate == nf->nf_finish ? '.' : ' ');
 318         st = &nf->nf_state[istate];
 319         ar = st->st_arc;
 320         for (i = 0; i < st->st_narcs; i++) {
 321                 if (i > 0)
 322                         printf("\n    ");
 323                 printf("-> %2d  %s", ar->ar_arrow,
 324                         PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
 325                 ar++;
 326         }
 327         printf("\n");
 328 }
 329
 330 static void
 331 dumpnfa(labellist *ll, nfa *nf)
 332 {
 333         int i;
 334
 335         printf("NFA '%s' has %d states; start %d, finish %d\n",
 336                 nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
 337         for (i = 0; i < nf->nf_nstates; i++)
 338                 dumpstate(ll, nf, i);
 339 }
 340
 341
 342 /* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */
 343
 344 static void
 345 addclosure(bitset ss, nfa *nf, int istate)
 346 {
 347         if (addbit(ss, istate)) {
 348                 nfastate *st = &nf->nf_state[istate];
 349                 nfaarc *ar = st->st_arc;
 350                 int i;
 351
 352                 for (i = st->st_narcs; --i >= 0; ) {
 353                         if (ar->ar_label == EMPTY)
 354                                 addclosure(ss, nf, ar->ar_arrow);
 355                         ar++;
 356                 }
 357         }
 358 }
 359
 360 typedef struct _ss_arc {
 361         bitset  sa_bitset;
 362         int     sa_arrow;
 363         int     sa_label;
 364 } ss_arc;
 365
 366 typedef struct _ss_state {
 367         bitset  ss_ss;
 368         int     ss_narcs;
 369         ss_arc  *ss_arc;
 370         int     ss_deleted;
 371         int     ss_finish;
 372         int     ss_rename;
 373 } ss_state;
 374
 375 typedef struct _ss_dfa {
 376         int     sd_nstates;
 377         ss_state *sd_state;
 378 } ss_dfa;
 379
 380 /* Forward */
 381 static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
 382                        labellist *ll, char *msg);
 383 static void simplify(int xx_nstates, ss_state *xx_state);
 384 static void convert(dfa *d, int xx_nstates, ss_state *xx_state);
 385
 386 static void
 387 makedfa(nfagrammar *gr, nfa *nf, dfa *d)
 388 {
 389         int nbits = nf->nf_nstates;
 390         bitset ss;
 391         int xx_nstates;
 392         ss_state *xx_state, *yy;
 393         ss_arc *zz;
 394         int istate, jstate, iarc, jarc, ibit;
 395         nfastate *st;
 396         nfaarc *ar;
 397
 398         ss = newbitset(nbits);
 399         addclosure(ss, nf, nf->nf_start);
 400         xx_state = PyMem_NEW(ss_state, 1);
 401         if (xx_state == NULL)
 402                 Py_FatalError("no mem for xx_state in makedfa");
 403         xx_nstates = 1;
 404         yy = &xx_state[0];
 405         yy->ss_ss = ss;
 406         yy->ss_narcs = 0;
 407         yy->ss_arc = NULL;
 408         yy->ss_deleted = 0;
 409         yy->ss_finish = testbit(ss, nf->nf_finish);
 410         if (yy->ss_finish)
 411                 printf("Error: nonterminal '%s' may produce empty.\n",
 412                         nf->nf_name);
 413
 414         /* This algorithm is from a book written before
 415            the invention of structured programming... */
 416
 417         /* For each unmarked state... */
 418         for (istate = 0; istate < xx_nstates; ++istate) {
 419                 yy = &xx_state[istate];
 420                 ss = yy->ss_ss;
 421                 /* For all its states... */
 422                 for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
 423                         if (!testbit(ss, ibit))
 424                                 continue;
 425                         st = &nf->nf_state[ibit];
 426                         /* For all non-empty arcs from this state... */
 427                         for (iarc = 0; iarc < st->st_narcs; iarc++) {
 428                                 ar = &st->st_arc[iarc];
 429                                 if (ar->ar_label == EMPTY)
 430                                         continue;
 431                                 /* Look up in list of arcs from this state */
 432                                 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
 433                                         zz = &yy->ss_arc[jarc];
 434                                         if (ar->ar_label == zz->sa_label)
 435                                                 goto found;
 436                                 }
 437                                 /* Add new arc for this state */
 438                                 PyMem_RESIZE(yy->ss_arc, ss_arc,
 439                                              yy->ss_narcs + 1);
 440                                 if (yy->ss_arc == NULL)
 441                                         Py_FatalError("out of mem");
 442                                 zz = &yy->ss_arc[yy->ss_narcs++];
 443                                 zz->sa_label = ar->ar_label;
 444                                 zz->sa_bitset = newbitset(nbits);
 445                                 zz->sa_arrow = -1;
 446                          found: ;
 447                                 /* Add destination */
 448                                 addclosure(zz->sa_bitset, nf, ar->ar_arrow);
 449                         }
 450                 }
 451                 /* Now look up all the arrow states */
 452                 for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
 453                         zz = &xx_state[istate].ss_arc[jarc];
 454                         for (jstate = 0; jstate < xx_nstates; jstate++) {
 455                                 if (samebitset(zz->sa_bitset,
 456                                         xx_state[jstate].ss_ss, nbits)) {
 457                                         zz->sa_arrow = jstate;
 458                                         goto done;
 459                                 }
 460                         }
 461                         PyMem_RESIZE(xx_state, ss_state, xx_nstates + 1);
 462                         if (xx_state == NULL)
 463                                 Py_FatalError("out of mem");
 464                         zz->sa_arrow = xx_nstates;
 465                         yy = &xx_state[xx_nstates++];
 466                         yy->ss_ss = zz->sa_bitset;
 467                         yy->ss_narcs = 0;
 468                         yy->ss_arc = NULL;
 469                         yy->ss_deleted = 0;
 470                         yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
 471                  done:  ;
 472                 }
 473         }
 474
 475         if (Py_DebugFlag)
 476                 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
 477                                                 "before minimizing");
 478
 479         simplify(xx_nstates, xx_state);
 480
 481         if (Py_DebugFlag)
 482                 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
 483                                                 "after minimizing");
 484
 485         convert(d, xx_nstates, xx_state);
 486
 487         /* XXX cleanup */
 488 }
 489
 490 static void
 491 printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
 492            labellist *ll, char *msg)
 493 {
 494         int i, ibit, iarc;
 495         ss_state *yy;
 496         ss_arc *zz;
 497
 498         printf("Subset DFA %s\n", msg);
 499         for (i = 0; i < xx_nstates; i++) {
 500                 yy = &xx_state[i];
 501                 if (yy->ss_deleted)
 502                         continue;
 503                 printf(" Subset %d", i);
 504                 if (yy->ss_finish)
 505                         printf(" (finish)");
 506                 printf(" { ");
 507                 for (ibit = 0; ibit < nbits; ibit++) {
 508                         if (testbit(yy->ss_ss, ibit))
 509                                 printf("%d ", ibit);
 510                 }
 511                 printf("}\n");
 512                 for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
 513                         zz = &yy->ss_arc[iarc];
 514                         printf("  Arc to state %d, label %s\n",
 515                                 zz->sa_arrow,
 516                                 PyGrammar_LabelRepr(
 517                                         &ll->ll_label[zz->sa_label]));
 518                 }
 519         }
 520 }
 521
 522
 523 /* PART THREE -- SIMPLIFY DFA */
 524
 525 /* Simplify the DFA by repeatedly eliminating states that are
 526    equivalent to another oner.  This is NOT Algorithm 3.3 from
 527    [Aho&Ullman 77].  It does not always finds the minimal DFA,
 528    but it does usually make a much smaller one...  (For an example
 529    of sub-optimal behavior, try S: x a b+ | y a b+.)
 530 */
 531
 532 static int
 533 samestate(ss_state *s1, ss_state *s2)
 534 {
 535         int i;
 536
 537         if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)
 538                 return 0;
 539         for (i = 0; i < s1->ss_narcs; i++) {
 540                 if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||
 541                         s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
 542                         return 0;
 543         }
 544         return 1;
 545 }
 546
 547 static void
 548 renamestates(int xx_nstates, ss_state *xx_state, int from, int to)
 549 {
 550         int i, j;
 551
 552         if (Py_DebugFlag)
 553                 printf("Rename state %d to %d.\n", from, to);
 554         for (i = 0; i < xx_nstates; i++) {
 555                 if (xx_state[i].ss_deleted)
 556                         continue;
 557                 for (j = 0; j < xx_state[i].ss_narcs; j++) {
 558                         if (xx_state[i].ss_arc[j].sa_arrow == from)
 559                                 xx_state[i].ss_arc[j].sa_arrow = to;
 560                 }
 561         }
 562 }
 563
 564 static void
 565 simplify(int xx_nstates, ss_state *xx_state)
 566 {
 567         int changes;
 568         int i, j;
 569
 570         do {
 571                 changes = 0;
 572                 for (i = 1; i < xx_nstates; i++) {
 573                         if (xx_state[i].ss_deleted)
 574                                 continue;
 575                         for (j = 0; j < i; j++) {
 576                                 if (xx_state[j].ss_deleted)
 577                                         continue;
 578                                 if (samestate(&xx_state[i], &xx_state[j])) {
 579                                         xx_state[i].ss_deleted++;
 580                                         renamestates(xx_nstates, xx_state,
 581                                                      i, j);
 582                                         changes++;
 583                                         break;
 584                                 }
 585                         }
 586                 }
 587         } while (changes);
 588 }
 589
 590
 591 /* PART FOUR -- GENERATE PARSING TABLES */
 592
 593 /* Convert the DFA into a grammar that can be used by our parser */
 594
 595 static void
 596 convert(dfa *d, int xx_nstates, ss_state *xx_state)
 597 {
 598         int i, j;
 599         ss_state *yy;
 600         ss_arc *zz;
 601
 602         for (i = 0; i < xx_nstates; i++) {
 603                 yy = &xx_state[i];
 604                 if (yy->ss_deleted)
 605                         continue;
 606                 yy->ss_rename = addstate(d);
 607         }
 608
 609         for (i = 0; i < xx_nstates; i++) {
 610                 yy = &xx_state[i];
 611                 if (yy->ss_deleted)
 612                         continue;
 613                 for (j = 0; j < yy->ss_narcs; j++) {
 614                         zz = &yy->ss_arc[j];
 615                         addarc(d, yy->ss_rename,
 616                                 xx_state[zz->sa_arrow].ss_rename,
 617                                 zz->sa_label);
 618                 }
 619                 if (yy->ss_finish)
 620                         addarc(d, yy->ss_rename, yy->ss_rename, 0);
 621         }
 622
 623         d->d_initial = 0;
 624 }
 625
 626
 627 /* PART FIVE -- GLUE IT ALL TOGETHER */
 628
 629 static grammar *
 630 maketables(nfagrammar *gr)
 631 {
 632         int i;
 633         nfa *nf;
 634         dfa *d;
 635         grammar *g;
 636
 637         if (gr->gr_nnfas == 0)
 638                 return NULL;
 639         g = newgrammar(gr->gr_nfa[0]->nf_type);
 640                         /* XXX first rule must be start rule */
 641         g->g_ll = gr->gr_ll;
 642
 643         for (i = 0; i < gr->gr_nnfas; i++) {
 644                 nf = gr->gr_nfa[i];
 645                 if (Py_DebugFlag) {
 646                         printf("Dump of NFA for '%s' ...\n", nf->nf_name);
 647                         dumpnfa(&gr->gr_ll, nf);
 648                 }
 649                 printf("Making DFA for '%s' ...\n", nf->nf_name);
 650                 d = adddfa(g, nf->nf_type, nf->nf_name);
 651                 makedfa(gr, gr->gr_nfa[i], d);
 652         }
 653
 654         return g;
 655 }
 656
 657 grammar *
 658 pgen(node *n)
 659 {
 660         nfagrammar *gr;
 661         grammar *g;
 662
 663         gr = metacompile(n);
 664         g = maketables(gr);
 665         translatelabels(g);
 666         addfirstsets(g);
 667         return g;
 668 }
 669
 670
 671 /*
 672
 673 Description
 674 -----------
 675
 676 Input is a grammar in extended BNF (using * for repetition, + for
 677 at-least-once repetition, [] for optional parts, | for alternatives and
 678 () for grouping).  This has already been parsed and turned into a parse
 679 tree.
 680
 681 Each rule is considered as a regular expression in its own right.
 682 It is turned into a Non-deterministic Finite Automaton (NFA), which
 683 is then turned into a Deterministic Finite Automaton (DFA), which is then
 684 optimized to reduce the number of states.  See [Aho&Ullman 77] chapter 3,
 685 or similar compiler books (this technique is more often used for lexical
 686 analyzers).
 687
 688 The DFA's are used by the parser as parsing tables in a special way
 689 that's probably unique.  Before they are usable, the FIRST sets of all
 690 non-terminals are computed.
 691
 692 Reference
 693 ---------
 694
 695 [Aho&Ullman 77]
 696         Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
 697         (first edition)
 698
 699 */