正確的順序左遞歸

假設我們有以下簡單的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

正確的順序左遞歸

回答

相關問題