轉(zhuǎn)載自??Jsoup代碼解讀之四-parser(上)

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

基礎(chǔ)知識(shí)

編譯器

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

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

編譯器的基本流程如下：

其中詞法分析、語法分析、語義分析這部分又叫編譯器的前端(front-end)，而此后的中間代碼生成直到目標(biāo)生成、優(yōu)化等屬于編譯器的后端(back-end)。編譯器的前端技術(shù)已經(jīng)很成熟了，也有yacc這樣的工具來自動(dòng)進(jìn)行詞法、語法分析(Java里也有一個(gè)類似的工具ANTLR)，而后端技術(shù)更加復(fù)雜，也是目前編譯器研究的重點(diǎn)。

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

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

狀態(tài)機(jī)

Jsoup的詞法分析和語法分析都用到了狀態(tài)機(jī)。狀態(tài)機(jī)可以理解為一個(gè)特殊的程序模型，例如經(jīng)常跟我們打交道的正則表達(dá)式就是用狀態(tài)機(jī)實(shí)現(xiàn)的。

它由狀態(tài)(state)和轉(zhuǎn)移(transition)兩部分構(gòu)成。根據(jù)狀態(tài)轉(zhuǎn)移的可能性，狀態(tài)機(jī)又分為DFA(確定有限狀態(tài)機(jī))和NFA(非確定有限狀態(tài)自動(dòng)機(jī))。這里拿一個(gè)最簡單的正則表達(dá)式"a[b]*"作為例子，我們先把它映射到一個(gè)狀態(tài)機(jī)DFA，大概是這樣子：

狀態(tài)機(jī)本身是一個(gè)編程模型，這里我們嘗試用程序去實(shí)現(xiàn)它，那么最直接的方式大概是這樣：

<!-- lang: java --> 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;} }

這樣寫簡單的狀態(tài)機(jī)倒沒有問題，但是復(fù)雜情況下就有點(diǎn)難受了。還有一種標(biāo)準(zhǔn)的狀態(tài)機(jī)解法，先建立狀態(tài)轉(zhuǎn)移表，然后使用這個(gè)表建立狀態(tài)機(jī)。這個(gè)方法的問題就是，只能做純狀態(tài)轉(zhuǎn)移，無法在代碼級別操作輸入輸出。

Jsoup里則使用了狀態(tài)模式來實(shí)現(xiàn)狀態(tài)機(jī)，初次看到時(shí)，確實(shí)讓人眼前一亮。狀態(tài)模式是設(shè)計(jì)模式的一種，它將狀態(tài)和對應(yīng)的行為綁定在一起。而在狀態(tài)機(jī)的實(shí)現(xiàn)過程中，使用它來實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移時(shí)的處理再合適不過了。

"a[b]*"的例子的狀態(tài)模式實(shí)現(xiàn)如下，這里采用了與Jsoup相同的方式，用到了枚舉來實(shí)現(xiàn)狀態(tài)模式：

<!-- lang: java --> public class StateModelABStateMachine implements ABStateMachine {State state;StringBuilder accum;enum State {Init {@Overridepublic 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。本文中提到的幾種狀態(tài)機(jī)的完整實(shí)現(xiàn)在這個(gè)倉庫的https://github.com/code4craft/jsoup-learning/tree/master/src/main/java/us/codecraft/learning路徑下。

下一篇文章將從Jsoup的詞法分析器開始來講狀態(tài)機(jī)的使用。

總結(jié)

以上是生活随笔為你收集整理的Jsoup代码解读之四-parser(上)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。