pgen.c revision 8586991099e4ace18ee94163a96b8ea1bed77ebe
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 15extern int Py_DebugFlag; 16 17 18/* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */ 19 20typedef struct _nfaarc { 21 int ar_label; 22 int ar_arrow; 23} nfaarc; 24 25typedef struct _nfastate { 26 int st_narcs; 27 nfaarc *st_arc; 28} nfastate; 29 30typedef 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 */ 39static void compile_rhs(labellist *ll, 40 nfa *nf, node *n, int *pa, int *pb); 41static void compile_alt(labellist *ll, 42 nfa *nf, node *n, int *pa, int *pb); 43static void compile_item(labellist *ll, 44 nfa *nf, node *n, int *pa, int *pb); 45static void compile_atom(labellist *ll, 46 nfa *nf, node *n, int *pa, int *pb); 47 48static int 49addnfastate(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 62static void 63addnfaarc(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 77static nfa * 78newnfa(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 94typedef struct _nfagrammar { 95 int gr_nnfas; 96 nfa **gr_nfa; 97 labellist gr_ll; 98} nfagrammar; 99 100/* Forward */ 101static void compile_rule(nfagrammar *gr, node *n); 102 103static nfagrammar * 104newnfagrammar(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 119static nfa * 120addnfa(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 135static 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 147static nfagrammar * 148metacompile(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 165static void 166compile_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 184static void 185compile_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 217static void 218compile_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 244static void 245compile_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 281static void 282compile_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 307static void 308dumpstate(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 330static void 331dumpnfa(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 344static void 345addclosure(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 360typedef struct _ss_arc { 361 bitset sa_bitset; 362 int sa_arrow; 363 int sa_label; 364} ss_arc; 365 366typedef 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 375typedef struct _ss_dfa { 376 int sd_nstates; 377 ss_state *sd_state; 378} ss_dfa; 379 380/* Forward */ 381static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits, 382 labellist *ll, char *msg); 383static void simplify(int xx_nstates, ss_state *xx_state); 384static void convert(dfa *d, int xx_nstates, ss_state *xx_state); 385 386static void 387makedfa(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 490static void 491printssdfa(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 532static int 533samestate(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 547static void 548renamestates(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 564static void 565simplify(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 595static void 596convert(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 629static grammar * 630maketables(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 657grammar * 658pgen(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 673Description 674----------- 675 676Input is a grammar in extended BNF (using * for repetition, + for 677at-least-once repetition, [] for optional parts, | for alternatives and 678() for grouping). This has already been parsed and turned into a parse 679tree. 680 681Each rule is considered as a regular expression in its own right. 682It is turned into a Non-deterministic Finite Automaton (NFA), which 683is then turned into a Deterministic Finite Automaton (DFA), which is then 684optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3, 685or similar compiler books (this technique is more often used for lexical 686analyzers). 687 688The DFA's are used by the parser as parsing tables in a special way 689that's probably unique. Before they are usable, the FIRST sets of all 690non-terminals are computed. 691 692Reference 693--------- 694 695[Aho&Ullman 77] 696 Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977 697 (first edition) 698 699*/ 700