用于收集参数的 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)。