使用Python语言编写简单的HTML5语法解析器
摘要：通过使用Python语言编写一个简单的HTML5语法解析器作为例子,探讨了在设计手写的递归下降语法解析器程序时需要注意的一些事项。
关键字：Python HTML5 语法解析器 正则表达式 递归下降 编译器技术
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>
根据上面的简单用例，我们的程序设计目标限定如下：它能够处理文档类型声明（DocType）、元素（Element）、元素属性（Attr）、Html注释（Comment）和普通文本（Text），暂不支持内嵌JavaScript 的<script>元素和内嵌CSS的<style>元素。也暂不考虑Unicode的解析，假设输入文件是纯英文ASCII编码的。
在此约束条件下，首先来定义此简化版的HTML5语法定义：
''' 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
这里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()
从上面的代码可以看到，我们需要实现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)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方法的第一个起始位置参数共同作用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) #匹配糟糕的是，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
从这个顶层的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_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()
元素节点的解析存在许多难点，比如说，需要在这里解析元素属性、需要递归地解析可能的子节点。让我们尝试着写写看吧：
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)
这里的容错处理逻辑是：至少当匹配了’<’及有效的tagName后，才认为找到了一个元素节点，这时可以创建一个element对象，但这时我们还不知道接下来的解析是否会成功，所以暂时不addChild到ctx父节点上。
接下来是属性解析：
if not self._parseAttrs(element): return False
如果属性解析失败，则_ parseElement也随之失败，否则将element添加到ctx上：
if ctx.type=="Document": ctx.rootElement = element else: ctx.addChild( element )
_parseAttrs函数的一个副作用是设置元素是否直接以‘/>’结束，如果是这样，则该元素没有进一步的子节点；否则需要进一步递归处理子节点的解析。
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>
_parseElement在解析img元素时遇到了</div>结束标签，然后这个结束标签与它自己并不匹配，于是，它需要通知上上层的处于解析<div>位置的_parseElement：
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的不同位置而已。
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 结语
对于递归下降的语法解析器而言，重要的就是要做好“向前看”的工作，自上而下的递归解析相比自底向上的解析，实际性能并没有什么大的损失，但其代码结构的可理解程度就要高不少了。
感谢你的耐心阅读，欢迎来信交流心得体会。