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