Top Down Recursive Descent Parsing: Unter Berufung auf Endrekursion Optimierung

Question

Ich baue eine Rekursiver Abstieg und ich habe zwei Regeln, die eine Liste zu erstellen:

ValueList -> TOKEN_IDENTIFER TOKEN_QUOTE ValueListP 

ValueListP -> ValueList 
      | %EPSILON% 

Jetzt weiß ich, dass Sie diese beiden Regeln in eine optimieren einzelne Regel mit einer Schleife leicht, aber ich weiß auch, dass der Compiler kann und wird Tail Call-Optimierung, wo es es sieht. Hier ist mein aktueller Code:

void Parser::grammarValueList(std::deque<std::unique_ptr<ValueNode>>& arg1)                                         
{                                                            
    std::string var1 = m_currentToken.getValue().string;                                             
    if(acceptToken(Token::Type::TOKEN_IDENTIFIER))                                              
    {                                                          
      std::string var2 = m_currentToken.getValue().string;                                           
      if(acceptToken(Token::Type::TOKEN_QUOTE))                                             
      {                                                        
        arg1.push_back(std::unique_ptr<ValueNode>(new ValueNode(var1, var2)));                                   
        if(peekValueListP())                                                 
        {                                                      
          return grammarValueListP(arg1);                                            
        }                                                      
      }                                                        
    }                                                          

    throw ParseException("Error: did not expect \"" + m_currentToken.toString() + "\"");                                     
} 

void Parser::grammarValueListP(std::deque<std::unique_ptr<ValueNode>>& arg1)                                         
{                                                            
    if(peekValueList())                                                     
    {                                                          
      return grammarValueList(arg1);                                                
    }                                                          
    else                                                         
    {                                                          
      return;                                                      
    }                                                          

    throw ParseException("Error: did not expect \"" + m_currentToken.toString() + "\"");                                     
} 

So habe ich zwei Fragen:

1) Ist meine bereitgestellten Code Hebel Endaufruf Optimierung?

2) Auch wenn ein Stück Code die Tail Call Optimierung nutzt, sollten wir als Programmierer versuchen, diese Optimierung zu unserem Selbst zu machen (Entfernen der Rekursion und Ersetzen durch eine Schleife) in trivialen Fällen?

Answer 1

Nein, grammarValueList führt keinen Tail-Call durch.

Das Problem ist, dass es zwei lokale Variablen vom Typ std::string gibt, die einen nicht-trivialen Destruktor hat. Diese Destruktoren müssen kurz vor der Rückkehr der Methode aufgerufen werden, die nach grammarValueListP aufgerufen wird. Also ist der Ruf nach grammarValueListP nicht in Heckposition.

Es ist natürlich möglich, dass ein optimiser mit Zugriff auf die Definition des destructor herausfinden kann, dass es möglich ist, vorzeitig var1 und var2 zu zerstören, ohne die Funktion der sichtbare Verhalten zu ändern (unter der Annahme, dass es möglich ist, es hängt zum Teil, was im Inneren des ValueNode Konstruktors passiert). Aber ich glaube nicht, dass die meisten C++ - Implementierungen versuchen, Tail-Aufrufe zu optimieren.

Persönlich würde ich eine Schleife verwenden, denn selbst wenn es Ihnen gelingt, die Destruktoraufrufe zu eliminieren, ist es durchaus möglich, dass der Compiler die TCO immer noch nicht findet. Wie man in diesem scheinbar einfachen Beispiel sehen kann, sind die Tail-Aufrufe in C++ oft nicht so trivial wie sie auf der Oberfläche aussehen, und es kann überraschend schwierig sein, den Optimierer davon zu überzeugen, einen zu erzeugen.