用于收集参数的 Bison 语法

Question

我有一个用于收集函数参数的野牛语法。到目前为止就是这样：

args: arg               {$$ = intArray($1);} //pseudo-code function
    | args arg          {$$ = $1 + $2;}       //pseudo-code array addition
arg : NUM               {$$ = $1;}
    | exp               {$$ = $1;}

如何创建一个没有固定长度的整数数组，可以像 Bison 中的普通 C 数组一样使用？

Answer 1

你不能。

但是，您可以使用数据结构创建类似的东西。

struct vector {
     void* data;
     size_t size;
     size_t capacity
};

如果您知道数据是什么类型，则可以使用 int* 或任何您想要的。然后只需使用realloc来扩展它。 “size”是数组的当前大小，capacity是
分配空间的大小。 （我们这样做是为了不再重新分配 1 个区块 - 它
最好一次分配大块的块）。

您还可以使用所谓的链接列表，它看起来像这样：

struct linked_list_node {
     void* data;
     struct linked_list_node* next;
};

同样，如果您已经知道数据，则可以使用 int （我在示例中使用了指针，因为所有指针都是相同的）长度（以字节为单位）。

通常添加到列表的开头会更有效。但是，我发现使用 bison 拥有另一个结构时很好：

struct linked_list {
     struct linked_list_node* start;
     struct linked_list_node* end;
};

因为这样您就可以添加结尾而不会出现性能问题并保持正常顺序。

在野牛中，我们可以做类似的事情

args: /* empty */ {
     struct linked_list* list = malloc(sizeof(struct linked_list));
     struct linked_list_node* node = malloc(sizeof(struct linked_list_node));
     list->start = node;
     list->end = node;

     $ = list;
}
|
args arg {
     struct linked_list_node* node = malloc(sizeof(struct linked_list_node));
     int val = $2; /* assuming arg is of type int */
     node->data = &val;

     struct linked_list* list = $1;
     list->end->next = node;
     list->end = node;

     $ = list;
}
;

（这里的所有代码都未经测试，可能需要稍作修改）

您可以在这里执行向量方法，其方式与我扩展链表的方式类似 - 只需重新分配并添加最后一个值。我认为向量可能更有效，但链表也可能效果很好。

链表的添加和删除元素的时间复杂度为 O(1)，并且比向量更快（当空间不足时，无需不断移动块）。它的迭代速度也同样快，因为两者都是O(n)。访问特定元素时必须小心，因为这需要迭代，这在链表中是 O(n) 。向量可以在 O(1) 中访问元素。