使用左递归文法在yacc中构建链表

Question

我想在yacc中建立一个数据链表。 我的语法是这样写的：

list: item
  | list ',' item
  ;

我已经在声明部分放置了适当的结构。但是我无法找到一种从这些数据中获取链表的方法。我必须存储递归获得的数据，然后将其重定向用于其他目的。

基本上我正在寻找这样的解决方案：但此解决方案适用于右递归，不适用于左递归。

Answer 1

如果您使用左递归规则，那么您需要将新项目推到列表的末尾而不是开头。

如果您的链表实现不支持push_back，则将连续的项目推到前面，并在完成后反转列表。

Answer 2

很简单。

list
    : item
    {
        $$ = new MyList<SomeType>();
        $$.add();
    }
    | list ',' item
    {
        .add();
        $$ = ;
    }
    ;

假设您使用的是 C++，但您没有说明，并且假设您有一些 MyList<T> class 和 add(T) 方法。

Answer 3

这在很大程度上取决于您如何实现链表，但是一旦实现，它就很简单了。类似于：

struct list_node {
    struct list_node  *next;
    value_t           value;
};
struct list {
    struct list_node  *head, **tail;
};

struct list *new_list() {
    struct list *rv = malloc(sizeof(struct list));
    rv->head = 0;
    rv->tail = &rv->head;
    return rv; }
void push_back(struct list *list, value_t value) {
    struct list_node *node = malloc(sizeof(struct list_node));
    node->next = 0;
    node->value = value;
    *list->tail = node;
    list->tail = &node->next; }

允许您将 yacc 代码编写为：

list: item { push_back($$ = new_list(), ); }
    | list ',' item { push_back($$ = , ); }
    ;

当然，您可能应该添加对运行内存不足的检查，并在这种情况下优雅地退出。

使用左递归文法在yacc中构建链表

Building a linked list in yacc with left recursive Grammar

yacc