4
\$\begingroup\$

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);

#

\$\endgroup\$
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I disagree with your arguments: 1) Easier to program? Really have you compared the two versions. 2) Easier to read: Have you read the two examples (admittedly you need to understand BNF for the yacc version but what computer scientist graduate does not). 3) Yes recursion adds stuff to the stack but where do you think the tokens are stored for the shift reduce version. The shift reduce version is just as likely to to overflow (just in a different way). \$\endgroup\$ – Martin York Jan 9 '12 at 2:54
  • 3
    \$\begingroup\$ @LokiAstari: I think David's comment was meant in general, not specifically to this code -- e.g., a recursive quicksort vs. non-recursive version. It tends to simplify code for problems (like Quicksort) that are defined recursively. A domain-specific language like yacc tends to do more to simplify programming within that domain. The problem is that the domain can be sharply circumscribed (e.g., if your input grammar doesn't fit yacc's lalr(1) limit). \$\endgroup\$ – Jerry Coffin Jan 9 '12 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.