SQLite Forum

Lemon rule precedence bug ?
Login

Lemon rule precedence bug ?

(1) By Domingo (mingodad) on 2021-11-12 19:04:07 [source]

Trying to compare grammar conflicts between parser generators I noticed that "lemon" differs form "yacc/bison" in how to assign rule precedence, "yacc/bison" uses the rightmost token but "lemon" uses the leftmost token (at least on the documentation).

But looking through the code it seems that "lemon" is only respecting the documentation for MULTITERMINAL but using the rightmost token otherwise (see bellow), the loop that goes through all rhs elements of a rule do not stop when it finds the first, so if we have more than one token with precedence defined the last one (rightmost) will prevail, except for MULTITERMINAL that stops at the first found.

======
void FindRulePrecedences(struct lemon *xp)
{
  struct rule *rp;
  for(rp=xp->rule; rp; rp=rp->next){
    if( rp->precsym==0 ){
      int i, j;
      for(i=0; i<rp->nrhs && rp->precsym==0; i++){
        struct symbol *sp = rp->rhs[i];
        if( sp->type==MULTITERMINAL ){
          for(j=0; j<sp->nsubsym; j++){
            if( sp->subsym[j]->prec>=0 ){
              rp->precsym = sp->subsym[j];
              break; ///<<<<< break only the inner loop, but continue looking in the outer loop
            }
          }
        }else if( sp->prec>=0 ){
          rp->precsym = rp->rhs[i]; ///<<<<< no break here, continue looking for more tokens
        }
      }
    }
  }
  return;
}
======

(2) By Domingo (mingodad) on 2021-11-12 19:07:04 in reply to 1 [link] [source]

My bad, after submit and rereading the code I noticed that test on the outer loop checking for "rp->precsym==0" what means stop if found any.

(3) By Domingo (mingodad) on 2021-11-13 18:18:10 in reply to 1 [link] [source]

Looking at "FindRulePrecedences" again it seems that it's not checking if the current symbol is a TERMINAL after testing for MULTITERMINAL, so if a NONTERMINAL has "prec>=0" it will be used to define the precedence for the current rule.

Am I missing something here ?

======
void FindRulePrecedences(struct lemon *xp)
{
  struct rule *rp;
  for(rp=xp->rule; rp; rp=rp->next){
    if( rp->precsym==0 ){
      int i, j;
      for(i=0; i<rp->nrhs && rp->precsym==0; i++){
        struct symbol *sp = rp->rhs[i];
        if( sp->type==MULTITERMINAL ){
          for(j=0; j<sp->nsubsym; j++){
            if( sp->subsym[j]->prec>=0 ){
              rp->precsym = sp->subsym[j];
              break;
            }
          }
        }else if( sp->prec>=0 ){ ///<<<< here a NONTERMINAL with prec>=0
          rp->precsym = rp->rhs[i];
        }
      }
    }
  }
  return;
}
======