如何使用 C++ 解析简单的类似 pango 的标记，获得类似树的节点结构？

Question

我试图将 Pango 风格的标记解析为树状结构，叶子是文本元素，分支是带有属性的标签元素。例如：

<b>This is bold</b>, <i>italic and <span color="red">red text</span></i> !

到目前为止，我已经得到了下面的 C++ 代码（没有类定义，我认为它们是无关紧要的），如果省略上面的部分，它可以正常工作<b></b>- 它只能解析每个级别的一个标签，但它在每个级别的多个标签上失败：

        bool parseStartTag(const std::string& s, size_t start, size_t end, std::string& tag_name, std::map<std::string, std::string>& attrs) {
            size_t tag_name_end = s.find_first_of(" \t\n", start);
            if (tag_name_end == std::string::npos or tag_name_end >= end) {
                tag_name = s.substr(start, end - start);
                return true;
            } else {
                tag_name = s.substr(start, tag_name_end - start);
            }
            start = tag_name_end;

            char quote = '\0';
            std::string attr_name = "";
            std::string attr_value = "";
            while (start <= end) {
                if (quote != '\0') {
                    if (s[start] == quote) {
                        quote = '\0';
                        attrs[attr_name] = attr_value;
                        attr_name = "";
                        attr_value = "";
                    } else {
                        attr_value += s[start];
                    }
                } else if ((s[start] == ' ' or s[start] == '\t' or s[start] == '\n') and quote == '\0') {
                } else if (s[start] == '"' or s[start] == '\'') {
                    quote = s[start];
                } else if (s[start] != '=') {
                    attr_name += s[start];
                }
                start++;
            }

            return true;
        }

        std::shared_ptr<SGMarkupTag> parse(const std::string& s, std::string tag_name) {
            std::shared_ptr<SGMarkupTag> tag = std::make_shared<SGMarkupTag>();
            tag->setName(tag_name);
            
            size_t opening_index = 0;
            size_t closing_index = 0;
            size_t tag_content_start = 0;
            size_t tag_content_end = 0;
            while (closing_index != std::string::npos) {
                opening_index = s.find("<", closing_index);
                std::string text_string;
                if (opening_index != std::string::npos) {
                    text_string = s.substr(closing_index, opening_index - closing_index);
                } else {
                    text_string = s.substr(closing_index);
                }
                tag->addText(text_string);

                if (opening_index == std::string::npos) {
                    return tag;
                }

                closing_index = s.find(">", opening_index);
                if (opening_index != std::string::npos and closing_index == std::string::npos) {
                    SG_LOG(SG_GENERAL, SG_ALERT, "Markup parse error: Missing closing bracket for tag after opening bracket at char " << opening_index << ":");
                    SG_LOG(SG_GENERAL, SG_ALERT, "\t" << s);
                    SG_LOG(SG_GENERAL, SG_ALERT, "\t" << std::string(opening_index, '-') << "^");
                    return tag;
                }

                std::string tag_name = "";
                std::map<std::string, std::string> attrs;
                if (!parseStartTag(s, opening_index + 1, closing_index, tag_name, attrs)) {
                    return tag;
                };
                tag_content_start = closing_index + 1;

                opening_index = closing_index + s.substr(closing_index).rfind("</");
                if (opening_index == std::string::npos) {
                    SG_LOG(SG_GENERAL, SG_ALERT, "Markup parse error: Missing closing tag after opening tag at char  " << closing_index - 1 << ":");
                    SG_LOG(SG_GENERAL, SG_ALERT, "\t" << s);
                    SG_LOG(SG_GENERAL, SG_ALERT, "\t" << std::string(closing_index - 1, '-') << "^");
                    return tag;
                }
                tag_content_end = opening_index;
                closing_index = opening_index + s.substr(opening_index).rfind(">");
                if (closing_index == std::string::npos) {
                    SG_LOG(SG_GENERAL, SG_ALERT, "Markup parse error: Missing closing bracket for tag after opening bracket at char " << opening_index << ":");
                    SG_LOG(SG_GENERAL, SG_ALERT, "\t" << s);
                    SG_LOG(SG_GENERAL, SG_ALERT, "\t" << std::string(opening_index, '-') << "^");
                    return tag;
                }
                std::string closing_tag_name = s.substr(opening_index + 2, closing_index - opening_index - 2);
                if (closing_tag_name != tag_name) {
                    SG_LOG(SG_GENERAL, SG_ALERT, "Markup parse error: Unmatched closing tag '" << closing_tag_name << "' at char " << opening_index + 1 << " for opening tag '" << tag_name << "':");
                    SG_LOG(SG_GENERAL, SG_ALERT, "\t" << s);
                    SG_LOG(SG_GENERAL, SG_ALERT, "\t" << std::string(opening_index + 1, '-') << "^");
                    return tag;
                }

                std::shared_ptr<SGMarkupElement> sub_tag = parse(s.substr(tag_content_start, tag_content_end - tag_content_start), tag_name);
                sub_tag->setAttributes(attrs);
                sub_tag->setParent(tag);
                sub_tag->setRoot(tag->getRoot());
                tag->addChild(sub_tag);

                closing_index++;
            }
            tag->addText(s.substr(closing_index));

            return tag;
        }

现在，我如何更改 while 循环parse以适用于每个级别的多个标签？我知道这不是代码编写服务，但是关于我需要添加或更改的内容的一些指示会很好​​。

Answer 1

要解析同一级别上的多个元素，您不需要假设与特定开始标记关联的结束标记始终是字符串中的最后一个结束标记（我的意思是结束标记</b>等</i>）。事实上，特定元素的结束标签甚至可能不是开始标签之后的下一个结束标签，因为其他元素可能嵌套在正在解析的元素内部，甚至可能不是相同类型的下一个结束标签，因为相同类型的另一个元素类型可以嵌套在元素中。没有简单的技巧可以用来忽略任意递归结构。

基本上，您应该将代码重构为递归下降解析器。

为此，您需要一组相互递归的函数，这些函数返回解析输出以及输入中函数消耗的内容右侧的位置。每个解析函数都知道如何解析一种事物并且允许失败。我所说的“允许失败”是指在输入并非绝对无效的情况下，解析失败不应引发异常或错误。如果输入不是绝对无效的情况不要抛出或以其他方式恐慌，那么您可以通过尝试解析当前位置的x并查看x解析器是否成功来解析析取（或子句） ；如果不继续进行y解析器...

然后你需要清楚你到底想要什么输出；也就是说，你需要清楚你正在解析的语法。在您的示例中，我不清楚应该<b>This is bold</b>, <i>italic and <span color="red">red text</span></i>返回什么，因为我不知道粗体元素和斜体元素之间的逗号会去哪里。所以说你不允许这样做。假设您允许每个元素包含文本或一系列其他元素。然后，要为该语法创建递归下降解析器，您可以使用具有如下签名的解析函数：

std::shared_ptr<Tag> parseOpeningTag(const std::string& inp, int& i);
bool parseClosingTag(const std::string& inp, int& i, const std::string& tag);
std::shared_ptr<Element> parseElement(const std::string& inp, int& i);
std::string parseText(const std::string& inp, int& i);
std::vector<std::shared_ptr<Element>> parseElementSequence(const std::string& inp, int& i);

请注意，i以上参数仅供参考。如果解析成功，i最终将包含开始解析的新位置。如果解析失败，返回值将为 null 或 false，并且i不会发生变化。

在这样的设置中，元素解析函数看起来像

std::shared_ptr<Element> parseElement(const std::string& inp, int& i) {
    auto tag = parseOpeningTag(inp, i);
    if (!tag) {
        return {};
    }
    auto element = std::make_shared<Element>(tag->name(), tag->attributes());

    // contents are either a sequence of elements or text; try elements first
    auto children = parseElementSequence(inp, i); 
    if (!children.empty()) {
        element->setChildren(children);
    } else {
        // We assume here that parseElementSequence does not change i if
        // it fails.
        auto txt = parseText(inp, i); 
        element->setText(txt);
    }
    bool success = parseClosingTag(inp, i, tag->name());
    if (!success) {
        throw std::runtime_error("bad element: " + tag->name());
    }
    return element;
}

你可以parseElementSequence用 来编写parseElement，循环调用它直到失败，等等。