解析大于 Bison/Yacc 的链

Question

我正在尝试使用 yacc/bison 语法构建一个比较链接列表。

简而言之，我在概念上想采取：

3 < 4 < 5

并创建一个基本的值、比较等链接列表。我试图将我现在拥有的内容简化为特定测试用例

%{

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

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

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

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

%%

FWIW，这可能无法编译，它试图成为我在这里尝试的一个接近示例。这样做的目标是结果将是一个 mylist 结构，如下所示：

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

Answer 1

你的 add_list 函数添加到列表的末尾，但是由于你的 yacc 规则是右递归的，它从右到左构建列表，这意味着你想添加到列表的前面.将其更改为：

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

你的语法也有问题，用 compare_chain 定义 expr，用 expr 定义 compare_chain。摆脱 expr: compare_chain 规则，并将 top_list 更改为 top_list: compare_chain.

解析大于 Bison/Yacc 的链

Parsing chain of greater than in Bison/Yacc

grammar

yacc

bison