基于ＡＬＩ的ＡＤＡ語言靜態分析器的研究與實現

摘要：Ada語言源代碼經編譯器編譯后生成一個后綴名為Ali的文本文件。該Ali文件中包含了豐富的有關Ada源代碼的信息。該文剖析了由M1750 Ada編譯器編譯生成的Ali文件內包含的具體信息內容，并介紹了基于Ali文件的分析并結合Lex詞法分析工具來實現ADA語言靜態分析器的過程。

關鍵詞：Ali文件；Ada語言；Lex；靜態分析器

中圖分類號：TP311 文獻標識碼：A文章編號：1009-3044(2008)33-1406-05

Research and Implementation of Ada Language Static Analyzer Based on ALI

ZHU Ye， ZHU Hong-ming

(SAST-Tongji Spaceflight Embedded Computing Lab， School of Software Engineering， Tongji University， Shanghai 201804， China)

Abstract: Ada language source code can generate a file suffixed by Ali. The Ali file contains much information about Ada source code. This paper dissects the detail information of Ali file generated by M1750 Ada compiler， and then introduces the process of implementing the ADA language static analyzer based on analysis of Ali file and the Lex lexical analysis tool.

Key words: ali file; ada language; lex; static analyzer

1 引言

Ada是一種表現能力很強的通用程序設計語言，它是美國國防部為克服軟件開發危機，耗費巨資，歷時近20年研制成功的，是美國國防部指定的唯一一種可用于軍用系統開發的語言，我國軍方也將其做為軍內開發標準。

Ada是一種實時語言，除了包括一組完整的通常的語言特征之外，還提供了多任務、同步實時處理以及為低級硬件設備直接進行程序設計的功能。因此，在工業控制、通訊和軍事系統這些常用的實時領域得到廣泛應用。Ada語言應用的領域要求它的編譯系統必須非常高效而且準確可靠。M1750 Ada是由xgc公司受歐洲太空局委托開發的一個商用的遵循GNU公共授權的開源軟件，是一套基于GCC-1750開發的、能生成可靠運行的目標碼的面向MIL-STD-1750A體系結構的Ada編譯器。該編譯器目前在航空航天領域廣泛應用。

M1750 Ada對Ada源代碼進行編譯后會產生一個擴展名為ali的文件。該文件中包含了詳細的有關源代碼的信息，基于對其的分析，可以編寫出Ada語言的靜態分析器。本文將剖析Ali文件的結構和內容，分析其包含的有用信息，并介紹如何利用這些有用信息來編寫Ada語言的靜態分析器，最后能夠得到Ada的程序結構圖。

2 Ali文件的生成

圖1 Ada源代碼的編譯過程

Ali文件是Ada編譯器編譯Ada源代碼時生成的中間文件，Ali的全稱為Ada library information file.

Ada源代碼的編譯可由一條gnatmake命令來完成：

gnatmake filename.adb (也可不加擴展名.adb)

此命令的執行過程如圖1所示，實際是由三個獨立的命令組成：

1) gcc -c filename.adb

Ada源代碼經GCC編譯后生成一個擴展名為.o的目標文件，以及擴展名為.ali的文本文件。

2) gnatbind filename.ali

此綁定命令的結果是生成兩個臨時工作文件b~filename.adb和b~filename.abs。

3) gnatlink filename.ali

經鏈接器鏈接后，最終生成一個可執行程序。

因此，最后得到的文件有：Ada源代碼文件(.adb，.ads)， 目標文件(.o)， Ali文件以及可執行程序。

3 Ada的程序結構

一個Ada程序（或Ada系統）由一個或多個程序單元組成，每個程序單元可以分別編譯。程序單元的內部還可以嵌套多個程序單元。一個程序單元可以是以下四種類型：

1) 子程序（procedure或function）：表達了單獨的動作。

2) 程序包（package）：計算資源的集合。

3) 任務（task）：邏輯上與其他任務并發執行的動作。

4) 類屬（generic）：用于不同數據類型上的通用算法樣板化。

每個Ada程序都有一個主程序，它可以調用其他編譯單元的服務程序。每個程序單元分成兩大部分：

1) 規格說明（即聲明）：定義了與外部界面的接口部分。

2) 體：包含了程序單元的實現細節。

簡單的程序實例：

howdy.ads 的內容如下所示（程序包Howdy的規格說明）：

package Howdy is

procedure Hello;

procedure Goodbye;

end Howdy;

howdy.adb的內容如下所示（程序包Howdy的體）：

with Text_IO; use Text_IO;

package body Howdy is

procedure Hello is

begin

Put_Line(“Howdy from package”);

End Hello;

procedure Goodbye is

begin

Put_Line(“Goodbye from package”);

End Goodbye;

End Howdy;

howdymain.adb的內容如下所示（過程Howdymain）：

With Howdy;

procedure HowdyMain is

begin

Howdy.hello;

Howdy.goodbye;

End HodyMain;

4 Ali文件內包含的信息

上節簡單介紹了Ada的程序結構，并舉了一個簡單是程序實例。此例的源代碼經gnatmake howdymain命令編譯的過程如圖2所示：

圖2 Ada程序實例編譯過程

編譯后得到兩個Ali文件howdymain.ali和howdy.ali。

howdymain.ali文件的內容如圖3所示：

圖3 howdymain.ali的內容

4.1 Ali文件內包含的信息

每個ALI文件包括以下信息：

1) 版本信息（指明編譯本單元的GNAT版本）；

2) 主程序信息（包括優先級、時間片設置和編譯期間使用的寬字符解碼）；

3) gcc編譯本單元使用的選項列表；

4) 本單元的屬性，包括pragmas設置、編譯是否成功、使用的異常模式等；

5) 應用在本單元的相關約束檢查列表；

6) 分類信息；

7) with的單元；

8) 使用在本單元的鏈接器的選項的編譯指示；

9) 本單元的版本屬性；

10) 依賴信息，它是一個文件列表，包括時間戳和校驗信息；

11) 交互引用信息。

在眾多信息中，最為復雜且對我們最為重要的信息就是交互引用信息，也就是圖3中的如下部分：

X 1 howdy.ads

1K9*Howdy 4e10 2|1r6 4r5 5r5

2U15*Hello 2|4r11

3U15*Goodbye 2|5r11

X 2 howdymain.adb

2U11*HowdyMain 6l5 6t14

這部分交互引用信息就是編寫Ada靜態分析器的關鍵有用的信息。

4.2 Ali文件信息內容說明

Header：

Xdependency-numberfilename

根據依賴文件列表為每一個源文件進行編號。

Entity：

line type col level entity renameref typeref refs

1) line：表示行號；

2) col：表示列號；

3) type：表示實體所屬的類型，由單個字母表示，區分大小寫，具體含義如表1所列；

4) level：表示可見性，如果為*號則表明該實體對外部是可見的（即外部可以引用它），如果為空格則反之，即對外部不可見；

5) entity：表示實體名字；

6) renameref：表示重命名引用，如果實體在別處被重命名為簡單的標識符或者擴展的名字，則renameref有如下的形式：

=line:col

這里，line:col表示實體的標識符(即名字)在其被重命名處出現的行號和列號。此處不需要文件號，因為重命名只能在同一個文件中進行。如果被重命名為一個復雜的表達式，則renameref這一項是被省略的。

7) typeref：表示實體被引用的方式，具體含義如表2所列；

8) refs：表示該實體的詳細說明，其格式為：

file ’|’ line type col [...]

file為文件的數字代號，如果所在文件為交互引用節開頭(即header)的文件則“file|” 省略；

line，col表示行號和列號；

type表示類型，具體含義如表3所列；

4.3 舉例說明

例如howdymain.ali文件中有如下兩列交互信息：

X 1 howdy.ads

1K9*Howdy 4e10 2|1r6 4r5 5r5

其含義是，howdy.ads文件序號為1，在該文件的第1行第9列處是一個類型為package的實體名字“Howdy”的開始，第4行第10列處是包Howdy聲明的結束。并且在文件序號為2的文件(即howdymain.adb)中，該包被三次引用，引用的地方分別是第1行第6列、第4行第5列以及第5行第5列。

5Ada語言靜態分析器的實現

剖析了Ali文件所包含的信息之后，發現其記錄的交互引用信息對于Ada代碼的靜態分析器的編寫十分有用且方便。于是想到利用這些有用的信息對Ada源代碼進行靜態分析。

5.1 Ali文件內信息的讀取

Ali文件中的信息不能直接利用，必須將其讀取出來，保存到我們可以利用的數據結構中，然后進行后續的處理。

Ali文件內的信息以行為單位，不同的信息有不同的格式，其含義已在前面的章節中介紹過。根據其信息的不同內容，我們設計了如下的結構體鏈表來存儲這些信息：

struct ALI_UNIT{

unsigned int line;

char type;

unsigned int col;

char level;

char *entity;

struct ALI_REF *parent;

struct ALI_REF *current;

struct ALI_REF *external;

struct ALI_UNIT *next;

};

存儲每個實體單元的信息，即讀取交互引用信息行line type col level entity renameref這部分內容，記錄下實體單元的行號列號，類型，可見性以及實體單元的名字，renameref部分如果是繼承類型，即LR=<>，則記下父類型的信息。

struct ALI_REF{

unsigned int number;

unsigned int line;

char ref_type;

unsigned int col;

struct ALI_REF *next;

};

存儲每個實體單元被引用的信息，即讀取交互引用信息行refs(file ’|’ line type col [...])部分的內容，記錄下實體單元被引用所在的文件，被引用處的行號和列號，被引用的類型。

struct ALI_FILE{

char type;

unsigned int number;

char *filename;

struct ALI_UNIT *units;

struct ALI_FILE *next;

};

存儲所有有關的文件的信息，即當讀到Ali文件中X、U、W開頭的信息行時，記錄下文件的類型、序號、名字，以及該文件中的所有實體單元。此處，文件類型是指，是主文件，引用文件，還是系統文件。

struct ALI_DEPENDENT{

unsigned int adb_flag;

unsigned int number;

char *filename;

struct ALI_DEPENDENT *next;

};

存儲整個Ada工程編譯時依賴的文件的信息，即讀到以D開頭的信息行時，記錄下文件是否為adb文件，記錄文件的序號，名字。

struct ALI_COMPLIER_UNIT{

struct ALI_FILE *self_list;

struct ALI_FILE *ref_list;

struct ALI_FILE *sys_list;

struct ALI_DEPENDENT *dep_list;

char **self_name_list;

unsigned int name_list_len;

struct ALI_COMPLIER_UNIT *next;

};

存儲主文件列表，引用文件列表，系統文件列表，依賴文件列表，主文件名字列表，主文件名字列表的長度。

讀完Ali文件之后，這些結構體所保存的信息是進行后續分析的基礎。因此，這些結構體的具體結構可根據對Ada語言靜態分析的具體要求和所要達到的程序來進行設計，便于后續分析和處理。

5.2 Lex詞法分析

LEX (lexical compiler)是在Unix下設計出來的一個優秀的計算機詞法分析工具。主要功能是生成一個詞法分析器（scanner）的C源碼。需要先編寫描述詞法分析器的文件，經過Lex便以后，生成一個lex，yy.c的文件，該代碼經過編譯可以被程序員作為庫文件調用。

我們用Lex對所有Ada文件除了系統文件進行詞法分析，得到單個的詞法元素。

最后輸出的結果是對于每一個文件都有：

char ** result ：指向存儲詞法元素的空間的指針。

unsigned int *line_eindex ：指向對應的詞法元素的行號信息。

unsigned int *col_eindex ：指向對應的詞法元素的列號信息。

我們可將得到的結果存儲如下的結構體中：

struct FILE_ELEMENT{

charfilename[FILE_NAME_LEN];

char** element;

unsigned int * col_eindex;

unsigned int *line_eindex;

};

當處理實體的從屬關系時，就需要用到這個結構體鏈表。因為實體會有開始與結束兩個行列號位置記錄，遍歷此結構體鏈表，當結構體內的行列號與實體開始處行列號匹配時，通過遍歷計數器就可得到實體開始時其名字在詞法元素表Result中的位置index1，同法可得結束處對應的index2，有了兩個實體的這兩個index值，就可知道，一個實體是否是嵌套在另一個實體內部，這對畫出程序結構圖是很關鍵的。

5.3 綜合處理

為了得到清晰的程序結構圖，還需對前面讀Ali文件得到的結構體內存儲的信息進行再分析，再處理。因此，根據實體的不同類型，我們設計出如下的目標結構體：

struct UNIT：存儲array object (except string)、array type (except string)、Boolean type、class-wide object、class-wide type、non-Boolean enumeration object、non-Boolean enumeration type、floating-point object、floating-point type、signed integer object、signed integer type、modular integer object、modular integer type、enumeration literal、named number、ordinary fixed-point object、ordinary fixed-point type、access object、access type、record object、record type、string object、string type、exception等類型的數據信息。

struct CALL：存儲被調用的實體的有關信息，包括被調用處的文件，行列號等。

struct BODY：存儲generic package、package、task object、task type、generic procedure、procedure、generic function or operator、function or operator、protected object、protected type、entry or entry family等類型的數據信息，包括名字，類型，聲明的位置，體的位置，在體中包含的UNIT（即struct UNIT結構體中保存的UNIT的子集），體中嵌套的其它BODY（即子BODY），體中調用的實體。

最后，整合到一個結構體，方面使用。

struct RES{

struct BODY *root;

struct BODY *bodys;

struct UNIT *units;

struct CALL *calls;

struct FILE_RES file[FILE_NUM];

};

有了這個總結性的結構體，我們可以方便的畫出程序結構圖，root記錄了最外層的實體BODY，有了這個根結點，再遍歷bodys，就可以畫出一個數狀結構的圖。根據calls還可以得到調用關系圖。至此，靜態分析就結束了。

6 總結

計算機語言的靜態分析是很復雜且耗費時間的，找到有用的工具作為分析的基礎是很重要的。Ali文件就是Ada程序靜態分析的有用工具。本文首先介紹了Ali文件的生成過程，接著剖析了Ali文件的內容，分析其包含的信息對Ada語言靜態分析的有用性，進而介紹了利用Ali文件所帶的信息來編寫Ada程序靜態分析器的主要思路和過程，希望能給從事Ada語言編碼與研究的工作者一定的參考和啟發。

參考文獻：

[1] Ada Core Technologies，Inc.lib-xref.ads[EB/OL].2001.

[2] Ada Core Technologies，Inc.lib-xref.adb[EB/OL].2002.

[3] Ada Core Technologies.GNAT User's Guide for Unix [M/OL].2002.

[4] Free Software Foundation.GNAT Reference Manual[M/OL].2002.

[5] XGC Software.XGC User's Guide[M/CD].2001.

[6] XGC Software.M1750 Ada Technical Summary[M/CD].2003.

[7] 田淑清，譚浩強.Ada導論[M].北京:清華大學出版社，1988.

[8] 陳火旺，劉春林.程序設計語言編譯原理[M].3版.北京:國防工業出版社，2004.

[9] 楊作梅，張旭東.lex與yacc[M].2版.北京:機械工業出版社，2003.