为 C++ 编写 JSON 解析器

Question

到目前为止，我已经设法将词法分析器和堆栈放在一起，以期实现 LL1 解析器。我这样做纯粹是为了了解解析的工作原理，并且可能在未来的项目中使用这些想法。我知道有很多更好的框架，比如json-cpp和rapid-json，但我想自己理解这一点。

头文件如下。

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

实现如下。

#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();
        } 
    }
}

我不确定如何从这里开始，但一直使用json 语法作为起点，并使用以下教程作为指导。

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

我有三个主要问题。

1. JSON 语法似乎留下了间接递归。由于语法不像教程中显示的那么简单，我不知道如何消除它。

2. 我不知道如何生成解析表（有限状态机），特别是对于类似的东西First(object)，这会是什么？是否有任何资源为 JSON 生成了解析表，并且可能为我指明正确的方向？

3. 本教程似乎更多地验证正在解析的表达式是由语法生成的，但我想将结构存储在变量中。这将在哪里完成，您对伪（甚至更好的 C++）代码的外观有什么建议。

为了完整起见，我使用以下 JSON 作为测试。

[
{
    "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
}
]

Answer 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.