1

次の機能がありますが、なぜ機能しないのかわかりません。

パラメーターは、非終端記号のセットと GrammarSymbol* (単語) のベクトルです。Nonterminal は GrammarSymbol のサブクラスです。この関数は、単語と非終端記号セットに含まれるすべての非終端記号をフィルター処理し、それらをセットで返すことになっています。

std::set<Nonterminal> Filter(const std::set<Nonterminal>& symbolSet, const std::vector<GrammarSymbol*> w){

  //resulting set
  std::set<Nonterminal> rSet;

  std::vector<GrammarSymbol*>::const_iterator wit;
  std::set<Nonterminal>::const_iterator ntit;

  //iterate over all symbols of the word
  for(wit = w.begin(); wit != w.end(); wit++){

    //test if current symbol is a nonterminal
    const Nonterminal* nt = dynamic_cast<const Nonterminal*>(*wit);
    if(nt != NULL){
      std::cout << "current symbol " << nt->Str() << " is nonterminal" << std::endl;

      for(ntit = symbolSet.begin(); ntit != symbolSet.end(); ntit++){
        std::cout << ntit->Str() << "  " << (!(*ntit < *nt) && !(*nt < *ntit))<< std::endl;
      }
      //look for the symbol in the nonterminal set
      ntit = symbolSet.find(*nt);

      //if the symbol was found, insert it into resulting set
      if(ntit != symbolSet.end()){
        rSet.insert(*ntit);
        std::cout << "inserted " << ntit->Str() << "into set, size: " << rSet.size() << std::endl;
      }
      else{
        std::cout << "not found in symbolSet" << std::endl;
      }
    }
  }
  return rSet;
}

これにより、出力が得られます

current symbol (1, 2, 2) is nonterminal
(1, 2, 2)  1
(2, 3, 3)  0
(3, 2)  0
(4, 3)  0
(5, 3, 1)  0
not found in symbolSet

フィルター関数に依存せず、自分でフィルター処理すると、うまく機能します。

std::set<Nonterminal> Filter(const std::set<Nonterminal>& symbolSet, const std::vector<GrammarSymbol*> w){

  //resulting set
  std::set<Nonterminal> rSet;

  std::vector<GrammarSymbol*>::const_iterator wit;
  std::set<Nonterminal>::const_iterator ntit;

  //iterate over all symbols of the word
  for(wit = w.begin(); wit != w.end(); wit++){

    //test if current symbol is a nonterminal
    const Nonterminal* nt = dynamic_cast<const Nonterminal*>(*wit);
    if(nt != NULL){
      std::cout << "current symbol " << nt->Str() << " is nonterminal" << std::endl;

      for(ntit = symbolSet.begin(); ntit != symbolSet.end(); ntit++){
        std::cout << ntit->Str() << "  " << (!(*ntit < *nt) && !(*nt < *ntit))<< std::endl;
        if(!(*ntit < *nt) && !(*nt < *ntit)){
          rSet.insert(*ntit);
        }
      }
    }
  }
  return rSet;
}

ここで何が起こっているのか、誰か説明してもらえますか? 私の知る限り、std::set は要素を operator< と比較することになっています。出力に示されているように、比較は問題なく機能しているようです。

私は自作のフィルターを使い続けたいと思いますが、もっと大きな根本的な問題があるのではないかと心配しています。

ありがとう！

編集：非端末および非端末の演算子<：

class Nonterminal : public GrammarSymbol{

  public: 

  /** The start state*/
  Idx mStartState;
  /** The stack symbol*/
  Idx mOnStack;
   /** The end state */
  Idx mEndState;
  //...
  }

Idx は単なる int の typedef です。

bool Nonterminal::operator<(const GrammarSymbol& other) const{
  if(typeid(*this) != typeid(other)) return true; //other is a terminal
  const Nonterminal& nt = dynamic_cast<const Nonterminal&>(other); //other is a nonterminal
  if (mStartState < nt.StartState()) return true;
  if (mOnStack < nt.OnStack()) return true;
  if (mEndState < nt.EndState()) return true;
  return false;    
}
4

1 に答える 1

3

あなたoperator <は間違っています

検討

Nonterminal nt1 (1,2,3);
Nonterminal nt2 (3,2,1);

bool b1 = nt1 < nt2;
bool b2 = nt2 < nt1;

nt1 < nt2比較のために：

  • 1 < 3すぐに怒鳴りtrueます。

の場合nt2 < nt1:

  • 3 < 1は成り立たないので、次に進みます
  • 2 < 2これは成り立たないので、次に進みます
  • 1 < 3保持する

したがって、 と の両方b1が にb2なりますtrue。これはナンセンスです

の2番目のバリアントについてはfilter、論理エラーのために機能します

for(ntit = symbolSet.begin(); ntit != symbolSet.end(); ntit++){
        std::cout << ntit->Str() << "  " << (!(*ntit < *nt) && !(*nt < *ntit))<< std::endl;
        if(!(*ntit < *nt) && !(*nt < *ntit)){
          rSet.insert(*ntit); 
        }

ここでは、一度ではなく、成立しないrSet.insert(*ntit);たびに呼び出されます。if(!(*ntit < *nt) && !(*nt < *ntit))

于 2012-11-13T12:03:59.333 に答える