Source Listing 31-MAR-2009 13:04:10 HP C V7.3-009-48GBT Page 1 21-DEC-1991 00:00:10 [LAISHEV.TOOLS.BISON-1_22]CLOSURE.C;1 1 /* Subroutines for bison 2 Copyright (C) 1984, 1989 Free Software Foundation, Inc. 3 4 This file is part of Bison, the GNU Compiler Compiler. 5 6 Bison is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2, or (at your option) 9 any later version. 10 11 Bison is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with Bison; see the file COPYING. If not, write to 18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ 19 20 21 /* subroutines of file LR0.c. 22 23 Entry points: 24 25 closure (items, n) 26 27 Given a vector of item numbers items, of length n, 28 set up ruleset and itemset to indicate what rules could be run 29 and which items could be accepted when those items are the active ones. 30 31 ruleset contains a bit for each rule. closure sets the bits 32 for all rules which could potentially describe the next input to be read. 33 34 itemset is a vector of item numbers; itemsetend points to just beyond the end 35 of the part of it that is significant. 36 closure places there the indices of all items which represent units of 37 input that could arrive next. 38 39 initialize_closure (n) 40 41 Allocates the itemset and ruleset vectors, 42 and precomputes useful data so that closure can be called. 43 n is the number of elements to allocate for itemset. 44 45 finalize_closure () 46 47 Frees itemset, ruleset and internal data. 48 49 */ 50 51 #include 1650 #include "system.h" 4202 #include "machine.h" 4242 #include "new.h" 4274 #include "gram.h" 4395 4396 Source Listing 31-MAR-2009 13:04:10 HP C V7.3-009-48GBT Page 2 21-DEC-1991 00:00:10 [LAISHEV.TOOLS.BISON-1_22]CLOSURE.C;1 4397 extern short **derives; 4398 extern char **tags; 4399 4400 void set_fderives(); 4401 void set_firsts(); 4402 4403 extern void RTC(); 4404 4405 short *itemset; 4406 short *itemsetend; 4407 static unsigned *ruleset; 4408 4409 /* internal data. See comments before set_fderives and set_firsts. */ 4410 static unsigned *fderives; 4411 static unsigned *firsts; 4412 4413 /* number of words required to hold a bit for each rule */ 4414 static int rulesetsize; 4415 4416 /* number of words required to hold a bit for each variable */ 4417 static int varsetsize; 4418 4419 4420 void 4421 initialize_closure(n) 4422 int n; 1 4423 { 1 4424 itemset = NEW2(n, short); 1 4425 1 4426 rulesetsize = WORDSIZE(nrules + 1); 1 4427 ruleset = NEW2(rulesetsize, unsigned); 1 4428 1 4429 set_fderives(); 1 4430 } 4431 4432 4433 4434 /* set fderives to an nvars by nrules matrix of bits 4435 indicating which rules can help derive the beginning of the data 4436 for each nonterminal. For example, if symbol 5 can be derived as 4437 the sequence of symbols 8 3 20, and one of the rules for deriving 4438 symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set. */ 4439 void 4440 set_fderives() 1 4441 { 1 4442 register unsigned *rrow; 1 4443 register unsigned *vrow; 1 4444 register int j; 1 4445 register unsigned cword; 1 4446 register short *rp; 1 4447 register int b; 1 4448 1 4449 int ruleno; 1 4450 int i; 1 4451 1 4452 fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; 1 4453 Source Listing 31-MAR-2009 13:04:10 HP C V7.3-009-48GBT Page 3 21-DEC-1991 00:00:10 [LAISHEV.TOOLS.BISON-1_22]CLOSURE.C;1 1 4454 set_firsts(); 1 4455 1 4456 rrow = fderives + ntokens * rulesetsize; 1 4457 1 4458 for (i = ntokens; i < nsyms; i++) 2 4459 { 2 4460 vrow = firsts + ((i - ntokens) * varsetsize); 2 4461 cword = *vrow++; 2 4462 b = 0; 2 4463 for (j = ntokens; j < nsyms; j++) 3 4464 { 3 4465 if (cword & (1 << b)) 4 4466 { 4 4467 rp = derives[j]; 4 4468 while ((ruleno = *rp++) > 0) 5 4469 { 5 4470 SETBIT(rrow, ruleno); 4 4471 } 3 4472 } 3 4473 3 4474 b++; 3 4475 if (b >= BITS_PER_WORD && j + 1 < nsyms) 4 4476 { 4 4477 cword = *vrow++; 4 4478 b = 0; 3 4479 } 2 4480 } 2 4481 2 4482 rrow += rulesetsize; 1 4483 } 1 4484 1X 4485 #ifdef DEBUG 1X 4486 print_fderives(); 1X 4487 #endif 1 4488 1 4489 FREE(firsts); 1 4490 } 4491 4492 4493 4494 /* set firsts to be an nvars by nvars bit matrix indicating which items 4495 can represent the beginning of the input corresponding to which other items. 4496 For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20, 4497 the symbol 8 can be the beginning of the data for symbol 5, 4498 so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */ 4499 void 4500 set_firsts() 1 4501 { 1 4502 register unsigned *row; 1 4503 /* register int done; JF unused */ 1 4504 register int symbol; 1 4505 register short *sp; 1 4506 register int rowsize; 1 4507 1 4508 int i; 1 4509 1 4510 varsetsize = rowsize = WORDSIZE(nvars); Source Listing 31-MAR-2009 13:04:10 HP C V7.3-009-48GBT Page 4 21-DEC-1991 00:00:10 [LAISHEV.TOOLS.BISON-1_22]CLOSURE.C;1 1 4511 1 4512 firsts = NEW2(nvars * rowsize, unsigned); 1 4513 1 4514 row = firsts; 1 4515 for (i = ntokens; i < nsyms; i++) 2 4516 { 2 4517 sp = derives[i]; 2 4518 while (*sp >= 0) 3 4519 { 3 4520 symbol = ritem[rrhs[*sp++]]; 3 4521 if (ISVAR(symbol)) 4 4522 { 4 4523 symbol -= ntokens; 4 4524 SETBIT(row, symbol); 3 4525 } 2 4526 } 2 4527 2 4528 row += rowsize; 1 4529 } 1 4530 1 4531 RTC(firsts, nvars); 1 4532 1X 4533 #ifdef DEBUG 1X 4534 print_firsts(); 1X 4535 #endif 1 4536 } 4537 4538 4539 void 4540 closure(core, n) 4541 short *core; 4542 int n; 1 4543 { 1 4544 register int ruleno; 1 4545 register unsigned word; 1 4546 register short *csp; 1 4547 register unsigned *dsp; 1 4548 register unsigned *rsp; 1 4549 1 4550 short *csend; 1 4551 unsigned *rsend; 1 4552 int symbol; 1 4553 int itemno; 1 4554 1 4555 rsp = ruleset; 1 4556 rsend = ruleset + rulesetsize; 1 4557 csend = core + n; 1 4558 1 4559 if (n == 0) 2 4560 { 2 4561 dsp = fderives + start_symbol * rulesetsize; 2 4562 while (rsp < rsend) 2 4563 *rsp++ = *dsp++; 1 4564 } 1 4565 else 2 4566 { 2 4567 while (rsp < rsend) Source Listing 31-MAR-2009 13:04:10 HP C V7.3-009-48GBT Page 5 21-DEC-1991 00:00:10 [LAISHEV.TOOLS.BISON-1_22]CLOSURE.C;1 2 4568 *rsp++ = 0; 2 4569 2 4570 csp = core; 2 4571 while (csp < csend) 3 4572 { 3 4573 symbol = ritem[*csp++]; 3 4574 if (ISVAR(symbol)) 4 4575 { 4 4576 dsp = fderives + symbol * rulesetsize; 4 4577 rsp = ruleset; 4 4578 while (rsp < rsend) 4 4579 *rsp++ |= *dsp++; 3 4580 } 2 4581 } 1 4582 } 1 4583 1 4584 ruleno = 0; 1 4585 itemsetend = itemset; 1 4586 csp = core; 1 4587 rsp = ruleset; 1 4588 while (rsp < rsend) 2 4589 { 2 4590 word = *rsp++; 2 4591 if (word == 0) 3 4592 { 3 4593 ruleno += BITS_PER_WORD; 2 4594 } 2 4595 else 3 4596 { 3 4597 register int b; 3 4598 3 4599 for (b = 0; b < BITS_PER_WORD; b++) 4 4600 { 4 4601 if (word & (1 << b)) 5 4602 { 5 4603 itemno = rrhs[ruleno]; 5 4604 while (csp < csend && *csp < itemno) 5 4605 *itemsetend++ = *csp++; 5 4606 *itemsetend++ = itemno; 4 4607 } 4 4608 4 4609 ruleno++; 3 4610 } 2 4611 } 1 4612 } 1 4613 1 4614 while (csp < csend) 1 4615 *itemsetend++ = *csp++; 1 4616 1X 4617 #ifdef DEBUG 1X 4618 print_closure(n); 1X 4619 #endif 1 4620 } 4621 4622 4623 void 4624 finalize_closure() Source Listing 31-MAR-2009 13:04:10 HP C V7.3-009-48GBT Page 6 21-DEC-1991 00:00:10 [LAISHEV.TOOLS.BISON-1_22]CLOSURE.C;1 1 4625 { 1 4626 FREE(itemset); 1 4627 FREE(ruleset); 1 4628 FREE(fderives + ntokens * rulesetsize); 1 4629 } 4630 4631 4632 X 4633 #ifdef DEBUG X 4634 X 4635 print_closure(n) X 4636 int n; X 4637 { X 4638 register short *isp; X 4639 X 4640 printf("\n\nn = %d\n\n", n); X 4641 for (isp = itemset; isp < itemsetend; isp++) X 4642 printf(" %d\n", *isp); X 4643 } X 4644 X 4645 X 4646 X 4647 print_firsts() X 4648 { X 4649 register int i; X 4650 register int j; X 4651 register unsigned *rowp; X 4652 X 4653 printf("\n\n\nFIRSTS\n\n"); X 4654 X 4655 for (i = ntokens; i < nsyms; i++) X 4656 { X 4657 printf("\n\n%s firsts\n\n", tags[i]); X 4658 X 4659 rowp = firsts + ((i - ntokens) * varsetsize); X 4660 X 4661 for (j = 0; j < nvars; j++) X 4662 if (BITISSET (rowp, j)) X 4663 printf(" %s\n", tags[j + ntokens]); X 4664 } X 4665 } X 4666 X 4667 X 4668 X 4669 print_fderives() X 4670 { X 4671 register int i; X 4672 register int j; X 4673 register unsigned *rp; X 4674 X 4675 printf("\n\n\nFDERIVES\n"); X 4676 X 4677 for (i = ntokens; i < nsyms; i++) X 4678 { X 4679 printf("\n\n%s derives\n\n", tags[i]); X 4680 rp = fderives + i * rulesetsize; X 4681 Source Listing 31-MAR-2009 13:04:10 HP C V7.3-009-48GBT Page 7 21-DEC-1991 00:00:10 [LAISHEV.TOOLS.BISON-1_22]CLOSURE.C;1 X 4682 for (j = 0; j <= nrules; j++) X 4683 if (BITISSET (rp, j)) X 4684 printf(" %d\n", j); X 4685 } X 4686 X 4687 fflush(stdout); X 4688 } X 4689 X 4690 #endif Command Line ------- ---- CC/INCLU=[]/LIS CLOSURE.C Hardware: /ARCHITECTURE=GENERIC /OPTIMIZE=TUNE=GENERIC These macros are in effect at the start of the compilation. ----- ------ --- -- ------ -- --- ----- -- --- ------------ __G_FLOAT=1 __DECC=1 vms=1 VMS=1 __32BITS=1 __PRAGMA_ENVIRONMENT=1 __CRTL_VER=80300000 __vms_version="V8.3 " CC$gfloat=1 __X_FLOAT=1 vms_version="V8.3 " __DATE__="Mar 31 2009" __STDC_VERSION__=199901L __DECC_MODE_RELAXED=1 __DECC_VER=70390009 __VMS=1 __ALPHA=1 VMS_VERSION="V8.3 " __IEEE_FLOAT=0 __VMS_VERSION="V8.3 " __TIME__="13:04:10" __Alpha_AXP=1 __VMS_VER=80300022 __BIASED_FLT_ROUNDS=2 __INITIAL_POINTER_SIZE=0 __STDC__=2 __LANGUAGE_C__=1 __vms=1 __alpha=1 __D_FLOAT=0