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を展開するために使用します。「サイズ」は配列の現在のサイズであり、容量は割り当てられたスペースのサイズです。(これを行うのは、1 つ以上のブロックを再割り当てし続けないようにするためです。ブロックのチャンクを一度に割り当てたほうがよいでしょう)。

次のようなリンク リストと呼ばれるものを使用することもできます。

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

繰り返しますが、int既にデータがわかっている場合は使用できます (すべてのポインターはバイト単位で同じ長さであるため、この例ではポインターを使用しました)。

通常、リストの先頭に追加する方が効率的です。ただし、バイソンを使用して別の構造体を使用する場合は、次のようにすると便利です。

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

(ここにあるすべてのコードはテストされておらず、わずかな変更が必要になる場合があります)

ここで、リンクされたリストを拡張した方法と同様の方法でベクトル メソッドを実行できます。最後の値を再割り当てして追加するだけです。ベクトルの方が効率的かもしれませんが、リンクされたリストもうまくいくかもしれません。

Linked List はO(1)要素を追加および削除する機能を備えており、ベクトルよりも高速です (スペースがなくなったときにブロックを継続的に移動する必要はありません)。両方と同じように、反復も同じくらい高速ですO(n)。O(n)リンクされたリストにある特定の要素へのアクセスには注意が必要です。これには反復が必要です。ベクトルは の要素にアクセスできますO(1)。

于 2010-08-19T18:03:07.737 に答える