我试图通过在Bison文件中包含以下内容来使用mpz_tGMP库中的类型作为类型yylval:
%define api.value.type {mpz_t}
我检查了生成的解析器并正确生成了该行typedef mpz_t YYSTYPE,YYSTYPE稍后用于创建yylval.
mpz_t被typdefed如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:错误:从类型'struct __mpz_struct*'分配类型'YYSTYPE'时出现不兼容的类型
*++ yyvsp = yylval;
yyvsp被定义为指向YYSTYPE.
知道怎么解决这个问题吗？
如你所说,mpz_ttypedef'作为数组类型的别名:
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管理内存的方式,禁止直接分配给a 是必要的.见下面的注1.
Bison假设可以将语义类型YYSTYPE分配给(参见注释2),这意味着它不能是数组类型.这通常不是问题,因为通常YYSTYPE是联合类型,并且可以分配与数组成员的联合.因此,使用带有bison的数组类型没有问题,只要将其包含在%union声明中即可.
但你不能用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;
您可以在解析之前初始化值堆栈,并在解析完成后清除所有元素.这使得内存管理变得更加简单,并允许您重用已分配的肢体向量.
像运算符和括号这样没有相关语义值的标记不会占用值堆栈上的空间.这不会节省太多空间,但它避免了初始化和清除堆栈槽的需要,堆栈槽中从未有过有用的数据.
根据gmp手册,制作mpz_t(和其他类似类型)大小为1的数组只是为了弥补C缺乏传递参考.由于数组在用作函数参数时衰减为指针,因此无需显式标记参数即可获得传递引用.但它必须超越某人的想法,使用数组类型也会阻止直接分配给mpz_t.由于gmp管理内存的方式,直接分配无法工作.
Gmp值必须包括对分配的存储的引用.(必要的是,因为bignum的大小没有限制,所以不同的bignum是不同的大小.)一般来说,管理这样的对象有两种方式:
使对象不可变.然后它可以任意共享,因为不可能进行修改.
始终在分配时复制对象,使共享无法进行.然后可以修改对象而不影响任何其他对象.
例如,这两种策略以字符串的Java和C++方法为例.不幸的是,这两种策略都依赖于语言中的某些基础设施
不可变字符串需要垃圾回收.没有垃圾收集器,就无法确定何时可以释放字符串的存储空间.可以引用计数内存分配,但引用计数需要递增和递减,除非您准备让代码成为引用计数维护的沼泽,否则需要一些语言支持.
复制字符串需要覆盖赋值运算符.这在C++中是可能的,但很少有其他语言如此灵活.
上述两种策略也存在性能问题.
修改时需要复制不可变对象,这可以将简单的线性复杂度转换为二次复杂度.这是一个众所周知的问题,重复附加到Java或Python字符串; Java的StringBuilder旨在弥补这个问题.不可变的整数会很烦人; 累积和,例如(sum += value;)很常见,并且sum每次通过这样的循环必须复制可能会大大减慢循环速度.
另一方面,在赋值时强制复制使得无法共享常量,甚至无法重新排列向量.这可能导致大量额外复制,再次导致线性算法转变为二次算法.
Gmp选择了可变对象策略.Bignums 必须在赋值时复制,并且由于C不允许覆盖赋值运算符,最简单的解决方案是禁止使用赋值运算符,强制使用库函数.
因为有时候在没有复制的情况下移动bignums是有用的 - 例如,洗牌一组bignums - 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.)
野牛YYSTYPE为每次减少创造了一个临时物体; 这个临时值是$$在野牛行动中表示的实际变量.在执行简化操作之前,解析器执行等效的操作$$ = $1;.一旦完成动作,就会$1从$n堆栈中弹出并将$$其推到它上面.实际上,这会覆盖旧$1的$$,这就是必须使用临时的原因.(否则,设置$$动作会令人惊讶地失效$1.)