用C ++编写的解释器如何处理内置函数？有什么好方法？

Question

我正在用C++为自己设计的类似lisp的语言编写解释器。这只是为了娱乐和学习，所以我不会追求绝对效率，但我会尽力让代码看起来更整洁清晰。我现在在考虑如何实现内置函数。

基本上，我的做法是：

我有一个抽象基类DataObject，它只提供类型信息(目前是double、int、bool)，并由特定的数据容器继承，例如：

class DataObject
{
public:
    virtual const Type *type() = 0;
};

template<class T, const Type * myType>
class DataObjectValue : public DataObject
{
T value;
public:
    const Type *type(){return myType;}
};

但是，当我想执行加法运算时，我必须做类似于以下的操作:

DataObject * sum(DataObject *a, DataObject *b)
{
    if(a->type() == &Integer and b->type == &Integer)
    {
        DataObjectValue<int>* ia = dynamic_cast< DataObjectValue<int>* >(a);
        DataObjectValue<int>* ib = dynamic_cast< DataObjectValue<int>* >(b);
        return new DataObjectValue<int>(ia->value+ib->value);
    }
    else if(a->type() == &Real and b->type == &Real)
    {
        DataObjectValue<double>* ra = dynamic_cast< DataObjectValue<double>* >(a);
        DataObjectValue<double>* rb = dynamic_cast< DataObjectValue<double>* >(b);
        return new DataObjectValue<double>(ra->value+rb->value);
    }
    else...
}

对于一些操作符（如 - * / < <= >= < > 等）和其他类型，重复的代码会很快让人感到烦恼。这样做很难维护。当然，我已经尽可能地简化了整个过程，引入了大量的模板，但是，我仍然认为可能有更清晰的方法。您是否 a) 理解我的问题（我怀疑我的解释，而不是您的能力）b) 有任何建议？

- djfm

---

要不把 DataObjectValue 设为联合类型怎么样？这样，你就可以检查 a.typy() == b.type() 然后使用 switch 语句。虽然这并不会提高性能（也就是说，算法基本上是相同的），但你的代码会更加简洁。 - Shahbaz

我恐怕无法避免这些情况。你可以将它们放在另一个文件中，只需编写一次，然后再也不看它，这样就不会干扰你更重要的代码了。 - Shahbaz

@Shahbaz 实际上，switch语句可以转换为跳转表，但我认为一系列的if/else if语句不能。 - Seth Carnegie

我用过的一种策略是编写一个更小、更简单的Python脚本来生成那些冗长而重复的C++代码，以使其易于维护。 - TJD

@SethCarnegie 当然可以。但这并不是重点，所以我不想让事情变得更复杂。 - Shahbaz

Python脚本看起来不错，但我想尽可能地使用纯C++来完成它 - 这也是我不太喜欢使用宏的原因。我知道宏是C++的一部分，但是...我不喜欢编写自动补全无法工作的代码 ;) - djfm

Answer 1

您当前的实现基本上是在存储的确切类型中执行类型擦除，并且您正在以稍微不寻常的方式进行操作（为什么不使用枚举而不是指向唯一对象的指针？）

我建议从基类提供“提升”操作，并在每个级别中实现它们：

enum DataType {
   type_bool,
   type_int,
   type_double
};

struct DataObject {
   virtual ~DataObject() {}    // remember to provide a virtual destructor if you
                               // intend on deleting through base pointers!!!
   virtual DataType type() const = 0;
   virtual bool   asBool() const = 0;
   virtual int    asInt() const = 0;
   virtual double asDouble() const = 0;
};

然后，您可以在一个简单的函数对象中实现这些操作：

template <typename T>
T sum_impl( T lhs, T rhs ) {
   return lhs + rhs;
}

并提供一个简单的分发函数：

DataType promoteTypes( DataType lhs, DataType rhs ) {
   if ( lhs == type_double || rhs == type_double ) {
      return type_double;
   } else if ( lhs == type_int || rhs == type_int ) {
      return type_int;
   } else {
      return type_bool;
   }
}
template <template <typename T> T operation (T,T)>
DataObject* perform_operation( DataObject* lhs, DataObject* rhs, operation op ) const {
   DataType result_type = promoteTypes( lhs->type(), rhs->type() );
   switch ( result_type ) {
   case type_double: 
      return new DataObjectValue<double>( op( lhs->asDouble(), rhs->asDouble() );
   case type_int:
      return new DataObjectValue<int>( op( lhs->asInt(), rhs->asInt() );
   case type_bool:
      return new DataObjectValue<bool>( op( lhs->asBool(), rhs->asBool() );
   default:
      abort();
   }
}

所有组件都准备就绪后，您几乎可以轻松地实现操作，只需为特定操作提供函数模板（如上述 sum），然后使用其余部分：

// sum_impl as above
DataObject* sum( DataObject* lhs, DataObject* rhs ) {
   return perform_operation( lhs, rhs, sum_impl );
}

这只是我会使用的模式，但我会做出一些改变。我更喜欢尽可能少地使用指针，这意味着我不会通过指针传递参数，而是通过引用传递。此外，我会进行适当的类型擦除（请查看boost any），并将Object作为包含DataObject元素的完整类型，并在该类型上执行操作（而不是在层次结构上）。这将使您能够提供函数，也可以通过值返回（并在内部隐藏动态内存分配，这也意味着资源管理可以在Object中控制，而不是用户代码的责任）。通过这些更改，您可以重复使用和简化上述结构，并提供更清晰的解决方案。

- David Rodríguez - dribeas

---

我非常喜欢这个版本，它更加优雅，接近于我的实际代码的非剥离版本。感谢您提供有趣主题的各种指针，我会深入研究！不过我对指针并不太担心，因为这些类都是从一个我已经实现了引用计数的类派生而来的（因为表达式树往往难以手动管理）。 - djfm

根据您的语言如何发展（即如果某些操作无法在特定类型的组合上执行），您可能希望转向更复杂的解决方案。至于指针，我仍然会考虑它，即使没有其他原因，它也可以使代码更容易理解（即您知道NULL不是任何函数的有效参数，无需记住特定指针是否已经包装在引用计数智能指针中 - 除非您修改所有接口以使用该引用计数指针）。 - David Rodríguez - dribeas

Answer 2

你可以使用宏的方法：

（为了简洁起见，我保留了\）

#define IMPLEMENT_OPERATOR(name, operator)
DataObject * name(DataObject *a, DataObject *b)
{
    if(a->type() == &Integer and b->type == &Integer)
    {
        DataObjectValue<int>* ia = dynamic_cast< DataObjectValue<int>* >(a);
        DataObjectValue<int>* ib = dynamic_cast< DataObjectValue<int>* >(b);
        return new DataObjectValue<int>(ia->value operator ib->value);
    }
    else if(a->type() == &Real and b->type == &Real)
    {
        DataObjectValue<double>* ra = dynamic_cast< DataObjectValue<double>* >(a);
        DataObjectValue<double>* rb = dynamic_cast< DataObjectValue<double>* >(b);
        return new DataObjectValue<double>(ra->value operator rb->value);
    }
    else...
}

现在，完成这个之后你可以这样做：

IMPLEMENT_OPERATOR(sum, +);
IMPLEMENT_OPERATOR(multiply, *);
IMPLEMENT_OPERATOR(division, /);
...

这种方法快速且易于维护，但对于特殊运算符可能存在问题。

编辑： Shahbaz提到您可以在其他宏中使用宏。可以按以下方式应用此方法。

（为简洁起见，再次省略\）

#define IMPLEMENT_OPERATOR_TYPE(typeobject, internal_type, operator)
if(a->type() == &typeobject and b->type == &typeobject)
{
    DataObjectValue<internal_type>* ia = dynamic_cast< DataObjectValue<internal_type>* >(a);
    DataObjectValue<internal_type>* ib = dynamic_cast< DataObjectValue<internal_type>* >(b);
    return new DataObjectValue<internal_type>(ia->value operator ib->value);
}

现在可以在IMPLEMENT_OPERATOR宏中使用：

#define IMPLEMENT_OPERATOR(name, operator)
DataObject * name(DataObject *a, DataObject *b)
{
    IMPLEMENT_OPERATOR_TYPE(&Integer, int, operator);
    IMPLEMENT_OPERATOR_TYPE(&Real, double, operator);
    ...
}

- Constantinius

---

宏来拯救！您甚至可以在每种情况下在宏内部使用宏。 - Shahbaz

好的，操作符中的每个类型也可以用宏声明。 - Constantinius

Answer 3

如果两个操作数必须是相同的类型，那么你可以尝试这样做：

class DataObject
{
public:
    virtual const Type *type() = 0;
    virtual DataObject *operator+(DataObject&) = 0;
    virtual DataObject *operator-(DataObject&) = 0;
    virtual DataObject *operator*(DataObject&) = 0;
    virtual DataObject *operator/(DataObject&) = 0;
};

template<class T, const Type * myType>
class DataObjectValue : public DataObject
{
    typedef DataObjectValue<T, myType> selfType;
    T value;
public:
    const Type *type(){return myType;}
    DataObject *operator+(DataObject& other) {
        if (other.type() != myType)
            return null;
        selfType &otherValue = static_cast<selfType&>(other);
        return new selfType(value + otherValue.value);
    }
    // etc.
};

当你开始允许 int + double 时，情况会变得更加复杂。在某些情况下，您可以通过检查所有已知的类型（即已经声明的类型）来处理它，否则将自己传递给其他对象：

if (other.type() != myType)
    return other + *this; // assume *other is a <double> that knows how to add an <int>

- Neil