1、CASL匯編器的設計與實現            摘  要 介紹了一種教學實驗系統CASL匯編器的設計過程，并使用了一種改進了的兩次掃描算法實現CASL匯編器。實驗表明，用該算法是實現的匯編器運行效率高，是一個功能完善、實用的教學實驗系統。      關鍵字  CASL匯編器；掃描算法；向前引用 1  引言        實用的匯編語言雖然功能非常

2、強大，但是結構也很復雜，不利于初學者學習。由國家軟件考試中心定義用于學習的CASL 匯編語言功能單一，程序格式規范，具有匯編語言的重要特征，是初學者學習匯編語言的最佳選擇。作為一種教學實驗系統，實現CASL匯編器具有很好的教學意義：首先，使用CASL匯編器可以方便學生學習CASL語言；其次，實現CASL匯編器可以幫助學生深入了解匯編器的工作原理1,2。2 匯編器功能簡介      匯編語言是一種面向機器、低級的計算機語言。匯編器的主要任務是將匯編語言的程序源程序翻譯為功能等價的特定機器的目標程序2。2.1 實用匯編器的功能  

3、;    實用的匯編語言翻譯器除了將匯編源程序翻譯為機器的語言外，還依據匯編語言不同的特征提供其他的功能。實用匯編器的一般工作包括：處理偽命令；定義和替換宏；進行錯誤檢查；生成機器代碼2。2.2 CASL匯編器的功能       CASL匯編器運行在普通的PC機上，產生COMET虛擬機的目標代碼（CASL匯編語言是建立在COMET機器上的虛擬語言），是一種交叉匯編的匯編器。因為CASL語言功能單一的特點，CASL匯編器的工作也相對較少4,5。CASL匯編器的主要工作有：(1)處理DC、DS偽命令定義的變量

4、。(2)將定義的標號替換為機器地址。(3)替換IN、OUT、EXIT三個宏。(4)對CASL源程序進行錯誤檢查。(5)生成COMET虛擬機的目標代碼。3 CASL匯編器設計3.1功能模塊3,5。圖1       詞法分析器將CASL源程序解釋成一個個獨立的記號，然后將記號的類型以及記號所對應的值返回給語法分析器。詞法分析器一般不產生錯誤信息。        語法分析器依據CASL語言的相關規則，對由詞法分析器返回的記號序列進行分析。在語法分析的過程中，一般會生成相應的符號表，同時調用代

5、碼生成器生成目標代碼。如果在語法分析過程中遇到任何錯誤語句，則調用錯誤處理模塊。       代碼生成器負責生成每個機器指令和最終目標代碼的存儲工作。在CASL源程序太長，或者指令參數使用錯誤時，代碼生成器將發生錯誤。       符號表是一個輔助功能模塊，主要用于處理標號信息。該模塊提供必要的符號操作：定義符號，查詢符號等。      錯誤處理模塊輸出相關的錯誤信息和發生錯誤的位置，然后退出程序。錯誤處理模塊不會分析產生錯誤原因，也不

6、會修復任何錯誤。3.2 數據結構     CASL匯編器采用了改進了的兩次掃描算法，使用的數據和普通兩次掃描算法相比要也有一些區別。CASL匯編器主要的數據結構包括：地址計數器LC，符號表，未知標號表1,2,5。      地址計數器LC用于計算每個標號對應的地址和生成目標代碼的存儲位置2,4。       CASL匯編器采用散列表來組織符號信息，同時使用鏈表來處理散列沖突的情況。       未知標號表記

7、錄在第一次掃描中遇到的向前引用標號的信息，然后在第二次掃描中用于修正目標代碼。CASL匯編器中未知標號結構定義如下：         static struct  int i, max;               struct  struct id *p;    &#

8、160;                 int off;  *stack;         unknow_id;      其中i為表中標號數目，max為表的容量，p指向符號表中符號的結構，off為標號對應目標代碼的存放位置。4 核心算法簡介4.1 傳統的兩遍匯編算法 

9、0;     傳統的匯編器采用兩次匯編來處理標號向前引用問題。在第一遍掃描先確定所有的標號的地址，并保存在符號表中。第二遍掃描依據第一遍掃描所生成的符號表來匯編每一條匯編語句2,4。由于在一遍掃描中并沒有完成足夠兩的工作，因此傳統的兩遍匯編無法達到最佳的掃描效果。4.2 改進的兩遍掃描算法      根據多遍掃描的原理可知，之前的遍歷應當盡量告訴稍后的遍歷做什么，而不是簡單地向它提供簡單的事實1。      CASL匯編器對算法改進的基本思路是，如果可能就

10、在第一遍掃描時完成所有的工作，從而達到簡化稍后邊的操作。CASL匯編器掃描算法的具體流程如圖2所示6。圖2      一遍掃描先生成絕大部分目標代碼，二遍掃描再生成剩下小部分的目標代碼，最后得到完整的目標代碼。4.3兩種算法的比較      為了量化兩種算法的時間，我們定性假設掃描每一條指令所花時間為常數t。匯編源程序的語句總數為n，有標號向前引用的語句數為x。      掃描整個源程序，傳統的兩遍掃描算法所花時間T1 = (n + n) * t

11、；改進后的算法所花時間T2 = (n + x) * t。兩種算法所花時間差T2 T1 = (n+n)*t - (n+x)*t = (n-x)*t。根據經驗可知，向前引用標號的數量一般遠小于匯編程序的語句總數，即x << n。因此，改進后的掃描算法比傳統的的兩遍掃描算法的效率要高出許多。5 CASL匯編器的代碼實現5.1 第一遍掃描的代碼實現       源程序未結束時執行一個大的循環，每次循環判斷并匯編每一個語句。lookahead是記錄當前記號的類型；match函數匹配并跳過當前記號；def_id記錄標號；emitter

12、生成目標代碼。在emitter生成目標代碼時，如果遇到未定義的標號，由get_id負責記錄該標號的相關信息（保存在unknow_id體結構中），以便在第二次掃描時使用。5.2 第二遍掃描的代碼實現       第二遍掃描的對象是第一遍掃描中記錄的未知標號包，在此對應為unknow_id結構。patch_id遍歷所有的未知標號，直到生成完整的目標代碼。如果標號的地址p->addr為-1（標號地址不可能為負數），則發生標號未定義錯誤。6 結語      實踐證明，實現CASL語言匯編器，可以更方便學習CASL匯編語言，同時也有助于了解匯編器的工作原理6。 參考文獻 1 Donald E.Knuth 著,蘇運霖 譯.計算機程序設計藝術. 第1卷 189-190，219-2202 Andrew S. Tanenbaum 著, 劉衛東 等 譯. 結構化計算機組成 第7章. 機械工業出版社, 20014 楊光, 冉峰. 單片機匯編器的設計與實現. 微計算機應用, 2005-3。5 程林輝, 張凱. 基于SAAM方法的CASL編譯程序軟件體系結構分析. 中南民族大學學報(自然科學版) ,第23卷, 第4期, 20