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

Question

我被告知并经常被人关注：不要使用正则表达式来解析（或“解析”）用HTML，XML等语言编写的文档。命名的原因各不相同，在这里并不重要。

当被问及如何去做时，通常你会被引用一个库来解析这样的文档 - 一个PHP扩展，一个JS框架等等。大多数时候他们似乎依赖于文档对象模型。

我的问题不是如何在程序或脚本中做到这一点。在真实情况下，我不会尝试再次发明轮子，而只是使用其中一个可用的框架。

我想知道的是 - 这些框架是如何做到的？或者我该怎么做没有框架（假设）？我没有具体谈论任何语言，我对从文档中提取信息的理论感兴趣。

Answer 1

解析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语法的混合一样工作。维基百科上的所有这些技术都有很好的文章，还有许多可用于构建各种解析器的工具。