4

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

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

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

4

1 回答 1

4

你不能。

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

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

如果你知道数据类型是什么，你可以使用int*或任何你想要的。然后只需使用realloc它来扩展它。“size”是数组的当前大小，容量是分配空间的大小。（我们这样做是为了不要再重新分配 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)。

于 2010-08-19T18:03:07.737 回答