正则表达式 – 如何解析HTML/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 ]+/ """

该语法由非终端(“标签”,“标签”,“属性”和“属性”)组成.非终端显示在规则右侧的任何地方,可以用任何可能的定义(由|分隔)替换.引号和正则表达式中的文本是终端,它必须与输入完全匹配.

标签非终端识别开始和结束标签,标签之间是非终端标签.每当解析器识别出开始标记时,它都希望在另一侧找到结束标记.标签将识别一个标签,然后再标记标签.此递归定义允许解析器识别无限数量的标记.

解析器生成器是将无上下文语法转换为下推自动机以识别输入语言的工具.虽然在准确指定语法方面存在许多挑战,但这会在构建解析器时带来很多复杂性.

其他解析方法

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