7

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

当被问到要做什么时，通常会参考一个库来解析这样的文档——一个 PHP 扩展、一个 JS 框架等。大多数时候它们似乎依赖于文档对象模型。

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

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

4

1 回答 1

8

解析 XML 需要一种能够识别称为“上下文无关语言”的工具。正则表达式识别正则语言，它们是上下文无关语言的子集。

识别常规语言

常规语言由确定性有限自动机 (DFA) 识别。DFA 是一组状态，状态之间有过渡边，还有一个输入缓冲区（您正在解析的字符串）。DFA 以其起始状态开始。DFA 在输入缓冲区的开头读取字符，告诉它要进行哪个转换。这会将 DFA 移动到下一个状态，并在此重复该过程。如果 DFA 遇到一个它没有转换的输入字符，它就会结束（输入未被识别）。如果 DFA 达到指定的结束状态，则输入已被识别

要记住的最重要的事情是，DFA 不记得他们去过什么州——只是他们现在在哪里，以及下一步要去哪里。这使得 DFA 无法识别某些类型的语言，例如匹配的 XML 标记。

正则表达式实现（如 PCRE）为方便起见有一些扩展（例如，'+'、'?' 和字符类），以及改变正则表达式功能的其他扩展（如前瞻和后向引用）。这些正则表达式比 DFA 更强大，但是仅使用这些扩展的正则表达式构建 XML 解析器是困难的或不可能的。

识别上下文无关语言

下推自动机识别上下文无关语言。这些工作就像 DFA，但增加了一个堆栈。下推自动机使用输入的第一个字符和堆栈顶部的值选择转换。在每一步中，机器消耗一个输入字符，并且可以将一个值压入堆栈，弹出一个值，或者对堆栈不做任何事情。

下推自动机可以使用堆栈来记住它们所在的位置，这使得它们适合解析 XML 等语言（或大多数编程语言，有一些特殊例外）。

解析 XML

解析器不是通过设计下推自动机来构建的，就像通过设计 DFA 无法识别常规语言一样。上下文无关语法是描述上下文无关语言的更好方法。它们通常以 Backus-Naur 形式 (BNF) 写下来。下面是 XML 子集的简单 BNF 语法：

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 ]+/ "\""

该语法由非终结符（“Tags”、“Tag”、“Attributes”和“Attribute”）组成。在规则右侧出现非终结符的任何地方，它都可以被任何可能的定义替换（由 | 分隔）。引号和正则表达式中的文本是终端，必须与输入完全匹配。

Tag 非终结符识别开始和结束标记，它们之间有一个非终结符标签。每当解析器识别出一个开始标签时，它就希望在另一边找到结束标签。标签将识别一个标签，然后再次识别标签。这个递归定义允许解析器识别无限数量的标签。

解析器生成器是将上下文无关语法转换为下推自动机以识别输入语言的工具。尽管在准确指定语法方面存在很多挑战，但这大大降低了构建解析器的复杂性。

其他解析方法

您可以编写解析器，而无需手动构建状态机，也可以编写上下文无关语法。通常，这可以通过递归下降解析器或手工制作的解析器来完成，该解析器使用正则表达式以及关于被解析语言的一些特殊知识。递归下降解析器看起来很像上下文无关文法，但有一些严重的性能问题和功能限制。还有解析表达式语法 (PEG)，其工作方式类似于正则表达式和 BNF 语法的混合体。Wikipedia 上有关于所有这些技术的精彩文章，以及许多可用于构建各种解析器的工具。

于 2012-04-26T23:54:53.127 回答