/ Check-in [67a135a0]
Login
Overview
Comment:Modify lemon to use much less memory for its parser tables. This reduces the size of the library by 50K, which is important for an embedded library. (CVS 389)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:67a135a051e7c96ddbfe85976539b4b8372c7026
User & Date: drh 2002-02-23 19:39:47
Context
2002-02-23
23:45
Added support for user-defined normal functions. Support for user-defined aggregates is pending. (CVS 390) check-in: c490a1ff user: drh tags: trunk
19:39
Modify lemon to use much less memory for its parser tables. This reduces the size of the library by 50K, which is important for an embedded library. (CVS 389) check-in: 67a135a0 user: drh tags: trunk
18:45
Bug fix in lemon: 3-way conflicts (SHIFT/REDUCE/REDUCE) were not detected or resolved. This is now fixed. Also, table compression works a little better. (CVS 388) check-in: 8da0ac9a user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to tool/lemon.c.

2922
2923
2924
2925
2926
2927
2928














2929
2930
2931
2932
2933
2934
2935
....
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
....
3023
3024
3025
3026
3027
3028
3029

3030
3031
3032
3033
3034
3035
3036



3037
3038
3039
3040
3041
3042
3043
....
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
....
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
....
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097

3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
....
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133

3134
3135
3136
3137
3138
3139
3140
  }
  fprintf(out,"  int yy%d;\n",lemp->errsym->dtnum); lineno++;
  free(stddt);
  free(types);
  fprintf(out,"} YYMINORTYPE;\n"); lineno++;
  *plineno = lineno;
}















/* Generate C source code for the parser */
void ReportTable(lemp, mhflag)
struct lemon *lemp;
int mhflag;     /* Output in makeheaders format if true */
{
  FILE *out, *in;
................................................................................
    fprintf(out,"#endif\n"); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate the defines */
  fprintf(out,"/* \001 */\n");
  fprintf(out,"#define YYCODETYPE %s\n",
    lemp->nsymbol>250?"int":"unsigned char");  lineno++;
  fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  fprintf(out,"#define YYACTIONTYPE %s\n",
    lemp->nstate+lemp->nrule>250?"int":"unsigned char");  lineno++;
  print_stack_union(out,lemp,&lineno,mhflag);
  if( lemp->stacksize ){
    if( atoi(lemp->stacksize)<=0 ){
      ErrorMsg(lemp->filename,0,
"Illegal stack size: [%s].  The stack size should be an integer constant.",
        lemp->stacksize);
      lemp->errorcnt++;
................................................................................

  /* Generate the action table.
  **
  ** Each entry in the action table is an element of the following 
  ** structure:
  **   struct yyActionEntry {
  **       YYCODETYPE            lookahead;

  **       YYACTIONTYPE          action;
  **       struct yyActionEntry *next;
  **   }
  **
  ** The entries are grouped into hash tables, one hash table for each
  ** parser state.  The hash table has a size which is the smallest
  ** power of two needed to hold all entries.



  */
  tablecnt = 0;

  /* Loop over parser states */
  for(i=0; i<lemp->nstate; i++){
    int tablesize;              /* size of the hash table */
    int j,k;                    /* Loop counter */
................................................................................
    stp->tabstart = tablecnt;
    stp->naction = 0;
    for(ap=stp->ap; ap; ap=ap->next){
      if( ap->sp->index!=lemp->nsymbol && compute_action(lemp,ap)>=0 ){
        stp->naction++;
      }
    }
    tablesize = 1;
    while( tablesize<stp->naction ) tablesize += tablesize;
    assert( tablesize<= sizeof(table)/sizeof(table[0]) );
    for(j=0; j<tablesize; j++){
      table[j] = 0;
      collide[j] = -1;
    }

    /* Hash the actions into the hash table */
................................................................................
    stp->tabdfltact = lemp->nstate + lemp->nrule;
    for(ap=stp->ap; ap; ap=ap->next){
      int action = compute_action(lemp,ap);
      int h;
      if( ap->sp->index==lemp->nsymbol ){
        stp->tabdfltact = action;
      }else if( action>=0 ){
        h = ap->sp->index & (tablesize-1);
        ap->collide = table[h];
        table[h] = ap;
      }
    }

    /* Resolve collisions */
    for(j=k=0; j<tablesize; j++){
................................................................................
        if( k<j ) j = k-1;
      }
    }

    /* Print the hash table */
    fprintf(out,"/* State %d */\n",stp->index); lineno++;
    for(j=0; j<tablesize; j++){
      if( table[j]==0 ){
        fprintf(out,
          "  {YYNOCODE,0,0}, /* Unused */\n");
      }else{
        fprintf(out,"  {%4d,%4d, ",
          table[j]->sp->index,

          compute_action(lemp,table[j]));
        if( collide[j]>=0 ){
          fprintf(out,"&yyActionTable[%4d] }, /* ",
            collide[j] + tablecnt);
        }else{
          fprintf(out,"0                    }, /* ");
        }
        PrintAction(table[j],out,22);
        fprintf(out," */\n"); 
      }
      lineno++;
    }

    /* Update the table count */
    tablecnt += tablesize;
  }
  tplt_xfer(lemp->name,in,out,&lineno);
................................................................................
  lemp->tablesize = tablecnt;

  /* Generate the state table
  **
  ** Each entry is an element of the following structure:
  **    struct yyStateEntry {
  **      struct yyActionEntry *hashtbl;
  **      int mask;
  **      YYACTIONTYPE actionDefault;
  **    }
  */
  for(i=0; i<lemp->nstate; i++){
    int tablesize;
    stp = lemp->sorted[i];
    tablesize = 1;
    while( tablesize<stp->naction ) tablesize += tablesize;
    fprintf(out,"  { &yyActionTable[%d], %d, %d},\n",
      stp->tabstart,
      tablesize - 1,

      stp->tabdfltact); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate a table containing the symbolic name of every symbol */
  for(i=0; i<lemp->nsymbol; i++){
    sprintf(line,"\"%s\",",lemp->symbols[i]->name);







>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|


|







 







>

<



|
|
>
>
>







 







|
<







 







|







 







|
<
<
<
|

>

<
<
<
<
<
<
|
|
<







 







|




<

<
<
|

<
>







2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
....
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
....
3037
3038
3039
3040
3041
3042
3043
3044
3045

3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
....
3066
3067
3068
3069
3070
3071
3072
3073

3074
3075
3076
3077
3078
3079
3080
....
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
....
3101
3102
3103
3104
3105
3106
3107
3108



3109
3110
3111
3112






3113
3114

3115
3116
3117
3118
3119
3120
3121
....
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133

3134


3135
3136

3137
3138
3139
3140
3141
3142
3143
3144
  }
  fprintf(out,"  int yy%d;\n",lemp->errsym->dtnum); lineno++;
  free(stddt);
  free(types);
  fprintf(out,"} YYMINORTYPE;\n"); lineno++;
  *plineno = lineno;
}

/*
** Return the name of a C datatype able to represent values between
** 0 and N, inclusive.
*/
static const char *minimum_size_type(int N){
  if( N<=255 ){
    return "unsigned char";
  }else if( N<65535 ){
    return "unsigned short int";
  }else{
    return "unsigned int";
  }
}

/* Generate C source code for the parser */
void ReportTable(lemp, mhflag)
struct lemon *lemp;
int mhflag;     /* Output in makeheaders format if true */
{
  FILE *out, *in;
................................................................................
    fprintf(out,"#endif\n"); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate the defines */
  fprintf(out,"/* \001 */\n");
  fprintf(out,"#define YYCODETYPE %s\n",
    minimum_size_type(lemp->nsymbol+5)); lineno++;
  fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  fprintf(out,"#define YYACTIONTYPE %s\n",
    minimum_size_type(lemp->nstate+lemp->nrule+5));  lineno++;
  print_stack_union(out,lemp,&lineno,mhflag);
  if( lemp->stacksize ){
    if( atoi(lemp->stacksize)<=0 ){
      ErrorMsg(lemp->filename,0,
"Illegal stack size: [%s].  The stack size should be an integer constant.",
        lemp->stacksize);
      lemp->errorcnt++;
................................................................................

  /* Generate the action table.
  **
  ** Each entry in the action table is an element of the following 
  ** structure:
  **   struct yyActionEntry {
  **       YYCODETYPE            lookahead;
  **       YYCODETYPE            next;
  **       YYACTIONTYPE          action;

  **   }
  **
  ** The entries are grouped into hash tables, one hash table for each
  ** parser state.  The hash table has a size which is the number of
  ** entries in that table.  In case of a collision, the "next" value
  ** contains one more than the index into the hash table of the next
  ** entry in the collision chain.  A "next" value of 0 means the end
  ** of the chain has been reached.
  */
  tablecnt = 0;

  /* Loop over parser states */
  for(i=0; i<lemp->nstate; i++){
    int tablesize;              /* size of the hash table */
    int j,k;                    /* Loop counter */
................................................................................
    stp->tabstart = tablecnt;
    stp->naction = 0;
    for(ap=stp->ap; ap; ap=ap->next){
      if( ap->sp->index!=lemp->nsymbol && compute_action(lemp,ap)>=0 ){
        stp->naction++;
      }
    }
    tablesize = stp->naction;

    assert( tablesize<= sizeof(table)/sizeof(table[0]) );
    for(j=0; j<tablesize; j++){
      table[j] = 0;
      collide[j] = -1;
    }

    /* Hash the actions into the hash table */
................................................................................
    stp->tabdfltact = lemp->nstate + lemp->nrule;
    for(ap=stp->ap; ap; ap=ap->next){
      int action = compute_action(lemp,ap);
      int h;
      if( ap->sp->index==lemp->nsymbol ){
        stp->tabdfltact = action;
      }else if( action>=0 ){
        h = ap->sp->index % tablesize;
        ap->collide = table[h];
        table[h] = ap;
      }
    }

    /* Resolve collisions */
    for(j=k=0; j<tablesize; j++){
................................................................................
        if( k<j ) j = k-1;
      }
    }

    /* Print the hash table */
    fprintf(out,"/* State %d */\n",stp->index); lineno++;
    for(j=0; j<tablesize; j++){
      assert( table[j]!=0 );



      fprintf(out,"  {%4d,%4d,%4d}, /* ",
          table[j]->sp->index,
          collide[j]+1,
          compute_action(lemp,table[j]));






      PrintAction(table[j],out,22);
      fprintf(out," */\n"); 

      lineno++;
    }

    /* Update the table count */
    tablecnt += tablesize;
  }
  tplt_xfer(lemp->name,in,out,&lineno);
................................................................................
  lemp->tablesize = tablecnt;

  /* Generate the state table
  **
  ** Each entry is an element of the following structure:
  **    struct yyStateEntry {
  **      struct yyActionEntry *hashtbl;
  **      YYCODETYPE nEntry;
  **      YYACTIONTYPE actionDefault;
  **    }
  */
  for(i=0; i<lemp->nstate; i++){

    stp = lemp->sorted[i];


    fprintf(out,"  { &yyActionTable[%d],%4d,%4d },\n",
      stp->tabstart,

      stp->naction,
      stp->tabdfltact); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate a table containing the symbolic name of every symbol */
  for(i=0; i<lemp->nsymbol; i++){
    sprintf(line,"\"%s\",",lemp->symbols[i]->name);

Changes to tool/lempar.c.

72
73
74
75
76
77
78

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
...
293
294
295
296
297
298
299


300
301
302
303
304

305
306
307
308
309
310
311
312
313
** The action table is really a series of hash tables.  Each hash
** table contains a number of entries which is a power of two.  The
** "state" table (which follows) contains information about the starting
** point and size of each hash table.
*/
struct yyActionEntry {
  YYCODETYPE   lookahead;   /* The value of the look-ahead token */

  YYACTIONTYPE action;      /* Action to take for this look-ahead */
  struct yyActionEntry *next; /* Next look-ahead with the same hash, or NULL */
};
static struct yyActionEntry yyActionTable[] = {
%%
};

/* The state table contains information needed to look up the correct
** action in the action table, given the current state of the parser.
** Information needed includes:
**
**  +  A pointer to the start of the action hash table in yyActionTable.
**
**  +  A mask used to hash the look-ahead token.  The mask is an integer
**     which is one less than the size of the hash table.  
**
**  +  The default action.  This is the action to take if no entry for
**     the given look-ahead is found in the action hash table.
*/
struct yyStateEntry {
  struct yyActionEntry *hashtbl; /* Start of the hash table in yyActionTable */
  int mask;                      /* Mask used for hashing the look-ahead */
  YYACTIONTYPE actionDefault;    /* Default action if look-ahead not found */
};
static struct yyStateEntry yyStateTable[] = {
%%
};

/* The following structure represents a single element of the
................................................................................
  int iLookAhead             /* The look-ahead token */
){
  struct yyStateEntry *pState;   /* Appropriate entry in the state table */
  struct yyActionEntry *pAction; /* Action appropriate for the look-ahead */
 
  /* if( pParser->idx<0 ) return YY_NO_ACTION;  */
  pState = &yyStateTable[pParser->top->stateno];


  if( iLookAhead!=YYNOCODE ){
    pAction = &pState->hashtbl[iLookAhead & pState->mask];
    while( pAction ){
      if( pAction->lookahead==iLookAhead ) return pAction->action;
      pAction = pAction->next;

    }
  }else if( pState->mask!=0 || pState->hashtbl->lookahead!=YYNOCODE ){
    return YY_NO_ACTION;
  }
  return pState->actionDefault;
}

/*
** Perform a shift action.







>

<











|
<






|







 







>
>
|
|
|

|
>

|







72
73
74
75
76
77
78
79
80

81
82
83
84
85
86
87
88
89
90
91
92

93
94
95
96
97
98
99
100
101
102
103
104
105
106
...
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
** The action table is really a series of hash tables.  Each hash
** table contains a number of entries which is a power of two.  The
** "state" table (which follows) contains information about the starting
** point and size of each hash table.
*/
struct yyActionEntry {
  YYCODETYPE   lookahead;   /* The value of the look-ahead token */
  YYCODETYPE   next;        /* Next entry + 1. Zero at end of collision chain */
  YYACTIONTYPE action;      /* Action to take for this look-ahead */

};
static struct yyActionEntry yyActionTable[] = {
%%
};

/* The state table contains information needed to look up the correct
** action in the action table, given the current state of the parser.
** Information needed includes:
**
**  +  A pointer to the start of the action hash table in yyActionTable.
**
**  +  The number of entries in the action hash table.

**
**  +  The default action.  This is the action to take if no entry for
**     the given look-ahead is found in the action hash table.
*/
struct yyStateEntry {
  struct yyActionEntry *hashtbl; /* Start of the hash table in yyActionTable */
  YYCODETYPE nEntry;             /* Number of entries in action hash table */
  YYACTIONTYPE actionDefault;    /* Default action if look-ahead not found */
};
static struct yyStateEntry yyStateTable[] = {
%%
};

/* The following structure represents a single element of the
................................................................................
  int iLookAhead             /* The look-ahead token */
){
  struct yyStateEntry *pState;   /* Appropriate entry in the state table */
  struct yyActionEntry *pAction; /* Action appropriate for the look-ahead */
 
  /* if( pParser->idx<0 ) return YY_NO_ACTION;  */
  pState = &yyStateTable[pParser->top->stateno];
  if( pState->nEntry==0 ){
    return pState->actionDefault;
  }else if( iLookAhead!=YYNOCODE ){
    pAction = &pState->hashtbl[iLookAhead % pState->nEntry];
    while( 1 ){
      if( pAction->lookahead==iLookAhead ) return pAction->action;
      if( pAction->next==0 ) return pState->actionDefault;
      pAction = &pState->hashtbl[pAction->next-1];
    }
  }else if( pState->hashtbl->lookahead!=YYNOCODE ){
    return YY_NO_ACTION;
  }
  return pState->actionDefault;
}

/*
** Perform a shift action.