面向VxWorks的嵌入式瀏覽器解析和布局技術研究

2010-11-26 01:33:58楊建紅舒江波

湖北大學學報(自然科學版) 2010年4期

楊建紅,舒江波

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

許多嵌入式瀏覽器都是基于開源瀏覽器進行Linux平臺的移植或改進,而對于其他一些嵌入式平臺相關的嵌入式瀏覽器開發,如實時的VxWorks嵌入式平臺下的嵌入式瀏覽器產品還相當的匱乏.VxWorks相比Linux的一個較大的區別就在于VxWorks是一個硬實時性操作系統,而Linux是一個軟實時性操作系統,VxWorks能更加容易的提供實時性保證,降低了依靠龐大的實時性代碼開發風險,這對于嵌入式瀏覽器的實時性要求是非常有利的.另外,嵌入式瀏覽器的兩個關鍵的問題就是數據的解析和布局顯示.經過分析,發現諸多現有的嵌入式瀏覽器中,在解析模塊和布局模塊中穿插著顯示模塊GUI的調用,顯示模塊與其他模塊緊密耦合在一起,相互之間缺乏層次感,如果想在后續開發中進行跨平臺的移植或是進行二次開發擴展功能都比較困難.

針對上述應用需求以及存在的問題,本文中主要探討面向VxWorks的嵌入式瀏覽器解析和布局技術.

1 嵌入式瀏覽器的整體架構

圖1 嵌入式瀏覽器的整體架構

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

2 解析技術

圖2 詞法解析狀態轉換圖

根據各個階段的功能,嵌入式瀏覽器的解析分為詞法分析,語法分析和語義分析3個階段.首先由詞法分析負責完成簡單的HTML標記名稱的匹配工作,然后由語法分析對標記的語法進行檢測,判斷解析出的標記對是否符合HTML語法規則,最后在語義分析階段完成語法檢測過的HTML標記的屬性名及屬性值信息的提取,并生成解析數據結構鏈表.由于大多數嵌入式瀏覽器解析中語法分析和語義分析的過程相同,我們不作討論,這里重點討論詞法分析.

詞法分析是嵌入式瀏覽器的解析過程的第一步,也是非常重要的一步,其主要功能是從接收的網頁數據字符流中識別出有意義的符號字符串.詞法分析的效率、準確性與容錯性關系到整個瀏覽器設計的質量.我們用有限自動機來表示詞法分析的過程與步驟[2],詞法解析狀態轉換如圖2所示,其中,各個狀態符號的含義為:init:初始狀態;erase:剔除狀態,用于跳過注釋及文檔類型說明字符串;parse:解析狀態,進行相關HTML標記類型的判斷;startTag:開始標記分類狀態,用于區分開始標記、結束標記、空元素標記,并負責處理開始標記和空元素標記;endTag:結束標記狀態,處理結束標記的相關操作,如標記出棧等;text:解析內容狀態;over:終止狀態.

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

圖3 哈希映射處理示意

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

(1)初始化位圖結構bitmap_hash1,bitmap_hash2,bitmap_hash3,將位圖中的各位清0,將HTML4.0中所有HTML標記名字符串經哈希函數映射到3個位圖中相應的bit位上.

(2)當前字符游標Char指向接收到的HTML數據字符串首字符.

(3)如果當前自如Char為’<’字符,則轉向(4)處理,否則,讀取Char后續字符直至遇到’<’字符或’