用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
}
]

- Ivor Denham-Dyson

---

我知道有更好的框架，比如json-cpp和rapid-json，但我想自己理解这个。-- 这些库不是都附带完整的源代码吗？如果是的话，那么有什么阻止你编译他们的代码并使用调试器查看代码呢？ - PaulMcKenzie

@PaulMcKenzie说：要真正理解一件事情，没有比自己从头开始推导、开发或设计它更好的方法了。阅读另一个库的源代码就像阅读关于某个主题的教科书：你也必须做练习才能真正学到东西，对于解析器来说，这意味着要实现自己的解析器。 - datenwolf

如果你正在学习解析，我建议写一个"递归下降解析器"。因为你已经有了语法图表，所以几乎可以1:1地从这个表示中编写代码。 - Richard Critten

解析器似乎受到摆动运动的影响。首先，每个人都编写了自己的定制实现。然后，理论赶上来了，我们得到了有关 LL(1) 等的漂亮的理论模型。然而，现实证明需要解决完全不同类别的难题。例如，简单的 C 规则“符号必须在使用之前定义”破坏了大多数理论模型。 - MSalters

@PaulMcKenzie 目前市面上没有一个令人满意的JSON库可以解析变体类型。请看这个链接： https://stackoverflow.com/questions/59919496/how-to-parse-json-file-with-type-composition-of-stdoptional-and-stdvariant?noredirect=1#comment105965858_59919496因此，我鼓励作者探索如何编写JSON解析器，这是解决问题的唯一方法。 - cpchung

Answer 1

我不希望留下这个问题的答案未被回答，但我个人不太喜欢伴随着这个答案的代码。它感觉效率低下，不是特别优雅，而且我不确定它是否代表了我一开始想要实现的理论模型。我从 @MSalters 的评论中得到启发，对我来说意味着先构建能工作的东西，再担心模型是否在理论上合理。以下是我的尝试。

标题添加了几个其他函数，其中许多纯粹是为了帮助 fsm 和 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);
};

实现文件如下。

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

这个想法是让 lexer 在每个分隔符处断开，并将生成的所有标记放入一个向量中。这个向量称为 scan，可以通过循环遍历它。在此循环的每次迭代中，会运行 parser。通常情况下，它会读取栈顶部的 s 并确定括号/大括号是打开还是关闭或者终端值是否已经找到。如果是括号/大括号打开，则会生成新的 jobject 或 jlist 并放置到新的堆栈 s_value 上，如果到达终端值，则运行 fsm（有限状态机）并确定其类型，并将其放置在 s_value 的顶部，如果到达逗号或闭合括号，则将适当的值移出栈并将 s_value 中的元素插入其适当的容器中。

这个JSON树中的元素如何称呼是这道意大利面条中最复杂的部分。

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

尽管这确实返回了1。但嵌套的std :: get调用似乎很明显是错误的，我不确定它们是否可以通过operator []或(哎)第三个跟踪存储对象类型的堆栈来合并。 这是我的基本尝试，它不太好看，但确实可以工作。希望我能进一步完善它并改进我所拥有的东西。

- Ivor Denham-Dyson

Answer 2

我不是解析专家，所以我的答案会非常启发式...

1. JSON语法很简单。我认为我们不需要尝试理解或遵循过度规范化的（E）BNF形式来实际解析JSON字符串。尝试编写自己的简单格式。在你这样做之后，你可能会感到需要一个更好的形式。然后你可以重新尝试充分理解为什么有这样的文法。

2. 有限状态机难道不只是“你必须在这个状态下执行吗？”状态最好由堆栈管理（不像你必须拥有一个实例，其成员指示状态，就像教科书中的抽象图一样，在许多实际世界的情况下），你将在基于堆栈顶部状态的循环中执行你必须做的事情。我认为你不需要一个'parse table'的实例。它可以是抽象的或者广泛存在于代码中的某个地方吗？

3. 我也开始用JSON练习解析。请查看我的single header file。

我使用了7个堆栈状态：

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

启发式地，我在跳过前置空格并检查第一个非空白字符后开始实际解析：

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

然后我实际上开始使用8个函数进行解析：

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

- ghchoi