[sqlite] Lemon: Simple recursive rule causes assertion failed: stateno <= YY_SHIFT_COUNT

[Kelvin Sherlock]

This lemon bug was reported about 6 months ago:


8<----

%include {
    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include "lemon-bug.h"
}

%code {
    int main()
    {
        void *pParser;

        pParser = ParseAlloc(malloc);
        if (!pParser)
        {
            printf("out of memory\n");
            exit(1);
        }

        ParseTrace(stderr, "Debug: ");

        Parse(pParser, CMDNAME, 0);
        Parse(pParser, INTEGER, 0);
        Parse(pParser, TEXT, 0);
        Parse(pParser, EOL, 0);

        Parse(pParser, CMDNAME, 0);
        Parse(pParser, INTEGER, 0);
        Parse(pParser, TEXT, 0);
        Parse(pParser, EOL, 0);

        Parse(pParser, 0, 0);
        ParseFree(pParser, free);
        return 0;
    }
}


database ::= entrylist.

entrylist ::= command.
entrylist ::= entrylist command.

command ::= CMDNAME cmdargs EOL. 
cmdargs ::= .
cmdargs ::= cmdargs cmdarg.

cmdarg ::= INTEGER.
cmdarg ::= TEXT.


8<----


./lemon-bug 
Debug: Input 'CMDNAME'
Debug: Shift 'CMDNAME', go to state 3
Debug: Return. Stack=[CMDNAME]
Debug: Input 'INTEGER'
Assertion failed: (stateno <= YY_SHIFT_COUNT), function yy_find_shift_action, 
file lemon-bug.c, line 512.
Abort trap: 6

which generates this code:

#define YY_MAX_SHIFT         3
#define YY_SHIFT_COUNT    (2)
#define YY_SHIFT_USE_DFLT (13)
static const unsigned char yy_shift_ofst[] = {
 /*     0 */     7,    1,    6,
};
…

  assert( stateno <= YY_SHIFT_COUNT );

without the shift table compression -- lemon.c line 4235:
        while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n—;

it will generate this:

#define YY_SHIFT_COUNT    (3)
static const unsigned char yy_shift_ofst[] = {
 /*     0 */     7,    1,    6,   13,
};

and the assert doesn’t fail.

Most of the time (and in the case of SQLite parse.y) the shift table won’t 
compress and YY_MAX_SHIFT == YY_SHIFT_COUNT.
Given that, it probably shouldn’t try to compress the shift table.

Kelvin Sherlock



_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users