Parsing chain of greater than in Bison/Yacc

Question

I'm attempting to construct a linked list of comparisons using yacc/bison grammar.

In short I conceptually want to take:

3 < 4 < 5

And create a basic linked list of value, comparison, etc. I've tried to simplify what I have now to the specific-ist test case

%{

#define LESS_THAN 1

typedef struct mylist {
    long num;
    int sym;
    mylist* next;
} mylist;

void destroy_mylist(mylist* l) {
    mylist* n = NULL;

    if (l->next != NULL) {
        n = l->next;
    }   

    free(l);

    if (n != NULL) {
        destroy_mylist(n);
    }
}

mylist* create_list(long left, long right, int sym) {
    mylist* l = malloc(sizeof(mylist));
    mylist* r = malloc(sizeof(mylist));
    l->num = left;
    l->sym = sym; 
    l->next = r;  
    r->num = right;
    return l;
}

mylist* add_list(mylist* l, long num, int sym) {
    mylist* n = malloc(sizeof(mylist));
    mylist* t = l;
    n->num = num;

    while (t->next != NULL) {
        t = t->next;
    }

    t->sym = sym;
    t->next = n;
    return l;
}

%}
%destructor { destroy_mylist($$); } <list>

%union {
    long tmp;
}

%type <list> top_list expr compare_chain
%left '<'
%token <tmp> T_LONG "Long"
%start start

%% /* Rules */

start:
    top_list { $1; }
;

top_list:
    expr { $$ = $1; }
|   { $$ = NULL; }
;

expr:
    compare_chain { $$ = $1; }
|   T_LONG { $$ = $1; }
;

compare_chain:
    compare_chain '<' expr { $$ = add_list($1, $3, LESS_THAN); }
|   expr '<' expr { $$ = create_list($1, $3, LESS_THAN); }
;

%%

FWIW, this probably won't compile, it's an attempt to be a close example of what i'm trying to attempt here. The goal of this being that the result would be a mylist struct that would look like:

1 = {num = 3, sym = 1, next = 2}
2 = {num = 4, sym = 1, next = 3}
3 = {num = 5, sym = -, next = null}

Chris Dodd Chris Dodd · Accepted Answer · 2016-12-03T02:11:15

Your add_list function adds to the end of the list, but since your yacc rule is right recursive it builds the list from right to left, which means you want to add on to the front of the list. Change it to:

mylist* add_list(mylist* l, long num, int sym) {
    mylist* n = malloc(sizeof(mylist));
    n->num = num;
    n->sym = sym;
    n->next = l;
    return n;
}

You also have a broken grammar, defining expr in terms of compare_chain and compare_chain in terms of expr. Get rid of the expr: compare_chain rule, and change top_list to be top_list: compare_chain.

Parsing chain of greater than in Bison/Yacc

1 Answers