c - 尝试将GNU GMP库中的类型用作Bison的yylval类型时出错

Question

我试图通过在Bison文件中包含以下内容，来将GMP库中的mpz_t类型用作yylval的类型：

%define api.value.type {mpz_t}

我检查了生成的解析器，它正确生成了行 typedef mpz_t YYSTYPE，随后使用 YYSTYPE创建了 yylval。

在GMP头文件 mpz_t中， typedef __mpz_struct mpz_t[1];被定义为 gmp.h。依次将 __mpz_struct定义为

typedef struct
{
    // struct members here - don't believe they're important
} __mpz_struct;

Bison运行没有错误，但是每当我尝试创建可执行文件时，都会出现以下错误：


calc.tab.c：在“ yyparse”函数中：

calc.tab.c：1148：12：错误：
从类型分配为类型“ YYSTYPE”时不兼容的类型
‘struct __mpz_struct *’

* ++ yyvsp = yylval;


yyvsp被定义为指向 YYSTYPE的指针。

关于如何解决这个问题的任何想法？

Answer 1

如您所说，mpz_t被定义为数组类型的别名：

typedef __mpz_struct mpz_t[1];

结果，分配给 mpz_t类型的变量是非法的：

mpz_t a, b;
mpz_init(b);
a = b;  /* Error: incompatible types when assigning to type ‘mpz_t’ */
        /* from type ‘struct __mpz_struct *’                        */

相反，必须使用内置分配功能之一：

mpz_t a, b;
mpz_inits(a, b, 0);
mpz_set(a, b);   /* a is now a copy of b */

由于gmp管理内存的方式，必须禁止直接分配给 mpz_t。请参阅下面的注释1。

Bison假定可以将语义类型 YYSTYPE分配给它（请参见注释2），这意味着它不能是数组类型。通常这不是问题，因为通常 YYSTYPE是联合类型，并且可以将具有数组成员的联合分配给它。因此，只要将数组类型包含在 %union声明中，就可以将其与bison一起使用。

但是您绝对不能使用gmp这样做，因为尽管它将编译，但将无法工作。最终会导致大量的内存泄漏，并且最终可能会遇到难以理解的错误，其中gmp计算错误的值（或者以更明显的方式失败，例如 free从 mpz_t下释放内存） 。

可以直接使用 mpz_t对象作为语义值，但这并不容易。您最终将花费大量时间来思考哪些堆栈插槽具有已初始化的语义值。哪些具有需要 mpz_clear的值以及许多其他麻烦的细节。

一个更简单（但不简单）的解决方案是使语义值成为指向 mpz_t的指针。如果您只是制作一个bignum计算器，则可以完全绕开语义值并维护自己的值堆栈。只要每个归约操作从值堆栈中弹出其所有参数并推送其结果，该方法就可以解决。

此值堆栈也将是 mpz_t值的向量，但它在某些重要方面与解析器堆栈不同，因为它完全在您的控制之下：


您没有义务创造野牛需要创造的临时价值（见注释2）。例如，如果要进行加法运算，这会将两个操作数从堆栈中弹出并将结果推回去，则可以执行以下操作：

mpz_add(val_stack[top - 2], val_stack[top - 2], val_stack[top - 1]);
--top;

您可以在解析之前初始化值堆栈，并在解析完成后清除所有元素。这使内存管理更加简单，并使您可以重用分配的肢体向量。
没有关联语义值的标记（如运算符和括号）不会在值堆栈上占用空间。这样不会节省太多空间，但是却避免了初始化和清除堆栈插槽的需求，而堆栈插槽中从来没有有用的数据。


笔记

1. GMP为什么不鼓励直接分配

根据gmp手册，制作大小为1的 mpz_t（和其他类似类型）数组只是为了弥补C缺少传递引用的情况。由于数组在用作函数参数时会衰减为指针，因此无需显式标记参数即可获得引用传递。但是一定有人想过，使用数组类型还会阻止直接分配给 mpz_t。由于gmp管理内存的方式，直接分配无法工作。

Gmp值必须包含对已分配存储的引用。 （由于对bignum的大小没有限制，因此，不同的bignum的大小是不同的。）通常来说，有两种管理对象的方式：


使对象不变。这样就可以任意共享，因为不可能进行修改。
始终在分配时复制对象，从而无法共享。然后可以修改对象而不会影响任何其他对象。


例如，这两种策略以Java和C ++字符串方法为例。不幸的是，这两种策略都依赖于该语言的某些基础架构：


不可变的字符串需要垃圾回收。没有垃圾收集器，就无法判断何时可以释放字符串存储。可以对内存分配进行引用计数，但是引用计数需要增加和减少，除非您准备使代码成为引用计数维护的沼泽，否则您需要某种语言支持。
复制字符串需要覆盖赋值运算符。这在C ++中是可能的，但是很少有其他语言如此灵活。


上述两种策略都存在性能问题。


不变对象需要在修改时进行复制，这会将简单的线性复杂度转换为二次复杂度。对Java或Python字符串进行重复追加是一个众所周知的问题。 Java的StringBuilder旨在弥补这一问题。不可变的整数会很烦人。累积总和非常常见，例如（ sum += value;），并且每次通过这样的循环都必须复制 sum会极大地降低循环速度。
另一方面，强制赋值复制使共享常量，甚至重新排列向量都变得不可能。这可能会导致大量额外的复制，再次导致线性算法变成二次算法。


Gmp选择了可变对象策略。必须在赋值时复制Bignum，并且由于C不允许重写赋值运算符，因此最简单的解决方案是禁止使用赋值运算符，从而强制使用库函数。

由于有时在不复制的情况下移动bignum很有用-例如，洗改bignum的数组-gmp还提供了交换功能。而且，如果您非常小心并且比我更了解gmp的内部结构，则可能可以使用上述的 union hack或使用 memcpy()来对gmp进行更复杂的重新排列对象，只要您保持重要的不变式：

每个肢体向量都必须仅由一个且仅一个 mpz_t对象引用。

重要的原因是gmp会在必要时使用realloc调整bignum的大小。假设 a和 b是 mpz_t，我们使用一些技巧使它们都成为相同的bignum，共享内存：

memcpy(a, b, sizeof(a));

现在，我们将 b变得更大：

mpz_mul(b, b, b);  /* Set b to b squared */

这可以正常工作，但在内部它会像

tmp = realloc(b->_mp_d, 2 * b->_mp_size);
if (tmp) b->_mp_d = tmp;

为了使 b足够大以容纳结果。这对于 b可以正常工作，但是可能会导致 a指向四肢进入混乱状态，因为成功分配新存储的 realloc将自动释放旧存储。

任何增加 b大小的操作都将发生相同的情况；将其平方就位只是一个例子。在几乎任何会增加 a： b大小的修改之后， mpz_add(b, tmp1, tmp2);都可能以悬挂指针结尾（假定 tmp1和/或 tmp2大于 b。）

2.为什么Bison要求语义值可分配

野牛为每次减少创建一个临时的 YYSTYPE对象；这个临时变量是野牛动作中表示为 $$的实际变量。在执行归约操作之前，解析器将执行 $$ = $1;的等效项。操作完成后，将 $1至 $n从堆栈中弹出，并将 $$压入堆栈。实际上，这会用 $1覆盖旧的 $$，这就是为什么必须使用临时文件的原因。 （否则，在操作中设置 $$会使 $1无效。）