did anyone evaluate this? I don't see a patch to lemon.c since the checkin vincent mentions below. I'm not smart enough to question his findings, but I use lemon in several projects and I would like to trust it.
rw from my mobile 434.851.1612 On Dec 3, 2009, at 10:58 PM, "Vincent Zweije" <vzwe...@zweije.nl> wrote: > > It seems my previous message has not gone through, so this is a repeat > post. > > A recent change to the lemon parser generator has reintroduced an > old bug. > > The old bug report can be found in the debian bug tracking system: > http://bugs.debian.org/233690 > > The old bug was fixed in CVS checkin 1249: > http://www.sqlite.org/cvstrac/chngview?cn=1249 > > However, the bug was re-introduced in checkin 27d8e684db: > http://www.sqlite.org/src/info/27d8e684db > > Here is a demonstration of the bug with a small grammar, and a patch > that, at least for me now, appears to fix the bug in the same way as > the CVS checkin mentioned above. > > $fossil status > repository: /home/vincent/fossil/sqlite > local-root: /home/vincent/src/sqlite/ > server-code: 3efcb091a6d5857b29c9fa3385fee9ee4e8f866f > checkout: 2f42f91fe65b0b21671936013df08037091f0cc6 2009-11-20 > 18:48:36 UTC > parent: cae949ce971ca216e0f8880b2f93866619fa05be 2009-11-20 > 17:23:13 UTC > tags: trunk > $cat x.y > start ::= S0. > start ::= S1. > start ::= S2. > start ::= n0. > n0 ::= n4 T0. > n4 ::= . > n4 ::= n4 T4. > > %include{ > > #include <assert.h> > #include <stdlib.h> > #include "x.h" > > void *ParseAlloc(void*(*)(size_t)); > void ParseTrace(FILE*,char*); > void Parse(void*,int,void*); > void ParseFree(void*,void(*)(void*)); > > int main(int argc, char *argv[]) > { > void *parser = ParseAlloc(&malloc); > ParseTrace(stderr, "x: "); > Parse(parser, T0, NULL); > Parse(parser, 0, NULL); > ParseFree(parser, &free); > return 0; > } > > } > $gcc -o tool/lemon tool/lemon.c > $tool/lemon -s x.y > Parser statistics: 6 terminals, 4 nonterminals, 7 rules > 8 states, 0 parser table entries, 0 conflicts > $gcc -o x x.c > $./x > x: Input T0 > x: Shift 7 > x: Stack: T0 > x: Input $ > x: Reduce [n0 ::= n4 T0]. > x: x.c:524: yy_find_reduce_action: Assertion `stateno<=(0)' failed. > Aborted > $cat crash.patch > Index: tool/lemon.c > =================================================================== > fossil diff /home/vincent/src/sqlite/tool/lemon.c > --- tool/lemon.c > +++ tool/lemon.c > @@ -518,11 +518,11 @@ > ** offset is found. In the worst case, we fall out of the > loop when > ** i reaches p->nAction, which means we append the new > transaction set. > ** > ** i is the index in p->aAction[] where p->mnLookahead is > inserted. > */ > - for(i=p->nAction-1; i>=0; i--){ > + for(i=p->nAction+p->mnLookahead-1; i>=0; i--){ > /* First look for an existing action table entry that can be > reused */ > if( p->aAction[i].lookahead==p->mnLookahead ){ > if( p->aAction[i].action!=p->mnAction ) continue; > for(j=0; j<p->nLookahead; j++){ > k = p->aLookahead[j].lookahead - p->mnLookahead + i; > @@ -541,11 +541,11 @@ > } > } > } > if( i<0 ){ > /* If no reusable entry is found, look for an empty slot */ > - for(i=0; i<p->nAction; i++){ > + for(i=0; i<p->nAction+p->mnLookahead; i++){ > if( p->aAction[i].lookahead<0 ){ > for(j=0; j<p->nLookahead; j++){ > k = p->aLookahead[j].lookahead - p->mnLookahead + i; > if( k<0 ) break; > if( p->aAction[k].lookahead>=0 ) break; > > $patch -p0 <crash.patch > patching file tool/lemon.c > $gcc -o tool/lemon tool/lemon.c > $tool/lemon -s x.y > Parser statistics: 6 terminals, 4 nonterminals, 7 rules > 8 states, 0 parser table entries, 0 conflicts > $gcc -o x x.c > $./x > x: Input T0 > x: Reduce [n4 ::=]. > x: Shift 1 > x: Stack: n4 > x: Shift 7 > x: Stack: n4 T0 > x: Input $ > x: Reduce [n0 ::= n4 T0]. > x: Shift 2 > x: Stack: n0 > x: Reduce [start ::= n0]. > x: Accept! > x: Popping $ > $ > > After night of bad sleep thinking, only the second hunk of this patch > seems necessary. > > The upper bound in the first hunk does not need to be increased, > because (as I understand) the loop looks to reuse an existing action > set. In fact, it may even be sharpened by only counting down from > nAction-(mxLookahead-mnLookahead)-1, because otherwise the new action > set falls off the end of the current action table anyway. > > I have not tested this... > > Ciao. Vincent. > -- > Vincent Zweije <zwe...@xs4all.nl> | "If you're flamed in a group > you > <http://www.xs4all.nl/~zweije/> | don't read, does anybody get > burnt?" > [Xhost should be taken out and shot] | -- Paul Tomblin on > a.s.r. > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
