出于好奇,我正在编写一个编程语言文本解析器.假设我想将标记的不可变(在运行时)图形定义为顶点/节点.这些自然是不同类型的 – 一些标记是关键字,一些是标识​​符等.但是它们都共享共同特征,其中图形中的每个标记指向另一个标记.此属性允许解析器知道特定标记后面的内容 – 因此图形定义了语言的正式语法.我的问题是几年前我每天都停止使用C语言,并且从那时起使用了很多更高级的语言,而且我的头部在堆分配,堆栈分配等方面完全分散.唉,我的C生锈了.

不过,我想立刻爬上陡峭的山坡,为自己设定以最高效的方式用这种命令式语言定义这个图形的目标.例如,我想避免使用’new’在堆上单独分配每个令牌对象,因为我认为如果我将这些令牌的整个图形背靠背地分配(以线性方式像数组中的元素一样),根据参考原理的每个位置,这将有利于性能 – 我的意思是当整个图形被压缩以沿着内存中的“线”占据最小空间,而不是将所有其令牌对象放在随机位置时,这是一个加号？无论如何,就像你看到的,这是一个非常开放的问题.

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解决方案感到满意.非常感谢你提前.

解决方法:

我的C也生锈了,所以我可能不知道最好的解决方案.但是,因为没有其他人上前……

你是对的,在一个块中分配所有节点会给你最好的位置.但是,如果在程序启动时动态分配图形,则堆分配也可能会紧密聚集在一起.

要在一个内存块中分配所有节点,我想到了两种可能性：创建并填充Vector<>在启动时(缺点是现在你在内存中有两次图形信息),或者使用静态数组初始化程序“Node [] graph = {…};” .

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

如果要保留各种节点类,则必须使用多个数组/向量：每种类型一个.

无论哪种方式,节点之间的连接必须首先根据数组索引定义(Node [3]后跟Node [10]).为了获得更好的解析性能,您可以在程序启动时根据这些索引创建直接对象指针.

我不会将文字字符串放入任何节点(在您的情况下为“word”)：关键字,标识符和其他词汇元素的识别应该在与解析器分开的词法模块中完成.我认为如果你根据程序的输入区分Lexer生成的标记和程序用来解析输入的语法图节点,那么它也会有所帮助.

我希望这有帮助.