pgen.c revision bd311d8e4eba6c8f9a24a068861aed2da88f5d4a
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 13extern int Py_DebugFlag; 14extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */ 15 16 17/* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */ 18 19typedef struct _nfaarc { 20 int ar_label; 21 int ar_arrow; 22} nfaarc; 23 24typedef struct _nfastate { 25 int st_narcs; 26 nfaarc *st_arc; 27} nfastate; 28 29typedef 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 */ 38static void compile_rhs(labellist *ll, 39 nfa *nf, node *n, int *pa, int *pb); 40static void compile_alt(labellist *ll, 41 nfa *nf, node *n, int *pa, int *pb); 42static void compile_item(labellist *ll, 43 nfa *nf, node *n, int *pa, int *pb); 44static void compile_atom(labellist *ll, 45 nfa *nf, node *n, int *pa, int *pb); 46 47static int 48addnfastate(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 61static void 62addnfaarc(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 76static nfa * 77newnfa(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 93typedef struct _nfagrammar { 94 int gr_nnfas; 95 nfa **gr_nfa; 96 labellist gr_ll; 97} nfagrammar; 98 99/* Forward */ 100static void compile_rule(nfagrammar *gr, node *n); 101 102static nfagrammar * 103newnfagrammar(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 118static nfa * 119addnfa(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 134static 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 146static nfagrammar * 147metacompile(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 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 REQ(n, ITEM); 233 compile_item(ll, nf, n, &a, &b); 234 addnfaarc(nf, *pb, a, EMPTY); 235 *pb = b; 236 } 237} 238 239static void 240compile_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 276static void 277compile_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 302static void 303dumpstate(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 325static void 326dumpnfa(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 339static void 340addclosure(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 355typedef struct _ss_arc { 356 bitset sa_bitset; 357 int sa_arrow; 358 int sa_label; 359} ss_arc; 360 361typedef 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 370typedef struct _ss_dfa { 371 int sd_nstates; 372 ss_state *sd_state; 373} ss_dfa; 374 375/* Forward */ 376static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits, 377 labellist *ll, char *msg); 378static void simplify(int xx_nstates, ss_state *xx_state); 379static void convert(dfa *d, int xx_nstates, ss_state *xx_state); 380 381static void 382makedfa(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 485static void 486printssdfa(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 527static int 528samestate(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 542static void 543renamestates(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 559static void 560simplify(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 590static void 591convert(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 624static grammar * 625maketables(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 652grammar * 653pgen(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 665grammar * 666Py_pgen(node *n) 667{ 668 return pgen(n); 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