Jsoup代碼解讀之四-parser(上)

作為Java世界最好的HTML 解析庫，Jsoup的parser實現非常具有代表性。這部分也是Jsoup最復雜的部分，需要一些數據結構、狀態機乃至編譯器的知識。好在HTML語法不復雜，解析只是到DOM樹為止，所以作為編譯器入門倒是挺合適的。這一塊不要指望囫圇吞棗，我們還是泡一杯咖啡，細細品味其中的奧妙吧。

基礎知識

編譯器

將計算機語言轉化為另一種計算機語言(通常是更底層的語言，例如機器碼、匯編、或者JVM字節碼)的過程就叫做編譯(compile)。編譯器(Compiler)是計算機科學的一個重要領域，已經有很多年歷史了，而最近各種通用語言層出不窮，加上跨語言編譯的興起、DSL概念的流行，都讓編譯器變成了一個很時髦的東西。

編譯器領域相關有三本公認的經典書籍，龍書《Compilers: Principles, Techniques, and Tools 》，虎書《Modern Compiler Implementation in X (X表示各種語言)》，鯨書《Advanced Compiler Design and Implementation》。其中龍書是編譯理論方面公認的不二之選，而后面兩本則對實踐更有指導意義。另外@裝配腦袋有個很好的編譯器入門系列博客： http://www.cnblogs.com/Ninputer/archive/2011/06/07/2074632.html

編譯器的基本流程如下：

其中詞法分析、語法分析、語義分析這部分又叫編譯器的前端(front-end)，而此后的中間代碼生成直到目標生成、優化等屬于編譯器的后端(back-end)。編譯器的前端技術已經很成熟了，也有yacc這樣的工具來自動進行詞法、語法分析(Java里也有一個類似的工具ANTLR)，而后端技術更加復雜，也是目前編譯器研究的重點。

說了這么多，回到咱們的HTML上來。HTML是一種聲明式的語言，可以理解它的最終的輸出是瀏覽器里圖形化的頁面，而并非可執行的目標語言，因此我將這里的Translate改為了Render。

在Jsoup(包括類似的HTML parser)里，只做了Lex(詞法分析)、Parse(語法分析)兩步，而HTML parse最終產出結果，就是DOM樹。至于HTML的語義解析以及渲染，不妨看看攜程UED團隊的這篇文章：《瀏覽器是怎樣工作的：渲染引擎，HTML解析》。

狀態機

Jsoup的詞法分析和語法分析都用到了狀態機。狀態機可以理解為一個特殊的程序模型，例如經常跟我們打交道的正則表達式就是用狀態機實現的。

它由狀態(state)和轉移(transition)兩部分構成。根據狀態轉移的可能性，狀態機又分為DFA(確定有限狀態機)和NFA(非確定有限狀態自動機)。這里拿一個最簡單的正則表達式”a[b]*“作為例子，我們先把它映射到一個狀態機DFA，大概是這樣子：

狀態機本身是一個編程模型，這里我們嘗試用程序去實現它，那么最直接的方式大概是這樣：

public void process(StringReader reader) throws StringReader.EOFException {
 char ch;
 switch (state) {
 case Init:
 ch = reader.read();
 if (ch == 'a') {
 state = State.AfterA;
 accum.append(ch);
 }
 break;
 case AfterA:
 ...
 break;
 case AfterB:
 ...
 break;
 case Accept:
 ...
 break;
 }
}

這樣寫簡單的狀態機倒沒有問題，但是復雜情況下就有點難受了。還有一種標準的狀態機解法，先建立狀態轉移表，然后使用這個表建立狀態機。這個方法的問題就是，只能做純狀態轉移，無法在代碼級別操作輸入輸出。

Jsoup里則使用了狀態模式來實現狀態機，初次看到時，確實讓人眼前一亮。狀態模式是 設計模式 的一種，它將狀態和對應的行為綁定在一起。而在狀態機的實現過程中，使用它來實現狀態轉移時的處理再合適不過了。

“a[b]*“的例子的狀態模式實現如下，這里采用了與Jsoup相同的方式，用到了枚舉來實現狀態模式：

public class StateModelABStateMachine implements ABStateMachine {
State state;
StringBuilder accum;
enum State {
 Init {
 @Override
 public void process(StateModelABStateMachine stateModelABStateMachine, StringReader reader) throws StringReader.EOFException {
 char ch = reader.read();
 if (ch == 'a') {
 stateModelABStateMachine.state = AfterA;
 stateModelABStateMachine.accum.append(ch);
 }
 }
 },
 Accept {
 ...
 },
 AfterA {
 ...
 },
 AfterB {
 ...
 };
public void process(StateModelABStateMachine stateModelABStateMachine, StringReader reader) throws StringReader.EOFException {
 }
 }
public void process(StringReader reader) throws StringReader.EOFException {
 state.process(this, reader);
 }
}

PS:我在github上fork了一份Jsoup的代碼，把這系列文章提交了上去，并且給一些代碼增加了中文注釋，有興趣的可以看看https://github.com/code4craft/jsoup-learning。本文中提到的幾種狀態機的完整實現在這個倉庫的https://github.com/code4craft/jsoup-learning/tree/master/src/main/java/us/codecraft/learning路徑下。

下一篇文章將從Jsoup的詞法分析器開始來講狀態機的使用。