vendredi 24 novembre 2017

Top Down Recursive Descent Parsing : Relying on tail call optimization

I am building a recursive descent parser and I have two rules which build a list:

ValueList  -> TOKEN_IDENTIFER TOKEN_QUOTE ValueListP

ValueListP -> ValueList
           |  %EPSILON%

Now I know that you can optimize these two rules into a single rule with a loop easily, but I also know that the compiler can and will perform tail call optimization where it sees it. Here is my current 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 I have two questions:

1) Does my provided code leverage tail call optimization?

2) Even if a piece of code does leverage tail call optimization, should we as programmers try to make that optimization our self ( removing the recursion and replacing with a loop ) in trivial cases?

Aucun commentaire:

Enregistrer un commentaire