楊建紅,舒江波

(1.武漢工業(yè)學(xué)院 計(jì)算機(jī)信息與工程系,湖北 武漢 430023;2.華中師范大學(xué) 計(jì)算機(jī)科學(xué)系,湖北 武漢 430079)

許多嵌入式瀏覽器都是基于開(kāi)源瀏覽器進(jìn)行Linux平臺(tái)的移植或改進(jìn),而對(duì)于其他一些嵌入式平臺(tái)相關(guān)的嵌入式瀏覽器開(kāi)發(fā),如實(shí)時(shí)的VxWorks嵌入式平臺(tái)下的嵌入式瀏覽器產(chǎn)品還相當(dāng)?shù)膮T乏.VxWorks相比Linux的一個(gè)較大的區(qū)別就在于VxWorks是一個(gè)硬實(shí)時(shí)性操作系統(tǒng),而Linux是一個(gè)軟實(shí)時(shí)性操作系統(tǒng),VxWorks能更加容易的提供實(shí)時(shí)性保證,降低了依靠龐大的實(shí)時(shí)性代碼開(kāi)發(fā)風(fēng)險(xiǎn),這對(duì)于嵌入式瀏覽器的實(shí)時(shí)性要求是非常有利的.另外,嵌入式瀏覽器的兩個(gè)關(guān)鍵的問(wèn)題就是數(shù)據(jù)的解析和布局顯示.經(jīng)過(guò)分析,發(fā)現(xiàn)諸多現(xiàn)有的嵌入式瀏覽器中,在解析模塊和布局模塊中穿插著顯示模塊GUI的調(diào)用,顯示模塊與其他模塊緊密耦合在一起,相互之間缺乏層次感,如果想在后續(xù)開(kāi)發(fā)中進(jìn)行跨平臺(tái)的移植或是進(jìn)行二次開(kāi)發(fā)擴(kuò)展功能都比較困難.

針對(duì)上述應(yīng)用需求以及存在的問(wèn)題,本文中主要探討面向VxWorks的嵌入式瀏覽器解析和布局技術(shù).

1 嵌入式瀏覽器的整體架構(gòu)

圖1 嵌入式瀏覽器的整體架構(gòu)

嵌入式瀏覽器一般采用C/S結(jié)構(gòu),瀏覽器軟件安裝在客戶端后,當(dāng)用戶輸入有效URL標(biāo)識(shí)后,瀏覽器的用戶交互模塊即向控制模塊發(fā)出URL指令,通過(guò)HTTP協(xié)議在網(wǎng)絡(luò)傳輸層建立TCP/IP網(wǎng)絡(luò)協(xié)議的連接,借助于Socket套接字的傳輸方式,從Web服務(wù)器端的80端口抓取HTML網(wǎng)頁(yè)資源,然后對(duì)網(wǎng)頁(yè)數(shù)據(jù)分段進(jìn)行解析、布局、最后將Web頁(yè)面顯示在屏幕上,展現(xiàn)給用戶[1].圖1給出了嵌入式瀏覽器的整體架構(gòu).其中,解析模塊負(fù)責(zé)將網(wǎng)頁(yè)傳輸模塊處接收到的網(wǎng)頁(yè)數(shù)據(jù)依次通過(guò)詞法分析、語(yǔ)法分析、語(yǔ)義分析處理,最后生成DOM樹(shù)結(jié)構(gòu)的解析數(shù)據(jù)結(jié)構(gòu)鏈表.在解析模塊生成解析數(shù)據(jù)結(jié)構(gòu)DOM樹(shù)后,布局模塊將會(huì)對(duì)每一個(gè)可顯示的DOM樹(shù)中的HTML標(biāo)記進(jìn)行布局排版.

2 解析技術(shù)

圖2 詞法解析狀態(tài)轉(zhuǎn)換圖

根據(jù)各個(gè)階段的功能,嵌入式瀏覽器的解析分為詞法分析,語(yǔ)法分析和語(yǔ)義分析3個(gè)階段.首先由詞法分析負(fù)責(zé)完成簡(jiǎn)單的HTML標(biāo)記名稱的匹配工作,然后由語(yǔ)法分析對(duì)標(biāo)記的語(yǔ)法進(jìn)行檢測(cè),判斷解析出的標(biāo)記對(duì)是否符合HTML語(yǔ)法規(guī)則,最后在語(yǔ)義分析階段完成語(yǔ)法檢測(cè)過(guò)的HTML標(biāo)記的屬性名及屬性值信息的提取,并生成解析數(shù)據(jù)結(jié)構(gòu)鏈表.由于大多數(shù)嵌入式瀏覽器解析中語(yǔ)法分析和語(yǔ)義分析的過(guò)程相同,我們不作討論,這里重點(diǎn)討論詞法分析.

詞法分析是嵌入式瀏覽器的解析過(guò)程的第一步,也是非常重要的一步,其主要功能是從接收的網(wǎng)頁(yè)數(shù)據(jù)字符流中識(shí)別出有意義的符號(hào)字符串.詞法分析的效率、準(zhǔn)確性與容錯(cuò)性關(guān)系到整個(gè)瀏覽器設(shè)計(jì)的質(zhì)量.我們用有限自動(dòng)機(jī)來(lái)表示詞法分析的過(guò)程與步驟[2],詞法解析狀態(tài)轉(zhuǎn)換如圖2所示,其中,各個(gè)狀態(tài)符號(hào)的含義為:init:初始狀態(tài);erase:剔除狀態(tài),用于跳過(guò)注釋及文檔類型說(shuō)明字符串;parse:解析狀態(tài),進(jìn)行相關(guān)HTML標(biāo)記類型的判斷;startTag:開(kāi)始標(biāo)記分類狀態(tài),用于區(qū)分開(kāi)始標(biāo)記、結(jié)束標(biāo)記、空元素標(biāo)記,并負(fù)責(zé)處理開(kāi)始標(biāo)記和空元素標(biāo)記;endTag:結(jié)束標(biāo)記狀態(tài),處理結(jié)束標(biāo)記的相關(guān)操作,如標(biāo)記出棧等;text:解析內(nèi)容狀態(tài);over:終止?fàn)顟B(tài).

在詞法分析模塊中還有涉及到一個(gè)非常關(guān)鍵的技術(shù)即標(biāo)記的識(shí)別算法,HTML4.0規(guī)范中定義的標(biāo)記有91個(gè),在解析過(guò)程中需要頻繁對(duì)它們進(jìn)行查找判定接收的字串是否為規(guī)范中定義的標(biāo)記,因此,需要設(shè)計(jì)一種高效快速的查找算法來(lái)識(shí)別解析文本中的標(biāo)記,我們?cè)噲D采用哈希表的設(shè)計(jì)思想,通過(guò)建立哈希表進(jìn)行靜態(tài)哈希映射查詢,而設(shè)計(jì)哈希表時(shí)一個(gè)重要的問(wèn)題就是防止沖突. H(name)=Len+conv(name[0])+conv(name[Len-1])是一個(gè)無(wú)沖突的哈希函數(shù),但是,通過(guò)對(duì)其測(cè)試,發(fā)現(xiàn)對(duì)HTML4.0中定義的91個(gè)標(biāo)記名進(jìn)行哈希時(shí),其字符到數(shù)字的轉(zhuǎn)換表是一個(gè)自定義的、離散的字符與數(shù)字之間的映射關(guān)系集合,因此每次在執(zhí)行字符到數(shù)字的轉(zhuǎn)換時(shí),都要對(duì)轉(zhuǎn)換表集合中的字符數(shù)字對(duì)應(yīng)關(guān)系進(jìn)行遍歷,最差情況下是遍歷完畢所有的關(guān)系組合.因此這種哈希算法效率與直接對(duì)HTML4.0標(biāo)準(zhǔn)中定義的標(biāo)記名稱進(jìn)行字符串匹配判別的方式相比,沒(méi)有很大的效率提升,因?yàn)槊看卧谶M(jìn)行網(wǎng)頁(yè)字符串是否為合法標(biāo)記名稱判別時(shí),都需要對(duì)自定義的關(guān)系集合進(jìn)行遍歷，且更大的弊端就是不具有擴(kuò)展性,如果HTML標(biāo)準(zhǔn)中擴(kuò)充了新的標(biāo)記名稱,那么就有可能導(dǎo)致其自定義的字符數(shù)字映射關(guān)系不再適用,而需要進(jìn)行重新評(píng)估與修正,進(jìn)而建立一種新的映射關(guān)系.

圖3 哈希映射處理示意

我們借鑒一種經(jīng)典的Hash公式,該哈希函數(shù)有一個(gè)哈希模式參數(shù),它能夠通過(guò)修改其中的哈希模式參數(shù)值,得到對(duì)同一個(gè)字符串的不同的哈希值.利用這種思想,可以實(shí)現(xiàn)將一個(gè)字符串經(jīng)過(guò)3次不同的哈希模式哈希后,表示在3個(gè)定長(zhǎng)的哈希表中,通過(guò)3個(gè)哈希值共同標(biāo)識(shí)出一個(gè)字符串.這樣處理后,其發(fā)生哈希值沖突的幾率大致為1/1022.3.另外,使用位圖充當(dāng)哈希表,每一種HTML標(biāo)記類型通過(guò)哈希函數(shù)映射到位圖中一個(gè)bit位上,位圖中的bit位為1,等價(jià)為將HTML標(biāo)記類型名稱存入哈希表,表示該位映射有HTML標(biāo)記類型;如果為0,則表示該位沒(méi)有對(duì)應(yīng)的HTML標(biāo)記,等價(jià)為哈希表中為空的元素.通過(guò)位圖的位移操作,可以輕易實(shí)現(xiàn)對(duì)HTML標(biāo)記類型的判斷,相比使用哈希表中的字符串匹配進(jìn)行判別的方式,時(shí)間復(fù)雜度要更低.已知VxWorks在32位機(jī)中int整型占4個(gè)字節(jié),即32位,因此在計(jì)算哈希表長(zhǎng)度時(shí)是以32為基數(shù)計(jì)算的,針對(duì)HTML4.0中定義的91個(gè)標(biāo)記類型,取哈希表長(zhǎng)度為:[(91/32)+1]*32=96,即哈希表長(zhǎng)度為96.哈希映射處理過(guò)程如圖3所示.詞法分析算法如下:

(1)初始化位圖結(jié)構(gòu)bitmap_hash1,bitmap_hash2,bitmap_hash3,將位圖中的各位清0,將HTML4.0中所有HTML標(biāo)記名字符串經(jīng)哈希函數(shù)映射到3個(gè)位圖中相應(yīng)的bit位上.

(2)當(dāng)前字符游標(biāo)Char指向接收到的HTML數(shù)據(jù)字符串首字符.

(3)如果當(dāng)前自如Char為’<’字符,則轉(zhuǎn)向(4)處理,否則,讀取Char后續(xù)字符直至遇到’<’字符或’