跨平臺解釋器的研究與設計

萬東

（廣東交通職業技術學院 廣東 廣州 510650）

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

1 ECMAScrip介紹及解釋器總體設計

ECMAScript是一種由歐洲計算機制造商協會通過ECMA-262標準化的腳本程序設計語言，是宿主環境中腳本語言的國際Web標準。ECMAScript實際上只是定義了一系列的語法和語義的規則，其具體的腳本語言主要包括JavaScript，JScrip，ActionScript等。 ECMAScript主要使用于網絡環境中，嵌入HTML文檔，提供Web與用戶交互功能，展示Web內容的多樣性。ECMAScript解釋器與其他的語言編譯功能類似，都是從源代碼輸入，經過一系列的解讀與加工，最終產生能在相應平臺運行的目標代碼。其工作原理圖1所示。

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

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

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

2 ECMAScript解釋器的具體設計

2.1 符號表設計

符號表是ECMAScript解釋器必不可少的部分，用于存放標識符各種信息，以便于程序對所用資源的快速定位與識別。符號表中必須提供到處理該標識聲明時所收集信息的訪問[4]，具體包括：類型，作用域，存儲地址以及函數標識符的參數個數，參數類型以及返回值等信息。符號表設計的關鍵，是設計合適的查找算法。

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

使用Hash表的設計方式，無可避免需要解決Hash沖突問題。在本文的設計中，使用Hash和二叉樹結合的方式來設計符號表。其中二叉樹使用紅黑樹來實現，Hash表中用于保存紅黑樹的樹根，紅黑樹的節點，用來保存具體的標識符信息。查找標識符信息時，首先將該標識符進行Hash，找到存儲該標識符的紅黑樹的樹根，再在紅黑樹中查找相應的標識符，這樣能實現的復雜度為 O（1）+O（log（n/Size））（Size 為Hash桶的大小）。

在符號表的設計中，另外需要考慮的一個因素就是標識符的作用域。不同的作用域中可能會出現相同的標識符[4]，因此一種可行的解決方案是，使用多級分層的多符號表方式，為每個函數動態分配單獨的符號表，查找一個標識符時，首先在同級的表中查找，查找失敗后再往上逐層查找，直到最頂層。

2.2 詞法分析器設計

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

DFA，即于一個給定的屬于該自動機的狀態和一個屬于該自動機字母表集合的字符，它都能根據事先給定的轉移函數轉移到下一個狀態（這個狀態可以是先前那個狀態），它可以根據輸入和約束規則，改變自身的狀態[4]。DFA主要由輸入集合、開始狀態集合、狀態轉移集合、狀態集合和結束狀態集合組成。

在DFA中，需要構造狀態轉換表，DFA按照轉換表進行狀態轉換。其實現的偽代碼表示為：

{

當前狀態為0；

掃描下一個字符char；

While（ture）

{

當前狀態=狀態（char）；

If當前狀態=0{return識別一個單詞成功；break}

If當前狀態=Error{return錯誤單詞；break}

Else

{

變為當前狀態；

緩存當前字符；

掃描下一個字符char；

}

}

}

2.3 語法分析器設計

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

說明部分

%%

規則部分

%%

輔助程序部分

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

A:

|B C

|B CD

|DE F

沖突產生在當語法分析器讀取到了’C’時，而且預讀的是’D’時，它不能決定是否歸類為A2還是A1后面跟著一個A3，Yacc把這種二義性稱為移進/規約沖突。可以使用下列相應規則解決這類沖突：

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”）；}

這里定義了各種語句類型，后面的代碼告訴語法分析器當發現了每個產生式時應該做什么，”Error statement”告訴Yacc當分析一條語句時如果遇到一個語法錯誤，應查找下一個END_STMT記號，然后繼續分析后面的東西，并把語法錯誤報告到main.cpp中定義的yyerror（）函數中。

構造出符合LR （1）文法的ECMAScript腳本語言的ES文法后，就可根據此文法建立語法預測分析表，預測分析表中得到的產生式的右部逆序進入語法棧，當語法棧的所有條目都出棧時，說明語法沒有錯誤。

3 解釋器功能驗證

ECMAScript解釋器是一個相對復雜的系統，通過前面核心模塊的設計和實現，解釋器的主要功能已經基本實現。為了調試的方便以及印證ECMAScript解釋器功能的實現，本文借助一個調試助手工具，調用ECMAScript解釋器所提供的詞法分析器接口、語法分析器接口和語義例程，界面如圖2所示。

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

圖2 中左邊是源碼，中間是語法分析后產生的中間代碼，右邊是詞法樹，下邊是執行結果。中間窗口4列分別表示：偏移量 操作符 第一參數 第二參數。從前面的分析可知，通過詞法分析可把輸入的源程序生成相應的詞法樹，通過對圖中左邊部分所示的一個簡單的腳本語言解釋過程為例，其右邊為源程序詞法分析過程中所得到的詞法樹。

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

4 結 論

人熟悉的Netscape Navigator瀏覽器和Intemet ExpIore瀏覽器和都能很好的支持腳本語言，嵌入式平臺瀏覽器支持Web網頁瀏覽的技術難點是如何解決對腳本語言的解釋，本文正提出了一種跨平臺ECMAScript解釋器的研究與設計方案，并對其中的幾大核心模塊的設計和實現進行了剖析，最后對ECMAScript解釋器對腳本語言的解釋過程進行了演示，實現了不同平臺智能終端上瀏覽器對ECMAScript的支持。

[1]左瑞金.嵌入式瀏覽器的資源管理與跨平臺的研究與優化[D].電子科技大學，2012.

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

[3]徐穎麗，劉志.Agent解釋器的設計與實現[J].計算機工程與應用，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.編譯器構造C語言描述[M].鄭啟龍，姚震，譯.北京：機械工業出版社，2005.

[5]吳作順，竇文華.幾個常用解釋器的性能分析[J].計算機工程與科學，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分析法在詞法分析器自動構造中的應用[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.