自顶向下递归下降解析:依赖尾调用优化

Question

我正在构建一个递归下降解析器，我有两个规则来构建一个列表：

ValueList  -> TOKEN_IDENTIFER TOKEN_QUOTE ValueListP

ValueListP -> ValueList
           |  %EPSILON%

现在，我知道您可以轻松地将这两个规则优化为一个带循环的规则，但我也知道编译器能够并且将在它看到的地方执行尾调用优化。以下是我的当前代码：

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() + "\"" );                                                                                                                                                
}

所以我有两个问题：

1)我提供的代码是否利用了尾调用优化？

2)即使一段代码确实利用了尾调用优化，我们作为程序员是否也应该尝试将该优化作为我们自己(删除递归并用循环替换)在一些琐碎的情况下进行？

Answer 1

不，grammarValueList不执行尾部调用。

问题是有两个std::string类型的局部变量，它有一个非平凡的析构函数。必须在方法返回之前调用这些析构函数，即在调用grammarValueListP之后。因此，对grammarValueListP的调用不在尾部位置。

当然，访问析构函数定义的优化器可能会发现，在不改变函数的可见行为的情况下，提前销毁var1和var2是可能的(假设它是可能的；这在一定程度上取决于ValueNode构造函数内部发生了什么)。但我不认为大多数C++实现都会那么努力地优化尾调用。

就我个人而言，我会使用一个循环，因为即使您设法消除析构函数调用，编译器仍然很有可能找不到TCO。从这个显然很简单的例子中可以看出，C++中的尾调用通常并不像表面所看到的那么简单，而且要说服优化者生成一个尾调用也是非常困难的。