YACC 左递归中的正确顺序

Question

假设我们有以下简单的 YACC 语法：

start:
    list
    {
        if ( != NULL) {
            Reverse(&); /*correct order*/
        }
        Generate();
    }
    ;

list:
    list item
    {
        $$ = Node(, );
    }
    |
    {
        $$ = NULL;
    }
    ;

有没有办法构建list的二元抽象语法树（仍然使用左递归），使得start中的元素顺序不必改正？作案手法是什么？

Answer 1

不是真的。

左递归语法从左到右执行归约。如果你想建立一个链表，那么你要么需要在最后反转列表，如 OP 所示，要么你需要保留一个指向列表末尾的指针，以便你可以附加到 O 中的列表(1). （当列表被完全解析时，你仍然需要从解析堆栈中丢弃这个指针。）

这是第二种策略的示例：

start
    : list      { if () {
                    $$ = ->next;
                    ->next = NULL;
                  }
                }
list:           { $$ = NULL; }
    | list node { if () {
                    $$ = Node(, ->next);
                    ->next = $$;
                  }
                  else {
                    $$ = Node(, NULL);
                    $$->next = $$;
                  }
                }

这里，中间列表是循环的，list的语义值是它的最后一个元素。实际上，我们保持列表向右旋转一个节点。最后，在start中，我们只需要将列表向左循环旋转一个节点并打破圆圈即可。（由于列表可能为空，代码变得复杂。如果不可能为空列表，或者如果我们愿意分配一个额外的头元素并在末尾丢弃它，则可以简化代码。）

实际上，我不会使用上面的代码，因为它不容易阅读并且没有真正的性能优势。

当然，您可以使用右递归向后减少元素，这有效地使用了解析堆栈来保存中间列表。这使用了可能无限量的堆栈 space 并且相反的处理顺序可能会产生其他后果（如果节点处理不起作用）；无论如何，它并不比从左到右的方法快。

YACC 左递归中的正确顺序

Correct order in YACC left-recursion

yacc