正确的顺序左递归

假设我们有以下简单的YACC语法：正确的顺序左递归

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

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

有没有一种方法来构建的list二进制抽象语法树（仍在使用左递归），这样的顺序的元素不需要在start中更正？什么是手法？

来源

2015-10-20 August Karlstrom

不是。

左递归语法从左到右执行减少。如果你想建立一个链表，那么你需要在最后反转列表，如OP所示，或者你需要保留一个指向列表结尾的指针，这样你可以在O中添加列表（1）。（你还需要从剖析栈丢弃这个指针当列表完全解析。）

这里的第二个策略的一个例子：

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中，我们只需要将列表中的一个节点循环向左旋转并打破圆圈。（由于列表为空，如果空列表不可用，或者如果我们愿意分配额外的标题元素并在末尾丢弃它，则代码可以简化）。

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

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

来源

2015-10-20 14:45:49 rici

正确的顺序左递归

回答

相关问题