如何在 win bison 中使用非平凡的 YYSTYPE

Question

起初我使用 bison 的 LR 解析器，现在由于一些语法难以处理，我决定尝试一下 bison 的 GLR 解析器。

目前我将 YYSTYPE 定义为一个非平凡的 class ParseNode，但是我在 bison 的生成代码中找到

union yyGLRStackItem {
  yyGLRState yystate;
  yySemanticOption yyoption; // my YYSTYPE is located in the struct
};

我的重要 class 包含在 union 中，因此整个代码无法编译。

通过搜索，我发现 %define api.value.type 可能对我有帮助。

但无论我如何尝试，输出总是显示

error: %define variable 'api.value.type' is not used

我的 win_bison 版本是 win_bison 2.4.8/2.5.8。也许这个版本不支持bison 3.0？如果可以，我还能做什么？

编辑

在我使用 bison 的 LR 解析器之前，我使用了我的 ParseNode，虽然堆栈不能自动增长，但在我切换到 GLR 解析器之前它确实工作了。我定义 ParseNode 如下：

struct ParseNode {
    FlexState fs; // all infomation I got from flex
    std::vector<ParseNode *> child;
    struct ParseNode * father;
    struct ParseAttr * attr = nullptr;
    void addchild(const ParseNode & n);
    ParseNode & get(int child_index);
    const ParseNode & get(int child_index) const;
    void setattr(ParseAttr * pa);
    std::string to_string() const { return fs.CurrentTerm.what; }

    ParseNode(const ParseNode &);
    ParseNode & operator= (const ParseNode &) ;
    ParseNode() = default;
    ParseNode(const FlexState & s, ParseNode * fa, ParseAttr * att = nullptr) : father(fa), attr(att), fs(s) {}
    ~ParseNode();
};

编辑 2

这是我对 ParseNode

的实现

ParseNode::~ParseNode()
{
    delete attr;
    for (int i = 0; i < child.size(); i++)
    {
        delete child[i];
    }
}
ParseNode::ParseNode(const ParseNode & pn)
{ 
    this->fs = pn.fs;
    this->father = pn.father;
    this->attr = (pn.attr == nullptr ? nullptr: pn.attr->clone());
    for (int i = 0; i < pn.child.size(); i++)
    {
        if (pn.child[i] != nullptr) {
            this->addchild(pn.get(i));
        }
        else {
            this->addchildptr(nullptr);
        }
    }
}
ParseNode & ParseNode::operator= (const ParseNode & pn) {
    if (this == &pn) {
        return *this;
    }
    else {
        delete this->attr;
        for (int i = 0; i < child.size(); i++)
        {
            delete child[i];
        }
        this->child.clear();

        this->fs = pn.fs;
        this->father = pn.father;
        this->attr = (pn.attr == nullptr ? nullptr : pn.attr->clone());
        for (int i = 0; i < pn.child.size(); i++)
        {
            this->addchild(pn.get(i));
        }

        return *this;
    }
}
void ParseNode::addchildptr(ParseNode * ptrn, bool add_back) {
    if (ptrn != nullptr) {
        ptrn->father = this;
    }
    if (add_back) {
        this->child.push_back(ptrn);
    }
    else {
        this->child.insert(this->child.begin(), ptrn);
    }
}
void ParseNode::addchild(const ParseNode & n, bool add_back ) {
    this->addchildptr(new ParseNode(n), add_back);
}

我通过 RAII 方法实现了我的 ParseNode class，因为资源管理将由编译器自动处理。所以我可以这样写代码：

/* more codes */
exp : exp '+' exp 
        {
            const ParseNode & exp1 = ;
            const ParseNode & op = ;
            const ParseNode & exp2 = ;
            ParseNode newnode = gen_exp(exp1, op, exp2);
            newnode.addchild(exp1); // add a copy of left operand exp's ParseNode
            newnode.addchild(op); // op
            newnode.addchild(exp2); // add a copy of right operand exp's ParseNode
            $$ = newnode;
        }
    /* more codes */

gen_exp函数生成一个ParseNode后，还有很多gen_函数，它们都接受const ParseNode &和returnParseNode。不用担心右边的三个ParseNode，因为当调用它的析构函数时，他拥有的所有指针（不包括father）都会被删除。 father 指针类似于 weak_ptr，除了帮助我调试外没有解析用途。一旦 bison 部分代码完成，%start 规则将 return 一个完整的语法树。

如果我将 ParseNode 更改为 ParseNode *，我需要做哪些更改？我决定在每个规则的末尾删除 .pointer_to_parsenode 到 $n.pointer_to_parsenode。是否足以避免内存泄漏，更重要的是，避免读取脏值或导致访问冲突？

Answer 1

一般来说，使用像您的 ParseNode 这样的重要数据类型的正常方法是使用指向此类对象的指针而不是对象本身作为您的语义类型。

解析栈，顾名思义，就是一个栈，随着解析的进行，元素被压入和弹出。因此，在堆栈上创建指向对象的引用或指针是危险的，因为稍后该堆栈槽可能会被完全不同的对象占用。您的 ParseNode 对象包含这样的指针：

std::vector<ParseNode *> child;
struct ParseNode * father;

如果没有看到您用来维护这些指针的代码，很难确定，但是您似乎不太可能在将 ParseNode 添加到 child 向量之前复制它，例如;如果您要插入此向量的节点地址是堆栈槽，那么您肯定会在执行期间的某个时刻调用未定义的行为。（编辑：好的，我错了：实现实际上在将整个树添加到 child 向量之前对整个树进行了深度复制，从而缩短了解析器执行时间输入大小是二次的而不是线性的。）

如果将语义类型设为 ParseNode* 而不是 ParseNode，则大部分问题都会消失，尽管您必须实施内存管理策略。（这不是缺点，因为允许对象在从堆栈中弹出时被删除的内存管理策略根本不起作用。）在仅构建语法 tree[=33 的简单应用程序中=]，问题并不严重，因为当你完成根时，你可以遍历树删除节点。如果应用程序可能形成语法林，例如通过通用子表达式 (CSE) 优化，那么内存管理就会变得更加困难。（虽然清扫垃圾收集器的代码并不太难，但我通常的方法是在 std::deque 或等效物中分配所有节点，然后在不再需要整个语法图之前不要担心删除任何节点，在哪一点只删除后备存储就足够了。）

一旦将语义类型更改为指针，使用非平凡类型的问题也会消失，因为指针是平凡类型，即使它指向的不是平凡类型。

最终结果是在您的解析节点实现和您的客户端代码（不再需要担心只使用对节点的引用以避免昂贵的副本）中进行大量简化，代价是使用std::unique_ptr 用于最终的 AST 根。

如何在 win bison 中使用非平凡的 YYSTYPE

How can I use non-trivial YYSTYPE in win bison

c++

yacc

compilation

bison