我正在构建一个递归下降解析器,我有两个构建列表的规则:
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) 即使一段代码确实利用了尾调用优化,作为程序员,我们是否应该在微不足道的情况下尝试自己进行优化(删除递归并用循环代替)?
最佳答案
不,grammarValueList
不执行尾调用。
问题是有两个 std::string
类型的局部变量,它们有一个非平凡的析构函数。这些析构函数必须在方法返回之前调用,也就是在调用 grammarValueListP
之后。所以对 grammarValueListP
的调用不在尾部位置。
当然,可以访问析构函数定义的优化器可能会发现可以过早地析构 var1
和 var2
而不会改变函数的可见行为(假设这是可能的;它部分取决于 ValueNode
构造函数内部发生的情况)。但我不相信大多数 C++ 实现会努力优化尾调用。
就我个人而言,我会使用循环,因为即使您设法消除了析构函数调用,编译器仍有可能找不到 TCO。从这个看似简单的示例中可以看出,C++ 中的尾调用通常并不像表面上看起来那么微不足道,而且说服优化器产生尾调用可能出奇地困难。
关于c++ - 自顶向下递归下降解析 : Relying on tail call optimization,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47480501/