在C++中查找字符串中的子串标记

确定假设我正在解析一些XML（在阅读任何“语言”时存在该问题，但XML是许多人熟悉的）。在C++中查找字符串中的子串标记

的XML如下所示：

<Tag> 
    <[CDATA[ blah blah]]> 
    <Tag2> 
    <Tag3/> 
    </Tag2> 
<Tag>

现在我想找到那个流上的各种标记。重要的代币如下（请原谅我蹩脚的“代币”名称;））。

<   = Open Token 
<[CDATA[ = Open CDATA Token 
]]>   = Close CDATA Token 
<!   = Open Comment Token 
/>   = Close Open Token 
</   = Open Close Token 
>   = Close Token

我的问题是，我有以上的数组，我试图正确地识别上述令牌之一，因为我在用字符的文件字符阅读。

所以我读了第一个字符'<'。即时的想法是，这与“Open Token”相匹配，所以我们会选择它。但是，这也与“打开关闭令牌”的第一个字符相匹配。因此，让我们说我们读了第二个字符和它的a'T'。所以我立即知道这是“Open Token”而不是“Open Close Token”。

同样在完成一个标签，例如“/>”。我读了第一个字符，并得到'/'。这匹配“关闭开放令牌”。但它不完整，所以我应该检查下一个字符，在这种情况下是'>'给我“/>”，它与Close Token匹配。

我的问题是，当这些令牌的数量显着增加时，很难跟踪可能的匹配项。有没有一个优雅的方式来做到这一点？或者我应该，只要当我遇到“标记字符串”之一的第一个字符时，将该标记推到一个向量上，然后只在随后的读取中检查这些标记？如果下一个字符不匹配，我可以清除令牌列表，然后重新开始。

这是解决问题的正确方法吗？有没有更好的办法？

（编辑：请不要指向我往Lexx，YACC等等......我想在这里学到一些基础知识）

任何帮助，将不胜感激:)

来源

2010-12-03 Goz

您提到的问题被称为预测和回溯。我认为，如果你想为解析器构建优雅的解决方案，那么你应该检查函数解析器和解析器组合器：这可以让你构建一个解析器，主要是声明语法生成规则。 – 2010-12-03 23:33:03

您需要跟踪解析器中的状态 - 我现在在哪里？接下来我期待什么？ - 以具体环境的方式。当你看到你接下来会看到什么时，你会根据当前状态的有效值列表进行检查，并可能存储完整的解析数据项，并可能改变状态。

只解析XML 看起来顺便说一句 - 如果你真的想自己动手做这项工作，有很多需要处理的角落案例。你的解析器是一个Finite State Machine，但这是一个不平凡的例子。

来源

2010-12-03 23:24:29

干杯史蒂夫我一直在考虑把它分解成一棵树，以便我知道下一个可能的状态是什么...... – Goz 2010-12-03 23:59:41

您可以让flex为您做到这一点。更好的是，为您的语言挖掘现有的XML解析器 - 我确信现在有人已经实现了它。

来源

2010-12-03 23:25:35

我很清楚这样的事情。我不使用它们，因为我正在教自己新的技巧...... – Goz 2010-12-03 23:57:36

@Goz：这并不意味着它不能有效地回答这个问题。如果你知道这样的事情，并不希望他们作为答案，那么你应该把这个问题放在你的问题上。 – 2010-12-04 00:03:54

最近我一直在做很多这种类型的解析（主要是用C＃）。

我不知道你想要完成什么，所以我不确定这有多大的帮助，但我会解析整个事情并将它存储在某种数据数组中。

找到开始标签。然后解析接下来的任何文本（当你到达文本的末尾时，你会知道，因为你会打空白或标点符号）。

您可以对“！”进行特殊测试并且在找到数据结构时可能会设置一个标志。我发现对已知序列进行快速扫描是不实际的。你需要分解整个事物，逐个角色。

你可以在http://www.softcircuits.com/Blog/post/2010/02/07/Parsing-HTML-Tags-in-C.aspx上看到我的C＃结果中的一个。

来源

2010-12-03 23:25:41

解析是一个众所周知的问题，但这并不意味着它很容易编程。你可以自己写任何东西，但正如你遇到的，这变得相当复杂很快。

您可以使用Boost.Spirit库，它非常大，可能需要一些时间才能掌握。

或者作为替代方案，使用Lex/Yacc（或类似的东西）来生成解析器和词法分析器。（这比C++更C，但这当然不一定是坏事）

我个人花时间学习掌握Boost Spirit库，虽然起初看起来很多工作，从长远来看，将节省大量时间和头痛。手动解析XML语言需要比您期望的更多的工作。

来源

2010-12-04 00:07:32 Pieter

在C++中查找字符串中的子串标记

回答

相关问题