---

basic_dfa_generator.cc

Go to the documentation of this file.

/*
 *  File:       basic_dfa_generator.cc
 *              $Id: basic_dfa_generator.cc,v 1.7 2002/05/27 02:58:12 alec Exp $
 *
 *  Author:     Alec Panoviciu (alecu@email.com)
 * 
 *  Comments:
 *
 *  Revision history:
 *
 *  $Log: basic_dfa_generator.cc,v $
 *  Revision 1.7  2002/05/27 02:58:12  alec
 *  doc update
 *
 *  Revision 1.6  2002/05/22 01:31:42  alec
 *  cleaned up firstpo/followpos/nullable computation
 *
 *  Revision 1.5  2002/05/07 10:02:18  alec
 *  fixed some bugs & mem leaks; added MORE tokens support
 *
 *  Revision 1.4  2002/05/04 17:39:22  alec
 *  the scanner works (slightly tested)
 *
 *  Revision 1.3  2002/05/01 16:32:14  alec
 *  dfa ok. huh !
 *
 *  Revision 1.2  2002/05/01 09:18:26  alec
 *  - vBitset fixes
 *  - FOLLOWPOS written (not tested yet)
 *
 *  Revision 1.1  2002/04/30 16:26:38  alec
 *  my big endian will eat your little endian
 *
 */

/*
  Copyright (C) 2002 Alexandru Panoviciu (alecu@email.com)

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  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

 */

#include <typeinfo>
#include <queue>

#include "prop_registry.hh"
#include "scanner_spec.hh"
#include "basic_dfa_generator.hh"
#include "basic_dfa_spec.hh"
#include "dfa_source_re.hh"
#include "re_node.hh"
#include "re_node_algo.hh"
#include "itoken_spec.hh"

BasicDfaGenerator::BasicDfaGenerator (ITokenSpec &tokens_,
                                      PropRegistry &registry_) :
  tokens(tokens_), registry(registry_)
{}


class LeafNumberGen : public ReNodeAlgo
{
public:

  LeafNumberGen () : counter(0) {}

  virtual bool operator () (ReNode &n)
  {
    ASSERT(&n != NULL, "Regexp tree corrupted !");
    
    if (typeid(n) == typeid(ReCharNode)) {
      ReCharNode &nn = dynamic_cast<ReCharNode&>(n);
      nn.pos = counter++;
    } else if (typeid(n) == typeid(ReEotNode)) {
      ReEotNode &nn = dynamic_cast<ReEotNode&>(n);
      nn.pos = counter++;
    } else if (typeid(n) == typeid(ReLambdaNode)) {
      ReLambdaNode &nn = dynamic_cast<ReLambdaNode&>(n);
      nn.pos = counter++;
    }
      
    return true;
  }
  
  unsigned int counter;
};


class FollowPosGen : public ReNodeAlgo
{
public:
  
  FollowPosGen (vBitset *table_) : table(table_) {}

  virtual bool operator () (ReNode &n)
  {
    if (typeid(n) == typeid(ReCatNode)) {
      ReCatNode &nn = dynamic_cast<ReCatNode&>(n);
      vBitset &preLast = nn.pre->lastPos;
      vBitset &postFirst = nn.post->firstPos;
      vBitset::reference ri = preLast.begin();
      for (unsigned int i = 0; ri.neq(preLast.end()); ri.next(), i++)
        if (ri.get())
          table[i] |= postFirst;
    } else if (typeid(n) == typeid(ReStarNode)) {
      ReStarNode &nn = dynamic_cast<ReStarNode&>(n);
      vBitset &nnLast = nn.lastPos;
      vBitset &nnFirst = nn.firstPos;
      vBitset::reference ri = nnLast.begin();
      for (unsigned int i = 0; ri.neq(nnLast.end()); ri.next(), i++)
        if (ri.get())
          table[i] |= nnFirst;
    }

    return true;
  }
  
  vBitset *table;
};


class LeafFinder : public ReNodeAlgo
{
public:
  
  LeafFinder (DfaSourceRe **leaves_) : leaves(leaves_)
  {}

  virtual bool operator () (ReNode &n)
  {
    ASSERT(&n != NULL, "Regexp tree corrupted !");
    
    if (typeid(n) == typeid(ReCharNode)) {
      ReCharNode &nn = dynamic_cast<ReCharNode&>(n);
      leaves[nn.pos] = &nn;
    } else if (typeid(n) == typeid(ReEotNode)) {
      ReEotNode &nn = dynamic_cast<ReEotNode&>(n);
      leaves[nn.pos] = &nn;
    } else if (typeid(n) == typeid(ReLambdaNode)) {
      ReLambdaNode &nn = dynamic_cast<ReLambdaNode&>(n);
      leaves[nn.pos] = &nn;
    }
    return true;
  }

  
  DfaSourceRe **leaves;
};


class AttributeGen : public ReNodeAlgo
{
public:

  virtual bool operator () (ReNode &n)
  {
    if (typeid(n) == typeid(ReCatNode)) {
      ReCatNode &nn = dynamic_cast<ReCatNode&>(n);
      nn.nullable = nn.pre->nullable && nn.post->nullable;
      nn.firstPos = nn.pre->firstPos;
      if (nn.pre->nullable) nn.firstPos |= nn.post->firstPos;
      nn.lastPos = nn.post->lastPos;
      if (nn.post->nullable) nn.lastPos |= nn.pre->lastPos;
    } else if (typeid(n) == typeid(ReOrNode)) {
      ReOrNode &nn = dynamic_cast<ReOrNode&>(n);
      nn.nullable = nn.pre->nullable || nn.post->nullable;
      nn.firstPos = nn.pre->firstPos;
      nn.firstPos |= nn.post->firstPos;
      nn.lastPos = nn.post->lastPos;
      nn.lastPos |= nn.pre->lastPos;
    } else if (typeid(n) == typeid(ReStarNode)) {
      ReStarNode &nn = dynamic_cast<ReStarNode&>(n);
      nn.nullable = true;
      nn.firstPos = nn.in->firstPos;
      nn.lastPos = nn.in->lastPos;
    } else if (typeid(n) == typeid(ReCharNode)) {
      ReCharNode &nn = dynamic_cast<ReCharNode&>(n);
      nn.nullable = false;
      nn.firstPos.resize(nn.pos + 1);
      nn.firstPos[nn.pos].set();
      nn.lastPos.resize(nn.pos + 1);
      nn.lastPos[nn.pos].set();
    } else if (typeid(n) == typeid(ReEotNode)) {
      ReEotNode &nn = dynamic_cast<ReEotNode&>(n);
      nn.nullable = true;
      nn.firstPos.resize(nn.pos + 1);
      nn.firstPos[nn.pos].set();
      nn.lastPos.resize(nn.pos + 1);
      nn.lastPos[nn.pos].set();
    } else if (typeid(n) == typeid(ReLambdaNode)) {
      ReLambdaNode &nn = dynamic_cast<ReLambdaNode&>(n);
      nn.nullable = true;
    } else ASSERT(0, "Bat typeid in AttributeGen::operator ()");

    return true;
  }
};



BasicDfaSpec& BasicDfaGenerator::createBasicDfa(const LexicalStateSpec &ls)
{
  BasicDfaSpec &res = *new BasicDfaSpec(ls.name);
  DfaSourceRe *regexp = dynamic_cast<DfaSourceRe*>(ls.regexp);

  
  
  // 1. do the numbering
  LeafNumberGen nr;
  regexp->dfTraverse(nr);

  // This vector tells us where leave nodes are. At index i, we have a a pointer
  // to leaf node with pos == i
  DfaSourceRe **leaves = new (DfaSourceRe*)[nr.counter];
  LeafFinder lf(leaves);
  regexp->dfTraverse(lf);
  
  
  // 2. compute attributes
  AttributeGen aga;
  regexp->dfTraverse(aga);
  
#ifdef DEBUG
  if (((string)registry["debug"]).find('f') != string::npos) {
    cerr << "-------------------------------------------------------------"
         << endl << "STATE NODES DUMP FOR STATE " << ls.name << endl;
    regexp->dump(cerr);
  }
#endif

  // 3. compute the followpos
  vBitset *followPos = new vBitset[nr.counter];
  FollowPosGen fpg(followPos);
  regexp->dfTraverse(fpg);

#ifdef DEBUG
  if (((string)registry["debug"]).find('f') != string::npos) {
    cerr << "-------------------------------------------------------------"
         << endl << "FOLLOWPOS table:" << endl;
    for (unsigned int i = 0; i < nr.counter; i++) {
      cerr << i << ": ";
      vBitset::reference ri = followPos[i].begin();
      for (unsigned int j = 0; ri.neq(followPos[i].end()); ri.next(), j++)
        if (ri.get()) cerr << j << " ";
      cerr << endl;
    }
  }
#endif

  // the bitvector associated to each state
  vector<vBitset*> statesDesc;

  // states for which transitions have not been computed yet.
  // the number stored is the index into statesDesc where the state is described
  queue<int> q;

  // create the initial state
  statesDesc.push_back(new vBitset(regexp->firstPos));
  res.states.push_back(BasicDfaSpec::State());
  q.push(0); 

  while (!q.empty())
  {
    int Dnum = q.front(); q.pop();
    vBitset &Dset = *statesDesc[Dnum];
    
    for (unsigned int c = 0; c < 256; c++) {
      vBitset *Uset = new vBitset();
      
      vBitset::reference pi = Dset.begin();
      for (unsigned int p = 0; pi.neq(Dset.end()); p++, pi.next())
        if (pi.get() && (typeid(*leaves[p]) == typeid(ReCharNode))) {
          ReCharNode &n = dynamic_cast<ReCharNode&>(*leaves[p]);
          if (n.match == c)  // node n at position p matches c, then add
                              // followPos(n) into Udesc
            *Uset |= followPos[p];
        }

      if (Uset->all0()) {
        delete Uset;
        continue; //if U is empty, continue with next c
      }
      
      int Unum = 0;

      for (; Unum < statesDesc.size(); Unum++)
        if (*statesDesc[Unum] == *Uset) break;
      
      if (Unum == statesDesc.size()) {
        // U is a new state
        statesDesc.push_back(Uset);
        res.states.push_back(BasicDfaSpec::State());
        q.push(Unum);
      } else
        delete Uset;
      
      res.states[Dnum].addTransition(c, Unum);
      
    }

  } // while !w.empty()


  // determine and mark as such the accepting states
  // a state is accepting state if at least one of the position that describes
  // it is that of an EOT leaf node
  for (int Snum = 0; Snum < statesDesc.size(); Snum++) {
    vBitset::reference pi = statesDesc[Snum]->begin();
    for (unsigned int i = 0; pi.neq(statesDesc[Snum]->end()); i++, pi.next())
      if (pi.get() && (typeid(*leaves[i]) == typeid(ReEotNode))) {
        ReEotNode &n = dynamic_cast<ReEotNode&>(*leaves[i]);
        // this warning is damn annoying !
        if (res.states[Snum].isFinal) {
          /*  cerr << formatWarning(leaves[i]->getPos(), string("Regexp for token ") +
                                tokens[res.states[Snum].tokId].name() +
                                " hides regexp for token "
                                + tokens[n.tokId].name() +
                                " which might not get matched while in lexical state " +
                                ls.name) << endl;*/
          continue;
        }
        res.states[Snum].isFinal = true;
        res.states[Snum].tokId = n.tokId;
      }
  }
 
  
#ifdef DEBUG
  if (((string)registry["debug"]).find('f') != string::npos) {
    cerr << "----------------------------------------------------" << endl
         << "DFA dump:" << endl;
    res.dump(cerr);
  }
#endif

  for (int i = 0; i < statesDesc.size(); i++) delete statesDesc[i];
  delete[] followPos;
  delete[] leaves;
  
  return res;
}

---