这是在 C++ 中构造抽象语法树的语法节点的合理方法(或者是否有更安全或更节省内存的构造)?

Is this a reasonable way to construct the syntax node of an abstract syntax tree in C++ (or is there a safer or more memory-efficient construction)?

提问人:Jose Fruan 提问时间:7/13/2023 更新时间:7/13/2023 访问量:59

问:

我正在为一种新的通用编程语言编写一个(很可能是自下而上的)解析器。我的解析器接受令牌流。为了完整起见,这里是 .token_t

struct token_t {
    // Kind of token enum
    token_kind kind;
    // Overall position in file
    int position;
    // The location of the token's first associated char (left-to-right, top-to-bottom)
    // Useful for giving feedback if there is a syntax error
    int row, col;
    // The substring associated with the token
    std::string value;
};

语法节点由以下部分组成:

struct syntax_node_t {
    // Kind of syntax node enum (what this node represents, i.e. binary expression)
    syntax_node_kind kind;
    // Token associated with this syntax node
    token_t token;
    // A list of children associated with this kind of syntax node
    std::vector<syntax_node_t> children;
};

我希望解析器在构造时以及完成抽象语法树时存储指向树根(即 )的指针。syntax_node_t

我有一个担忧,那就是子向量应该是指向 的指针向量,以便子向量仅具有对节点的引用而不是它们的副本。这种担忧是否有效,我应该将类型更改为指针吗?syntax_node_t

也欢迎任何其他反馈。

C++ 解析 编译器构造 编程语言 抽象语法树

评论

0赞 Botje 7/13/2023
不,这很好。它们之所以被称为语法,是因为每个节点只有一个所有者,所以 a 就可以了。std::vector<syntax_node_t>
0赞 Botje 7/13/2023
其他一些备注:如果将整个源文件/输入加载到内存中,则可以将 和 替换为单个 或 .但不要担心过早的优化:计算机速度很快,解析是任何编程语言实现中最不重要的部分。valuepositionstd::string_viewstd::span
0赞 Eljay 7/13/2023
根据你正在做的事情,LLVM的万花筒编程语言前端(玩具教程语言)可能会引起你的兴趣。或者,Aho、Ullman、Sethi 和 Lam 撰写的备受推崇的 Compilers “龙书”可能会引起人们的兴趣。
0赞 kaba 7/13/2023
我支持@Botje的提议,即替换值/位置(如果他的介词成立的话)。这不仅仅是一个优化的问题,而是合理选择类型的问题。总的来说,我会重新考虑 int 对位置/行/列的选择:负值在这里真的有意义吗?让他们不签名会更有意义吗?
0赞 chrysante 7/13/2023
只要您不将指向树节点的指针(即父指针)存储在其他地方,这种方法就可以了,这在语义分析中可能很有帮助。然后,您可以使用 稳定地址。std::vector<std::unique_ptr<syntax_node_t>>

答: 暂无答案