Grammaire de Bison pour la collecte des arguments

Question

J'ai une grammaire de bison pour collecter les arguments d'une fonction. C'est ce qu'il est à ce jour:

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

Comment puis-je créer un tableau de nombres entiers sans une longueur fixe qui peut être utilisé comme un tableau normal C dans Bison?

Answer 1

Vous ne pouvez pas. Toutefois, vous pouvez créer quelque chose de similaire à l'aide de structures de données.

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

Si vous savez quelles sont les données type est, vous pouvez utiliser int* ou tout ce que vous voulez. Ensuite, utilisez simplement realloc pour l'agrandir. "size" est la taille actuelle du tableau, et la capacité est la taille de l'espace alloué. (Nous faisons cela donc nous ne continuons pas à réaffecter 1 bloc de plus - Son mieux pour allouer des blocs de blocs à la fois).

Vous pouvez également utiliser ce qu'on appelle une liste chaînée, qui ressemble à ceci:

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

Encore une fois, vous pouvez utiliser int si vous connaissez déjà les données (j'ai utilisé un pointeur dans l'exemple parce que tout les pointeurs ont la même longueur en octets).

Habituellement, il est plus efficace d'ajouter au début d'une liste. Cependant, je trouve agréable lors de l'utilisation du bison d'avoir un autre struct:

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

Parce que vous pouvez ajouter à la fin sans problèmes de performance et maintenir l'ordre normal.

Dans le bison, nous pouvons faire quelque chose comme

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

(Tout le code est ici non testé et pourrait avoir besoin de légères modifications)

Vous pouvez faire la méthode vectorielle ici d'une manière similaire à la façon dont j'ai élargi la liste liée - Juste realloc et ajouter dans la dernière valeur. Je pense que les vecteurs pourraient être plus efficaces, mais une liste chaînée pourrait aussi bien fonctionner.

Liste liée a O(1) pour ajouter et supprimer des éléments et est plus rapide à ce qu'un vecteur (pas besoin de déplacer continuellement des blocs lorsque vous manquez d'espace). Il est également tout aussi rapide à itérer, car les deux sont O(n). Vous devez faire attention à l'accès à un élément particulier, car cela nécessite une itération, qui est O(n) dans une liste chaînée. Un vecteur peut accéder à un élément dans O(1).