尝试使用 GNU GMP 库中的类型作为 Bison 的 yylval 类型时出错

2023-11-27

我正在尝试使用该类型mpz_t来自 GMP 库的类型yylval通过在 Bison 文件中包含以下内容:

%define api.value.type {mpz_t}

我检查了生成的解析器,它正确生成了该行typedef mpz_t YYSTYPE, with YYSTYPE后来被用来创建yylval.

mpz_t类型定义为typedef __mpz_struct mpz_t[1];在 GMP 头文件中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”时不兼容的类型 ‘结构__mpz_struct *’

*++yyvsp = yylval;

yyvsp被定义为一个指向YYSTYPE.

知道如何解决这个问题吗?


正如你所说,mpz_t被 typedef'ed 作为数组类型的别名:

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 */

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

Bison 假设语义类型YYSTYPE可以赋值给(见注2),这意味着它不能是数组类型。这通常不是问题,因为通常YYSTYPE是联合体类型,可以对带有数组成员的联合体进行赋值。因此,只要将数组类型包含在 bison 中,使用数组类型就没有问题。%union宣言。

但你不能对 gmp 这样做,因为虽然它可以编译,但它不会工作。您最终会出现大量内存泄漏,并且很可能会出现模糊的错误,其中 gmp 计算出错误的值(或者以更明显的方式失败,例如free从下面的内存中取出mpz_t).

Using mpz_t直接将对象作为语义值是可能的,但这并不容易。您最终将花费大量时间思考哪些堆栈槽具有已初始化的语义值;哪些具有需要的值mpz_cleared,以及许多其他令人不安的细节。

一个更简单(但不简单)的解决方案是使语义值成为指向 an mpz_t。如果您只是制作一个 bignum 计算器,您可以完全绕过语义值并维护自己的值堆栈。只要每个归约操作从值堆栈中弹出其所有参数并推送其结果,就可以解决这个问题。

这个值栈也将是一个向量mpz_t值,但它在几个重要方面与解析器堆栈不同,因为它完全在您的控制之下:

  1. 您没有义务创造 bison 需要创造的临时价值(参见注释 2)。例如,如果您想做一个加法,从堆栈中弹出两个操作数并将结果推回,您可以这样做:

    mpz_add(val_stack[top - 2], val_stack[top - 2], val_stack[top - 1]);
    --top;
    
  2. 您可以在解析之前初始化值堆栈,并在解析完成后清除所有元素。这使得内存管理变得更加简单,并且可以让您重用分配的肢体向量。

  3. 诸如运算符和括号之类的标记没有关联的语义值,因此不占用值堆栈上的空间。这并没有节省太多空间,但它避免了初始化和清除堆栈槽的需要,因为堆栈槽中从来没有有用的数据。

Notes

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

根据gmp手册,制作mpz_t(和其他类似类型)大小为 1 的数组只是为了补偿 C 缺乏按引用传递。由于数组在用作函数参数时会衰减为指针,因此您无需显式标记参数即可实现引用传递。但肯定有人想到过,使用数组类型也会阻止直接分配给mpz_t。由于 gmp 管理内存的方式,直接分配无法工作。

Gmp 值必须包含对分配存储的引用。 (必然的,因为bignum的大小没有限制,所以不同的bignum有不同的大小。)一般来说,有两种管理对象的方法:

  1. 使对象不可变。然后就可以任意共享,因为无法修改。

  2. 始终在分配时复制对象,从而使共享变得不可能。然后可以修改对象而不影响任何其他对象。

例如,Java 和 C++ 的字符串方法就是这两种策略的例证。不幸的是,这两种策略都依赖于语言中的一些基础设施:

  • 不可变字符串需要垃圾回收。如果没有垃圾收集器,就无法知道何时可以释放字符串的存储空间。可以对内存分配进行引用计数,但引用计数需要递增和递减,除非您准备好使代码成为引用计数维护的沼泽,否则您需要一些语言支持。

  • 复制字符串需要覆盖赋值运算符。这在 C++ 中是可能的,但很少有其他语言能如此灵活。

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

  • 不可变对象在修改时需要复制,这可以将简单的线性复杂性变成二次复杂性。这是一个众所周知的重复附加到 Java 或 Python 字符串的问题; Java 的 StringBuilder 旨在弥补这个问题。不可变的整数会很烦人;累积总和是很常见的,例如(sum += value;),并且必须复制sum每次经过这样的循环都会大大减慢循环速度。

  • 另一方面,强制复制赋值使得共享常量变得不可能,甚至无法重新排列向量。这可能会导致大量额外的复制,再次导致线性算法变成二次算法。

Gmp 选择了可变对象策略。大数must在赋值时被复制,并且由于 C 不允许覆盖赋值运算符,最简单的解决方案是禁止使用赋值运算符,强制使用库函数。

由于有时在不复制的情况下移动 bignum 是有用的——例如,洗牌 bignum 数组——gmp 还提供了一个交换函数。而且,如果您非常非常小心并且比我更了解 gmp 的内部结构,那么可能只使用union上面提到的 hack,或者使用memcpy(),为了对 gmp 对象进行更复杂的重新排列,前提是您保持重要的不变量:

每一个四肢向量必须精确地被一个且仅一个引用mpz_t object.

重要的原因是 gmp 将在必要时使用 realloc 调整 bignum 的大小。假设a and b are mpz_t,我们使用一些 hack 使它们都是相同的 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 and/or tmp2大于b.)

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

Bison 创建了一个临时的YYSTYPE每次减少的对象;这个临时变量是实际变量,表示为$$在野牛行动中。在执行归约操作之前,解析器执行相当于$$ = $1;。一旦行动完成,$1通过$n从堆栈中弹出,并且$$被推到它上面。实际上,这会覆盖旧的$1 with $$,这就是必须使用临时的原因。 (否则,设置$$在一个行动中会令人惊讶地无效$1.)

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

尝试使用 GNU GMP 库中的类型作为 Bison 的 yylval 类型时出错 的相关文章

随机推荐