Logo Search packages:      
Sourcecode: mairix version File versions  Download package

compdfa.c

/***************************************
  $Header: /cvs/src/dfasyn/compdfa.c,v 1.3 2003/03/03 00:05:41 richard Exp $

  Routines for compressing the DFA by commoning-up equivalent states
  ***************************************/

/* 
 **********************************************************************
 * Copyright (C) Richard P. Curnow  2001-2003
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of version 2 of the GNU General Public License as
 * published by the Free Software Foundation.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 * 
 **********************************************************************
 */

/*
  The input to this stage is the 'raw' DFA build from the NFA by the subset
  construction.  Depending on the style of the NFA, there may be large chunks
  of the DFA that have equivalent functionality, in terms of resulting in the
  same exit value for the same sequence of input tokens, but which are reached
  by different prefixes.  The idea of this stage is to common up such regions,
  to reduce the size of the DFA and hence the table sizes that are generated.

  Conceptually, the basis of the algorithm is to assign the DFA states to
  equivalence classes.  If there are N different exit values, there are
  initially N+1 classes.  All states that can exit with a particular value are
  placed in a class together, and all non-accepting states are placed together.
  Now, a pass is made over all pairs of states.  Two states remain equivalent
  if for each token, their outbound transitions go to states in the same class.
  If the states do not stay equivalent, the class they were in is split
  accordingly.  This is repeated again and again until no more bisections
  occur.

  The algorithm actually used is to assign an ordering to the states based on
  their current class and outbound transitions.  The states are then sorted.
  This allows all checking to be done on near-neighbours in the sequence
  generated by the sort, which brings the execution time down to something
  finite. 

  */

#include "n2d.h"

static int last_eq_class; /* Next class to assign */
static int Nt; /* Number of tokens; has to be made static to be visible to comparison fn. */

/* To give 'general_compre' visibility of the current equiv. classes of the
   destination states */
static DFANode **local_dfas;

static void calculate_signatures(DFANode **seq, DFANode **dfas, int ndfas)/*{{{*/
/**** Determine state signatures based on transitions and current classes. ****/
{
  unsigned long sig;
  int i, t;

  for (i=0; i<ndfas; i++) {
    DFANode *s = seq[i];
    sig = 0UL;
    for (t=0; t<Nt; t++) {
      int di = s->map[t];
      if (di >= 0) {
        DFANode *d = dfas[di];
        int deq_class = d->eq_class;
      
        sig = increment(sig, deq_class & 0xf); /* 16 bit pairs in sig */
      }
    }

    s->signature = sig;
  }
}
/*}}}*/
static int general_compare(const void *a, const void *b)/*{{{*/
/************************* Do full compare on states *************************/
{
  Castderef (a, const DFANode *, aa);
  Castderef (b, const DFANode *, bb);

  if (aa->eq_class < bb->eq_class) {
    return -1;
  } else if (aa->eq_class > bb->eq_class) {
    return +1;
  } else if (aa->signature < bb->signature) {
    return -1;
  } else if (aa->signature > bb->signature) {
    return +1;
  } else {
    /* The hard way... */
    int i;
    for (i=0; i<Nt; i++) {
      int am = aa->map[i];
      int bm = bb->map[i];
      
      /* Map transition destinations to the current equivalence class of the
         destination state (otherwise compressor is very pessimistic). */
      am = (am>=0) ? local_dfas[am]->eq_class: -1;
      bm = (bm>=0) ? local_dfas[bm]->eq_class: -1;

      if      (am < bm) return -1;
      else if (am > bm) return +1;
    }

  }

  /* If you get here, the states are still equivalent */
  return 0;

}
/*}}}*/
static int split_classes(DFANode **seq, DFANode **dfas, int ndfas)/*{{{*/
/*********************** Do one pass of class splitting ***********************/
{
  int i;
  int had_to_split = 0;
  
  calculate_signatures(seq, dfas, ndfas);
  qsort(seq, ndfas, sizeof(DFANode *), general_compare);
  
  seq[0]->new_eq_class = seq[0]->eq_class;
  
  for (i=1; i<ndfas; i++) {
    seq[i]->new_eq_class = seq[i]->eq_class;

    if (seq[i]->eq_class == seq[i-1]->eq_class) {
      /* May need to split, otherwise states were previously separated anyway
         */
      
      if (general_compare(seq+i, seq+i-1) != 0) {
        /* Different transition pattern, split existing equivalent class */
        had_to_split = 1;
        seq[i]->new_eq_class = ++last_eq_class;
        if (verbose) fprintf(stderr, "Found %d equivalence classes\r", last_eq_class+1);
      } else {
        /* This works even if seq[i-1] was assigned a new class due to
           splitting from seq[i-2] etc. */
        seq[i]->new_eq_class = seq[i-1]->new_eq_class;
      }
    }
  }

  /* Set classes to new class values. */
  for (i=0; i<ndfas; i++) {
    seq[i]->eq_class = seq[i]->new_eq_class;
  }

  return had_to_split;

}
/*}}}*/
static int initial_compare(const void *a, const void *b)/*{{{*/
/************************** Sort based on exit value **************************/
{
  Castderef (a, const DFANode *, aa);
  Castderef (b, const DFANode *, bb);
  int status;
  int aok, bok;

  if (!aa->result && bb->result) {
    /* Put all non-accepting states first in sort order */
    return -1;
  } else if (aa->result && !bb->result) {
    return +1;
  } else if (!aa->result && !bb->result) {
    return 0;
  } else {
    status = strcmp(aa->result, bb->result);
    if      (status < 0) return -1;
    else if (status > 0) return +1;
    else {
      aok = (aa->attribute != 0);
      bok = (bb->attribute != 0);
      if (!aok && bok) {
        return -1;
      } else if (aok && !bok) {
        return +1;
      } else if (!aok && !bok)  {
        return 0;
      } else {
        return strcmp(aa->attribute, bb->attribute);
      }
    }
  }
}
/*}}}*/
static void assign_initial_classes(DFANode **seq, int ndfas)/*{{{*/
/******************* Determine initial equivalence classes. *******************/
{
  int i;
  qsort(seq, ndfas, sizeof(DFANode *), initial_compare);
  
  last_eq_class = 0;
  
  seq[0]->eq_class = last_eq_class;

  for (i=1; i<ndfas; i++) {
    if (initial_compare(seq+i-1, seq+i) != 0) {
      /* Not same as previous entry, assign a new class */
      seq[i]->eq_class = ++last_eq_class;
    } else {
      /* Same class as last entry */
      seq[i]->eq_class = last_eq_class;
    }
  }
}
/*}}}*/
static int compress_states(DFANode **dfas, int ndfas)/*{{{*/
/***** Compress the DFA so there is precisely one state in each eq. class *****/
{
  int *reps;
  int i, j, t;
  int neqc;
  int new_index;

  neqc = 1 + last_eq_class;

  /* Array containing which state is the representative of each eq. class.
     Keep the state which had the lowest array index. */
  reps = new_array(int, neqc);
  
  for (i=0; i<neqc; i++) reps[i] = -1; /* undefined */

  /* Go through DFA states to find the representative of each class. */
  for (i=0; i<ndfas; i++) {
    int eqc = dfas[i]->eq_class;
    if (reps[eqc] < 0) {
      reps[eqc] = i;
      dfas[i]->is_rep = 1;
    } else {
      dfas[i]->is_rep = 0;
    }
  }

  /* Go through DFA states and assign new indices. */
  for (i=0, new_index=0; i<ndfas; i++) {
    if (dfas[i]->is_rep) {
      dfas[i]->new_index = new_index++;
      if (report) fprintf(report, "Old DFA state %d becomes %d\n", i, dfas[i]->new_index);
    } else {
      int eqc = dfas[i]->eq_class;
      int rep = reps[eqc];

      /* This assignment works because the representative for the class
         must have been done earlier in the loop. */
      dfas[i]->new_index = dfas[rep]->new_index;

      if (report) fprintf(report, "Old DFA state %d becomes %d (formerly %d)\n", i, dfas[i]->new_index, rep);
    }
  }
  
  /* Go through all transitions and fix them up. */
  for (i=0; i<ndfas; i++) {
    DFANode *s = dfas[i];
    for (t=0; t<Nt; t++) {
      int dest = s->map[t];
      if (dest >= 0) {
        s->map[t] = dfas[dest]->new_index;
      }
    }
  }

  /* Go through and crunch the entries in the DFA array, fixing up the indices */
  for (i=j=0; i<ndfas; i++) {
    if (dfas[i]->is_rep) {
      dfas[j] = dfas[i];
      dfas[j]->index = dfas[j]->new_index;
      j++;
    }
  }

  free(reps);
  return neqc;
}
/*}}}*/
static void discard_nfa_bitmaps(DFANode **dfas, int ndfas)/*{{{*/
/********** Discard the (now inaccurate) NFA bitmaps from the states **********/
{
  int i;
  for (i=0; i<ndfas; i++) {
    free(dfas[i]->nfas);
    dfas[i]->nfas = NULL;
  }
  return;
}
/*}}}*/
static void print_classes(DFANode **dfas, int ndfas)/*{{{*/
{
  int i;
#if 1
  /* Comment out to print this stuff for debug */
  return;
#endif
  if (!report) return;
  fprintf(report, "Equivalence classes are :\n");
  for (i=0; i<ndfas; i++) {
    fprintf(report, "State %d class %d\n", i, dfas[i]->eq_class);
  }
  fprintf(report, "\n");
  return;
}
/*}}}*/
int compress_dfa(DFANode **dfas, int ndfas, int ntokens)/*{{{*/
/************************ The main callable interface. ************************/
{
  DFANode **seq; /* Storage for node sequence */
  int i;
  int had_to_split;
  int new_ndfas;

  /* Safety net */
  if (ndfas <= 0) return 0;

  local_dfas = dfas;
  Nt = ntokens;
  
  seq = new_array(DFANode *, ndfas);
  for (i=0; i<ndfas; i++) {
    seq[i] = dfas[i];
  }

  assign_initial_classes(seq, ndfas);

  do {
    print_classes(dfas, ndfas);
    had_to_split = split_classes(seq, dfas, ndfas);
  } while (had_to_split);

  print_classes(dfas, ndfas);

  new_ndfas = compress_states(dfas, ndfas);
  discard_nfa_bitmaps(dfas, new_ndfas);

  free(seq);
  return new_ndfas;

}
/*}}}*/


Generated by  Doxygen 1.6.0   Back to index