From fdbf928b086647acaee77889b2f51783d903e835 Mon Sep 17 00:00:00 2001 From: drh Date: Tue, 21 Oct 2003 16:34:41 +0000 Subject: [PATCH] Fix bugs in lemon associated with the change to a perfect hash table. (CVS 1113) FossilOrigin-Name: c0d1b26966aeb445fea5792e5a9e93632e758c2a --- manifest | 14 +++---- manifest.uuid | 2 +- tool/lemon.c | 113 +++++++++++++++++++++++++++++++++++--------------- tool/lempar.c | 2 +- 4 files changed, 89 insertions(+), 42 deletions(-) diff --git a/manifest b/manifest index d7fb996020..33a5cdda09 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Convert\slemon\sto\suse\sa\ssingle\sperfect\shash\stable\sfor\sstoring\sthe\sactions.\nThis\sshould\smake\sthe\sresulting\sparser\sboth\ssmaller\sand\sfaster.\s(CVS\s1112) -D 2003-10-21T13:16:04 +C Fix\sbugs\sin\slemon\sassociated\swith\sthe\schange\sto\sa\sperfect\shash\stable.\s(CVS\s1113) +D 2003-10-21T16:34:42 F Makefile.in ab585a91e34bc33928a1b6181fa2f6ebd4fb17e1 F Makefile.linux-gcc b86a99c493a5bfb402d1d9178dcdc4bd4b32f906 F README f1de682fbbd94899d50aca13d387d1b3fd3be2dd @@ -138,8 +138,8 @@ F test/version.test 605fd0d7e7d571370c32b12dbf395b58953de246 F test/view.test 1ee12c6f8f4791a2c0655120d5562a49400cfe53 F test/where.test cb3a2ed062ce4b5f08aff2d08027c6a46d68c47b F tool/diffdb.c 7524b1b5df217c20cd0431f6789851a4e0cb191b -F tool/lemon.c 37d1493549a238bba56cc8a6e614191f43eac573 -F tool/lempar.c a3406868634ef5e67a8a03675317dcf5623d4740 +F tool/lemon.c e37dcb5b8cdb16f4ac98338134bf8d8cd28e399f +F tool/lempar.c 043b18f4e82012f48240e44aa68d9b95bdf431cc F tool/memleak.awk 16ef9493dcd36146f806e75148f4bb0201a123ec F tool/memleak2.awk 9cc20c8e8f3c675efac71ea0721ee6874a1566e8 F tool/mkopts.tcl 66ac10d240cc6e86abd37dc908d50382f84ff46e x @@ -174,7 +174,7 @@ F www/speed.tcl 2f6b1155b99d39adb185f900456d1d592c4832b3 F www/sqlite.tcl 3c83b08cf9f18aa2d69453ff441a36c40e431604 F www/tclsqlite.tcl b9271d44dcf147a93c98f8ecf28c927307abd6da F www/vdbe.tcl 9b9095d4495f37697fd1935d10e14c6015e80aa1 -P ddb364635a207658664ea92fc677cf16a143a938 -R c217117a68a15b5b6ece4f04bcc9b9b1 +P 4f955c00076b16166ff837749efb84201eab3c3a +R 476d560510b73636a2e46afa340dadeb U drh -Z 76b8ed5abf9139dcfee1277f9c2ad231 +Z e55c6ef0dbc0e0ad2050ca7323671ea5 diff --git a/manifest.uuid b/manifest.uuid index 78fc3c5f91..6315e6efa6 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -4f955c00076b16166ff837749efb84201eab3c3a \ No newline at end of file +c0d1b26966aeb445fea5792e5a9e93632e758c2a \ No newline at end of file diff --git a/tool/lemon.c b/tool/lemon.c index 0fe454b943..4904106615 100644 --- a/tool/lemon.c +++ b/tool/lemon.c @@ -493,6 +493,7 @@ int acttab_insert(acttab *p){ */ n = p->mxLookahead - p->mnLookahead + 1; if( p->nAction + n >= p->nActionAlloc ){ + int oldAlloc = p->nActionAlloc; p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20; p->aAction = realloc( p->aAction, sizeof(p->aAction[0])*p->nActionAlloc); @@ -500,7 +501,7 @@ int acttab_insert(acttab *p){ fprintf(stderr,"malloc failed\n"); exit(1); } - for(i=p->nAction; inActionAlloc; i++){ + for(i=oldAlloc; inActionAlloc; i++){ p->aAction[i].lookahead = -1; p->aAction[i].action = -1; } @@ -520,7 +521,13 @@ int acttab_insert(acttab *p){ if( k<0 ) break; if( p->aAction[k].lookahead>=0 ) break; } - if( j==p->nLookahead ) break; /* Fits in empty slots */ + if( jnLookahead ) continue; + for(j=0; jnAction; j++){ + if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break; + } + if( j==p->nAction ){ + break; /* Fits in empty slots */ + } }else if( p->aAction[i].lookahead==p->mnLookahead ){ if( p->aAction[i].action!=p->mnAction ) continue; for(j=0; jnLookahead; j++){ @@ -532,9 +539,12 @@ int acttab_insert(acttab *p){ if( jnLookahead ) continue; n = 0; for(j=0; jnAction; j++){ - if( p->aAction[j].lookahead==j+i-p->mnLookahead ) n++; + if( p->aAction[j].lookahead<0 ) continue; + if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++; + } + if( n==p->nLookahead ){ + break; /* Same as a prior transaction set */ } - if( n==p->nLookahead ) break; /* Same as a prior transaction set */ } } /* Insert transaction set at index i. */ @@ -3125,6 +3135,27 @@ static const char *minimum_size_type(int lwr, int upr){ } } +/* +** Each state contains a set of token transaction and a set of +** nonterminal transactions. Each of these sets makes an instance +** of the following structure. An array of these structures is used +** to order the creation of entries in the yy_action[] table. +*/ +struct axset { + struct state *stp; /* A pointer to a state */ + int isTkn; /* True to use tokens. False for non-terminals */ + int nAction; /* Number of actions */ +}; + +/* +** Compare to axset structures for sorting purposes +*/ +static int axset_compare(const void *a, const void *b){ + struct axset *p1 = (struct axset*)a; + struct axset *p2 = (struct axset*)b; + return p2->nAction - p1->nAction; +} + /* Generate C source code for the parser */ void ReportTable(lemp, mhflag) struct lemon *lemp; @@ -3141,6 +3172,7 @@ int mhflag; /* Output in makeheaders format if true */ char *name; int mnTknOfst, mxTknOfst; int mnNtOfst, mxNtOfst; + struct axset *ax; in = tplt_open(lemp); if( in==0 ) return; @@ -3241,6 +3273,11 @@ int mhflag; /* Output in makeheaders format if true */ */ /* Compute the actions on all states and count them up */ + ax = malloc( sizeof(ax[0])*lemp->nstate*2 ); + if( ax==0 ){ + fprintf(stderr,"malloc failed\n"); + exit(1); + } for(i=0; instate; i++){ stp = lemp->sorted[i]; stp->nTknAct = stp->nNtAct = 0; @@ -3258,45 +3295,50 @@ int mhflag; /* Output in makeheaders format if true */ } } } + ax[i*2].stp = stp; + ax[i*2].isTkn = 1; + ax[i*2].nAction = stp->nTknAct; + ax[i*2+1].stp = stp; + ax[i*2+1].isTkn = 0; + ax[i*2+1].nAction = stp->nNtAct; } mxTknOfst = mnTknOfst = 0; mxNtOfst = mnNtOfst = 0; - /* Compute the action table. Do this in two passes. The first - ** pass does all entries with two or more actions and the second - ** pass does all states with a single action. + /* Compute the action table. In order to try to keep the size of the + ** action table to a minimum, the heuristic of placing the largest action + ** sets first is used. */ + qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare); pActtab = acttab_alloc(); - for(j=0; j<=1; j++){ - for(i=0; instate; i++){ - stp = lemp->sorted[i]; - if( (j==0 && stp->nTknAct>=2) || (j==1 && stp->nTknAct==1) ){ - for(ap=stp->ap; ap; ap=ap->next){ - int action; - if( ap->sp->index>=lemp->nterminal ) continue; - action = compute_action(lemp, ap); - if( action<0 ) continue; - acttab_action(pActtab, ap->sp->index, action); - } - stp->iTknOfst = acttab_insert(pActtab); - if( stp->iTknOfstiTknOfst; - if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst; + for(i=0; instate*2 && ax[i].nAction>0; i++){ + stp = ax[i].stp; + if( ax[i].isTkn ){ + for(ap=stp->ap; ap; ap=ap->next){ + int action; + if( ap->sp->index>=lemp->nterminal ) continue; + action = compute_action(lemp, ap); + if( action<0 ) continue; + acttab_action(pActtab, ap->sp->index, action); } - if( (j==0 && stp->nNtAct>=2) || (j==1 && stp->nNtAct==1) ){ - for(ap=stp->ap; ap; ap=ap->next){ - int action; - if( ap->sp->indexnterminal ) continue; - if( ap->sp->index==lemp->nsymbol ) continue; - action = compute_action(lemp, ap); - if( action<0 ) continue; - acttab_action(pActtab, ap->sp->index, action); - } - stp->iNtOfst = acttab_insert(pActtab); - if( stp->iNtOfstiNtOfst; - if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst; + stp->iTknOfst = acttab_insert(pActtab); + if( stp->iTknOfstiTknOfst; + if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst; + }else{ + for(ap=stp->ap; ap; ap=ap->next){ + int action; + if( ap->sp->indexnterminal ) continue; + if( ap->sp->index==lemp->nsymbol ) continue; + action = compute_action(lemp, ap); + if( action<0 ) continue; + acttab_action(pActtab, ap->sp->index, action); } + stp->iNtOfst = acttab_insert(pActtab); + if( stp->iNtOfstiNtOfst; + if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst; } } + free(ax); /* Output the yy_action table */ fprintf(out,"static YYACTIONTYPE yy_action[] = {\n"); lineno++; @@ -3304,6 +3346,7 @@ int mhflag; /* Output in makeheaders format if true */ for(i=j=0; insymbol + lemp->nrule + 2; + if( j==0 ) fprintf(out," /* %5d */ ", i); fprintf(out, " %4d,", action); if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; @@ -3319,6 +3362,7 @@ int mhflag; /* Output in makeheaders format if true */ for(i=j=0; insymbol; + if( j==0 ) fprintf(out," /* %5d */ ", i); fprintf(out, " %4d,", la); if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; @@ -3339,6 +3383,7 @@ int mhflag; /* Output in makeheaders format if true */ stp = lemp->sorted[i]; ofst = stp->iTknOfst; if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1; + if( j==0 ) fprintf(out," /* %5d */ ", i); fprintf(out, " %4d,", ofst); if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; @@ -3359,6 +3404,7 @@ int mhflag; /* Output in makeheaders format if true */ stp = lemp->sorted[i]; ofst = stp->iNtOfst; if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1; + if( j==0 ) fprintf(out," /* %5d */ ", i); fprintf(out, " %4d,", ofst); if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; @@ -3374,6 +3420,7 @@ int mhflag; /* Output in makeheaders format if true */ n = lemp->nstate; for(i=j=0; isorted[i]; + if( j==0 ) fprintf(out," /* %5d */ ", i); fprintf(out, " %4d,", stp->iDflt); if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; diff --git a/tool/lempar.c b/tool/lempar.c index 88d93b5637..225c3020e1 100644 --- a/tool/lempar.c +++ b/tool/lempar.c @@ -59,7 +59,7 @@ #define YY_ACCEPT_ACTION (YYNSTATE+YYNRULE+1) #define YY_ERROR_ACTION (YYNSTATE+YYNRULE) -/* Next are that ables used to determine what action to take based on the +/* Next are that tables used to determine what action to take based on the ** current state and lookahead token. These tables are used to implement ** functions that take a state number and lookahead value and return an ** action integer. -- 2.47.3