Lemon parser assertion failure if a set has only one entry

Question

This might be my misunderstanding of how parsers reduce rather than a potential bug in SQLite's lemon parser. I have been experimenting with simple grammars for a database input file. The database consists of a list of at least one entry sets, things like "commands", or "maps" or...

Here's a grammar that does not work - I have started creating the entry sets and so far all I have is a "command":

database ::= entrylist.

entrylist ::= entrylist entryset.
entrylist ::= entryset.

entryset ::= command.

/* Commands are in the form %command [arguments] \n */

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

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

If I run this with a test program that just feeds in tokens I get:

$ test
Debug: Input 'CMDNAME'
Debug: Shift 'CMDNAME', go to state 3
Debug: Return. Stack=[CMDNAME]
Debug: Input 'INTEGER'
Assertion failed: stateno <= YY_SHIFT_COUNT, file testpar.c, line 513

If I give the entryset an additional alternative:

entryset ::= command.
entryset ::= map.
...
map ::= MAPNAME EOL.

then the whole thing works as expected. I think perhaps you aren't allowed create a situation where a::=b and b::=c. You must have b ::= c | d at the very least. I'd like to understand if this is my mistake in understanding.

Answer 1

Bug logged to SQLite mailing list:

http://www.mail-archive.com/[email protected]/msg99712.html

http://www.mail-archive.com/[email protected]/msg99716.html

Answer 2

Lemon compresses the shift table to remove default actions from the end of the table. Presumably, default actions should be handled elsewhere but they aren't. Your example happens to have default actions so the table is compressed, YY_MAX_SHIFT and YY_SHIFT_COUNT are out of sync, and the assert is triggered.

In lemon.c, around line 4235, you can comment out this line:

while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;

to prevent compression and to prevent the bug.

Generated code with compression:

#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,
};

Generated code without compression:

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

I submitted the details to the SQLite mailing list earlier this year but nothing has happened yet. The correct solution is probably to continue compressing but handle default actions in the template.