c++ - 如何在 C++ 中有效地实现异构不可变对象(immutable对象)的不可变图？

Question

出于好奇，我正在编写一个编程语言文本解析器。假设我想将 token 的不可变(在运行时)图定义为顶点/节点。这些自然是不同类型的——一些标记是关键字，一些是标识​​符，等等。但是它们都有共同的特征，即图中的每个标记都指向另一个标记。此属性让解析器知道特定标记后面可能有什么 - 因此该图定义了语言的形式语法。我的问题是，几年前我不再每天使用 C++，从那时起使用了很多高级语言，而我的头脑在堆分配、堆栈分配等方面完全支离 splinter 。唉，我的 C++ 生锈了。

不过，我还是想立刻爬上陡峭的山坡，并为自己设定目标，以最高效的方式用这种命令式语言定义这个图。例如，我想避免使用“new”在堆上单独分配每个 token 对象，因为我认为如果我背靠背分配这些 token 的整个图形可以这么说(以线性方式，如数组中的元素)，根据引用原则的局部性，这将以某种方式有利于性能——我的意思是当整个图形被压缩以沿着内存中的“线”占用最小空间，而不是将其所有标记对象都放在随机位置时，这是一个加号？无论如何，如您所见，这是一个非常开放的问题。

class token
{

}

class word: token
{
    const char* chars;

    word(const char* s): chars(s)
    {
    }
}

class ident: token
{
    /// haven't thought about these details yet
}

template<int N> class composite_token: token
{
    token tokens[N];
}

class graph
{
    token* p_root_token;
}

直接的问题是:创建这个图形对象的过程是什么？它是不可变的，并且它认为结构在编译时是已知的，这就是为什么我可以并且想要避免按值复制东西等等 - 应该可以用文字组成这个图？我希望我在这里说得有道理……(这不是我第一次没有。)该图将在运行时由解析器用作编译器的一部分。仅仅因为这是 C++，我也会对 C 解决方案感到满意。非常感谢您。

Answer 1

我的 C++ 也生锈了，所以我可能不知道最好的解决方案。但是既然没有其他人站出来......

你说得对，在一个区 block 中分配所有节点会给你最好的位置。但是，如果您在程序启动时动态分配图，您的堆分配很可能也会紧密地聚集在一起。

要在单个内存块中分配所有节点，我想到了两种可能性:在启动时创建并填充一个 Vector<>(缺点是现在您在内存中有两次图形信息)，或者使用静态数组初始值设定项“节点 [] 图 = { ... };” .

对于这两种方法，最大的障碍是您想要创建异构对象图。一个明显的解决方案是“不要”:您可以使您的节点成为所有可能字段的超集，并使用显式“类型”成员区分类型。

如果要保留各种节点类，则必须使用多个数组/vector :每种类型一个。

无论哪种方式，节点之间的连接都必须根据数组索引进行初始定义(Node[3] 后跟 Node[10])。当然，为了更好的解析性能，您可以根据这些索引在程序启动时创建直接对象指针。

我不会将文字字符串放入任何节点(在您的情况下为“单词”):关键字、标识符和其他词汇元素的识别应该在与解析器分开的词法分析器模块中完成。我认为，如果您在词法分析器基于程序输入生成的标记与您的程序用于解析输入的语法图节点之间区分终端学，也会有所帮助。

希望对您有所帮助。