YACC左递归中的正确顺序 [英] Correct order in YACC left-recursion

问题描述

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

Suppose we have the following simplistic YACC grammar:

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

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

有没有办法构造list的二进制抽象语法树(仍然使用左递归)，这样元素的顺序就不必在start?作案手法是什么?

Is there a way to construct the binary abstract syntax tree of list (still using left-recursion) so that the order of the elements doesn't have to be corrected in start? What is the modus operandi?

推荐答案

并非如此.

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

A left-recursive grammar performs reductions left-to-right. If you want to build a linked list, then you either need to reverse the list at the end, as shown in the OP, or you need to keep a pointer to the end of the list so that you can append to the list in O(1). (And you still need to discard this pointer from the parse stack when the list is fully parsed.)

这是第二种策略的示例:

Here's an example of the second strategy:

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

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

Here, the intermediate list is circular and the semantic value of list is its last element. In effect, we maintain the list rotated one node to the right. At the end, in start, we just need to rotate the list one node circularly to the left and break the circle. (The code is complicated by the possibility that the list is empty. If empty lists are not possible or if we are willing to allocate an extra header element and discard it at the end, the code can be simplified.)

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

In practice, I wouldn't use the above code because it is not easy to read and has no real performance advantage.

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

Of course, you could use right recursion to reduce the elements backwards, which effectively uses the parse stack to hold the intermediate list. That uses a potentially unbounded amount of stack space and the reversed processing order can have other consequences (if node processing is not functional); in any case, it is no faster than the left-to-right methods.

这篇关于YACC左递归中的正确顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！