Parser/pgen.c

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