基于自動機的嵌入式HTML解析器的設(shè)計與實現(xiàn).pdf

1、隨著嵌入式系統(tǒng)的廣泛應(yīng)用和網(wǎng)絡(luò)技術(shù)的快速發(fā)展，嵌入式瀏覽器已成為嵌入式平臺上非常重要的的應(yīng)用軟件。嵌入式瀏覽器是一個網(wǎng)絡(luò)信息瀏覽器，支持HTTP或者WAP等其他傳輸協(xié)議，支持HTML，XML，XHTML，JavaScript，WML等語言等。它可以廣泛應(yīng)用于機頂盒，手機，PDA，車載電腦等非PC的嵌入式設(shè)備上，通過實現(xiàn)特定的網(wǎng)絡(luò)傳輸協(xié)議，根據(jù)系統(tǒng)設(shè)備的多樣性進行修改，實現(xiàn)對文字，圖像，聲音等的需求。
　　與桌面PC上的普通瀏覽器相

2、比，嵌入式瀏覽器具有多樣性的特點。不同的設(shè)備生產(chǎn)廠商在芯片選擇，系統(tǒng)功能定義，顯示設(shè)備，耗電限制有不同的要求，所以需要根據(jù)需求進行針對的開發(fā)。如由于顯示器類型的不同，嵌入式瀏覽器需要針對具體的設(shè)備進行顯示優(yōu)化（如字體識別，字庫，圖形，頁面的顯示結(jié)構(gòu)）。而且嵌入式瀏覽器只有有限的存儲空間和內(nèi)存空間可以利用，針對嵌入式系統(tǒng)的資源的有限性需要開發(fā)相應(yīng)的算法，以保證高的運行速度和運行效率。
　　本文設(shè)計的嵌入式瀏覽器是和深圳某公司合作的車

3、載嵌入式系統(tǒng)的網(wǎng)絡(luò)模塊的一部分。該瀏覽器基于 WinCE平臺用EVC進行開發(fā)，支持中文顯示，并且采用了分塊解析的算法。
　　本文開發(fā)設(shè)計了該嵌入式瀏覽器的網(wǎng)絡(luò)傳輸?shù)牡讓幽Ｐ?。用EVC的WinInet類實現(xiàn)基于 HTTP協(xié)議的網(wǎng)頁傳輸，支持網(wǎng)頁的轉(zhuǎn)向，用單獨一個線程進行網(wǎng)頁數(shù)據(jù)流的下載。針對嵌入式系統(tǒng)的資源的有限性需要開發(fā)了基于DFA的解析算法，用于瀏覽器解析模塊的詞法語法分析。首先我們抽象出HTML解析器的確定的有限自動機DFA（

4、Deterministic Finite Automaton)的數(shù)學(xué)模型,基于此模型設(shè)計了一個最小化DFA的算法。其中的最小化算法的核心是把一個確定型有限自動機的狀態(tài)集分成一些不相交的子集，使得任何不同兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的。也就是說，一臺最小化的確定型有限自動機，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個互相等價。形成存儲解析結(jié)果的DOM樹，以便于結(jié)構(gòu)化編輯(添加、刪除、移動等等)HTML文檔。