论文部分内容阅读
摘要：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文件的生成
图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.
关键词：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文件的生成
图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.