[sqlite] Lemon-generated parser gives an assertion failure
The test case can be simplified to:
bug.lemon:
---
%include {
#include
#include
#include
#include "bug.h"
}
%code {
int main(void) {
void *pParser;
pParser = ParseAlloc(malloc);
if (!pParser) {
printf("out of memory\n");
exit(1);
}
ParseTrace(stderr, "Debug: ");
Parse(pParser, X, 0);
Parse(pParser, 0, 0);
ParseFree(pParser, free);
return 0;
}
}
main ::= decls.
decls ::= .
decls ::= decls decl.
decl ::= X
—
which generates this code:
default:
/* (0) main ::= decls */ yytestcase(yyruleno==0);
/* (1) decls ::= (OPTIMIZED OUT) */ assert(yyruleno!=1);
break;
I believe the issue is line 4164 which should be … = LEMON_TRUE. Currently,
when i=0, all rules will erroneously be optimized out.
4157/* Mark rules that are actually used for reduce actions after all
4158** optimizations have been applied
4159*/
4160for(rp=lemp->rule; rp; rp=rp->next) rp->doesReduce = LEMON_FALSE;
4161for(i=0; inxstate; i++){
4162 for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
4163if( ap->type==REDUCE || ap->type==SHIFTREDUCE ){
4164 ap->x.rp->doesReduce = i;
4165}
4166 }
4167}
Kelvin Sherlock
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
[sqlite] Lemon: Simple recursive rule causes assertion failed: stateno <= YY_SHIFT_COUNT
This lemon bug was reported about 6 months ago:
8<
%include {
#include
#include
#include
#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
[sqlite] Lemon reduce action merge bug
> On Apr 29, 2016, at 7:29 AM, Richard Hipp wrote:
>
> On 4/28/16, Kelvin Sherlock wrote:
>> I believe the lemon reduce action optimizer needs to compare the codePrefix
>> and codeSuffix.
>
> Thanks for the bug report. A fix has now been checked in.
>
> --
> D. Richard Hipp
> drh at sqlite.org
Here are a couple more edge cases I noticed:
---
bug_report ::= rule.
%destructor malloc{free($$)}
rule ::= .
rule ::= malloc . /* 1 */
rule ::= malloc malloc . /* 2 */
malloc(X) ::= ID . { X = malloc(100); }
---
1. the rhs[0] destructor will not be called since the lhsalias null check
happens first and the codePrefix is never generated.
The empty lhsalias check can be moved down to compensate:
@@ -3552,30 +3552,30 @@ PRIVATE int translate_code(struct lemon *lemp, struct
rule *rp){
if( rp->code==0 ){
static char newlinestr[2] = { '\n', '\0' };
rp->code = newlinestr;
rp->line = rp->ruleline;
}
- if( rp->lhsalias==0 ){
-/* There is no LHS value symbol. */
-lhsdirect = 1;
- }else if( rp->nrhs==0 ){
+ if( rp->nrhs==0 ){
/* If there are no RHS symbols, then writing directly to the LHS is ok */
lhsdirect = 1;
}else if( rp->rhsalias[0]==0 ){
/* The left-most RHS symbol has not value. LHS direct is ok. But
** we have to call the distructor on the RHS symbol first. */
lhsdirect = 1;
if( has_destructor(rp->rhs[0],lemp) ){
append_str(0,0,0,0);
append_str(" yy_destructor(yypParser,%d,[%d].minor);\n", 0,
rp->rhs[0]->index,1-rp->nrhs);
rp->codePrefix = Strsafe(append_str(0,0,0,0));
}
+ }else if( rp->lhsalias==0 ){
+/* There is no LHS value symbol. */
+lhsdirect = 1;
}else if( strcmp(rp->lhsalias,rp->rhsalias[0])==0 ){
/* The LHS symbol and the left-most RHS symbol are the same, so
** direct writing is allowed */
lhsdirect = 1;
lhsused = 1;
used[0] = 1;
2. if there is a codePrefix or codeSuffix but no code, it will be merged into
the default rule and the prefix/suffix will be lost.
@@ -3715,7 +3715,7 @@ PRIVATE int translate_code(struct lemon *lemp, struct
rule *rp){
/* Suffix code generation complete */
cp = append_str(0,0,0,0);
- if( cp ) rp->codeSuffix = Strsafe(cp);
+ if( cp && cp[0] ) rp->codeSuffix = Strsafe(cp);
return rc;
}
@@ -4397,7 +4397,8 @@ void ReportTable(
for(rp=lemp->rule; rp; rp=rp->next){
struct rule *rp2; /* Other rules with the same action */
if( rp->code==0 ) continue;
-if( rp->code[0]=='\n' && rp->code[1]==0 ) continue; /* Will be default: */
+if( rp->code[0]=='\n' && rp->code[1]==0 && rp->codePrefix==0
+ && rp->codeSuffix==0 ) continue; /* Will be default: */
fprintf(out," case %d: /* ", rp->iRule);
writeRuleText(out, rp);
fprintf(out, " */\n"); lineno++;
@@ -4419,7 +4420,8 @@ void ReportTable(
fprintf(out," default:\n"); lineno++;
for(rp=lemp->rule; rp; rp=rp->next){
if( rp->code==0 ) continue;
-assert( rp->code[0]=='\n' && rp->code[1]==0 );
+assert( rp->code[0]=='\n' && rp->code[1]==0 && rp->codePrefix==0
+ && rp->codeSuffix==0 );
fprintf(out," /* (%d) ", rp->iRule);
writeRuleText(out, rp);
fprintf(out, " */ yytestcase(yyruleno==%d);\n", rp->iRule); lineno++;
Thanks,
Kelvin
[sqlite] Lemon reduce action merge bug
I believe the lemon reduce action optimizer needs to compare the codePrefix and
codeSuffix. Consider this example:
8<
%type malloc {void *}
%destructor malloc {free($$)}
%type contrived_example {int}
bug_report ::= contrived_example.
contrived_example(LHS) ::= INT INT INT. { LHS = 0; }
contrived_example(LHS) ::= malloc malloc malloc. { LHS = 0; }
malloc(LHS) ::= . { LHS = malloc(100); }
8<
Since the code (but not the codeSuffix) matches, they will be merged together
into this:
case 0: /* contrived_example ::= INT INT INT */
case 1: /* contrived_example ::= malloc malloc malloc */
yytestcase(yyruleno==1);
#line 8 "bug.lemon"
{ yymsp[-2].minor.yy4 = 0; }
#line 725 "bug.c"
break;
or this:
/** Begin reduce actions **/
case 0: /* contrived_example ::= malloc malloc malloc */
case 1: /* contrived_example ::= INT INT INT */ yytestcase(yyruleno==1);
{ yy_destructor(yypParser,3,[-2].minor);
#line 8 "bug.lemon"
{ yymsp[-2].minor.yy4 = 0; }
#line 726 "bug.c"
yy_destructor(yypParser,3,[-1].minor);
yy_destructor(yypParser,3,[0].minor);
}
break;
depending on which rule is first.
patch:
diff --git a/lemon.c b/lemon.c
index 903fe97..dca5a08 100644
--- a/lemon.c
+++ b/lemon.c
@@ -4402,7 +4402,11 @@ void ReportTable(
writeRuleText(out, rp);
fprintf(out, " */\n"); lineno++;
for(rp2=rp->next; rp2; rp2=rp2->next){
- if( rp2->code==rp->code ){
+ if(
+rp2->code==rp->code &&
+rp2->codePrefix==rp->codePrefix &&
+rp2->codeSuffix==rp->codeSuffix
+ ){
fprintf(out," case %d: /* ", rp2->iRule);
writeRuleText(out, rp2);
fprintf(out," */ yytestcase(yyruleno==%d);\n", rp2->iRule); lineno++;
Thanks,
Kelvin Sherlock
