parsing - 如何增加 bison 中的堆栈大小(并解决 "memory exhausted")

Question

我的基于 Bison 的解析器开始被我最近生成的一些中等大小的文件阻塞。

它抛出一个关于“内存耗尽”的异常。

bison 手册页说这可能是由于使用了右手递归。在不尝试重写语法的情况下(我的截止日期很紧)，我想简单地增加堆栈以使解析器解析该文件。我尝试遵循 bison 手册页并 #define YYMAXDEPTH 到大于默认 10000 的某个数字，但这不起作用。当我查看 bison 的输出时，似乎 YYMAXDEPTH 仅在定义 YYSTACK_RELOCATE 时才有条件使用，并且仅在这种情况下定义 YYSTACK_RELOCATE:

#if (! defined yyoverflow \
     && (! defined __cplusplus \
         || (defined YYLTYPE_IS_TRIVIAL && YYLTYPE_IS_TRIVIAL \
             && defined YYSTYPE_IS_TRIVIAL && YYSTYPE_IS_TRIVIAL)))

由于我使用 C++ 进行编译，因此上述 #ifdef 失败，因此未定义 YYSTACK_RELOCATE。

这是一个错误还是一个功能？有人知道增加堆栈大小的正确方法是什么吗？

顺便说一句，这是 bison 生成的堆栈溢出代码片段:

....
....
if (yyss + yystacksize - 1 <= yyssp)
{
  /* Get the current used size of the three stacks, in elements.  */
  YYSIZE_T yysize = yyssp - yyss + 1;

#ifdef yyoverflow
  {
    /* Give user a chance to reallocate the stack.  Use copies of
       these so that the &'s don't force the real ones into
       memory.  */
    YYSTYPE *yyvs1 = yyvs;
    yytype_int16 *yyss1 = yyss;
    YYLTYPE *yyls1 = yyls;

    /* Each stack pointer address is followed by the size of the
       data in use in that stack, in bytes.  This used to be a
       conditional around just the two extra args, but that might
       be undefined if yyoverflow is a macro.  */
    yyoverflow (YY_("memory exhausted"),
                &yyss1, yysize * sizeof (*yyssp),
                &yyvs1, yysize * sizeof (*yyvsp),
                &yyls1, yysize * sizeof (*yylsp),
                &yystacksize);

    yyls = yyls1;
    yyss = yyss1;
    yyvs = yyvs1;
  }
#else /* no yyoverflow */
# ifndef YYSTACK_RELOCATE
  goto yyexhaustedlab;             // <====== Overflows and throws exception here
# else
  ......
  ......

Answer 1

一般来说，C++ 对象(与 C 数据类型不同)不能由 memcpy 重定位。因此，bison 拒绝重新定位其堆栈，除非它以某种方式知道堆栈对象是“琐碎的”，并且如果对象是 C++ 对象，它会假设它们不是。

YYMAXDEPTH 是解析器将分配的最大堆栈，但初始堆栈大小为 YYINITDEPTH。由于 C++ 堆栈无法重定位，因此初始大小必须足以容纳任何输入，因此您需要增加 YYINITDEPTH，而不是 YYMAXDEPTH。

或者，你可以弄清楚如何告诉 bison C++ 堆栈对象是可重定位的(如果是的话)，或者你可以尝试更新版本的 bison:据称，v3 更愿意让你烧死自己，但是我自己没试过。最后，您可以定义 yyoverflow 来提供您自己的堆栈重定位机制:不幸的是，这没有记录并且不必要地复杂。