Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Lemon enhancement: avoid unnecessary reduce actions that convert one non-terminal into another but have no side effects. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
a86e782ad1aa6f5a8b2c54f9dcf0fa61 |
User & Date: | drh 2016-05-23 16:15:02.530 |
Context
2016-05-23
| ||
16:16 | Improve the error messages generated by the rtree module when a constraint fails. (check-in: 3ad2531efb user: dan tags: trunk) | |
16:15 | Lemon enhancement: avoid unnecessary reduce actions that convert one non-terminal into another but have no side effects. (check-in: a86e782ad1 user: drh tags: trunk) | |
14:24 | Fix comment typos and improve clarity of presention in Lemon. The output should be identical. (check-in: b91a5b8297 user: drh tags: trunk) | |
Changes
Changes to tool/lemon.c.
︙ | ︙ | |||
337 338 339 340 341 342 343 344 345 346 347 348 349 350 | struct action { struct symbol *sp; /* The look-ahead symbol */ enum e_action type; union { struct state *stp; /* The new state, if a shift */ struct rule *rp; /* The rule, if a reduce */ } x; struct action *next; /* Next action for this state */ struct action *collide; /* Next action with the same hash */ }; /* Each state of the generated parser's finite state machine ** is encoded as an instance of the following structure. */ struct state { | > | 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 | struct action { struct symbol *sp; /* The look-ahead symbol */ enum e_action type; union { struct state *stp; /* The new state, if a shift */ struct rule *rp; /* The rule, if a reduce */ } x; struct symbol *spOpt; /* SHIFTREDUCE optimization to this symbol */ struct action *next; /* Next action for this state */ struct action *collide; /* Next action with the same hash */ }; /* Each state of the generated parser's finite state machine ** is encoded as an instance of the following structure. */ struct state { |
︙ | ︙ | |||
528 529 530 531 532 533 534 535 536 537 538 539 540 541 | ){ struct action *newaction; newaction = Action_new(); newaction->next = *app; *app = newaction; newaction->type = type; newaction->sp = sp; if( type==SHIFT ){ newaction->x.stp = (struct state *)arg; }else{ newaction->x.rp = (struct rule *)arg; } } /********************** New code to implement the "acttab" module ***********/ | > | 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 | ){ struct action *newaction; newaction = Action_new(); newaction->next = *app; *app = newaction; newaction->type = type; newaction->sp = sp; newaction->spOpt = 0; if( type==SHIFT ){ newaction->x.stp = (struct state *)arg; }else{ newaction->x.rp = (struct rule *)arg; } } /********************** New code to implement the "acttab" module ***********/ |
︙ | ︙ | |||
3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 | result = 0; } break; case NOT_USED: result = 0; break; } return result; } /* Generate the "*.out" log file */ void ReportOutput(struct lemon *lemp) { int i; | > > > | 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 | result = 0; } break; case NOT_USED: result = 0; break; } if( result && ap->spOpt ){ fprintf(fp," /* because %s==%s */", ap->sp->name, ap->spOpt->name); } return result; } /* Generate the "*.out" log file */ void ReportOutput(struct lemon *lemp) { int i; |
︙ | ︙ | |||
4505 4506 4507 4508 4509 4510 4511 | ** In this version, we take the most frequent REDUCE action and make ** it the default. Except, there is no default if the wildcard token ** is a possible look-ahead. */ void CompressTables(struct lemon *lemp) { struct state *stp; | | | 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 | ** In this version, we take the most frequent REDUCE action and make ** it the default. Except, there is no default if the wildcard token ** is a possible look-ahead. */ void CompressTables(struct lemon *lemp) { struct state *stp; struct action *ap, *ap2, *nextap; struct rule *rp, *rp2, *rbest; int nbest, n; int i; int usesWildcard; for(i=0; i<lemp->nstate; i++){ stp = lemp->sorted[i]; |
︙ | ︙ | |||
4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 | pNextState = ap->x.stp; if( pNextState->autoReduce && pNextState->pDfltReduce!=0 ){ ap->type = SHIFTREDUCE; ap->x.rp = pNextState->pDfltReduce; } } } } /* ** Compare two states for sorting purposes. The smaller state is the ** one with the most non-terminal actions. If they have the same number ** of non-terminal actions, then the smaller is the one with the most | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 4622 4623 4624 4625 4626 4627 4628 4629 4630 | pNextState = ap->x.stp; if( pNextState->autoReduce && pNextState->pDfltReduce!=0 ){ ap->type = SHIFTREDUCE; ap->x.rp = pNextState->pDfltReduce; } } } /* If a SHIFTREDUCE action specifies a rule that has a single RHS term ** (meaning that the SHIFTREDUCE will land back in the state where it ** started) and if there is no C-code associated with the reduce action, ** then we can go ahead and convert the action to be the same as the ** action for the RHS of the rule. */ for(i=0; i<lemp->nstate; i++){ stp = lemp->sorted[i]; for(ap=stp->ap; ap; ap=nextap){ nextap = ap->next; if( ap->type!=SHIFTREDUCE ) continue; rp = ap->x.rp; if( rp->noCode==0 ) continue; if( rp->nrhs!=1 ) continue; #if 1 /* Only apply this optimization to non-terminals. It would be OK to ** apply it to terminal symbols too, but that makes the parser tables ** larger. */ if( ap->sp->index<lemp->nterminal ) continue; #endif /* If we reach this point, it means the optimization can be applied */ nextap = ap; for(ap2=stp->ap; ap2 && (ap2==ap || ap2->sp!=rp->lhs); ap2=ap2->next){} assert( ap2!=0 ); ap->spOpt = ap2->sp; ap->type = ap2->type; ap->x = ap2->x; } } } /* ** Compare two states for sorting purposes. The smaller state is the ** one with the most non-terminal actions. If they have the same number ** of non-terminal actions, then the smaller is the one with the most |
︙ | ︙ |