使用Python语言编写简单的HTML5语法解析器_python教程_开发教程

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>
<html><!-- this is comment--><head><title>Test</title></head>
<bodystyle=”background:#000;”><div>Text Content</div></body></html>

<!DOCTYPEhtml>
<html><!-- this is comment--><head><title>Test</title></head>
<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 = "" Node = Comment | Element | Text Comment = "'... "-->" Element = "<" TagName Attrs" /"? ">" |"<" TagName Attrs ">" Node "" Text = ...any characters until '<' TagName = [a-zA-Z][a-zA-Z0-9] Attrs = | AttrAttrs Attr = AttrName ( "=" AttrValue)? #No WShere AttrName = [a-zA-Z ][a-zA-Z0-9 -] AttrValue = '"' [^"]* '"' '''

'''
Document = DocType Node*
DocType = "<!DOCTYPE" TypeName">"
Node = Comment | Element | Text
Comment = "<!--" ...any text without'-->'... "-->"
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")
        self.name = name
        self.value = value
class Document(Node):
    def __init__(self, pos=0):
        Node.__init__(self, pos,"Document")
        self.docType = None
        self.rootElement = None

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 = []
    defaddAttr(self, attr):
        attr.parent = self
        self.attrs.append(attr)
    defaddChild(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")
        self.name = name
        self.value = value
class Document(Node):
    def__init__(self, pos=0):
        Node.__init__(self, pos,"Document")
        self.docType = None
        self.rootElement = None

这里Node是所有DOM树节点的基类，DocType、Comment、Element、Attr、Text、Document都是Node的子类。

2.3 TDD：main程序入口

前面说到，我们使用的是Python语言，让我们追随直觉，快速写下main程序的启动代码吧：

if __name__=="__main__":
    print "Parsing %s" %(sys.argv[1])
    html_string =open(sys.argv[1]).read()
    P = Parser(Lexer(html_string))
    P.parse()
    D = P.getDocument()

if __name__=="__main__":
    print "Parsing %s" %(sys.argv[1])
    html_string =open(sys.argv[1]).read()
    P = Parser(Lexer(html_string))
    P.parse()
    D = P.getDocument()

从上面的代码可以看到，我们需要实现2个类：Lexer和Parser，一个核心方法parse，解析的结果以Document对象返回。

2.4 Lexer设计与实现

编译原理里提到的文法解析通常基于正则文法（有限自动机理论），然而，实际世界中使用的正则表达式引擎则支持更高级的特性，如字符类、命名捕获、分组捕获、后向引用等。我们这里不关心如何实现一个基于正则文法的有限自动机，而只是使用正则表达式引擎实现Lexer。由于Lexer的输入为字符流，输出为Token序列，那么将此接口命名为nextToken。首先，它应该带一个模式（pattern）字符串参数，代表我们期望从字符流中扫描的模式，同时，Lexer对象维护一个状态pos，代表当前扫描的起始位置。其次，我们给nextToken加上额外的2个参数（注意：这里的API设计仅仅从权考虑，在正式的产品开发中，可能需要根据实际的需求做出改动）：

skipLeadingWS 代表在扫描调用者提供的下一个模式之前，是否先忽略前导空白字符串
groupExtract 有的时候，扫描模式有匹配之后，我们只想提取其中的部分返回，这里根据正则表达式引擎的一般后向引用定义，0代表整个模式，而1代表第1个左圆括号对应的部分。

OK，Lexer的设计部分大抵差不多了，可以开始写代码了：

class Lexer:
    WS =re.compile("\s{1,}", re.MULTILINE|re.DOTALL)
    def nextToken(self, pattern, skipLeadingWS=True, groupExtract=0):
        if skipLeadingWS:
            m= Lexer.WS.match(self.html_string, self.pos)
              ifm:
               ws_length = len(m.group(0))
                  self.pos = self.pos + ws_length #Python没有+=操作
         p = re.compile(pattern,re.MULTILINE|re.DOTALL)
         m = p.match(self.html_string, self.pos)
         if m:
              m_length= len(m.group(0))
              self.pos= self.pos + m_length
              return(m.pos, m.group(groupExtract)) #返回值的设计：(pattern的起始位置，token字符串)
         else:
              return(-1, None)

class Lexer:
    WS =re.compile("\s{1,}", re.MULTILINE|re.DOTALL)
    defnextToken(self, pattern, skipLeadingWS=True, groupExtract=0):
        if skipLeadingWS:
            m= Lexer.WS.match(self.html_string, self.pos)
              ifm:
              ws_length = len(m.group(0))
                  self.pos = self.pos + ws_length #Python没有+=操作
        p = re.compile(pattern,re.MULTILINE|re.DOTALL)
        m = p.match(self.html_string, self.pos)
        if m:
              m_length= len(m.group(0))
              self.pos= self.pos + m_length
              return(m.pos, m.group(groupExtract)) #返回值的设计：(pattern的起始位置，token字符串)
        else:
              return(-1, None)

2.4.1验证你不了解的API！

请再看一下上面的函数Lexer.nextToken的API设计与实现。这里的核心要点就是用到了Python 正则表达式库的API PatternObject.match方法。这里的要点是：对于你不了解的API（所谓的不了解，就是以前你没怎么用过），一定要仔细阅读该API的帮助手册，最好是编写简单的单元测试case来验证它是否能够满足你的需求。事实上，我一开始使用的是PatternObject.search，而不是match方法，但是我发现了问题：

p=re.compile(r”^[a-z]{1,}”)  
p.search(“123abc”, 3) #不匹配，虽然模式使用了^，并期望与search方法的第一个起始位置参数共同作用

p=re.compile(r”^[a-z]{1,}”)  
p.search(“123abc”, 3) #不匹配，虽然模式使用了^，并期望与search方法的第一个起始位置参数共同作用

Python帮助手册里对此API行为居然做出了明确规定，但我不明白API这样设计有何合理性——相当地违背直觉嘛。山穷水尽疑无路，柳暗花明又一村。当感觉有点绝望的时候（实际上也没那么夸张，可以用一个方法绕过这个缺陷并仍然使用search API来完成工作，就是会有性能缺陷），再看看match方法：… 嗯？这不就是我想要的API嘛：

p=re.compile(r”[a-z]{1,}”)
     m = p.match(“abc456”) #匹配
     m = p.match(“123abc456”) #不匹配
     m = p.match(“123abc456”, 3) #匹配

    p=re.compile(r”[a-z]{1,}”)
    m = p.match(“abc456”) #匹配
    m = p.match(“123abc456”) #不匹配
    m = p.match(“123abc456”, 3) #匹配

糟糕的是，match API也有一个问题：m.endpos理所当然的应当返回匹配模式在源字符串中的结束位置，但它实际上返回的却是整个源字符串的结束位置（也就是它的长度），还好，这个问题可以用len(m.group(0))巧妙地绕过且不影响性能。结论：API使用内藏陷阱，请谨慎使用，使用之前先做好单元测试功能验证。

2.5 Parser设计与实现

让我们先写出parse入口函数：

def parse(self):
        ifnot self._parseDocType(self.document):
              pass#Ignore
        try:
            return self._parseElement(self.document) #MUST start with <html>?
       except ParseFinishException, e:
            return True

    defparse(self):
        ifnotself._parseDocType(self.document):
              pass#Ignore
        try:
            return self._parseElement(self.document) #MUST start with <html>?
      exceptParseFinishException, e:
            return True

从这个顶层的parse()来看，一个HTML文档由一个开始的DocType节点和一个根<html>元素组成。parse()内部调用了2个方法：_ parseDocType和_ parseElement。注意，后2个函数名前面加了下划线，代表私有函数，不提供外部使用（脚本语言通常没有C++的名字可见性概念，通常使用命名规范来达到同样的目的）。 ParseFinishException的用法请参考2.7节说明。

2.6 验证Lexer.nextToken：实现_parseDocType()

DocType节点的语法声明参考2.1，下面是_parseDocType()的实现：

def_parseDocType(self, ctx):  
    print"_parseDocType: enter"  
   assert ctx.type=="Document"  
    pos,docType = self.lexer.nextToken(r"<!DOCTYPE\s{1,}([a-z]+)>", True, 1)  
    if docType:  
       ctx.docType = DocType(pos, docType)  
       return True  
    else:  
       print "No DOCTYPE node found."  
       return False

def_parseDocType(self, ctx):  
    print"_parseDocType: enter"  
  assert ctx.type=="Document"  
    pos,docType = self.lexer.nextToken(r"<!DOCTYPE\s{1,}([a-z]+)>", True, 1)  
    if docType:  
      ctx.docType = DocType(pos, docType)  
      return True  
    else:  
      print "No DOCTYPE node found."  
      return False

_parseDocType的代码完美演示了Lexer.nextToken API的用法，其形参ctx代表当前的上下文节点，比如说，解析DocType时，其ctx就是根Document对象。这里_parseDocType使用的扫描模式可以提取出像“<!DOCTYPE html>”中的“html”。不过，也许这里可以放松条件以匹配HTML4的语法。

2.7 实现_parseComment()时的代码健壮性考虑

前面实现_parseDocType()时只使用了1次nextToken扫描，这里实现_parseComment()将考虑使得代码更健壮一点。怎么讲呢？HTML注释节点以“<!–”开始，以“–>”结束，中间是任意的字符（不包含连续的–>）。

如果我们的扫描模式写成：

p=re.compile(r”<!–(.*)–>”)

则由于正则表达式的默认贪心模式匹配，它将匹配字符串“<!—abc–>123–>”中的“abc–>123”，为此，可改用非贪心模式匹配：

p=re.compile(r”<!–(.* ? )–>”)

这样就行了吗？还不行。当html字符串中只有开始的<!–，没有结束的–>时，将视为一直到文档结束都是注释。为实现这个规约，需要补充进行一次扫描：

如果p=re.compile(r”<!–(.* ? )–>”)扫描失败，就用p=re.compile(r”<!–(.* ? ) $ “)重新扫描一次。

2.8难点：递归的_parseElement()

元素节点的解析存在许多难点，比如说，需要在这里解析元素属性、需要递归地解析可能的子节点。让我们尝试着写写看吧：

Python

def _parseElement(self, ctx):  
        print"_parseElement: enter"  
        pos,tagName = self.lexer.nextToken(r"<([a-zA-Z][a-zA-Z0-9]*)", True, 1)  
        ifnot tagName:  
           print "_parseElement: tagName not found."  
           return False  
       element = Element(pos, tagName)

def _parseElement(self, ctx):  
        print"_parseElement: enter"  
        pos,tagName = self.lexer.nextToken(r"<([a-zA-Z][a-zA-Z0-9]*)", True, 1)  
        ifnottagName:  
          print "_parseElement: tagName not found."  
          return False  
      element = Element(pos, tagName)

这里的容错处理逻辑是：至少当匹配了’<’及有效的tagName后，才认为找到了一个元素节点，这时可以创建一个element对象，但这时我们还不知道接下来的解析是否会成功，所以暂时不addChild到ctx父节点上。

接下来是属性解析：

Python

if not self._parseAttrs(element):  
      return False

if not self._parseAttrs(element):  
      return False

如果属性解析失败，则_ parseElement也随之失败，否则将element添加到ctx上：

Python

if ctx.type=="Document":  
   ctx.rootElement = element  
else:  
    ctx.addChild( element )

if ctx.type=="Document":  
  ctx.rootElement = element  
else:  
    ctx.addChild( element )

_parseAttrs函数的一个副作用是设置元素是否直接以‘/>’结束，如果是这样，则该元素没有进一步的子节点；否则需要进一步递归处理子节点的解析。

Python

if element.hasEndSlashMark:  
   return True  
 #now try to recursive descendant parse childnodes:         
while True:  
    pos, endTagName =self.lexer.nextToken(r"</([a-zA-Z][a-zA-Z0-9]*)>", True, 1)  
    if endTagName:  
        if endTagName==tagName:  
           break

if element.hasEndSlashMark:  
  return True  
 #now try to recursive descendant parse childnodes:        
while True:  
    pos, endTagName =self.lexer.nextToken(r"</([a-zA-Z][a-zA-Z0-9]*)>", True, 1)  
    if endTagName:  
        if endTagName==tagName:  
          break

由于子节点的数目定义在语法规则中是*（0个或多个），则我们需要向前看，即查找形如 </xxx> 这样的结束标签。如果匹配到endTagName，并且等于当前元素的tagName，则递归解析可以结束；

否则的话，需要向上抛出一个定制的异常，请考虑下面的case：

<div>  
       <span id=”x” name=”a”>  
              <img src=”a.jpg”>  
                     </div>

<div>  
      <spanid=”x” name=”a”>  
              <imgsrc=”a.jpg”>  
                    </div>

_parseElement在解析img元素时遇到了</div>结束标签，然后这个结束标签与它自己并不匹配，于是，它需要通知上上层的处于解析<div>位置的_parseElement：

Python

else:  
               find_match = False  
               n = ctx.parent  
               while n:  
                    if n.type=="Element" and n.tagName==endTagName:  
                        find_match = True  
                        break  
                    n = n.parent  
               if find_match:  
                    raise FindElementEndTagException(endTagName)  
               else:  
                    pass #Ignore this unknown </xxx>!

          else:  
              find_match = False  
              n = ctx.parent  
              while n:  
                    if n.type=="Element" and n.tagName==endTagName:  
                        find_match = True  
                        break  
                    n = n.parent  
              if find_match:  
                    raise FindElementEndTagException(endTagName)  
              else:  
                    pass #Ignore this unknown </xxx>!

注意，抛出FindElementEndTagException异常的是_parseElement，接受此异常的同样是_parseElement，只不过两者处于Call Stack的不同位置而已。

Python

pos_before= self.lexer.pos  
try:  
    self._parseNode(element)  
except FindElementEndTagException, e:  
    if e.endTagName==tagName:  
        return True  
    else:  
         raise e  
pos_after = self.lexer.pos  
if pos_before==pos_after:  
       if self.lexer.reachEnd():  
        raise ParseFinishException()  
    else:  
        print"_parseElement: something error happened!"  
        raise ParseError()  
return True

pos_before= self.lexer.pos  
try:  
    self._parseNode(element)  
except FindElementEndTagException, e:  
    if e.endTagName==tagName:  
        return True  
    else:  
        raise e  
pos_after = self.lexer.pos  
if pos_before==pos_after:  
      if self.lexer.reachEnd():  
        raise ParseFinishException()  
    else:  
        print"_parseElement: something error happened!"  
        raise ParseError()  
return True

由于FindElementEndTagException异常由Call Stack的最底层向上抛出，tagName与endTagName第一个匹配的_parseElement将捕获到它。

此外，_parseElement 递归调用_parseNode的时候，我们要一对变量（pos_before和pos_after）记住Lexer的前后状态，如果Lexer状态没有发生变化（pos_before==pos_after），说明_parseNode失败。

这对应什么情况呢？因为Node对象包含3种：Comment、Element、Text，不匹配其中任意一种的话，_parseNode就会失败，比如说，一个单独的‘<’。

目前demo程序以抛出解析异常的方法结束，至于怎么容错处理（忽略，或仍然当作Text节点处理），留待读者自行考虑。

如此，最难的_parseElement()函数就结束了。

3 测试

HTML解析之后是一个DOM树，其根节点为Document对象，怎么验证解析得对不对呢？

把这个DOM树重新序列化为html字符串，与原始输入进行比较即可。考虑到HTML5的容错处理，序列化后的结果不能保证与源输入结构上一致。

DOM树的序列化代码从略，它其实就是一个针对子节点的递归调用，这里代码从略（完整脚本代码请参考附件）。

OK，现在HTML5语法解析器基本上已经编写完成了。

4 结语

对于递归下降的语法解析器而言，重要的就是要做好“向前看”的工作，自上而下的递归解析相比自底向上的解析，实际性能并没有什么大的损失，但其代码结构的可理解程度就要高不少了。

(责任编辑：好模板)