Bison grammar for collecting arguments

Question

I have a bison grammar for collecting arguments of a function. This is what it is so far:

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

How can I create an array of integers without a fixed length that can be used like a normal C array in Bison?

Answer 1

You can't.

However, you can create something similar using data structures.

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

If you know what type data is, you can use int* or whatever you want. Then just use realloc to expand it. "size" is the current size of the array, and capacity is the size of the allocated space. (We do this so we don't keep reallocing 1 more block - Its better to alloc chunks of blocks at a time).

You can also use what is called a linked list, which looks something like this:

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

Again, you could use int if you already know the data (I used a pointer in the example because all pointers are the same length in bytes).

Usually its more efficient to add to the beginning of a list. However, I find it nice when using bison to have another struct:

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

Because then you can add the end without performance issues and keep the normal order.

In bison, we can do something like

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;
}
;

(All code here is untested and might need slight modifications)

You can do the vector method here in a similar way to how I expanded the linked list - Just realloc and add in the last value. I think vectors might be more efficient, but a linked list might work well too.

Linked List has O(1) for adding and removing elements and is faster at that than a vector (no need to continually move blocks around when you run out of space). Its also just as fast to iterate, as both are O(n). You have to be careful about accessing a particular element, as that requires iteration, which is O(n) in a linked list. A vector can access an element in O(1).