3

出于好奇，我正在编写一个编程语言文本解析器。假设我想将令牌的不可变（在运行时）图定义为顶点/节点。这些自然是不同的类型——一些标记是关键字，一些是标识​​符，等等。但是它们都有一个共同的特征，即图中的每个标记都指向另一个标记。该属性让解析器知道特定标记后面可能会出现什么 - 因此该图定义了语言的形式语法。我的问题是几年前我不再每天使用 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 解决方案感到满意。非常感谢您提前。

4

3 回答 3

3

我不明白你将如何定义一个定义任何实用编程语言语法的标记“图”，特别是如果标记之间的关系是“允许遵循”的。

表示编程语言语法的常用方法是使用Backus-Naur 形式 (BNF)或称为“EBNF”的扩展版本。

如果您想表示一个 EBNF（“作为不可变图”），这个 SO answer 讨论了如何在 C# 中做到这一点。这些想法在 C++ 中有直接的类似物。

坏消息是大多数解析引擎不能直接使用 EBNF，因为它在实践中效率太低。使用语法规则的直接表示来构建高效的解析器是很困难的；这就是人们发明解析器生成器的原因。因此，除非您打算编写解析器生成器，否则根本需要将这些规则放入内存结构中，更不用说“高效”的了。

最后，即使您确实以某种方式优化了语法信息，它也可能不会对实际性能产生任何影响。解析器的大部分时间都花在对词素中的字符进行分组上，有时甚至只是进行空白抑制。

于 2010-10-28T22:46:20.933 回答
3

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

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

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

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

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

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

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

我希望这有帮助。

于 2010-10-28T19:57:31.883 回答
1

我不认为令牌的许多小分配将成为瓶颈，如果确实如此，您总是可以选择一个内存池。

解决问题；因为所有标记都有相似的数据（有一个指向下一个的指针，也许还有我们正在处理的标记的一些枚举值）你可以将相似的数据放在一个 std::vector 中。这将是内存中的连续数据，并且循环非常有效。

循环时，您检索所需的信息类型。我敢打赌，理想情况下，令牌本身只包含“动作”（成员函数），例如：如果上一个和下一个令牌是数字，而我是加号，我们应该将这些数字相加。

因此，数据存储在一个中心位置，分配令牌（但实际上可能不包含太多数据）并处理中心位置的数据。这实际上是一种面向数据的设计。

向量可能如下所示：

struct TokenData
{
    token *previous, *current, *next;
    token_id id; // some enum?
    ... // more data that is similar
}

std::vector<TokenData> token_data;

class token
{
    std::vector<TokenData> *token_data;
    size_t index;

    TokenData &data()
    {
        return (*token_data)[index];
    }

    const TokenData &data() const
    {
        return (*token_data)[index];
    }
}

// class plus_sign: token
// if (data().previous->data().id == NUMBER && data().next->data().id == NUMBER)

for (size_t i = 0; i < token_data.size(); i++)
{
    token_data[i].current->do_work();
}

这是一个想法。

于 2010-10-28T23:01:38.037 回答