萬(wàn)東

（廣東交通職業(yè)技術(shù)學(xué)院 廣東 廣州 510650）

嵌入式瀏覽器是嵌入式設(shè)備終端用戶瀏覽網(wǎng)頁(yè)信息內(nèi)容的應(yīng)用軟件，其重要性日益提高，已經(jīng)不可或缺[1]。著名的開(kāi)源瀏覽器Firefox在PC上具有強(qiáng)大的功能，但是還沒(méi)有成功的嵌入式應(yīng)用。Minimo瀏覽器的跨平臺(tái)性以及高效管理瀏覽器的緩存資源，但是不支持中文。Linux的版本只支持Window mobile，IE也只支持Window mobile。嵌入式瀏覽器是嵌入式設(shè)備終端用戶瀏覽網(wǎng)頁(yè)信息內(nèi)容的應(yīng)用軟件，其重要性日益提高，已經(jīng)不可或缺。目前攜帶方便的智能型終端大量出現(xiàn)，使嵌入式瀏覽器成為社會(huì)研究的熱點(diǎn)之一。本文提出了一種跨平臺(tái)ECMAScript解釋器的研究與設(shè)計(jì)方案。剖析了幾大核心模塊的設(shè)計(jì)和實(shí)現(xiàn)進(jìn)行了。

1 ECMAScrip介紹及解釋器總體設(shè)計(jì)

ECMAScript是一種由歐洲計(jì)算機(jī)制造商協(xié)會(huì)通過(guò)ECMA-262標(biāo)準(zhǔn)化的腳本程序設(shè)計(jì)語(yǔ)言，是宿主環(huán)境中腳本語(yǔ)言的國(guó)際Web標(biāo)準(zhǔn)。ECMAScript實(shí)際上只是定義了一系列的語(yǔ)法和語(yǔ)義的規(guī)則，其具體的腳本語(yǔ)言主要包括JavaScript，JScrip，ActionScript等。 ECMAScript主要使用于網(wǎng)絡(luò)環(huán)境中，嵌入HTML文檔，提供Web與用戶交互功能，展示W(wǎng)eb內(nèi)容的多樣性。ECMAScript解釋器與其他的語(yǔ)言編譯功能類似，都是從源代碼輸入，經(jīng)過(guò)一系列的解讀與加工，最終產(chǎn)生能在相應(yīng)平臺(tái)運(yùn)行的目標(biāo)代碼。其工作原理圖1所示。

圖1 ECMAScript工作原理圖Fig.1 ECMAScript operating principle

圖1 中，ECMAScript解釋器按其模塊可以劃分為詞法分析模塊、符號(hào)表模塊、語(yǔ)法分析模塊、語(yǔ)義分析模塊以及代碼生成模塊。ECMAScript解釋器讀入源代碼后，依次調(diào)用詞法分析，語(yǔ)法分析，生成中間代碼嵌入代碼段中，以供虛擬機(jī)解釋執(zhí)行。詞法分析和語(yǔ)法分析都是ECMAScript中的文法，而中間代碼則使用自定義的字節(jié)碼，以便于不同平臺(tái)的虛擬機(jī)都能解釋執(zhí)行，達(dá)到跨平臺(tái)的目的[2]。

傳統(tǒng)編譯器的可以多遍實(shí)現(xiàn)，即每遍輸入一個(gè)文件、生成一個(gè)結(jié)果文件，也可以一遍實(shí)現(xiàn)，即將多個(gè)階段組合起來(lái)[3]。多遍讀入，可以節(jié)省內(nèi)存開(kāi)銷，但是多次的輸入輸出也會(huì)影響編譯的效率；一遍實(shí)現(xiàn)效率高，但是需要將階段性的信息保留于內(nèi)存中，對(duì)系統(tǒng)內(nèi)存要求高。目前隨著智能設(shè)備硬件的升級(jí)，內(nèi)存不再是制約智能設(shè)備使用的主要方向，所以在本文的ECMAScript編譯器設(shè)計(jì)中采用一遍實(shí)現(xiàn)的技術(shù)。

2 ECMAScript解釋器的具體設(shè)計(jì)

2.1 符號(hào)表設(shè)計(jì)

符號(hào)表是ECMAScript解釋器必不可少的部分，用于存放標(biāo)識(shí)符各種信息，以便于程序?qū)λ觅Y源的快速定位與識(shí)別。符號(hào)表中必須提供到處理該標(biāo)識(shí)聲明時(shí)所收集信息的訪問(wèn)[4]，具體包括：類型，作用域，存儲(chǔ)地址以及函數(shù)標(biāo)識(shí)符的參數(shù)個(gè)數(shù)，參數(shù)類型以及返回值等信息。符號(hào)表設(shè)計(jì)的關(guān)鍵，是設(shè)計(jì)合適的查找算法。

符號(hào)表的實(shí)現(xiàn)方法有很多種，包括無(wú)序表，有序表，hash表，二叉樹(shù)等方法。在無(wú)序表的設(shè)計(jì)中，符號(hào)表只是一個(gè)簡(jiǎn)單的數(shù)組或者鏈表，所有的標(biāo)識(shí)符都是按照先后順序依次放入數(shù)組或鏈表中，平均時(shí)間復(fù)雜度為O（n/2）。有序表則是將標(biāo)識(shí)符保持有序，以便于使用二分查找是能達(dá)到 O（log（n））的效率，但是需要對(duì)有序表進(jìn)行頻繁的插入和刪除操作，而且在數(shù)據(jù)較大的情況下，插入和刪除新的標(biāo)識(shí)符，也需要O（n）的時(shí)間。二叉樹(shù)符號(hào)表的設(shè)計(jì)中，使用近似平衡二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)，能使插入和搜索標(biāo)識(shí)符的時(shí)間為 O（log（n））。Hash表則是更多產(chǎn)品級(jí)編譯器所青睞的實(shí)現(xiàn)方式[5]，通過(guò)構(gòu)造合適大小的hash桶以及良好的Hash函數(shù)，最理想情況下能達(dá)到O（1）的效率，但是實(shí)際上很難達(dá)到這種效率。

使用Hash表的設(shè)計(jì)方式，無(wú)可避免需要解決Hash沖突問(wèn)題。在本文的設(shè)計(jì)中，使用Hash和二叉樹(shù)結(jié)合的方式來(lái)設(shè)計(jì)符號(hào)表。其中二叉樹(shù)使用紅黑樹(shù)來(lái)實(shí)現(xiàn)，Hash表中用于保存紅黑樹(shù)的樹(shù)根，紅黑樹(shù)的節(jié)點(diǎn)，用來(lái)保存具體的標(biāo)識(shí)符信息。查找標(biāo)識(shí)符信息時(shí)，首先將該標(biāo)識(shí)符進(jìn)行Hash，找到存儲(chǔ)該標(biāo)識(shí)符的紅黑樹(shù)的樹(shù)根，再在紅黑樹(shù)中查找相應(yīng)的標(biāo)識(shí)符，這樣能實(shí)現(xiàn)的復(fù)雜度為 O（1）+O（log（n/Size））（Size 為Hash桶的大?。?。

在符號(hào)表的設(shè)計(jì)中，另外需要考慮的一個(gè)因素就是標(biāo)識(shí)符的作用域。不同的作用域中可能會(huì)出現(xiàn)相同的標(biāo)識(shí)符[4]，因此一種可行的解決方案是，使用多級(jí)分層的多符號(hào)表方式，為每個(gè)函數(shù)動(dòng)態(tài)分配單獨(dú)的符號(hào)表，查找一個(gè)標(biāo)識(shí)符時(shí)，首先在同級(jí)的表中查找，查找失敗后再往上逐層查找，直到最頂層。

2.2 詞法分析器設(shè)計(jì)

詞法分析器的功能輸入源程序，按照構(gòu)詞規(guī)則分解成一系列單詞符號(hào)。單詞是語(yǔ)言中具有獨(dú)立意義的最小單位，包括關(guān)鍵字、標(biāo)識(shí)符、運(yùn)算符、界符和常量等。就多數(shù)的程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，詞法的結(jié)構(gòu)設(shè)計(jì)比較簡(jiǎn)單，但是真正實(shí)現(xiàn)詞法的自動(dòng)識(shí)別卻比較困難，而且需要依賴于詞法的嚴(yán)格定義[6]。ECMAScript語(yǔ)言中，對(duì)詞法記號(hào)有著嚴(yán)格的定義。在ECMAScript的詞法分析器中，其主要功能就是過(guò)濾掉源程序中與程序語(yǔ)言不相關(guān)的字符后，將輸入字符轉(zhuǎn)化成單詞序列。目前現(xiàn)有的詞法分析器Lex是一個(gè)比較完善的工具，它是基于正則表達(dá)式的描述詞法分析器的工具，可以根據(jù)用戶設(shè)定的正則表達(dá)式去分析，切割出單詞，但是其支持的宿主語(yǔ)言只是C。分析Lex的具體實(shí)現(xiàn)，也是使用確定的有限狀態(tài)自動(dòng)機(jī)（DFA）實(shí)現(xiàn)詞法的分析。

DFA，即于一個(gè)給定的屬于該自動(dòng)機(jī)的狀態(tài)和一個(gè)屬于該自動(dòng)機(jī)字母表集合的字符，它都能根據(jù)事先給定的轉(zhuǎn)移函數(shù)轉(zhuǎn)移到下一個(gè)狀態(tài)（這個(gè)狀態(tài)可以是先前那個(gè)狀態(tài)），它可以根據(jù)輸入和約束規(guī)則，改變自身的狀態(tài)[4]。DFA主要由輸入集合、開(kāi)始狀態(tài)集合、狀態(tài)轉(zhuǎn)移集合、狀態(tài)集合和結(jié)束狀態(tài)集合組成。

在DFA中，需要構(gòu)造狀態(tài)轉(zhuǎn)換表，DFA按照轉(zhuǎn)換表進(jìn)行狀態(tài)轉(zhuǎn)換。其實(shí)現(xiàn)的偽代碼表示為：

{

當(dāng)前狀態(tài)為0；

掃描下一個(gè)字符char；

While（ture）

{

當(dāng)前狀態(tài)=狀態(tài)（char）；

If當(dāng)前狀態(tài)=0{return識(shí)別一個(gè)單詞成功；break}

If當(dāng)前狀態(tài)=Error{return錯(cuò)誤單詞；break}

Else

{

變?yōu)楫?dāng)前狀態(tài)；

緩存當(dāng)前字符；

掃描下一個(gè)字符char；

}

}

}

2.3 語(yǔ)法分析器設(shè)計(jì)

語(yǔ)法分析器的任務(wù)主要是檢查詞法分析得到的token流是否符合ECMA的語(yǔ)法，語(yǔ)法分析器可以采用Yacc語(yǔ)法分析工具。Yacc文件的分段實(shí)際上與Lex文件十分相似：

說(shuō)明部分

%%

規(guī)則部分

%%

輔助程序部分

＜說(shuō)明部分＞包括記號(hào)的定義、類型信息以及Lex中聲明的yylval共用體。Yacc使用同一共同體在兩個(gè)不同的“語(yǔ)言概念”之間傳遞信息，例如表達(dá)式、語(yǔ)句、程序。根據(jù)這些定義，Yacc產(chǎn)生lexsymb.h解析文件。Yacc有一個(gè)需要注意的地方，就是使用的語(yǔ)言必須使用LR（1）文法描述，LR（1）文法的基本思想是語(yǔ)法分析器能在查看當(dāng)前語(yǔ)法記號(hào)或者最多預(yù)讀一個(gè)符號(hào)就能識(shí)別出使用什么樣的語(yǔ)法規(guī)則，而下面的語(yǔ)法規(guī)則會(huì)產(chǎn)生一個(gè)移進(jìn)/規(guī)約沖突（shift/reduce conflict）:

A:

|B C

|B CD

|DE F

沖突產(chǎn)生在當(dāng)語(yǔ)法分析器讀取到了’C’時(shí)，而且預(yù)讀的是’D’時(shí)，它不能決定是否歸類為A2還是A1后面跟著一個(gè)A3，Yacc把這種二義性稱為移進(jìn)/規(guī)約沖突?？梢允褂孟铝邢鄳?yīng)規(guī)則解決這類沖突：

statement

:END_STMT{puts（“Empty statement”）；}

|expression END_STMT{puts（“Expression statement”）；}

|PRINT expression END_STMT{puts（“Print statement”）；}

|INPUT identifier END_STMT{puts（“Input statement”）；}

|if_statement{puts（“If statement”）；}

|compound_statement{puts（“Compound statement”）；}

|error END_STMT{puts（“Error statement”）；}

這里定義了各種語(yǔ)句類型，后面的代碼告訴語(yǔ)法分析器當(dāng)發(fā)現(xiàn)了每個(gè)產(chǎn)生式時(shí)應(yīng)該做什么，”Error statement”告訴Yacc當(dāng)分析一條語(yǔ)句時(shí)如果遇到一個(gè)語(yǔ)法錯(cuò)誤，應(yīng)查找下一個(gè)END_STMT記號(hào)，然后繼續(xù)分析后面的東西，并把語(yǔ)法錯(cuò)誤報(bào)告到main.cpp中定義的yyerror（）函數(shù)中。

構(gòu)造出符合LR （1）文法的ECMAScript腳本語(yǔ)言的ES文法后，就可根據(jù)此文法建立語(yǔ)法預(yù)測(cè)分析表，預(yù)測(cè)分析表中得到的產(chǎn)生式的右部逆序進(jìn)入語(yǔ)法棧，當(dāng)語(yǔ)法棧的所有條目都出棧時(shí)，說(shuō)明語(yǔ)法沒(méi)有錯(cuò)誤。

3 解釋器功能驗(yàn)證

ECMAScript解釋器是一個(gè)相對(duì)復(fù)雜的系統(tǒng)，通過(guò)前面核心模塊的設(shè)計(jì)和實(shí)現(xiàn)，解釋器的主要功能已經(jīng)基本實(shí)現(xiàn)。為了調(diào)試的方便以及印證ECMAScript解釋器功能的實(shí)現(xiàn)，本文借助一個(gè)調(diào)試助手工具，調(diào)用ECMAScript解釋器所提供的詞法分析器接口、語(yǔ)法分析器接口和語(yǔ)義例程，界面如圖2所示。

圖2 詞法分析及中間代碼執(zhí)行結(jié)果顯示Fig.2 Lexical analysis and intermediate code execution results show

圖2 中左邊是源碼，中間是語(yǔ)法分析后產(chǎn)生的中間代碼，右邊是詞法樹(shù)，下邊是執(zhí)行結(jié)果。中間窗口4列分別表示：偏移量 操作符 第一參數(shù) 第二參數(shù)。從前面的分析可知，通過(guò)詞法分析可把輸入的源程序生成相應(yīng)的詞法樹(shù)，通過(guò)對(duì)圖中左邊部分所示的一個(gè)簡(jiǎn)單的腳本語(yǔ)言解釋過(guò)程為例，其右邊為源程序詞法分析過(guò)程中所得到的詞法樹(shù)。

圖2中中間部分顯示了源程序生成的中間代碼，通過(guò)lmovr指令分別把兩個(gè)源地址的值賦予vlocal_0，vlocal_1兩個(gè)本地變量寄存器，由jz指令根據(jù)條件進(jìn)行跳轉(zhuǎn)，如果i為0，跳出循環(huán)，輸出j的值，如果i＞0，則執(zhí)行循環(huán)體。中間代碼的執(zhí)行是由虛擬機(jī)完成的，通過(guò)輸出窗口，可以看到腳本語(yǔ)言經(jīng)過(guò)ECMAScrip解釋器能夠得到正確執(zhí)行。

4 結(jié) 論

人熟悉的Netscape Navigator瀏覽器和Intemet ExpIore瀏覽器和都能很好的支持腳本語(yǔ)言，嵌入式平臺(tái)瀏覽器支持Web網(wǎng)頁(yè)瀏覽的技術(shù)難點(diǎn)是如何解決對(duì)腳本語(yǔ)言的解釋，本文正提出了一種跨平臺(tái)ECMAScript解釋器的研究與設(shè)計(jì)方案，并對(duì)其中的幾大核心模塊的設(shè)計(jì)和實(shí)現(xiàn)進(jìn)行了剖析，最后對(duì)ECMAScript解釋器對(duì)腳本語(yǔ)言的解釋過(guò)程進(jìn)行了演示，實(shí)現(xiàn)了不同平臺(tái)智能終端上瀏覽器對(duì)ECMAScript的支持。

[1]左瑞金.嵌入式瀏覽器的資源管理與跨平臺(tái)的研究與優(yōu)化[D].電子科技大學(xué)，2012.

[2]Alfred v.Aho，Ravi Sethi，Jeffrey D.Ullman.Compilers Principles Techniques and Tools[M].Addision－Wesley Publishing Company，1996.

[3]徐穎麗，劉志.Agent解釋器的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2005（25）:91－95.XU Ying-li，LIU Zhi.Design and implementation of agent interpreter[J].Computer Engineering and Applications，2005（25）:91－95.

[4]Charles N.Fischer，Richard j.LeBlacn.編譯器構(gòu)造C語(yǔ)言描述[M].鄭啟龍，姚震，譯.北京：機(jī)械工業(yè)出版社，2005.

[5]吳作順，竇文華.幾個(gè)常用解釋器的性能分析[J].計(jì)算機(jī)工程與科學(xué)，2002，24（4）:83－85.WU Zuo-shun，DOU Wen-hua.Several commonly used to explain the performance analysis[J].Computer Engineering and Science，2002，24（4）:83－85.

[6]溫敬和.LR分析法在詞法分析器自動(dòng)構(gòu)造中的應(yīng)用[J].計(jì)算機(jī)工程，2001，27（7）:188－190.WEN Jing-he.LR analysis in lexical analyzer automatically configured application[J].Computer Engineering，2001，27（7）:188－190.