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