Writing a JSON parser for C++

Question

So far I have managed to put together a lexer and a stack in the hopes of achieving a LL1 parser. I am doing this purely to understand how parsing works, and maybe to use these ideas in future projects. I understand there are much better frameworks out there like json-cpp and rapid-json but I would like to understand this for myself.

The header file is give below.

#pragma once

#include <string>
#include <vector>
#include <map>
#include <variant>
#include <fstream>
#include <stack>

#include "Helper.h"

// Debugging
#include <iostream>

// Types to store JSON ouput
struct jlist;
struct jobject;

using json_value = std::variant<int, float, bool, std::string, jlist, jobject>;

enum tag { int_value, float_value, string_value, list, object };

struct jlist {
    tag type;
    std::vector<json_value *> vector_value;
};

struct jobject {
    tag type;
    std::map<std::string, json_value *> map_value;
};

class JSONParser
{
public:
    JSONParser();

    ~JSONParser();

    void parseFile(std::string);

private:
    std::stack<std::string> s;

    bool checkDeliminator(char);
    std::vector<std::string> lexer(std::ifstream &);
    void parser(std::vector<std::string> &);
    void transitionTable(std::string cursor);
};

The implementation is as follows.

#include "genetic-optimization/JSONParser.h"

JSONParser::JSONParser() {
}

JSONParser::~JSONParser() = default;

void JSONParser::parseFile(std::string FILE) {
    std::ifstream configfile(FILE);
    std::vector<std::string> scan = lexer(configfile);
    parser(scan);
}

bool JSONParser::checkDeliminator(char piece) {
    switch (piece) {
        case '[':
            return true;
        case ']':
            return true;
        case '{':
            return true;
        case '}':
            return true;
        case ':':
            return true;
        case ',':
            return true;
        case '"':
            return true;
        default:
            return false;
    }
}

std::vector<std::string> JSONParser::lexer(std::ifstream & configfile) {
    char piece;
    std::string capture = "";
    std::string conversion;
    std::vector<std::string> capture_list;

    while(configfile >> piece) {
        if (checkDeliminator(piece)) {
            conversion = piece;
            if (capture != "") {
                capture_list.push_back(capture);
                capture_list.push_back(conversion);
                capture = "";
            } else {
                capture_list.push_back(conversion);
            }
        } else {
            capture += piece;
        }
    }

    return capture_list;
}

void JSONParser::parser(std::vector<std::string> & scan) {
    for (auto it = scan.begin(); it != scan.end(); ++it) {
        std::cout << *it << "\n"; // Make sure the lexer works
        transitionTable(*it);
    }
}

void JSONParser::transitionTable(std::string cursor) {
    if(s.empty()) {
        s.push(cursor); 
    } else {
        if (s.top() == "[") {
            s.push(cursor);
        } else if (s.top() == "]") {
            s.pop();
        } else if (s.top() == "{") {
            s.push(cursor);
        } else if (s.top() == "}") {
            s.pop();
        } 
    }
}

I am unsure of how to proceed from here but have been using the json grammar as a starting point and the following tutorial for guidance.

json -> element
value -> object|array|string|number|bool|
object -> {}|{members}
members -> member|member,members
member -> string:element
array -> []|[elements]
elements -> element|element,elements
element -> value

I have three main problems.

1. The JSON grammar seems to have left indirect recursion. Since the grammar is not as simple as that shown in the tutorial I do not know how to eliminate it.

2. I do not know how to generate the parse table (finite state machine), specifically for something like First(object), what would this be? Is there any resource that has produced a parse table for JSON and might point me in the right direction?

3. The tutorial seems more to verify that the expression being parsed is produced by the grammar but I would like to store the structure in a variable. Where would this be done and do you have any advice for how this might look in pseudo (or even better C++) code.

For completeness, I am using the following JSON as a test.

[
{
    "libraries":[
        "terminal",
        "binary"
        ] ,
    "functions":[
        "terminal-basic",
        "binary-basic"
    ]
}
,
{
    "name":"addition",
    "type":"binary-basic",
    "function":"add_float",
    "input":{
        "float" : 2
        },
    "output":"float",
    "max-number":2
}
,
{
    "name":"exponent",
    "type":"binary-basic",
    "function":"exponent_float",
    "input":{
        "float":2
        },
    "output":"float",
    "max-number":2
}
,
{
    "name":"exponent",
    "type":"binary-basic",
    "function":"exponent_float",
    "input":{
        "float":2,
        "int":1
        },
    "output":"float",
    "max-number":1
}
,
{
    "name":"constant_1",
    "type":"terminal-basic",
    "function":"non_random_constant",
    "value":0.5,
    "input":{ },
    "output":"float",
    "max-number":3
}
,
{
    "name":"constant_2",
    "type":"terminal-basic",
    "function":"non_random_constant",
    "value":2.0,
    "input":{ },
    "output":"float",
    "max-number":3
}
,
{
    "name":"constant_3",
    "type":"terminal-basic",
    "function":"non_random_constant",
    "value":true,
    "input":{
        "bool":1
    },
    "output":"bool",
    "max-number":1
}
]

Solution 1

I wouldn't like to leave this question unanswered for anyone coming here in the future, however, I am personally not a big fan of the code that accompanies this answer. It feels inefficient, not particularly elegant and I am unsure if it represents the theoretical model I was trying to implement in the first place. I took my lead from @MSalters comment, which to me meant build something that works and worry if the model is theoretically sound later. Below is my attempt.

The header adds a few more functions. Many of them purely to assist fsm and parser.

class JSONParser
{
public:
        JSONParser();

        ~JSONParser();

        void parseFile(std::string);

private:
        json_value root;
        std::stack<std::string> s;
        std::stack<json_value> s_value;

        // Lexer
        bool checkDeliminator(char);
        std::vector<std::string> lexer(std::ifstream &);

        // FSM varaibles
        enum state { int_value, float_value, bool_value, string_value, default_value, bad_state};
        state current;

        // FSM
        void fsm(std::string);

        // Parser variables
        enum stack_map { list_open, list_close, object_open, object_close, colon, comma, buffer, follow};
        std::map<std::string, stack_map> stack_conversion;

        // Parser helper functions
        template<typename T> void addElement();

        template<typename T> void insert(std::string &, T (*)(const std::string &));
        template<typename T> void insert();
        void insert(std::string &);
        void pushBuffer();

        template<typename ... T> bool multiComparision(const char scope, T ... args);
        bool isDigit(const char);
        static int st2i(const std::string & value);
        static float st2f(const std::string & value);
        static bool st2b(const std::string & value);

        // Parser
        void parser(const std::string & cursor);
};

The implementation file follows.

#include "genetic-optimization/JSONParser.h"

JSONParser::JSONParser() {
    state current = default_value;
    stack_conversion = { { "[", list_open }, { "]", list_close }, { "{", object_open }, { "}", object_close }, { ":", colon }, { ",", comma }, { "buffer", buffer } };
}

JSONParser::~JSONParser() = default;

void JSONParser::parseFile(std::string FILE) {
    std::ifstream configfile(FILE);
    std::vector<std::string> scan = lexer(configfile);

    scan.push_back("terminate");
    for (auto it = scan.begin(); it != scan.end(); ++it) {
            parser(*it);
    }
    root = s_value.top();
    s_value.pop();
}

// Lexer
bool JSONParser::checkDeliminator(char piece) {
    switch (piece) {
        case '[':
            return true;
        case ']':
            return true;
        case '{':
            return true;
        case '}':
            return true;
        case ':':
            return true;
        case ',':
            return true;
        default:
            return false;
    }
}

std::vector<std::string> JSONParser::lexer(std::ifstream & configfile) {
    char piece;
    std::string capture = "";
    std::string conversion;
    std::vector<std::string> capture_list;

    while(configfile >> piece) {
        if (checkDeliminator(piece)) {
            conversion = piece;
            if (capture != "") {
                capture_list.push_back(capture);
                capture_list.push_back(conversion);
                capture = "";
            } else {
                capture_list.push_back(conversion);
            }
        } else {
            capture += piece;
        }
    }

    return capture_list;
}

// FSM
void JSONParser::fsm(std::string value) {
    current = default_value;
    char point;
    auto it = value.begin();

    while (it != value.end()) {
        point = *it;
        if (point == '"' & current == default_value) {
            current = string_value;
            return;
        } else if (isdigit(point)) {
            if (current == default_value | current == int_value) {
                current = int_value;
                ++it;
            } else if (current == float_value) {
                ++it;
            } else {
                current = bad_state;
                return;
            }
        } else if (point == '.' & current == int_value) {
            current = float_value;
            ++it;
        } else if (point == 'f' & current == float_value) {
            ++it;
        } else if (current == default_value) {
            if (value == "true" | value == "false") {
                current = bool_value;
                return;
            } else {
                current = bad_state;
                return;
            }
        } else {
            current = bad_state;
            return;
        }
    }
}

// Parser Helper functions
template<>
void JSONParser::addElement<jobject>() {
    json_value value_read;
    json_value key_read;

    value_read = s_value.top();
    s_value.pop();
    key_read = s_value.top();
    s_value.pop();

    std::get<jobject>(s_value.top()).insert(key_read, value_read);
}

template<>
void JSONParser::addElement<jlist>() {
    json_value value_read;

    value_read = s_value.top();
    s_value.pop();

    std::get<jlist>(s_value.top()).push_back(value_read);
}

template<typename T>
void JSONParser::insert(std::string & value, T (*fptr)(const std::string &)) {
        T T_value(fptr(value));
        s_value.push(T_value);
}

template<typename T>
void JSONParser::insert() {
        T T_value;
        s_value.push(T_value);
}

void JSONParser::insert(std::string & value) {
    value.erase(std::remove(value.begin(), value.end(), '"'), value.end());
        s_value.push(value);
}

void JSONParser::pushBuffer() {
    s.pop();
    s.push("buffer");
}

template<typename ... T>
bool JSONParser::multiComparision(const char scope, T ... args) {
    return (scope == (args || ...));
}

bool JSONParser::isDigit(const char c) {
    return multiComparision<char>(c, '1', '2', '3', '4', '5', '6', '7', '8', '9', '0');
}

int JSONParser::st2i(const std::string & value) {
        return stoi(value);
}

float JSONParser::st2f(const std::string & value) {
        return stof(value);
}

bool JSONParser::st2b(const std::string & value) {
        if (value == "true") {
                return true;
        } else {
                return false;
        }
}

// Parser
void JSONParser::parser(const std::string & cursor) {
    if(s.empty()) {
        s.push(cursor); 
    } else {
        stack_map stack_value;
        std::string value = s.top();

        if (stack_conversion.find(value) != stack_conversion.end()) {
            stack_value = stack_conversion[s.top()];
        } else {
            stack_value = follow;
        }

        switch (stack_value) {
            case buffer:
                s.pop();
                break;
            case list_open:
                insert<jlist>();
                if (cursor == "]") {
                    pushBuffer();
                    return;
                }
                break;
            case list_close:
                addElement<jlist>();
                s.pop();
                s.pop();
                break;
            case object_open:
                insert<jobject>();
                if (cursor == "}") {
                    pushBuffer();
                    return;
                }
                break;
            case object_close:
                addElement<jobject>();
                s.pop();
                s.pop();
                break;
            case colon:
                s.pop();
                break;
            case comma:
                s.pop();
                if (s.top() == "{") {
                    addElement<jobject>();
                } else {
                    addElement<jlist>();
                }
                break;
            default:
                s.pop();
                fsm(value);
                switch (current) {
                    case string_value:
                        insert(value);
                        break;
                    case int_value:
                        insert<int>(value, st2i);
                        break;
                    case float_value:
                        insert<float>(value, st2f);
                        break;
                    case bool_value:
                        insert<bool>(value, st2b);
                        break;
                    default:
                        std::cout << "Bad state\n"; 
                }
        }
        s.push(cursor);
    }
}

The idea was to have the lexer break at each deliminator and place all the generated tokens into a vector. This vector called scan could then be looped through. At each iteration of this loop parser would be run. In general this reads the top of the stack s and determines whether a bracket/brace is opening or closing or a terminal value has been reached. If a bracket/brace is opening, a new jobject or jlist is generated and placed onto a new stack s_value, if a terminal value is reached fsm (finite state machine) runs and determines the type of value and places it on top of s_value, should a comma or closing bracket be reached the appropriate values are moved off the stack and the elements in s_value are inserted into their appropriate containers.

The biggest meatball in this spaghetti is how elements in the JSON tree are called.

std::cout << std::get<bool>(std::get<jobject>(std::get<jobject>(std::get<jlist>(root)[6])["input"])["bool"]); // Should return 1

While this does indeed return 1. The nested std::get calls seem just plain wrong and I'm not sure if they can be incorporated into the operator [] or through (sigh) a third stack that tracks the type of object being stored.

This was my basic attempt, it's not pretty but it does work. Hopefully I can refine it further and improve on what I have.

Solution 2

I am not an expert at parsing so my answer would be very heuristic...

1. JSON grammar is simple. I believe we do not need to try to understand of follow over-specified (E)BNF form to actually parse JSON string. Try to write your own simple form. After you do that, you may feel a need for a better form. Then you can re-try to fully understand why there are such grammars.

2. Isn't FSM simply "you have to do that in this state?" States are preferably managed by a stack (not like you have to have an instance whose members indicate states like an abstract figure in text book in many cases of the real world) and you will do what you have to do in loops based on a top state of the stack. I believe you do not need an instance of 'parse table.' Can it be abstract or pervasively exists somewhere in code?

3. I also started to practice parsing with JSON. Please check my single header file.

I used 7 stack statuses:

enum status {
    READING_OBJECT_KEY,
    READ_OBJECT_KEY,
    READING_OBJECT_VALUE, READING_ARRAY_VALUE,
    READ_OBJECT_VALUE, READ_ARRAY_VALUE, READ_OTHER_VALUE
};

Heuristically, I started actual parsing after skipping preceding whitespace and check the first non-whitespace character:

    } else if (p.c == '{') {
            p.ps.push(json::parsing::READING_OBJECT_KEY);
            j = json::object();
            p.js.push(j.v);
            break;
    } else if (p.c == '[') {
            p.ps.push(json::parsing::READING_ARRAY_VALUE);
            j = json::array();
            p.js.push(j.v);
            break;
    }

Then I actually started to parse with 8 functions:

  while (p.iss.get(p.c)) {
      p.i++;
      if      (p.c == ' ' ) {}
      else if (p.c == '{' ) json::parse__left_brace(p);
      else if (p.c == '}' ) json::parse__right_brace(p);
      else if (p.c == '[' ) json::parse__left_bracket(p);
      else if (p.c == ']' ) json::parse__right_bracket(p);
      else if (p.c == ':' ) json::parse__colon(p);
      else if (p.c == ',' ) json::parse__comma(p);
      else if (p.c == '\"') json::parse__quote(p);
      else                  json::parse__else(p);
  }