1 #ifdef _WIN32 2 #include <windows.h> 3 #include <io.h> 4 #endif 5 #include <stdlib.h> 6 #include <string.h> 7 #include <ctype.h> 8 #include "tools/re2c/substr.h" 9 #include "tools/re2c/globals.h" 10 #include "tools/re2c/dfa.h" 11 #include "tools/re2c/parse.h" 12 13 #ifdef _WIN32 14 /* tmpfile() replacment for Windows. 15 * 16 * On Windows tmpfile() creates the file in the root directory. This 17 * may fail due to unsufficient privileges. 18 */ 19 static FILE * 20 win32_tmpfile (void) 21 { 22 DWORD path_len; 23 WCHAR path_name[MAX_PATH + 1]; 24 WCHAR file_name[MAX_PATH + 1]; 25 HANDLE handle; 26 int fd; 27 FILE *fp; 28 29 path_len = GetTempPathW (MAX_PATH, path_name); 30 if (path_len <= 0 || path_len >= MAX_PATH) 31 return NULL; 32 33 if (GetTempFileNameW (path_name, L"ps_", 0, file_name) == 0) 34 return NULL; 35 36 handle = CreateFileW (file_name, 37 GENERIC_READ | GENERIC_WRITE, 38 0, 39 NULL, 40 CREATE_ALWAYS, 41 FILE_ATTRIBUTE_NORMAL | FILE_FLAG_DELETE_ON_CLOSE, 42 NULL); 43 if (handle == INVALID_HANDLE_VALUE) { 44 DeleteFileW (file_name); 45 return NULL; 46 } 47 48 fd = _open_osfhandle((intptr_t) handle, 0); 49 if (fd < 0) { 50 CloseHandle (handle); 51 return NULL; 52 } 53 54 fp = fdopen(fd, "w+b"); 55 if (fp == NULL) { 56 _close(fd); 57 return NULL; 58 } 59 60 return fp; 61 } 62 #endif 63 64 static void useLabel(size_t value) { 65 while (value >= vUsedLabelAlloc) { 66 vUsedLabels = realloc(vUsedLabels, vUsedLabelAlloc * 2); 67 if (!vUsedLabels) { 68 fputs("Out of memory.\n", stderr); 69 exit(EXIT_FAILURE); 70 } 71 memset(vUsedLabels + vUsedLabelAlloc, 0, vUsedLabelAlloc); 72 vUsedLabelAlloc *= 2; 73 } 74 vUsedLabels[value] = 1; 75 } 76 77 /* there must be at least one span in list; all spans must cover 78 * same range 79 */ 80 81 void Go_compact(Go *g){ 82 /* arrange so that adjacent spans have different targets */ 83 unsigned int i = 0, j; 84 for(j = 1; j < g->nSpans; ++j){ 85 if(g->span[j].to != g->span[i].to){ 86 ++i; g->span[i].to = g->span[j].to; 87 } 88 g->span[i].ub = g->span[j].ub; 89 } 90 g->nSpans = i + 1; 91 } 92 93 void Go_unmap(Go *g, Go *base, State *x){ 94 Span *s = g->span, *b = base->span, *e = &b[base->nSpans]; 95 unsigned int lb = 0; 96 s->ub = 0; 97 s->to = NULL; 98 for(; b != e; ++b){ 99 if(b->to == x){ 100 if((s->ub - lb) > 1) 101 s->ub = b->ub; 102 } else { 103 if(b->to != s->to){ 104 if(s->ub){ 105 lb = s->ub; ++s; 106 } 107 s->to = b->to; 108 } 109 s->ub = b->ub; 110 } 111 } 112 s->ub = e[-1].ub; ++s; 113 g->nSpans = s - g->span; 114 } 115 116 static void doGen(Go *g, State *s, unsigned char *bm, unsigned char m){ 117 Span *b = g->span, *e = &b[g->nSpans]; 118 unsigned int lb = 0; 119 for(; b < e; ++b){ 120 if(b->to == s) 121 for(; lb < b->ub; ++lb) bm[lb] |= m; 122 lb = b->ub; 123 } 124 } 125 #if 0 126 static void prt(FILE *o, Go *g, State *s){ 127 Span *b = g->span, *e = &b[g->nSpans]; 128 unsigned int lb = 0; 129 for(; b < e; ++b){ 130 if(b->to == s) 131 printSpan(o, lb, b->ub); 132 lb = b->ub; 133 } 134 } 135 #endif 136 static int matches(Go *g1, State *s1, Go *g2, State *s2){ 137 Span *b1 = g1->span, *e1 = &b1[g1->nSpans]; 138 unsigned int lb1 = 0; 139 Span *b2 = g2->span, *e2 = &b2[g2->nSpans]; 140 unsigned int lb2 = 0; 141 for(;;){ 142 for(; b1 < e1 && b1->to != s1; ++b1) lb1 = b1->ub; 143 for(; b2 < e2 && b2->to != s2; ++b2) lb2 = b2->ub; 144 if(b1 == e1) return b2 == e2; 145 if(b2 == e2) return 0; 146 if(lb1 != lb2 || b1->ub != b2->ub) return 0; 147 ++b1; ++b2; 148 } 149 } 150 151 typedef struct BitMap { 152 Go *go; 153 State *on; 154 struct BitMap *next; 155 unsigned int i; 156 unsigned char m; 157 } BitMap; 158 159 static BitMap *BitMap_find_go(Go*, State*); 160 static BitMap *BitMap_find(State*); 161 static void BitMap_gen(FILE *, unsigned int, unsigned int); 162 /* static void BitMap_stats(void);*/ 163 static BitMap *BitMap_new(Go*, State*); 164 165 static BitMap *BitMap_first = NULL; 166 167 BitMap * 168 BitMap_new(Go *g, State *x) 169 { 170 BitMap *b = malloc(sizeof(BitMap)); 171 b->go = g; 172 b->on = x; 173 b->next = BitMap_first; 174 BitMap_first = b; 175 return b; 176 } 177 178 BitMap * 179 BitMap_find_go(Go *g, State *x){ 180 BitMap *b; 181 for(b = BitMap_first; b; b = b->next){ 182 if(matches(b->go, b->on, g, x)) 183 return b; 184 } 185 return BitMap_new(g, x); 186 } 187 188 BitMap * 189 BitMap_find(State *x){ 190 BitMap *b; 191 for(b = BitMap_first; b; b = b->next){ 192 if(b->on == x) 193 return b; 194 } 195 return NULL; 196 } 197 198 void BitMap_gen(FILE *o, unsigned int lb, unsigned int ub){ 199 BitMap *b = BitMap_first; 200 if(b){ 201 unsigned int n = ub - lb; 202 unsigned int i; 203 unsigned char *bm = malloc(sizeof(unsigned char)*n); 204 fputs("\tstatic unsigned char yybm[] = {", o); 205 for(i = 0; b; i += n){ 206 unsigned char m; 207 unsigned int j; 208 memset(bm, 0, n); 209 for(m = 0x80; b && m; b = b->next, m >>= 1){ 210 b->i = i; b->m = m; 211 doGen(b->go, b->on, bm-lb, m); 212 } 213 for(j = 0; j < n; ++j){ 214 if(j%8 == 0) {fputs("\n\t", o); oline++;} 215 fprintf(o, "%3u, ", (unsigned int) bm[j]); 216 } 217 } 218 fputs("\n\t};\n", o); oline+=2; 219 free(bm); 220 } 221 } 222 223 #if 0 224 void BitMap_stats(void){ 225 unsigned int n = 0; 226 BitMap *b; 227 for(b = BitMap_first; b; b = b->next){ 228 prt(stderr, b->go, b->on); fputs("\n", stderr); 229 ++n; 230 } 231 fprintf(stderr, "%u bitmaps\n", n); 232 BitMap_first = NULL; 233 } 234 #endif 235 236 static void genGoTo(FILE *o, State *from, State *to, int *readCh, 237 const char *indent) 238 { 239 #if 0 240 if (*readCh && from->label + 1 != to->label) 241 { 242 fputs("%syych = *YYCURSOR;\n", indent, o); oline++; 243 *readCh = 0; 244 } 245 #endif 246 fprintf(o, "%sgoto yy%u;\n", indent, to->label); oline++; 247 useLabel(to->label); 248 } 249 250 static void genIf(FILE *o, const char *cmp, unsigned int v, int *readCh) 251 { 252 #if 0 253 if (*readCh) 254 { 255 fputs("\tif((yych = *YYCURSOR) ", o); 256 *readCh = 0; 257 } else { 258 #endif 259 fputs("\tif(yych ", o); 260 #if 0 261 } 262 #endif 263 fprintf(o, "%s '", cmp); 264 prtCh(o, v); 265 fputs("')", o); 266 } 267 268 static void indent(FILE *o, unsigned int i){ 269 while(i-- > 0) 270 fputc('\t', o); 271 } 272 273 static void need(FILE *o, unsigned int n, int *readCh) 274 { 275 unsigned int fillIndex; 276 int hasFillIndex = (0<=vFillIndexes); 277 if (hasFillIndex) { 278 fillIndex = vFillIndexes++; 279 fprintf(o, "\tYYSETSTATE(%u);\n", fillIndex); 280 ++oline; 281 } 282 283 if(n == 1) { 284 fputs("\tif(YYLIMIT == YYCURSOR) YYFILL(1);\n", o); oline++; 285 } else { 286 fprintf(o, "\tif((YYLIMIT - YYCURSOR) < %u) YYFILL(%u);\n", n, n); 287 oline++; 288 } 289 290 if (hasFillIndex) { 291 fprintf(o, "yyFillLabel%u:\n", fillIndex); 292 ++oline; 293 } 294 295 fputs("\tyych = *YYCURSOR;\n", o); oline++; 296 *readCh = 0; 297 } 298 299 void 300 Action_emit(Action *a, FILE *o, int *readCh) 301 { 302 int first = 1; 303 unsigned int i; 304 unsigned int back; 305 306 switch (a->type) { 307 case MATCHACT: 308 if(a->state->link){ 309 fputs("\t++YYCURSOR;\n", o); 310 need(o, a->state->depth, readCh); 311 #if 0 312 } else if (!Action_readAhead(a)) { 313 /* do not read next char if match */ 314 fputs("\t++YYCURSOR;\n", o); 315 *readCh = 1; 316 #endif 317 } else { 318 fputs("\tyych = *++YYCURSOR;\n", o); 319 *readCh = 0; 320 } 321 oline++; 322 break; 323 case ENTERACT: 324 if(a->state->link){ 325 fputs("\t++YYCURSOR;\n", o); 326 fprintf(o, "yy%u:\n", a->d.label); oline+=2; 327 need(o, a->state->depth, readCh); 328 } else { 329 /* we shouldn't need 'rule-following' protection here */ 330 fputs("\tyych = *++YYCURSOR;\n", o); 331 fprintf(o, "yy%u:\n", a->d.label); oline+=2; 332 *readCh = 0; 333 } 334 break; 335 case SAVEMATCHACT: 336 if (bUsedYYAccept) { 337 fprintf(o, "\tyyaccept = %u;\n", a->d.selector); 338 oline++; 339 } 340 if(a->state->link){ 341 fputs("\tYYMARKER = ++YYCURSOR;\n", o); oline++; 342 need(o, a->state->depth, readCh); 343 } else { 344 fputs("\tyych = *(YYMARKER = ++YYCURSOR);\n", o); oline++; 345 *readCh = 0; 346 } 347 break; 348 case MOVEACT: 349 break; 350 case ACCEPTACT: 351 for(i = 0; i < a->d.Accept.nRules; ++i) 352 if(a->d.Accept.saves[i] != ~0u){ 353 if(first){ 354 first = 0; 355 bUsedYYAccept = 1; 356 fputs("\tYYCURSOR = YYMARKER;\n", o); 357 fputs("\tswitch(yyaccept){\n", o); oline+=2; 358 } 359 fprintf(o, "\tcase %u:", a->d.Accept.saves[i]); 360 genGoTo(o, a->state, a->d.Accept.rules[i], readCh, "\t"); 361 } 362 if(!first) { 363 fputs("\t}\n", o); oline++; 364 } 365 break; 366 case RULEACT: 367 back = RegExp_fixedLength(a->d.rule->d.RuleOp.ctx); 368 if(back != ~0u && back > 0u) 369 fprintf(o, "\tYYCURSOR -= %u;", back); 370 fprintf(o, "\n"); oline++; 371 line_source(o, a->d.rule->d.RuleOp.code->line); 372 SubStr_out(&a->d.rule->d.RuleOp.code->text, o); 373 fprintf(o, "\n"); oline++; 374 if (!iFlag) 375 fprintf(o, "#line %u \"%s\"\n", oline++, outputFileName); 376 break; 377 } 378 } 379 380 Action * 381 Action_new_Accept(State *x, unsigned int n, unsigned int *s, State **r) 382 { 383 Action *a = malloc(sizeof(Action)); 384 a->type = ACCEPTACT; 385 a->state = x; 386 a->d.Accept.nRules = n; 387 a->d.Accept.saves = s; 388 a->d.Accept.rules = r; 389 x->action = a; 390 return a; 391 } 392 393 static void doLinear(FILE *o, unsigned int i, Span *s, unsigned int n, 394 State *from, State *next, int *readCh){ 395 for(;;){ 396 State *bg = s[0].to; 397 while(n >= 3 && s[2].to == bg && (s[1].ub - s[0].ub) == 1){ 398 if(s[1].to == next && n == 3){ 399 indent(o, i); 400 genIf(o, "!=", s[0].ub, readCh); 401 genGoTo(o, from, bg, readCh, "\t"); 402 indent(o, i); 403 genGoTo(o, from, next, readCh, "\t"); 404 return; 405 } else { 406 indent(o, i); 407 genIf(o, "==", s[0].ub, readCh); 408 genGoTo(o, from, s[1].to, readCh, "\t"); 409 } 410 n -= 2; s += 2; 411 } 412 if(n == 1){ 413 indent(o, i); 414 genGoTo(o, from, s[0].to, readCh, "\t"); 415 return; 416 } else if(n == 2 && bg == next){ 417 indent(o, i); 418 genIf(o, ">=", s[0].ub, readCh); 419 genGoTo(o, from, s[1].to, readCh, "\t"); 420 indent(o, i); 421 genGoTo(o, from, next, readCh, "\t"); 422 return; 423 } else { 424 indent(o, i); 425 genIf(o, "<=", s[0].ub - 1, readCh); 426 genGoTo(o, from, bg, readCh, "\t"); 427 n -= 1; s += 1; 428 } 429 } 430 indent(o, i); 431 genGoTo(o, from, next, readCh, "\t"); 432 } 433 434 void 435 Go_genLinear(Go *g, FILE *o, State *from, State *next, int *readCh){ 436 doLinear(o, 0, g->span, g->nSpans, from, next, readCh); 437 } 438 439 static void genCases(FILE *o, unsigned int lb, Span *s){ 440 if(lb < s->ub){ 441 for(;;){ 442 fputs("\tcase '", o); prtCh(o, lb); fputs("':", o); 443 if(++lb == s->ub) 444 break; 445 fputs("\n", o); oline++; 446 } 447 } 448 } 449 450 void 451 Go_genSwitch(Go *g, FILE *o, State *from, State *next, int *readCh){ 452 if(g->nSpans <= 2){ 453 Go_genLinear(g, o, from, next, readCh); 454 } else { 455 State *def = g->span[g->nSpans-1].to; 456 Span **sP = malloc(sizeof(Span*)*(g->nSpans-1)), **r, **s, **t; 457 unsigned int i; 458 459 t = &sP[0]; 460 for(i = 0; i < g->nSpans; ++i) 461 if(g->span[i].to != def) 462 *(t++) = &g->span[i]; 463 464 if (dFlag) 465 fputs("\tYYDEBUG(-1, yych);\n", o); 466 467 #if 0 468 if (*readCh) { 469 fputs("\tswitch((yych = *YYCURSOR)) {\n", o); 470 *readCh = 0; 471 } else 472 #endif 473 fputs("\tswitch(yych){\n", o); 474 oline++; 475 while(t != &sP[0]){ 476 State *to; 477 r = s = &sP[0]; 478 if(*s == &g->span[0]) 479 genCases(o, 0, *s); 480 else 481 genCases(o, (*s)[-1].ub, *s); 482 to = (*s)->to; 483 while(++s < t){ 484 if((*s)->to == to) 485 genCases(o, (*s)[-1].ub, *s); 486 else 487 *(r++) = *s; 488 } 489 genGoTo(o, from, to, readCh, "\t"); 490 t = r; 491 } 492 fputs("\tdefault:", o); 493 genGoTo(o, from, def, readCh, "\t"); 494 fputs("\t}\n", o); oline++; 495 496 free(sP); 497 } 498 } 499 500 static void doBinary(FILE *o, unsigned int i, Span *s, unsigned int n, 501 State *from, State *next, int *readCh){ 502 if(n <= 4){ 503 doLinear(o, i, s, n, from, next, readCh); 504 } else { 505 unsigned int h = n/2; 506 indent(o, i); 507 genIf(o, "<=", s[h-1].ub - 1, readCh); 508 fputs("{\n", o); oline++; 509 doBinary(o, i+1, &s[0], h, from, next, readCh); 510 indent(o, i); fputs("\t} else {\n", o); oline++; 511 doBinary(o, i+1, &s[h], n - h, from, next, readCh); 512 indent(o, i); fputs("\t}\n", o); oline++; 513 } 514 } 515 516 void 517 Go_genBinary(Go *g, FILE *o, State *from, State *next, int *readCh){ 518 doBinary(o, 0, g->span, g->nSpans, from, next, readCh); 519 } 520 521 void 522 Go_genBase(Go *g, FILE *o, State *from, State *next, int *readCh){ 523 if(g->nSpans == 0) 524 return; 525 if(!sFlag){ 526 Go_genSwitch(g, o, from, next, readCh); 527 return; 528 } 529 if(g->nSpans > 8){ 530 Span *bot = &g->span[0], *top = &g->span[g->nSpans-1]; 531 unsigned int util; 532 if(bot[0].to == top[0].to){ 533 util = (top[-1].ub - bot[0].ub)/(g->nSpans - 2); 534 } else { 535 if(bot[0].ub > (top[0].ub - top[-1].ub)){ 536 util = (top[0].ub - bot[0].ub)/(g->nSpans - 1); 537 } else { 538 util = top[-1].ub/(g->nSpans - 1); 539 } 540 } 541 if(util <= 2){ 542 Go_genSwitch(g, o, from, next, readCh); 543 return; 544 } 545 } 546 if(g->nSpans > 5){ 547 Go_genBinary(g, o, from, next, readCh); 548 } else { 549 Go_genLinear(g, o, from, next, readCh); 550 } 551 } 552 553 void 554 Go_genGoto(Go *g, FILE *o, State *from, State *next, int *readCh){ 555 unsigned int i; 556 if(bFlag){ 557 for(i = 0; i < g->nSpans; ++i){ 558 State *to = g->span[i].to; 559 if(to && to->isBase){ 560 BitMap *b = BitMap_find(to); 561 if(b && matches(b->go, b->on, g, to)){ 562 Go go; 563 go.span = malloc(sizeof(Span)*g->nSpans); 564 Go_unmap(&go, g, to); 565 fprintf(o, "\tif(yybm[%u+", b->i); 566 #if 0 567 if (*readCh) 568 fputs("(yych = *YYCURSOR)", o); 569 else 570 #endif 571 fputs("yych", o); 572 fprintf(o, "] & %u) {\n", (unsigned int) b->m); oline++; 573 genGoTo(o, from, to, readCh, "\t\t"); 574 fputs("\t}\n", o); oline++; 575 Go_genBase(&go, o, from, next, readCh); 576 free(go.span); 577 return; 578 } 579 } 580 } 581 } 582 Go_genBase(g, o, from, next, readCh); 583 } 584 585 void State_emit(State *s, FILE *o, int *readCh){ 586 if (vUsedLabels[s->label]) 587 fprintf(o, "yy%u:", s->label); 588 if (dFlag) 589 fprintf(o, "\n\tYYDEBUG(%u, *YYCURSOR);\n", s->label); 590 Action_emit(s->action, o, readCh); 591 } 592 593 static unsigned int merge(Span *x0, State *fg, State *bg){ 594 Span *x = x0, *f = fg->go.span, *b = bg->go.span; 595 unsigned int nf = fg->go.nSpans, nb = bg->go.nSpans; 596 State *prev = NULL, *to; 597 /* NB: we assume both spans are for same range */ 598 for(;;){ 599 if(f->ub == b->ub){ 600 to = f->to == b->to? bg : f->to; 601 if(to == prev){ 602 --x; 603 } else { 604 x->to = prev = to; 605 } 606 x->ub = f->ub; 607 ++x; ++f; --nf; ++b; --nb; 608 if(nf == 0 && nb == 0) 609 return x - x0; 610 } 611 while(f->ub < b->ub){ 612 to = f->to == b->to? bg : f->to; 613 if(to == prev){ 614 --x; 615 } else { 616 x->to = prev = to; 617 } 618 x->ub = f->ub; 619 ++x; ++f; --nf; 620 } 621 while(b->ub < f->ub){ 622 to = b->to == f->to? bg : f->to; 623 if(to == prev){ 624 --x; 625 } else { 626 x->to = prev = to; 627 } 628 x->ub = b->ub; 629 ++x; ++b; --nb; 630 } 631 } 632 } 633 634 const unsigned int cInfinity = ~0; 635 636 typedef struct SCC { 637 State **top, **stk; 638 } SCC; 639 640 static void SCC_init(SCC*, unsigned int); 641 static SCC *SCC_new(unsigned int); 642 static void SCC_destroy(SCC*); 643 static void SCC_delete(SCC*); 644 static void SCC_traverse(SCC*, State*); 645 646 static void 647 SCC_init(SCC *s, unsigned int size) 648 { 649 s->top = s->stk = malloc(sizeof(State*)*size); 650 } 651 652 static SCC * 653 SCC_new(unsigned int size){ 654 SCC *s = malloc(sizeof(SCC)); 655 s->top = s->stk = malloc(sizeof(State*)*size); 656 return s; 657 } 658 659 static void 660 SCC_destroy(SCC *s){ 661 free(s->stk); 662 } 663 664 static void 665 SCC_delete(SCC *s){ 666 free(s->stk); 667 free(s); 668 } 669 670 static void SCC_traverse(SCC *s, State *x){ 671 unsigned int k, i; 672 673 *s->top = x; 674 k = ++s->top - s->stk; 675 x->depth = k; 676 for(i = 0; i < x->go.nSpans; ++i){ 677 State *y = x->go.span[i].to; 678 if(y){ 679 if(y->depth == 0) 680 SCC_traverse(s, y); 681 if(y->depth < x->depth) 682 x->depth = y->depth; 683 } 684 } 685 if(x->depth == k) 686 do { 687 (*--s->top)->depth = cInfinity; 688 (*s->top)->link = x; 689 } while(*s->top != x); 690 } 691 692 static unsigned int maxDist(State *s){ 693 unsigned int mm = 0, i; 694 for(i = 0; i < s->go.nSpans; ++i){ 695 State *t = s->go.span[i].to; 696 if(t){ 697 unsigned int m = 1; 698 if(!t->link) { 699 if (t->depth == -1) 700 t->depth = maxDist(t); 701 m += t->depth; 702 } 703 if(m > mm) 704 mm = m; 705 } 706 } 707 return mm; 708 } 709 710 static void calcDepth(State *head){ 711 State *t, *s; 712 for(s = head; s; s = s->next){ 713 if(s->link == s){ 714 unsigned int i; 715 for(i = 0; i < s->go.nSpans; ++i){ 716 t = s->go.span[i].to; 717 if(t && t->link == s) 718 goto inSCC; 719 } 720 s->link = NULL; 721 } else { 722 inSCC: 723 s->depth = maxDist(s); 724 } 725 } 726 } 727 728 void DFA_findSCCs(DFA *d){ 729 SCC scc; 730 State *s; 731 732 SCC_init(&scc, d->nStates); 733 for(s = d->head; s; s = s->next){ 734 s->depth = 0; 735 s->link = NULL; 736 } 737 738 for(s = d->head; s; s = s->next) 739 if(!s->depth) 740 SCC_traverse(&scc, s); 741 742 calcDepth(d->head); 743 744 SCC_destroy(&scc); 745 } 746 747 void DFA_split(DFA *d, State *s){ 748 State *move = State_new(); 749 Action_new_Move(move); 750 DFA_addState(d, &s->next, move); 751 move->link = s->link; 752 move->rule = s->rule; 753 move->go = s->go; 754 s->rule = NULL; 755 s->go.nSpans = 1; 756 s->go.span = malloc(sizeof(Span)); 757 s->go.span[0].ub = d->ubChar; 758 s->go.span[0].to = move; 759 } 760 761 void DFA_emit(DFA *d, FILE *o){ 762 static unsigned int label = 0; 763 State *s; 764 unsigned int i, bitmap_brace = 0; 765 unsigned int nRules = 0; 766 unsigned int nSaves = 0; 767 unsigned int *saves; 768 unsigned int nOrgOline; 769 State **rules; 770 State *accept = NULL; 771 Span *span; 772 FILE *tmpo; 773 int hasFillLabels; 774 int maxFillIndexes, orgVFillIndexes; 775 unsigned int start_label; 776 777 hasFillLabels = (0<=vFillIndexes); 778 if (hasFillLabels && label!=0) { 779 fputs("re2c : error : multiple /*!re2c blocks aren't supported when -f is specified\n", stderr); 780 exit(1); 781 } 782 783 DFA_findSCCs(d); 784 d->head->link = d->head; 785 786 maxFill = 1; 787 for(s = d->head; s; s = s->next) { 788 s->depth = maxDist(s); 789 if (maxFill < s->depth) 790 maxFill = s->depth; 791 if(s->rule && s->rule->d.RuleOp.accept >= nRules) 792 nRules = s->rule->d.RuleOp.accept + 1; 793 } 794 795 saves = malloc(sizeof(unsigned int)*nRules); 796 memset(saves, ~0, (nRules)*sizeof(unsigned int)); 797 798 /* mark backtracking points */ 799 for(s = d->head; s; s = s->next){ 800 RegExp *ignore = NULL;/*RuleOp*/ 801 if(s->rule){ 802 for(i = 0; i < s->go.nSpans; ++i) 803 if(s->go.span[i].to && !s->go.span[i].to->rule){ 804 free(s->action); 805 if(saves[s->rule->d.RuleOp.accept] == ~0u) 806 saves[s->rule->d.RuleOp.accept] = nSaves++; 807 Action_new_Save(s, saves[s->rule->d.RuleOp.accept]); 808 continue; 809 } 810 ignore = s->rule; 811 } 812 } 813 814 /* insert actions */ 815 rules = malloc(sizeof(State*)*nRules); 816 memset(rules, 0, (nRules)*sizeof(State*)); 817 for(s = d->head; s; s = s->next){ 818 State *ow; 819 if(!s->rule){ 820 ow = accept; 821 } else { 822 if(!rules[s->rule->d.RuleOp.accept]){ 823 State *n = State_new(); 824 Action_new_Rule(n, s->rule); 825 rules[s->rule->d.RuleOp.accept] = n; 826 DFA_addState(d, &s->next, n); 827 } 828 ow = rules[s->rule->d.RuleOp.accept]; 829 } 830 for(i = 0; i < s->go.nSpans; ++i) 831 if(!s->go.span[i].to){ 832 if(!ow){ 833 ow = accept = State_new(); 834 Action_new_Accept(accept, nRules, saves, rules); 835 DFA_addState(d, &s->next, accept); 836 } 837 s->go.span[i].to = ow; 838 } 839 } 840 841 /* split ``base'' states into two parts */ 842 for(s = d->head; s; s = s->next){ 843 s->isBase = 0; 844 if(s->link){ 845 for(i = 0; i < s->go.nSpans; ++i){ 846 if(s->go.span[i].to == s){ 847 s->isBase = 1; 848 DFA_split(d, s); 849 if(bFlag) 850 BitMap_find_go(&s->next->go, s); 851 s = s->next; 852 break; 853 } 854 } 855 } 856 } 857 858 /* find ``base'' state, if possible */ 859 span = malloc(sizeof(Span)*(d->ubChar - d->lbChar)); 860 for(s = d->head; s; s = s->next){ 861 if(!s->link){ 862 for(i = 0; i < s->go.nSpans; ++i){ 863 State *to = s->go.span[i].to; 864 if(to && to->isBase){ 865 unsigned int nSpans; 866 to = to->go.span[0].to; 867 nSpans = merge(span, s, to); 868 if(nSpans < s->go.nSpans){ 869 free(s->go.span); 870 s->go.nSpans = nSpans; 871 s->go.span = malloc(sizeof(Span)*nSpans); 872 memcpy(s->go.span, span, nSpans*sizeof(Span)); 873 } 874 break; 875 } 876 } 877 } 878 } 879 free(span); 880 881 free(d->head->action); 882 883 if(bFlag) { 884 fputs("{\n", o); 885 oline++; 886 bitmap_brace = 1; 887 BitMap_gen(o, d->lbChar, d->ubChar); 888 } 889 890 bUsedYYAccept = 0; 891 892 start_label = label; 893 894 Action_new_Enter(d->head, label++); 895 896 for(s = d->head; s; s = s->next) 897 s->label = label++; 898 899 nOrgOline = oline; 900 maxFillIndexes = vFillIndexes; 901 orgVFillIndexes = vFillIndexes; 902 #ifdef _WIN32 903 tmpo = win32_tmpfile(); 904 #else 905 tmpo = tmpfile(); 906 #endif 907 for(s = d->head; s; s = s->next){ 908 int readCh = 0; 909 State_emit(s, tmpo, &readCh); 910 Go_genGoto(&s->go, tmpo, s, s->next, &readCh); 911 } 912 fclose(tmpo); 913 maxFillIndexes = vFillIndexes; 914 vFillIndexes = orgVFillIndexes; 915 oline = nOrgOline; 916 917 fputs("\n", o); 918 oline++; 919 if (!iFlag) 920 fprintf(o, "#line %u \"%s\"\n", oline++, outputFileName); 921 922 if (!hasFillLabels) { 923 fputs("{\n\tYYCTYPE yych;\n", o); 924 oline += 2; 925 if (bUsedYYAccept) { 926 fputs("\tunsigned int yyaccept;\n", o); 927 oline++; 928 } 929 } else { 930 fputs("{\n\n", o); 931 oline += 2; 932 } 933 934 if (!hasFillLabels) { 935 fprintf(o, "\tgoto yy%u;\n", start_label); 936 oline++; 937 useLabel(label); 938 } else { 939 int i; 940 fputs("\tswitch(YYGETSTATE()) {\n", o); 941 fputs("\t\tcase -1: goto yy0;\n", o); 942 943 for (i=0; i<maxFillIndexes; ++i) 944 fprintf(o, "\t\tcase %u: goto yyFillLabel%u;\n", i, i); 945 946 fputs("\t\tdefault: /* abort() */;\n", o); 947 fputs("\t}\n", o); 948 fputs("yyNext:\n", o); 949 950 oline += maxFillIndexes; 951 oline += 5; 952 } 953 954 for(s = d->head; s; s = s->next){ 955 int readCh = 0; 956 State_emit(s, o, &readCh); 957 Go_genGoto(&s->go, o, s, s->next, &readCh); 958 } 959 fputs("}\n", o); oline++; 960 if (bitmap_brace) { 961 fputs("}\n", o); 962 oline++; 963 } 964 965 BitMap_first = NULL; 966 967 free(saves); 968 free(rules); 969 } 970
