best way to build array (or collection) of heterogeneous data types in bison / yacc semantic actions

Question

Think of it as more of a collection of elements which are not necessarily all of the same type. I have the following code:

// The struct I'll use inside Bison to dynamically create collections:
typedef struct ListElementType {
    union value {
        int intVal;
        float floatVal;
        char* charptrVal;
    } value;

    struct ListElementType* next;
} ListElementType;

Then in Bison I have:

%union
{
    int int_type;
    char char_type;
    float float_type;
    char* charptr_type;
    ListElementType* listElementType;
}
//----------------------------------------------------
%token <charptr_type> STRING
%token <int_type> INTEGER
%token <float_type> REAL
%type<listElementType> ElementList
//----------------------------------------------------
//----------------------------------------------------
ElementList
: ElementList ',' LiteralType
{ 
    $$ = malloc(sizeof(listElementType));
    $$->next = $1;
    $$->value = $3;
}

| LiteralType
{ 
    $$ = malloc(sizeof(listElementType));
    $$->next = 0;
    $$->value = $1;
}
;
//----------------------------------------------------
LiteralType
: STRING
| INTEGER
| REAL
;

There are a few things / issues here. But first, trying to generate the parser like this Bison says that $3 in the recursive production and $1 in the base /terminal case have no declared types. As I see it, they actually do have declared types. They are LiteralType and as such, can be either strings or ints or floats, which should be automatically set by leaving the last terminal productions blank (given that the first thing I did is make their type explicit by choosing the appropriate from the global union).

Second, I wouldn't expect Bison to complain that there's no declared type but rather that there's a clash or ambiguity since I'm assigning to $$->value but $2,$1 could have any of three possible values (depending on which union member was assigned in their respective productions). For this situation I made the value member in the ListElementType struct a union. I was thinking instead of trying to take advantage of the fact that a struct's first member will be in the "label" location of the struct address itself plus that a union's members all start also on the union's mem address to try and directly assign regardless of type. Something along the lines of (void)$$ = $2, whatever $2 happens to be.

SO, I changed to code to:

//----------------------------------------------------
ElementList
: ElementList ',' LiteralType
{ 
    $$ = malloc(sizeof(listElementType));
    $$->next = $1;
    *$$ = (void*)$3;
}

| LiteralType
{ 
    $$ = malloc(sizeof(listElementType));
    $$->next = 0;
    $$->value = $1;
}
;
//----------------------------------------------------
LiteralType
: STRING
{
    $<charptr_type>$ = $1;
}

| INTEGER
{
    $<int_type>$ = $1;
}

| REAL
{
    $<float_type>$ = $1;
}

;

Now I have explicitly set the union for the INT, REAL ,STRING cases. Which I thought wasn't necessary, but someone correct me if I'm wrong. AND, I also tried the typeless union assignment but still the same errors: that $3 and $1 have no declared types.

So my thoughts, questions:

Must I create separate StringList, IntList and RealList productions where the only thing that changes is that the right hand side nonterminal is straight out the sepecific type of element in the list, like so:

//----------------------------------------------------
ElementList
: IntElementList
| RealElementList
;

IntElementList
: IntElementList ',' INTEGER
{ 
    $$ = malloc(sizeof(listElementType));
    $$->next = $1;
    $$->intVal = $3;
}

| INTEGER
{ 
    $$ = malloc(sizeof(listElementType));
    $$->next = 0;
    $$->intVal = $1;
}

RealElementList
: RealElementList ',' REAL
{ 
    $$ = malloc(sizeof(listElementType));
    $$->next = $1;
    $$->floatVal = $3;
}

| REAL
{ 
    $$ = malloc(sizeof(listElementType));
    $$->next = 0;
    $$->floatVal = $1;
}

;

Or is there a way to state that LiteralType can have any of three values and then try and pull the typeless union assignment?

Or is the whole approach wrong and there's a better way?

Answer 1

Generally what you want to do is to have a type tag in your heterogenous list type:

typedef enum ListElementType { INTEGER, REAL, STRING } ListElementType
typedef struct ListElement {
    ListElementType  type;
    union {
        int intVal;
        float floatVal;
        char* charptrVal;
    } value;
    struct ListElement* next;
} ListElement;

Then whenever you create a ListElement, you set the type field appropriately. Later, you can check the type field to see what it is.

Your bison code then becomes:

%union
{
    int int_type;
    char char_type;
    float float_type;
    char* charptr_type;
    ListElement* listElement;
    struct { ListElement *head, *tail } list;
}
//----------------------------------------------------
%token <charptr_type> STRING
%token <int_type> INTEGER
%token <float_type> REAL
%type<list> ElementList
%type<listElement> LiteralType
//----------------------------------------------------
%%
//----------------------------------------------------
ElementList
: ElementList ',' LiteralType
    { $$.head = $1.head;
      $$.tail = $1.tail->next = $3; }
| LiteralType
    { $$.head = $$.tail = $1; }
;
//----------------------------------------------------
LiteralType
: STRING  { ($$ = NewListElement(STRING))->value.charptrVal = $1; }
| INTEGER { ($$ = NewListElement(INTEGER))->value.intVal = $1; }
| REAL    { ($$ = NewListElement(REAL))->value.floatVal = $1; }
;
%%
ListElement *NewListElement(ListElementType type) {
    ListElement *rv = malloc(sizeof(ListElement));
    rv->type = type;
    rv->next = 0;
    return rv; }

Answer 2

I ended up going for this approach.

1. Note that instead of having Element productions (ex LiteralType nonterminal) reduce to a union, it reduces to a struct with a union and a type member. The type member is the way to tell the type for each element stored in the collection.
2. Also note that the ListType struct has a void* pointer to element. In this contrived example a member of the ElementType struct type would have sufficed. However, I',m making the element a generic pointer to use the same structs to store, in turn, declaration lists which are made up of element lists.

%code requires { typedef struct Element {

%code requires {
    typedef struct Element {
        union {
            int intVal;
            float floatVal;
            char* charptrVal;            
        };

    char type;

    } ElementType;

    typedef struct ListType {
        void* element;
        struct ListType* next;

    } ListType;
}

%union
{
    int int_type;
    char char_type;
    float float_type;
    char* charptr_type;
    ListType* ListType;
    ElementType* ElementType;
}



%token <charptr_type> KEYWORD
%token <charptr_type> ID
%token <charptr_type> STRING
%token <int_type> INTEGER
%token <float_type> REAL
%token END 0


%type<ElementType> Element
%type<ListType> ElementList

//----------------------------------------------------
ElementList
: Element ',' ElementList
{
    $$ = malloc(sizeof(ListType));
    $$->element = (void*)$1;
    $$->next = $3;
}

| Element
{
    $$ = malloc(sizeof(ListType));
    $$->element = (void*)$1;
    $$->next = NULL;
}
;
//----------------------------------------------------
Element
: STRING
{
    char* aString = malloc(sizeof(char)*strlen($1)+1);
    strcpy(aString, $1);
    free(yylval.charptr_type);

    $$ = malloc(sizeof(ElementType));
    $$->charptrVal = aString;
    $$->type = 's';
}
| INTEGER
{
    $$ = malloc(sizeof(ElementType));
    $$->intVal = $1;
    $$->type = 'i';
}

| REAL
{
    $$ = malloc(sizeof(ElementType));
    $$->floatVal = $1;
    $$->type = 'f';    
}
;

Answer 3

I think you are missing the fact that Bison does not try to implement full C type checking. Since you have given different type names to STRING and LiteralType, it is its task to report that its default action ($$ = $1) does something weird from the (bison-)type checking point of view. If you do want to use the default assignment, just give them the same type (value in your case).

Also, you are coding twice the union value, that does not seem necessary:

%code requires
{
  typedef struct ListElementType {
    union value {
      int intVal;
      float floatVal;
      char* charptrVal;
    } value;

    struct ListElementType* next;
  } ListElementType;
}

%union
 {
   union value value;
   ListElementType* list;
 };

%token <value> STRING INTEGER REAL
%type <value> LiteralType 
%type <list> ElementList
%%
ElementList
: ElementList ',' LiteralType
{ 
  $$ = malloc(sizeof($$));
  $$->next = $1;
  $$->value = $3;
}
| LiteralType
{ 
  $$ = malloc(sizeof($$));
  $$->next = 0;
  $$->value = $1;
}
;
//----------------------------------------------------
LiteralType
: STRING
| INTEGER
| REAL
;