2

我需要编写一些类来在我的代码中实现上下文无关语法。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 为空。但是，如果我将打印 *it2 的行更改为

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

它工作得很好，*it2 不为空。我不知道为什么会这样，任何建议都将不胜感激。如果有必要发布被调用的函数，我会这样做。我没有，因为我希望它对这个问题不重要，而且数量会相当大（至少对于一个帖子来说）。

编辑：我已经缩小了问题范围，归结为这个

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()返回向量，因此它在完整表达式的末尾被销毁：

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

这就产生it2了一个悬空迭代器，它与悬空指针基本相同。取消引用此迭代器将导致 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 回答