Грамматика бизонов для сбора аргументов - PullRequest
Новая
       6

Грамматика бизонов для сбора аргументов

4 голосов
/ 19 августа 2010

У меня есть грамматика бизонов для сбора аргументов функции. Вот что это такое: 

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

Как создать массив целых чисел без фиксированной длины, который можно использовать как обычный массив C в Bison?

1 Ответ

4 голосов
/ 19 августа 2010

Вы не можете.

Однако вы можете создать нечто подобное, используя структуры данных. 

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

Если вы знаете тип данных, вы можете использовать int* или что хотите. Затем просто используйте realloc, чтобы развернуть его. «размер» - это текущий размер массива, а емкость - это размер выделенного пространства. (Мы делаем это, чтобы не продолжать перераспределять еще 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).

...