task.grammar.nonterminalhierarchy.hpp

Go to the documentation of this file.

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use these files except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Copyright 2012 - Gonzalo Iglesias, Adrià de Gispert, William Byrne

#ifndef TASK_GRAMMAR_NONTERMINALHIERARCHY
#define TASK_GRAMMAR_NONTERMINALHIERARCHY

namespace ucam {
namespace hifst {

class NonTerminalHierarchy {
 private:
  unordered_set<std::string> h_;
  unordered_set<std::string> nt_;

  bool s_;

 public:
  NonTerminalHierarchy() {};
  inline void insertIdentityRule ( const std::string& identityrule ) {
    h_.insert ( identityrule );
  };

  inline void insertLHS ( const std::string& nt ) {
    nt_.insert ( nt );
  };

  bool operator() ( std::string& ntlist ) {
    s_ = false;
    ntlist = "";
    unordered_set<std::string> haux = h_;
    unordered_set<std::string> nt = nt_;
    populate_nt ( nt );
    if ( !nt.size() ) return true;
    uint count = 0;
    uint previoussize;
    do {
      previoussize = haux.size();
      LINFO ( "round " << ++count << ": haux.size=" << previoussize );
      ntlist += identify_highest_nt ( haux, nt );
      if ( !s_ ) {
        LERROR ( "Incorrect grammar? S is expected to have the highest hierarchy!" );
        boost::algorithm::trim ( ntlist );
        ucam::util::find_and_replace ( ntlist, " ", "," );
        return false;
      }
    } while ( haux.size() < previoussize );
    boost::algorithm::trim ( ntlist );
    if ( haux.size() ) {
      LINFO ( "Conflict!" );
      LINFO ( "Partial list of ordered non-terminals:" << ntlist );
      LINFO ( "Rules containing a cycle:" );
      for ( unordered_set<std::string>::iterator itx = haux.begin();
            itx != haux.end(); ++itx )
        LINFO ( "===" << *itx );
      return false;
    }
    ntlist = "S " + ntlist;
    ucam::util::find_and_replace ( ntlist, " ", "," );
    LINFO ( "DONE!" );
    return true;
  }

 private:

  void populate_nt ( unordered_set<std::string>& nt ) {
    for ( unordered_set<std::string>::iterator itx = h_.begin(); itx != h_.end();
          ++itx ) {
      std::vector<std::string> aux;
      boost::algorithm::split ( aux, *itx, boost::algorithm::is_any_of ( " " ) );
      getFilteredNonTerminal ( aux[1] );
      nt.insert ( aux[0] );
      nt.insert ( aux[1] );
    }
    LINFO ( "Number of non-terminals=" << nt.size() );
  }

  std::string identify_highest_nt ( unordered_set<std::string>& h,
                                    unordered_set<std::string>& nt ) {
    std::map<std::string, uint> ntorder;
    int order = 0;
    for ( std::unordered_set<std::string>::iterator itx = nt.begin();
          itx != nt.end(); ++itx ) {
      ntorder[*itx] = 0;
      LINFO ( "nt:" << *itx );
    }
    for ( std::unordered_set<std::string>::iterator itx = h.begin();
          itx != h.end(); ++itx ) {
      std::vector<std::string> aux;
      boost::algorithm::split ( aux, *itx, boost::algorithm::is_any_of ( " " ) );
      getFilteredNonTerminal ( aux[1] );
      ntorder[aux[1]]++;
    }
    LINFO ( "Extract highest nt" );
    std::string ntstring;
    std::unordered_set<std::string> nttodelete;
    for ( std::map<std::string, uint>::iterator itx = ntorder.begin();
          itx != ntorder.end(); ++itx ) {
      if ( !itx->second ) {
        if ( itx->first != "S" ) {
          LINFO ( "Found " << itx->first );
          ntstring += " " + itx->first;
        } else {
          LINFO ( "Found category S" );
          s_ = true; //This one should be encountered first call and must hold highest hierarchy. Will be prepended at the end
        }
        nt.erase ( itx->first );
        nttodelete.insert ( itx->first );
      }
    }
    unordered_set<std::string> nttodelete2;
    for ( unordered_set<std::string>::iterator itx = h.begin(); itx != h.end();
          ++itx ) {
      std::vector<std::string> aux;
      boost::algorithm::split ( aux, *itx, boost::algorithm::is_any_of ( " " ) );
      if ( nttodelete.find ( aux[0] ) != nttodelete.end() ) {
        nttodelete2.insert ( *itx );
      }
    }
    for ( unordered_set<std::string>::iterator itx = nttodelete2.begin();
          itx != nttodelete2.end(); ++itx ) {
      h.erase ( *itx );
    }
    LINFO ( "ntstring=" << ntstring << ", HSIZE=" << h.size() << "NTSIZE=" <<
            nt.size() );
    return ntstring;
  }

  ZDISALLOW_COPY_AND_ASSIGN ( NonTerminalHierarchy );

};

}
} // end namespaces

#endif