Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
| Comment: | In the "parse.out" output file from Lemon, show addition the complete text of rules on reduce actions. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
b6ffb7e471e51ff69668154ad2c8790e |
| User & Date: | drh 2015-09-07 14:22:24 |
|
2015-09-07
| ||
| 20:11 | Enhance the Lemon parser generator to add SHIFTREDUCE states that reduce the sizes of some of the parser tables. (check-in: 99b992fa user: drh tags: trunk) | |
| 18:23 | For the Lemon-generated parser, add a new action type SHIFTREDUCE and use it to further compress the parser tables and improve parser performance. (check-in: 531c3974 user: drh tags: lemon-update) | |
| 14:22 | In the "parse.out" output file from Lemon, show addition the complete text of rules on reduce actions. (check-in: b6ffb7e4 user: drh tags: trunk) | |
| 02:23 | Improved "Parser Statistics" output (the -s option) for the Lemon parser generator. (check-in: 809503e4 user: drh tags: trunk) | |
Changes to main.mk.
578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 |
# Rules to build parse.c and parse.h - the outputs of lemon. # parse.h: parse.c parse.c: $(TOP)/src/parse.y lemon $(TOP)/addopcodes.awk cp $(TOP)/src/parse.y . rm -f parse.h ./lemon $(OPTS) parse.y mv parse.h parse.h.temp $(NAWK) -f $(TOP)/addopcodes.awk parse.h.temp >parse.h sqlite3.h: $(TOP)/src/sqlite.h.in $(TOP)/manifest.uuid $(TOP)/VERSION $(TOP)/ext/rtree/sqlite3rtree.h tclsh $(TOP)/tool/mksqlite3h.tcl $(TOP) >sqlite3.h keywordhash.h: $(TOP)/tool/mkkeywordhash.c |
| |
578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 |
# Rules to build parse.c and parse.h - the outputs of lemon.
#
parse.h: parse.c
parse.c: $(TOP)/src/parse.y lemon $(TOP)/addopcodes.awk
cp $(TOP)/src/parse.y .
rm -f parse.h
./lemon -s $(OPTS) parse.y
mv parse.h parse.h.temp
$(NAWK) -f $(TOP)/addopcodes.awk parse.h.temp >parse.h
sqlite3.h: $(TOP)/src/sqlite.h.in $(TOP)/manifest.uuid $(TOP)/VERSION $(TOP)/ext/rtree/sqlite3rtree.h
tclsh $(TOP)/tool/mksqlite3h.tcl $(TOP) >sqlite3.h
keywordhash.h: $(TOP)/tool/mkkeywordhash.c
|
Changes to tool/lemon.c.
336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 .... 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 .... 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 .... 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 .... 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 .... 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 .... 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 .... 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 |
struct state {
struct config *bp; /* The basis configurations for this state */
struct config *cfp; /* All configurations in this set */
int statenum; /* Sequential number for this state */
struct action *ap; /* Array of actions for this state */
int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */
int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */
int iDflt; /* Default action */
};
#define NO_OFFSET (-2147483647)
/* A followset propagation link indicates that the contents of one
** configuration followset should be propagated to another whenever
** the first changes. */
struct plink {
................................................................................
printf(".");
if( rp->precsym ) printf(" [%s]",rp->precsym->name);
/* if( rp->code ) printf("\n %s",rp->code); */
printf("\n");
}
}
void ConfigPrint(FILE *fp, struct config *cfp)
{
struct rule *rp;
struct symbol *sp;
int i, j;
rp = cfp->rp;
fprintf(fp,"%s ::=",rp->lhs->name);
for(i=0; i<=rp->nrhs; i++){
if( i==cfp->dot ) fprintf(fp," *");
if( i==rp->nrhs ) break;
sp = rp->rhs[i];
if( sp->type==MULTITERMINAL ){
fprintf(fp," %s", sp->subsym[0]->name);
for(j=1; j<sp->nsubsym; j++){
fprintf(fp,"|%s",sp->subsym[j]->name);
}
}else{
fprintf(fp," %s", sp->name);
}
}
}
/* #define TEST */
#if 0
/* Print a set */
PRIVATE void SetPrint(out,set,lemp)
FILE *out;
char *set;
................................................................................
}
}
#endif
/* Print an action to the given file descriptor. Return FALSE if
** nothing was actually printed.
*/
int PrintAction(struct action *ap, FILE *fp, int indent){
int result = 1;
switch( ap->type ){
case SHIFT:
fprintf(fp,"%*s shift %d",indent,ap->sp->name,ap->x.stp->statenum);
break;
case REDUCE:
fprintf(fp,"%*s reduce %d",indent,ap->sp->name,ap->x.rp->index);
break;
case ACCEPT:
fprintf(fp,"%*s accept",indent,ap->sp->name);
break;
case ERROR:
fprintf(fp,"%*s error",indent,ap->sp->name);
break;
case SRCONFLICT:
case RRCONFLICT:
fprintf(fp,"%*s reduce %-3d ** Parsing conflict **",
indent,ap->sp->name,ap->x.rp->index);
break;
case SSCONFLICT:
fprintf(fp,"%*s shift %-3d ** Parsing conflict **",
indent,ap->sp->name,ap->x.stp->statenum);
break;
case SH_RESOLVED:
if( showPrecedenceConflict ){
fprintf(fp,"%*s shift %-3d -- dropped by precedence",
indent,ap->sp->name,ap->x.stp->statenum);
}else{
result = 0;
}
break;
case RD_RESOLVED:
if( showPrecedenceConflict ){
fprintf(fp,"%*s reduce %-3d -- dropped by precedence",
indent,ap->sp->name,ap->x.rp->index);
}else{
result = 0;
}
break;
case NOT_USED:
result = 0;
................................................................................
void ReportOutput(struct lemon *lemp)
{
int i;
struct state *stp;
struct config *cfp;
struct action *ap;
FILE *fp;
fp = file_open(lemp,".out","wb");
if( fp==0 ) return;
for(i=0; i<lemp->nstate; i++){
stp = lemp->sorted[i];
fprintf(fp,"State %d:\n",stp->statenum);
if( lemp->basisflag ) cfp=stp->bp;
else cfp=stp->cfp;
................................................................................
PlinkPrint(fp,cfp->bplp,"From");
#endif
if( lemp->basisflag ) cfp=cfp->bp;
else cfp=cfp->next;
}
fprintf(fp,"\n");
for(ap=stp->ap; ap; ap=ap->next){
if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
}
fprintf(fp,"\n");
}
fprintf(fp, "----------------------------------------------------\n");
fprintf(fp, "Symbols:\n");
for(i=0; i<lemp->nsymbol; i++){
int j;
................................................................................
fprintf(fp, " %s", lemp->symbols[j]->name);
}
}
}
fprintf(fp, "\n");
}
fclose(fp);
return;
}
/* Search for the file "name" which is in the same directory as
** the exacutable */
PRIVATE char *pathsearch(char *argv0, char *name, int modemask)
{
................................................................................
/* Output the default action table */
fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
n = lemp->nstate;
lemp->tablesize += n*szActionType;
for(i=j=0; i<n; i++){
stp = lemp->sorted[i];
if( j==0 ) fprintf(out," /* %5d */ ", i);
fprintf(out, " %4d,", stp->iDflt);
if( j==9 || i==n-1 ){
fprintf(out, "\n"); lineno++;
j = 0;
}else{
j++;
}
}
................................................................................
int i;
struct state *stp;
struct action *ap;
for(i=0; i<lemp->nstate; i++){
stp = lemp->sorted[i];
stp->nTknAct = stp->nNtAct = 0;
stp->iDflt = lemp->nstate + lemp->nrule;
stp->iTknOfst = NO_OFFSET;
stp->iNtOfst = NO_OFFSET;
for(ap=stp->ap; ap; ap=ap->next){
if( compute_action(lemp,ap)>=0 ){
if( ap->sp->index<lemp->nterminal ){
stp->nTknAct++;
}else if( ap->sp->index<lemp->nsymbol ){
stp->nNtAct++;
}else{
stp->iDflt = compute_action(lemp, ap);
}
}
}
}
qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
stateResortCompare);
for(i=0; i<lemp->nstate; i++){
|
| | < > | < | > > > > > > | > > > > > | > | > > > > > | > | > > | | | | > > > > > > > > > > | > | | | |
336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 .... 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 .... 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 .... 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 .... 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 .... 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 .... 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 .... 4368 4369 4370 4371 4372 4373 4374 4375 4376 4377 4378 4379 4380 4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 |
struct state {
struct config *bp; /* The basis configurations for this state */
struct config *cfp; /* All configurations in this set */
int statenum; /* Sequential number for this state */
struct action *ap; /* Array of actions for this state */
int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */
int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */
int iDflt; /* Default action is reduce by this rule */
};
#define NO_OFFSET (-2147483647)
/* A followset propagation link indicates that the contents of one
** configuration followset should be propagated to another whenever
** the first changes. */
struct plink {
................................................................................
printf(".");
if( rp->precsym ) printf(" [%s]",rp->precsym->name);
/* if( rp->code ) printf("\n %s",rp->code); */
printf("\n");
}
}
/* Print a single rule.
*/
void RulePrint(FILE *fp, struct rule *rp, int iCursor){
struct symbol *sp;
int i, j;
fprintf(fp,"%s ::=",rp->lhs->name);
for(i=0; i<=rp->nrhs; i++){
if( i==iCursor ) fprintf(fp," *");
if( i==rp->nrhs ) break;
sp = rp->rhs[i];
if( sp->type==MULTITERMINAL ){
fprintf(fp," %s", sp->subsym[0]->name);
for(j=1; j<sp->nsubsym; j++){
fprintf(fp,"|%s",sp->subsym[j]->name);
}
}else{
fprintf(fp," %s", sp->name);
}
}
}
/* Print the rule for a configuration.
*/
void ConfigPrint(FILE *fp, struct config *cfp){
RulePrint(fp, cfp->rp, cfp->dot);
}
/* #define TEST */
#if 0
/* Print a set */
PRIVATE void SetPrint(out,set,lemp)
FILE *out;
char *set;
................................................................................
}
}
#endif
/* Print an action to the given file descriptor. Return FALSE if
** nothing was actually printed.
*/
int PrintAction(
struct action *ap, /* The action to print */
FILE *fp, /* Print the action here */
int indent, /* Indent by this amount */
struct rule **apRule /* All rules by index */
){
int result = 1;
switch( ap->type ){
case SHIFT: {
struct state *stp = ap->x.stp;
fprintf(fp,"%*s shift %-7d",indent,ap->sp->name,stp->statenum);
if( stp->nTknAct==0 && stp->nNtAct==0 && apRule ){
fprintf(fp,"then reduce %d: ", stp->iDflt);
RulePrint(fp, apRule[stp->iDflt], -1);
}
break;
}
case REDUCE: {
struct rule *rp = ap->x.rp;
fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->index);
if( apRule ) RulePrint(fp, apRule[rp->index], -1);
break;
}
case ACCEPT:
fprintf(fp,"%*s accept",indent,ap->sp->name);
break;
case ERROR:
fprintf(fp,"%*s error",indent,ap->sp->name);
break;
case SRCONFLICT:
case RRCONFLICT:
fprintf(fp,"%*s reduce %-7d ** Parsing conflict **",
indent,ap->sp->name,ap->x.rp->index);
break;
case SSCONFLICT:
fprintf(fp,"%*s shift %-7d ** Parsing conflict **",
indent,ap->sp->name,ap->x.stp->statenum);
break;
case SH_RESOLVED:
if( showPrecedenceConflict ){
fprintf(fp,"%*s shift %-7d -- dropped by precedence",
indent,ap->sp->name,ap->x.stp->statenum);
}else{
result = 0;
}
break;
case RD_RESOLVED:
if( showPrecedenceConflict ){
fprintf(fp,"%*s reduce %-7d -- dropped by precedence",
indent,ap->sp->name,ap->x.rp->index);
}else{
result = 0;
}
break;
case NOT_USED:
result = 0;
................................................................................
void ReportOutput(struct lemon *lemp)
{
int i;
struct state *stp;
struct config *cfp;
struct action *ap;
FILE *fp;
struct rule **apRule;
apRule = malloc( sizeof(apRule[0])*(lemp->nrule+1) );
if( apRule ){
struct rule *x;
memset(apRule, 0, sizeof(apRule[0])*(lemp->nrule+1) );
for(x=lemp->rule; x; x=x->next){
assert( x->index>=0 && x->index<(lemp->nrule+1) );
apRule[x->index] = x;
}
}
fp = file_open(lemp,".out","wb");
if( fp==0 ) return;
for(i=0; i<lemp->nstate; i++){
stp = lemp->sorted[i];
fprintf(fp,"State %d:\n",stp->statenum);
if( lemp->basisflag ) cfp=stp->bp;
else cfp=stp->cfp;
................................................................................
PlinkPrint(fp,cfp->bplp,"From");
#endif
if( lemp->basisflag ) cfp=cfp->bp;
else cfp=cfp->next;
}
fprintf(fp,"\n");
for(ap=stp->ap; ap; ap=ap->next){
if( PrintAction(ap,fp,30,apRule) ) fprintf(fp,"\n");
}
fprintf(fp,"\n");
}
fprintf(fp, "----------------------------------------------------\n");
fprintf(fp, "Symbols:\n");
for(i=0; i<lemp->nsymbol; i++){
int j;
................................................................................
fprintf(fp, " %s", lemp->symbols[j]->name);
}
}
}
fprintf(fp, "\n");
}
fclose(fp);
free(apRule);
return;
}
/* Search for the file "name" which is in the same directory as
** the exacutable */
PRIVATE char *pathsearch(char *argv0, char *name, int modemask)
{
................................................................................
/* Output the default action table */
fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
n = lemp->nstate;
lemp->tablesize += n*szActionType;
for(i=j=0; i<n; i++){
stp = lemp->sorted[i];
if( j==0 ) fprintf(out," /* %5d */ ", i);
fprintf(out, " %4d,", stp->iDflt+n);
if( j==9 || i==n-1 ){
fprintf(out, "\n"); lineno++;
j = 0;
}else{
j++;
}
}
................................................................................
int i;
struct state *stp;
struct action *ap;
for(i=0; i<lemp->nstate; i++){
stp = lemp->sorted[i];
stp->nTknAct = stp->nNtAct = 0;
stp->iDflt = lemp->nrule;
stp->iTknOfst = NO_OFFSET;
stp->iNtOfst = NO_OFFSET;
for(ap=stp->ap; ap; ap=ap->next){
if( compute_action(lemp,ap)>=0 ){
if( ap->sp->index<lemp->nterminal ){
stp->nTknAct++;
}else if( ap->sp->index<lemp->nsymbol ){
stp->nNtAct++;
}else{
stp->iDflt = compute_action(lemp, ap) - lemp->nstate;
}
}
}
}
qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
stateResortCompare);
for(i=0; i<lemp->nstate; i++){
|