解析HTML/XML文檔如何工作？

我被告知並經常被人關注：不要使用正則表達式來解析（或「解析」）用HTML，XML等語言編寫的文檔。命名的原因各不相同，在這裏並不重要。解析HTML/XML文檔如何工作？

當被問及如何去做時，通常你會被引用一個庫來解析這樣的文檔 - 一個PHP擴展，一個JS框架等等。大多數時候他們似乎依賴於文檔對象模型。

我的問題不是如何在程序或腳本中做到這一點。在真實情況下，我不會嘗試再次發明輪子，而只是使用其中一個可用的框架。

我想知道的是 - 這些框架是如何做到的？或者我該怎麼做沒有框架（假設）？我沒有具體談論任何語言，我對從文檔中提取信息的理論感興趣。

2012-04-17 Armatus

閱讀[parser generators]（http://en.wikipedia.org/wiki/Parser_generator）;一般來說，你一次一個地瀏覽字符串中的字符，以便跟蹤要查找什麼類型的事物，例如，「如果我看到一個'< - '，那麼進入解析註釋的模式;如果我看到一個'<'，那麼進入我正在解析元素的模型」。所以你可以[爲XML使用解析器生成器和語法]（http://stackoverflow.com/questions/570144/best-practices-for-writing-a-parser），或者你可以編寫自己的有狀態解析器地面起來。 – Phrogz 2012-04-17 16:06:29

所以它是一個類似於正則表達式引擎這樣做的文本解析 - 只專門用於期望的代碼結構，交換性能的靈活性？ – Armatus 2012-04-17 16:11:13

類似的，是的。的確，在某些語言中，很容易[構建一個使用正則表達式來解析字符的解析器]（http://www.ruby-doc.org/stdlib-1.9.3/libdoc/strscan/rdoc/StringScanner.html）。不同之處在於，一個正則表達式無法很好地解釋狀態（例如，在解析器確實記錄了它的位置時搜索'/ + + /'/裏面的<！ - <不是元素> - >是。 – Phrogz 2012-04-17 16:15:26

解析XML需要一個能夠識別稱爲「上下文無關語言」的工具。正則表達式識別常規語言，它們是上下文無關語言的子集。

認識則語言

正規語言是由確定性有限自動機（有限自動機）的認可。 DFA是一組具有狀態間轉換邊界的狀態，以及一個輸入緩衝區（您正在解析的字符串）。 DFA從其開始狀態開始。 DFA讀取輸入緩衝區開始處的字符，告訴它要進行哪個轉換。這將DFA移至下一個狀態，重複此過程。如果DFA遇到輸入字符，它沒有轉換，它會結束（輸入未被識別）。如果DFA達到指定的最終狀態，則輸入已被識別

要記住的最重要的事情是，DFA不記得他們去過哪些狀態---他們現在在哪裏，以及在哪裏去下一個。這使得DFA無法識別某些類型的語言，例如匹配的XML標記。正則表達式實現（如PCRE）爲方便起見（例如'+'，'？'和字符類）以及其他改變正則表達式（比如向前和向後引用）功能的其他擴展。。這些正則表達式比DFA更強大，但僅使用這些擴展的正則表達式來構建XML解析器將會很難或不可能。

認識上下文無關語言

上下文無關語言被下推自動識別。這些工作就像DFA一樣，但增加了一個堆棧。下推自動機使用輸入和的第一個字符選擇堆棧頂部的值。在每一步中，機器都會消耗一個輸入字符，並且可以在堆棧上推送一個值，關閉一個或禁用堆棧。

下推自動機可以使用堆棧來記住他們去過的地方，這使得它們適用於解析XML等語言（或大多數編程語言，只有一些特殊的例外）。

解析XML

解析器沒有被設計下推自動機，你不設計一個DFA識別正規語言以同樣的方式建造。上下文無關語法是描述上下文無關語言的更好方式。他們通常以巴克斯 - 諾爾形式（BNF）書寫。這裏有一個簡單的BNF語法XML的一個子集：

Tags ::= Tag Tags | <nothing> 

Tag ::= "<" /[a-zA-Z]+/ Attributes ">" Document "</" /[a-zA-Z]+/ ">" 

Attributes ::= Attribute Attributes | <nothing> 

Attribute ::= /[a-zA-Z]+/ "=" "\"" /[a-zA-Z0-9 ]+/ "\""

這個語法是由非終端（「標籤」，「標籤」，「屬性」和「屬性」）的。任何一個非終端出現在規則的右側，它都可以被任何可能的定義替換（用|分隔）。引號和正則表達式中的文本是終端，它們必須完全匹配輸入。

標籤非終端識別開始和結束標籤，其間有標籤非終端。每當解析器識別到一個開始標籤時，它都希望在另一側找到結束標籤。標籤會識別一個標籤，然後再次標籤。這個遞歸定義允許解析器識別無限數量的標籤。

解析器生成器是將上下文無關語法轉化爲下推自動機來識別輸入語言的工具。除了構建解析器之外，這需要很多複雜性，但準確指定語法有很多挑戰。

用於解析

其他方法可以，也可以通過寫上下文無關文法書寫，而無需手動建立狀態機分析器。通常，這可以通過遞歸下降解析器或手工解析器來完成，該解析器使用正則表達式以及有關正在解析的語言的一些特殊知識。遞歸下降解析器看起來很像上下文無關語法，但有一些嚴重的性能問題和功能限制。還有解析表達式語法（PEG），它們像正則表達式和BNF語法的混合一樣工作。維基百科上的所有這些技術都有很好的文章，還有許多可用於構建各種解析器的工具。

來源

2012-04-26 23:54:53 ccurtsinger

我想不出更多我想知道的東西。非常感謝您的精彩回答！ – Armatus 2012-04-27 07:31:08

解析HTML/XML文檔如何工作？

回答

相關問題