c++ - 自顶向下递归下降解析 : Relying on tail call optimization

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++ 中的尾调用通常并不像表面上看起来那么微不足道，而且说服优化器产生尾调用可能出奇地困难。