使用Python语言编写简单的HTML5语法解析器

429 查看

1 问题

如何编写一个语法解析器（Parser）呢？在C/C++语言领域，我们有lex & yacc（文法解析器和语法解析器的生成器）及其GNU移植版本flex & bison，yacc是根据大牛Knuth的LALR文法设计的，自底向上进行解析；在Java语言领域，我们有ANTLR，这是是一个基于LL(n)文法的解析器生成器（递归下降，向前看n个Token消解冲突）。通过这些工具，我们只要写出要解析语言的文法、语法定义，就可以让它们帮我们生成对应的解析器，这通常称为编译器的前端（后端指的是代码生成和指令优化），此外，还有称为‘解析器组合子’的半自动工具可用于前端语法分析。

抛开这些工具和第三方库，现在的问题是：给你一个HTML5文件，如何仅使用编程语言本身的库，编写一个语法解析器程序呢？

首先，一个语法解析器需要文法扫描器（Lexer）提供Token序列的输入。而文法扫描器的每个Token通常使用正则表达式来定义，对这里的任务，我们可不想自己实现一套正则表达式引擎（重复造轮子），反之，将依赖本身就提供了正则表达式的编程语言来完成Lexer的编写。

那么，哪些编程语言内置正则表达式引擎呢？C没有，C++ 11之前也没有（可以使用Boost），C++ 11有，Java、C#、Python、Ruby、PHP、Perl则都提供了支持。这里我选择Python，原因无它，相比其他脚本语言，我个人更熟悉Python。而编译型语言处理字符串则不如脚本语言灵活。虽然无类型的Python不像C++/C#/Java那样，有一个好的IDE及调试环境，但记住一点：开发原型优先选择灵活的脚本语言，待技术实现可靠性得到验证后，可以再移植到编译型语言以进一步提高性能。这里值得一说的是，上述语言均支持OOP。我想强调的是，好的OO设计风范（主要涉及类层次结构的定义和核心流程的参数传递）对于编写可读性佳、可维护性高的代码无疑是十分重要的。

2 程序设计思路

2.1 简化版HTML5语法定义

首先，给出一段要解析的HTML文件内容如下：

<!DOCTYPE html>

<bodystyle=”background:#000;”><div>Text Content</div></body></html>

根据上面的简单用例，我们的程序设计目标限定如下：它能够处理文档类型声明（DocType）、元素（Element）、元素属性（Attr）、Html注释（Comment）和普通文本（Text），暂不支持内嵌JavaScript 的<script>元素和内嵌CSS的<style>元素。也暂不考虑Unicode的解析，假设输入文件是纯英文ASCII编码的。

在此约束条件下，首先来定义此简化版的HTML5语法定义：

'''

Document = DocType Node*

DocType = "<!DOCTYPE" TypeName">"

Node = Comment | Element | Text

Comment = "'... "-->"

Element = "<" TagName Attrs"/"? ">"

|"<" TagName Attrs ">" Node* "</" TagName">"

Text = ...any characters until '<'

TagName = [a-zA-Z][a-zA-Z0-9]*

Attrs = <empty>

| AttrAttrs

Attr = AttrName ( "=" AttrValue)? #No WShere

AttrName = [a-zA-Z_][a-zA-Z0-9_\-]*

AttrValue = '"' [^"]* '"'

'''

注意，这里没有写出严格的定义。在编写demo程序的过程中，重要的是保持思路清晰，但不需要把细节问题一步详细到位，只要保证细枝末节的问题可以随时扩展修正即可。

2.2简化版DOM数据结构定义

我曾经做过Java XML/DOM解析，也维护过浏览器内核DOM模块的代码，但对于我们的demo开发而言，没必要写一个完善的DOM类层次结构定义。尽管如此，保持简明扼要还是很重要的。 DOM数据结构的Python代码如下：（Python没有枚举类型，直接使用字符串代替）

class Node:

def __init__(self, pos, type):

self.type = type

self.pos = pos #startposition if ref html string

self.parent = None

class DocType(Node):

def __init__(self, pos,docType):

Node.__init__(self, pos,"DocType")

self.value = docType

class Comment(Node):

def __init__(self, pos,comment):

Node.__init__(self, pos,"Comment")

self.value = comment

class Element(Node):

def __init__(self, pos,tagName):

Node.__init__(self, pos,"Element")

self.tagName = tagName

self.attrs = []

self.hasEndSlashMark =False #True, if <xxx .... />

self.childrenNodes = []

def addAttr(self, attr):

attr.parent = self

self.attrs.append(attr)

def addChild(self, node):

node.parent = self

self. childrenNodes.append(node)

class Text(Node):

def __init__(self, pos, text):

Node.__init__(self, pos,"Text")

self.text = text

class Attr(Node):

def __init__(self, pos, name,value=None):

Node.__init__(self, pos,"Attr")

cc（文法解析器和语法解析器的生成器）及其GNU移植版本flex & bison，yacc是根据大牛Knuth的LALR文法设计的，自底向上进行解析；在Java语言领域，我们有ANTLR，这是是一个基于LL(n)文法的解析器生成器（递归下降，向前看n个Token消解冲突）。通过这些工具，我们只要写出要解析语言的文法、语法定义，就可以让它们帮我们生成对应的解析器，这通常称为编译器的前端（后端指的是代码生成和指令优化），此外，还有称为‘解析器组合子’的半自动工具可用于前端语法分析。