在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++中查找字符串中的子串標記

回答

相關問題