Yet another C++ Json Parser (Recursive)

Question

Following on from this request Yet another C++ Json Parser

A friend pointed out that he though a recursive decent parser would be more efficient.
Before I agree I want to test it so I wrote it for testing.

I found the implementation of the parser much more complex than using yacc (but that could be a result of using yacc a few times and not trying to write recursive descent parsers).

Any comments on the implementation appreciated:

JsonRecParser.h

#ifndef THORSANVIL_JSON_PARSER_JSON_REC_PARSER_H
#define THORSANVIL_JSON_PARSER_JSON_REC_PARSER_H

#include "JsonRecParser.h"
#include "JsonParser.tab.hpp"

class yyFlexLexer;

using namespace ThorsAnvil::JsonParser;


namespace ThorsAnvil
{       
    namespace JsonParser
    {       

class JsonRecParser
{   
    yyFlexLexer&    lexer;

        int JsonValueParse(int val);
        int JsonMapValueListParse(int val);
        int JsonArrayValueListParse(int val);
        int JsonMapParse(int val);
        int JsonArrayParse(int val);
        int JsonObjectParse(int val);

    public: 
        JsonRecParser(yyFlexLexer& lexer)
            : lexer(lexer)
        {}
        int parse();
};  
    }
}

#endif 

JsonRecParser.cpp

#include "JsonParser.tab.hpp"

using namespace ThorsAnvil::JsonParser;

int JsonRecParser::JsonValueParse(int val)
{
    switch(val)
    {
        case '{':                                       return JsonMapParse(lexer.yylex());
        case '[':                                       return JsonArrayParse(lexer.yylex());
        case yy::JsonParser::token::JSON_STRING:   return 0;
        case yy::JsonParser::token::JSON_NUMBER:   return 0;
        case yy::JsonParser::token::JSON_TRUE:     return 0;
        case yy::JsonParser::token::JSON_FALSE:    return 0;
        case yy::JsonParser::token::JSON_NULL:     return 0;
        default:                                        break;
    }
    return val;
}       
int JsonRecParser::JsonMapValueListParse(int val)
{
    if ((val == yy::JsonParser::token::JSON_STRING) && ((val = lexer.yylex()) == ':') && ((val = JsonValueParse(lexer.yylex())) == 0))
    {   
        val = lexer.yylex();
        switch(val)
        {
            case '}':   return 0;
            case ',':   return JsonMapValueListParse(lexer.yylex());
            default:    break;
        }   
    }
    return val;
}
int JsonRecParser::JsonArrayValueListParse(int val)
{
    if ((val = JsonValueParse(val)) == 0)
    {
        val = lexer.yylex();
        switch(val)
        {
            case ']':   return 0;
            case ',':   return JsonArrayValueListParse(lexer.yylex());
            default:    break;
        }
    }
    return val;
}  
int JsonRecParser::JsonMapParse(int val)
{
    if (val == '}')
    {   return 0;   /* Empty Map */
    }
    return JsonMapValueListParse(val);
}
int JsonRecParser::JsonArrayParse(int val)
{
    if (val == ']')
    {   return 0;   /* Empty Array */
    }
    return JsonArrayValueListParse(val);
}
int JsonRecParser::JsonObjectParse(int val)
{
    switch(val)
    {
        case '{':   return JsonMapParse(lexer.yylex());
        case '[':   return JsonArrayParse(lexer.yylex());
        default:    break;
    }
    return val;
}
int JsonRecParser::parse()
{
    return JsonObjectParse(lexer.yylex());
}

All other files are the same. With this small change to main:

Changes to main.cpp

    //yy::JsonShiftParser parser(lexer);
    ThorsAnvil::JsonParser::JsonRecParser   parser(lexer);

#

Answer 1

Recursion generally isn't more efficient, just easier to program and understand. For simpler examples it also leads to much neater code however can be harder to understand if you have multiple levels of recursion jumping around.

Each function call will add stuff to the stack as such it will use more memory and take longer as it has to allocate and initialize that memory, even when using pointers/references. You might also find you run into a depth limit in the form of a stack overflow (like the site name ☺).

With that said for most JSON it wouldn't likely be an issue, unless someone was sending malicious JSON your way which you should assume for any external input.