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) do { \ 140 if (i < count) { \ 141 fprintf(stderr, REQNFMT, count); \ 142 Py_FatalError("REQN"); \ 143 } \ 144 } while (0) 145 146 #else 147 #define REQN(i, count) /* empty */ 148 #endif 149 150 static nfagrammar * 151 metacompile(node *n) 152 { 153 nfagrammar *gr; 154 int i; 155 156 if (Py_DebugFlag) 157 printf("Compiling (meta-) parse tree into NFA grammar\n"); 158 gr = newnfagrammar(); 159 REQ(n, MSTART); 160 i = n->n_nchildren - 1; /* Last child is ENDMARKER */ 161 n = n->n_child; 162 for (; --i >= 0; n++) { 163 if (n->n_type != NEWLINE) 164 compile_rule(gr, n); 165 } 166 return gr; 167 } 168 169 static void 170 compile_rule(nfagrammar *gr, node *n) 171 { 172 nfa *nf; 173 174 REQ(n, RULE); 175 REQN(n->n_nchildren, 4); 176 n = n->n_child; 177 REQ(n, NAME); 178 nf = addnfa(gr, n->n_str); 179 n++; 180 REQ(n, COLON); 181 n++; 182 REQ(n, RHS); 183 compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish); 184 n++; 185 REQ(n, NEWLINE); 186 } 187 188 static void 189 compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb) 190 { 191 int i; 192 int a, b; 193 194 REQ(n, RHS); 195 i = n->n_nchildren; 196 REQN(i, 1); 197 n = n->n_child; 198 REQ(n, ALT); 199 compile_alt(ll, nf, n, pa, pb); 200 if (--i <= 0) 201 return; 202 n++; 203 a = *pa; 204 b = *pb; 205 *pa = addnfastate(nf); 206 *pb = addnfastate(nf); 207 addnfaarc(nf, *pa, a, EMPTY); 208 addnfaarc(nf, b, *pb, EMPTY); 209 for (; --i >= 0; n++) { 210 REQ(n, VBAR); 211 REQN(i, 1); 212 --i; 213 n++; 214 REQ(n, ALT); 215 compile_alt(ll, nf, n, &a, &b); 216 addnfaarc(nf, *pa, a, EMPTY); 217 addnfaarc(nf, b, *pb, EMPTY); 218 } 219 } 220 221 static void 222 compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb) 223 { 224 int i; 225 int a, b; 226 227 REQ(n, ALT); 228 i = n->n_nchildren; 229 REQN(i, 1); 230 n = n->n_child; 231 REQ(n, ITEM); 232 compile_item(ll, nf, n, pa, pb); 233 --i; 234 n++; 235 for (; --i >= 0; n++) { 236 REQ(n, ITEM); 237 compile_item(ll, nf, n, &a, &b); 238 addnfaarc(nf, *pb, a, EMPTY); 239 *pb = b; 240 } 241 } 242 243 static void 244 compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb) 245 { 246 int i; 247 int a, b; 248 249 REQ(n, ITEM); 250 i = n->n_nchildren; 251 REQN(i, 1); 252 n = n->n_child; 253 if (n->n_type == LSQB) { 254 REQN(i, 3); 255 n++; 256 REQ(n, RHS); 257 *pa = addnfastate(nf); 258 *pb = addnfastate(nf); 259 addnfaarc(nf, *pa, *pb, EMPTY); 260 compile_rhs(ll, nf, n, &a, &b); 261 addnfaarc(nf, *pa, a, EMPTY); 262 addnfaarc(nf, b, *pb, EMPTY); 263 REQN(i, 1); 264 n++; 265 REQ(n, RSQB); 266 } 267 else { 268 compile_atom(ll, nf, n, pa, pb); 269 if (--i <= 0) 270 return; 271 n++; 272 addnfaarc(nf, *pb, *pa, EMPTY); 273 if (n->n_type == STAR) 274 *pb = *pa; 275 else 276 REQ(n, PLUS); 277 } 278 } 279 280 static void 281 compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb) 282 { 283 int i; 284 285 REQ(n, ATOM); 286 i = n->n_nchildren; 287 (void)i; /* Don't warn about set but unused */ 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 struct _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 = (ss_state *)PyObject_MALLOC(sizeof(ss_state)); 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 size_t size; 420 yy = &xx_state[istate]; 421 ss = yy->ss_ss; 422 /* For all its states... */ 423 for (ibit = 0; ibit < nf->nf_nstates; ++ibit) { 424 if (!testbit(ss, ibit)) 425 continue; 426 st = &nf->nf_state[ibit]; 427 /* For all non-empty arcs from this state... */ 428 for (iarc = 0; iarc < st->st_narcs; iarc++) { 429 ar = &st->st_arc[iarc]; 430 if (ar->ar_label == EMPTY) 431 continue; 432 /* Look up in list of arcs from this state */ 433 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) { 434 zz = &yy->ss_arc[jarc]; 435 if (ar->ar_label == zz->sa_label) 436 goto found; 437 } 438 /* Add new arc for this state */ 439 size = sizeof(ss_arc) * (yy->ss_narcs + 1); 440 yy->ss_arc = (ss_arc *)PyObject_REALLOC( 441 yy->ss_arc, size); 442 if (yy->ss_arc == NULL) 443 Py_FatalError("out of mem"); 444 zz = &yy->ss_arc[yy->ss_narcs++]; 445 zz->sa_label = ar->ar_label; 446 zz->sa_bitset = newbitset(nbits); 447 zz->sa_arrow = -1; 448 found: ; 449 /* Add destination */ 450 addclosure(zz->sa_bitset, nf, ar->ar_arrow); 451 } 452 } 453 /* Now look up all the arrow states */ 454 for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) { 455 zz = &xx_state[istate].ss_arc[jarc]; 456 for (jstate = 0; jstate < xx_nstates; jstate++) { 457 if (samebitset(zz->sa_bitset, 458 xx_state[jstate].ss_ss, nbits)) { 459 zz->sa_arrow = jstate; 460 goto done; 461 } 462 } 463 size = sizeof(ss_state) * (xx_nstates + 1); 464 xx_state = (ss_state *)PyObject_REALLOC(xx_state, 465 size); 466 if (xx_state == NULL) 467 Py_FatalError("out of mem"); 468 zz->sa_arrow = xx_nstates; 469 yy = &xx_state[xx_nstates++]; 470 yy->ss_ss = zz->sa_bitset; 471 yy->ss_narcs = 0; 472 yy->ss_arc = NULL; 473 yy->ss_deleted = 0; 474 yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish); 475 done: ; 476 } 477 } 478 479 if (Py_DebugFlag) 480 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll, 481 "before minimizing"); 482 483 simplify(xx_nstates, xx_state); 484 485 if (Py_DebugFlag) 486 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll, 487 "after minimizing"); 488 489 convert(d, xx_nstates, xx_state); 490 491 /* XXX cleanup */ 492 PyObject_FREE(xx_state); 493 } 494 495 static void 496 printssdfa(int xx_nstates, ss_state *xx_state, int nbits, 497 labellist *ll, char *msg) 498 { 499 int i, ibit, iarc; 500 ss_state *yy; 501 ss_arc *zz; 502 503 printf("Subset DFA %s\n", msg); 504 for (i = 0; i < xx_nstates; i++) { 505 yy = &xx_state[i]; 506 if (yy->ss_deleted) 507 continue; 508 printf(" Subset %d", i); 509 if (yy->ss_finish) 510 printf(" (finish)"); 511 printf(" { "); 512 for (ibit = 0; ibit < nbits; ibit++) { 513 if (testbit(yy->ss_ss, ibit)) 514 printf("%d ", ibit); 515 } 516 printf("}\n"); 517 for (iarc = 0; iarc < yy->ss_narcs; iarc++) { 518 zz = &yy->ss_arc[iarc]; 519 printf(" Arc to state %d, label %s\n", 520 zz->sa_arrow, 521 PyGrammar_LabelRepr( 522 &ll->ll_label[zz->sa_label])); 523 } 524 } 525 } 526 527 528 /* PART THREE -- SIMPLIFY DFA */ 529 530 /* Simplify the DFA by repeatedly eliminating states that are 531 equivalent to another oner. This is NOT Algorithm 3.3 from 532 [Aho&Ullman 77]. It does not always finds the minimal DFA, 533 but it does usually make a much smaller one... (For an example 534 of sub-optimal behavior, try S: x a b+ | y a b+.) 535 */ 536 537 static int 538 samestate(ss_state *s1, ss_state *s2) 539 { 540 int i; 541 542 if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish) 543 return 0; 544 for (i = 0; i < s1->ss_narcs; i++) { 545 if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow || 546 s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label) 547 return 0; 548 } 549 return 1; 550 } 551 552 static void 553 renamestates(int xx_nstates, ss_state *xx_state, int from, int to) 554 { 555 int i, j; 556 557 if (Py_DebugFlag) 558 printf("Rename state %d to %d.\n", from, to); 559 for (i = 0; i < xx_nstates; i++) { 560 if (xx_state[i].ss_deleted) 561 continue; 562 for (j = 0; j < xx_state[i].ss_narcs; j++) { 563 if (xx_state[i].ss_arc[j].sa_arrow == from) 564 xx_state[i].ss_arc[j].sa_arrow = to; 565 } 566 } 567 } 568 569 static void 570 simplify(int xx_nstates, ss_state *xx_state) 571 { 572 int changes; 573 int i, j; 574 575 do { 576 changes = 0; 577 for (i = 1; i < xx_nstates; i++) { 578 if (xx_state[i].ss_deleted) 579 continue; 580 for (j = 0; j < i; j++) { 581 if (xx_state[j].ss_deleted) 582 continue; 583 if (samestate(&xx_state[i], &xx_state[j])) { 584 xx_state[i].ss_deleted++; 585 renamestates(xx_nstates, xx_state, 586 i, j); 587 changes++; 588 break; 589 } 590 } 591 } 592 } while (changes); 593 } 594 595 596 /* PART FOUR -- GENERATE PARSING TABLES */ 597 598 /* Convert the DFA into a grammar that can be used by our parser */ 599 600 static void 601 convert(dfa *d, int xx_nstates, ss_state *xx_state) 602 { 603 int i, j; 604 ss_state *yy; 605 ss_arc *zz; 606 607 for (i = 0; i < xx_nstates; i++) { 608 yy = &xx_state[i]; 609 if (yy->ss_deleted) 610 continue; 611 yy->ss_rename = addstate(d); 612 } 613 614 for (i = 0; i < xx_nstates; i++) { 615 yy = &xx_state[i]; 616 if (yy->ss_deleted) 617 continue; 618 for (j = 0; j < yy->ss_narcs; j++) { 619 zz = &yy->ss_arc[j]; 620 addarc(d, yy->ss_rename, 621 xx_state[zz->sa_arrow].ss_rename, 622 zz->sa_label); 623 } 624 if (yy->ss_finish) 625 addarc(d, yy->ss_rename, yy->ss_rename, 0); 626 } 627 628 d->d_initial = 0; 629 } 630 631 632 /* PART FIVE -- GLUE IT ALL TOGETHER */ 633 634 static grammar * 635 maketables(nfagrammar *gr) 636 { 637 int i; 638 nfa *nf; 639 dfa *d; 640 grammar *g; 641 642 if (gr->gr_nnfas == 0) 643 return NULL; 644 g = newgrammar(gr->gr_nfa[0]->nf_type); 645 /* XXX first rule must be start rule */ 646 g->g_ll = gr->gr_ll; 647 648 for (i = 0; i < gr->gr_nnfas; i++) { 649 nf = gr->gr_nfa[i]; 650 if (Py_DebugFlag) { 651 printf("Dump of NFA for '%s' ...\n", nf->nf_name); 652 dumpnfa(&gr->gr_ll, nf); 653 printf("Making DFA for '%s' ...\n", nf->nf_name); 654 } 655 d = adddfa(g, nf->nf_type, nf->nf_name); 656 makedfa(gr, gr->gr_nfa[i], d); 657 } 658 659 return g; 660 } 661 662 grammar * 663 pgen(node *n) 664 { 665 nfagrammar *gr; 666 grammar *g; 667 668 gr = metacompile(n); 669 g = maketables(gr); 670 translatelabels(g); 671 addfirstsets(g); 672 PyObject_FREE(gr); 673 return g; 674 } 675 676 grammar * 677 Py_pgen(node *n) 678 { 679 return pgen(n); 680 } 681 682 /* 683 684 Description 685 ----------- 686 687 Input is a grammar in extended BNF (using * for repetition, + for 688 at-least-once repetition, [] for optional parts, | for alternatives and 689 () for grouping). This has already been parsed and turned into a parse 690 tree. 691 692 Each rule is considered as a regular expression in its own right. 693 It is turned into a Non-deterministic Finite Automaton (NFA), which 694 is then turned into a Deterministic Finite Automaton (DFA), which is then 695 optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3, 696 or similar compiler books (this technique is more often used for lexical 697 analyzers). 698 699 The DFA's are used by the parser as parsing tables in a special way 700 that's probably unique. Before they are usable, the FIRST sets of all 701 non-terminals are computed. 702 703 Reference 704 --------- 705 706 [Aho&Ullman 77] 707 Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977 708 (first edition) 709 710 */ 711
