2

コードに Context Free Grammar を実装するために、いくつかのクラスを作成する必要があります。CFGには「左辺→右辺」という形式の制作規則があります。それらは次のように実装されます。

class GrammarProduction{

  public:

  Nonterminal mLhs;
  std::vector<GrammarSymbol*> mRhs;

プロダクション ルールを std::set に保存して、誰も重複したルールを追加できないようにしたいと考えています。重複検出を機能させるために、以下に示すように GrammarProductions の operator< を実装しました。

bool GrammarProduction::operator<(const GrammarProduction& other) const{
  if (mLhs < other.Lhs()) return true;
  if (mRhs.size() < other.Rhs().size()) return true;
  std::vector<GrammarSymbol*>::const_iterator it1, it2;
  it2 = other.Rhs().begin();
  for(it1 = mRhs.begin(); it1 != mRhs.end(); it1++){
    std::cout << (*it1) << std::endl;
    std::cout << (*it2) << std::endl;
    if(**it1 < **it2) return true;
    it2++;
  }
  return false;    
}

このコードを実行すると、次の行でセグメンテーション違反が発生します

    if(**it1 < **it2) return true;

ポインター *it2 が null であるためです。ただし、 *it2 を出力する行を変更すると

    std::cout << (*it2) << other.Str() << std::endl;

それは問題なく動作し、*it2 は null ではありません。その理由がわかりません。アドバイスをいただければ幸いです。呼び出される関数を投稿する必要がある場合は、投稿します。質問にとって重要ではなく、かなりの量になることを願っているため（少なくとも投稿の場合）、そうしませんでした。

編集：問題を絞り込みましたが、これに要約されます

bool GrammarProduction::operator<(const GrammarProduction& other) const{
  std::vector<GrammarSymbol*>::const_iterator it1, it2;

  it1 = mRhs.begin();
  std::cout << "it1:" << std::endl;
  std::cout << (*(mRhs.begin()))->Str() << std::endl; //output (1,2,2)
  std::cout << (*it1)->Str() << std::endl; //output (1,2,2)

  it2 = other.Rhs().begin();
  std::cout << "it2:" << std::endl;
  std::cout << (*(other.Rhs().begin()))->Str() << std::endl; //output (1,2,2)
  std::cout << (*it2)->Str() << std::endl; //Segmentation Fault

  //do whatever
  return false;
}
4

3 に答える 3

2

it2 == other.Rhs().end()ループでチェックする必要があります。イテレータを最後の要素を超えてインクリメントすると、それを逆参照することは無効になり、セグメンテーション違反が発生する可能性があります。

于 2012-10-12T12:12:59.313 に答える
2

未定義の動作を呼び出しています。関数はvalueRhs()でvector を返すため、完全な式の最後で破棄されます。

//          vvvvv -- created here
it2 = other.Rhs().begin();
//          gone here -- ^

これによりit2、ダングリング iteratorが作成されます。これは、基本的にダングリング ポインターと同じです。この反復子を逆参照すると、UB が発生します。修正するには、戻り値の型を参照にします。

std::vector<GrammarSymbol*>& Rhs(){ return mRhs; } // depending on your needs
std::vector<GrammarSymbol*> const& Rhs() const{ return mRhs; }
于 2012-10-12T13:41:16.007 に答える
1 
if(**it1 < **it2) return true;
it2++;

forループでは、it2がリストの最後に到達したかどうかを確認しないため、あまり良くありません。

動作するはずのバージョンは次のとおりです。

bool GrammarProduction::operator<(const GrammarProduction& other) const{
  if (mLhs < other.Lhs()) return true;
  if (mRhs.size() < other.Rhs().size()) return true;
  std::vector<GrammarSymbol*>::const_iterator it1, it2;
  it2 = other.Rhs().begin();
  it2End = other.Rhs().end();
  for(it1 = mRhs.begin(); it1 != mRhs.end(); it1++){
    std::cout << (*it1) << std::endl;
    if (it2 == it2End ) return true;
    std::cout << (*it2) << std::endl;
    if(**it1 < **it2) return true;
    it2++;
  }
  return false;

}

于 2012-10-12T12:07:38.073 に答える