It seems my previous messages have 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
