使用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 結語
對于遞歸下降的語法解析器而言，重要的就是要做好“向前看”的工作，自上而下的遞歸解析相比自底向上的解析，實際性能并沒有什么大的損失，但其代碼結構的可理解程度就要高不少了。
感謝你的耐心閱讀，歡迎來信交流心得體會。