目 录
第一章 背景和任务叙述…………………………….…………4
1 问题背景简介……………………………………………….4
2 设计模式简介……………………………………………….4
3关键信息确定………………………………………………..4
4选择中间语言………………………………………………..5
5完整系统框图………………………………………………..5
第二章 软件平台和工具简介……………………..……………8
1 Visual Studio.net简介…………………………………….…8
2 Visio简介.……………………………………………….…..8
第三章 分系统设计……………………………………..………9
第四章 词法分析实现…………………………………….……10
第五章 信息提取和管理的实现………………………….……14
第六章 小结…………………………………………….……....29
参考文献………………………………………………….……..30
附录A AOL扩展BNF语法…………………………………31
附录B C++ 扩展BNF语法…………………………………34
第一章 任务背景和叙述
1、 问题背景
面向对象的设计模式已经被认识、发掘和应用,通过采用面向对象的设计模式,软件将拥有更好的封装性、模块化、可维护性。如果能对软件中所采用的设计模式进行有效的识别,将有助于我们对软件的理解和评价。另外,如何发掘程序中新的设计模式,并加以抽象,以便于重用,也是一个值得探讨的问题。
以前,对面向对象的设计模式的认识和使用,往往是由有经验的程序员实施的。随着设计模式的成熟和增多,有必要对设计模式的提取、管理和重用实现自动化。本文所作的工作就是关于以上问题的基础性工作:如何提取和表征面向对象的设计模式。
2、面向对象的设计模式
模式可以应用于开发过程的每个阶段,如需求模式、分析模式、体系模式、设计模式等。他们分别表示在不同抽象层面上解决某一问题的方法。本文集中于设计层面的模式处理。设计模式代表一种众所周知并被经常重用的设计微体系,而不包括其它或高或低、或大或小的其他模式。
面向对象的设计模式的描述,应该通过描述模式的参加者,即类和对象,及其关系,体现出模式的静态结构,也应体现参加者各自的角色和他们之间的消息传递,比如参与者的行为。描述应力图抓住设计模式的本质,以便于学习并在类似的环境中重用模式。模式在交流思想和经验时应该成为一种公共语言。
为解决以上问题,需要将纷繁复杂的程序代码加以处理,抽取出对设计模式的识别有标志性的关键信息,并用一种独立于编程语言的中间语言表达出来。
3、关键信息确定
通过分析面向对象实例特征,初步确立了八种最关键的信息。
1. class(CLA_ID(类名))
设计模式中涉及哪些类。
2. attribute(CLA_ID(所属类), VAR_ID(变量名),scope, CLA_ID(变量类型))
scope = PUBLIC | PRIVATE | PROTECT
类中有哪些属性,类型、范围如何。
3. operation(CLA_ID(所属类), OPE_ID(函数名), scope, CLA_ID(返回类型) , [ CLA_ID(参数类型), ])
类中有哪些操作,范围、返回值类型、参数类型如何。
4. inherit (CLA_ID(父类名), CLA_ID(子类名), scope )
模式中涉及哪些继承关系。
5. aggregation (CLA_ID(包容类名), CLA_ID(被包类名), multiple )
multiple = ONE | MANY
模式中涉及哪些聚合关系。
6. association (CLA_ID(包容类名), CLA_ID(指针类型))
模式中涉及哪些相连关系。
7. invoke ( CLA_ID(主调函数所在类), OPE_ID(主调函数名), CLA_ID(被调函数所在类), OPE_ID(被调函数名))
函数之间涉及哪些调用关系(主要指类成员函数之间)。
8. create ( CLA_ID(创建函数所在类), OPE_ID(创建函数名), CLA_ID(被创建类型))
哪些函数参与创建对象(主要之类成员函数)。
4、选择中间语言
UML(unified modeling language)是业界的通用建模语言,表现力强,内容丰富,实质上已经可以成为一种编程语言。但其语法和内容过于庞大,不适合作为中间语言,而更适合做为被分析的对象。通过分析由UML表述的设计(主要指类图)可以完成对设计的模式分析。
AOL(abstract object language)是基于UML的简化语言。设计的初衷就是为了通过一种与语言和工具无关的语法,抓住面向对象的概念。是一种通用的描述性语言。它符合BNF范式,格式为断言式,便于下一步通过Prolog等人工智能语言进行处理,最终成为了本设计的中间语言。
AOL的BNF语法范式见附录A。
5、完整系统框图
完整的识别过程如图1所示:
模式的识别和匹配过程依赖模式信息库进行识别。而信息库的建立主要靠分析现有的面向对象的设计模式,由中间语言表示,用人工智能的组织方式建成。由于模式信息库和代码分析后的信息都是由同一种语言(AOL)表示的,对下一步的匹配工作大有帮助。
考虑到时间和能力有限,本工作只完成其中的C++代码到AOL语言的转化工作。
第二章 软件平台和工具简介
1、Visual Studio.net简介
Visual Studio.net是VC6.0的后续版本。最大的改进是把帮助集成在了开发环境中。作为最成熟的C++编译器,它所支持的MFC类库包含了对字符串的丰富操作,成为本项目的首选。
2、Rose简介
Rose是基于UML的开发平台,主要用于工程各阶段的建模。并可由模型自动生成代码。本项目主要用其作出词法分析时的状态转换图。
第三章 分系统设计
代码分析可以有两种思路,一种是模拟词法分析器的原理,对源代码进行全面地分析,再剔除掉无用信息。另一种就是“直奔主题式”的分析方法,需要哪些信息就直接搜索源代码中相关的关键字,对无关信息在源代码层次就直接跳过。
这两种方法各有利弊。词法分析方法分析过程细腻周到,对语言信息把握准确全面,不会出现遗漏或误判。但其实现过程非常繁琐,需要对语言本身的规范十分熟悉,要求十分严格。C++语言本身语法是庞大的,实际使用时又十分灵活。构建C++语言词法分析器的工作量超出了本工作的承受范围。另外,由此得到的信息大部分对模式分析和描述而言是无用的。
直接在源代码中搜索关键字,而后在其周围小范围的区域进行分析和处理,是一种比较快速的方法,简单有效,易于编程实现。但是由于C++的使用比较灵活,不是完全面向对象的,所以可能出现误判。比如注释部分或字符串中的内容就容易造成误判。C++中关键字和保留字较多,类和对象的定义方式和使用方法也较多,如何能完备的识别所有类构造方式也是难点之一,若仅凭这种方法想作出工业强度的程序也不可行。
基于以上考虑,本程序倾向于把两种方法结合起来,主体程序用“直奔主题式”的方法实现,如果考虑到某些较大障碍时,再用词法分析的方法进行源代码的预处理,为主体程序扫清障碍。这样系统可分为两部分,词法分析部分和信息提取管理部分。两部分程序不仅实现时可以分别实现,而且修改时也可分别修改,对于词法分析部分,甚至可以用现有的词法分析器或词法分析器构造工具实现,为以后的逐步完善和改进打下坚实的框架。
在自主实现词法分析器时,由于考虑问题更具针对性,其状态空间大大减少,由代码实现是可行的。
第四章 词法分析实现
在词法分析的实现上,主要有基于表格驱动和代码驱动两种方法。表格驱动可通过工具软件生成驱动表格,简单高效,但其存储较复杂;而代码驱动一般采用手工编程实现,适合简单的词法分析,但代码量相对较大,效率有时不如表格驱动方法高。
基于表格驱动的词法分析器的实现方法是:将词法自动机的状态作为驱动表格的行,输入字符作为表格的列。词法分析程序从初始状态开始,根据输入字符查表进入下一状态,然后再从该状态出发,根据输入字符查表进入下一状态,如此直至最长匹配终态,返回该终态值作为词码。可以看出,表格驱动程序非常简单,只要将自动机的类树型结构利用表格化为线性处理方式,以数据的复杂性换取实现的简单和高效,由于驱动表格庞大,在实际应用中常采用压缩表的存储结构(如Hash表)。它的不足之处是,词法分析类的小修改将带来驱动表格的大变动,因此驱动表格通常用工具软件来生成,把类产生式语言转化为驱动表格。典型的是ScanGen和Lex两个软件,当ScanGen到达终态时,返回定义的主次词码。而当Lex到达终态时,执行相应的子程序返回定义的词码。
基于代码驱动的实现方法是将词法自动机的每个状态对应一小段代码,根据输入字符执行相应的代码分支,直至该代码执行完毕,返回相应的词码。
下面就如何去掉注释和缩减字符串,举例说明典型的词法分析预处理过程。
在程序设计中,适当使用注释可以增强程序的可读性,以及暂时屏蔽不需要的代码。注释对语法分析并无用处,也不参加编译。因此在词法分析阶段就应该将注释过滤掉。在各类程序设计语言中,注释可分为单行注释和整段注释,在C++语言中,单行注释用∥开头,直到该行结尾;整段注释用/*开头,以*/结尾。
字符串是在各种编程语言中大量使用的,但其字符串本身的信息对设计模式的识别而言是无用的,但其内容却会影响识别。所以也要通过预处理过程把内容缩短为零。
相应的状态转换图如图2所示。
相应的代码实现如下。
for(int i=0;i {
switch(state)
{
case 0:
if(str_sou[i]=='\"')state=1;
else if(str_sou[i]=='\\')state=2;
else ;
break;
case 1:
if(str_sou[i]=='\"')state=0;
else if(str_sou[i]=='\\')state=5;
else
{
str_sou.Delete(i);
i=i-1;
}
break;
case 2:
if(str_sou[i]=='\\')state=4;
else if(str_sou[i]=='\r')state=3;
else state=0;
break;
case 3:
state=0;
str_sou.Delete(i-2,3);
i=i-3;
break;
case 4:
if(str_sou[i]=='\\')state=6;
else if(str_sou[i]=='\r')state=0;
else
{
str_sou.Delete(i);
i=i-1;
}
break;
case 5:
state=1;
str_sou.Delete(i-1,2);
i=i-2;
break;
case 6:
if(str_sou[i]=='\r')state=7;
else
{
state=4;
str_sou.Delete(i-1,2);
i=i-2;
}
break;
case 7:
state=4;
str_sou.Delete(i-2,3);
i=i-3;
break;
}
}
可见,作为功能单一的词法分析程序,其状态空间是较小的,易于编程实现。并且,完成不同功能的状态转换图可以单独设计,最后拼接在一起,甚至就分别由代码实现。在初期未能考虑到的问题,可以在以后完善时方便的加上去,而第二部分,信息提取和管理,几乎不需要改动。
第五章 信息提取和管理的实现
经过预处理的代码,去掉了注释和字符串内容,对于关键字和保留字也作了适当删减。为下一步的信息提取做好了准备。
首先是对类定义的识别,这是识别其他信息的基础,因为其它大部分信息都包含在类定义中,或类的成员函数的实现中。
程序基本思路是,首先查找class关键字。然后判断类名、继承关系,如果是类的定义式,而不是声明式,则保存其类的定义体,留待以后分析。相应代码如下。
void CAOL02View::ExtrClass(void)
{
int cur_pos=0;
int next_pos=0;
CString token;
while(1)
{
cur_pos=str_source.Find("class",cur_pos);
if(cur_pos==-1)break;
cur_pos+=5;
next_pos=str_source.Find('{',cur_pos);
token=str_source.Mid(cur_pos,next_pos-cur_pos);
CCLass* p_class=new(CCLass);
p_class->str_name=token;
m_ClassList.AddTail(p_class);
cur_pos=next_pos;
next_pos=FindTheOne(cur_pos,str_source);
token=str_source.Mid(cur_pos+1,next_pos-cur_pos-1);
p_class->str_body=token;
cur_pos=next_pos;
}
}
void CAOL02View::DoClassName(void)
{
for( POSITION pos = m_ClassList.GetHeadPosition(); pos != NULL; )
{
CCLass* p_curclass=(CCLass*)m_ClassList.GetNext(pos);
CString resToken;
int curPos= 0;
resToken= p_curclass->str_name.Tokenize(" ,:",curPos);
while (resToken != "")
{
CString* p_name_part=new(CString);
p_name_part->Append(resToken); p_curclass->NameList.AddTail((CObject*)p_name_part);
resToken= p_curclass->str_name.Tokenize(" ,:",curPos);
}
POSITION pos2=p_curclass->NameList.GetHeadPosition();
CString* p_curname=
(CString*)p_curclass->NameList.GetNext(pos2);
CString name = *p_curname;
name.Trim(" ");
p_curclass->name=name;
CString scope;
CString parent;
CString token;
token.Format("class(%s)\r\n", name);
m_ClassArray.Add(name);
while(pos2!=NULL)
{
p_curname=
(CString*)p_curclass->NameList.GetNext(pos2);
scope=*p_curname;
p_curname=
(CString*)p_curclass->NameList.GetNext(pos2);
parent=*p_curname;
token.Format("%s,%s,%s",parent,name,scope);
m_InheritArray.Add(token);
}
}
}
第三步是分析函数体,确定函数之间的调用关系,以及是否有创建关系。调用关系主要靠发现函数名调用或函数指针调用,创建关系主要靠发现new、malloc等关键字来确定。相应代码如下。
void CAOL02View::Cre(void)
{
for(int i=0;i {
int cur_pos;
cur_pos=m_OpeBodyArray[i].Find("new");
if(cur_pos==-1)continue;
if((m_OpeBodyArray[i][cur_pos-1]==' '||m_OpeBodyArray[i][cur_pos-1]=='=')&&(m_OpeBodyArray[i][cur_pos+3]==' '||m_OpeBodyArray[i][cur_pos+3]=='('))
{
CString str1;
str1=GetThePart(m_OperationArray[i],1);
CString str2;
str2=GetThePart(m_OperationArray[i],2);
CString str3;
int next_pos=m_OpeBodyArray[i].Find(")");
str3=m_OpeBodyArray[i].Mid(cur_pos+4,next_pos-cur_pos-4);
str3.Trim(" ()");
CString token;
token.Format("%s,%s,%s",str1,str2,str3);
m_CreArray.Add(token);
}
}
}void CAOL02View::Cre(void)
{
for(int i=0;i {
int cur_pos;
cur_pos=m_OpeBodyArray[i].Find("new");
if(cur_pos==-1)continue;
if((m_OpeBodyArray[i][cur_pos-1]==' '||m_OpeBodyArray[i][cur_pos-1]=='=')&&(m_OpeBodyArray[i][cur_pos+3]==' '||m_OpeBodyArray[i][cur_pos+3]=='('))
{
CString str1;
str1=GetThePart(m_OperationArray[i],1);
CString str2;
str2=GetThePart(m_OperationArray[i],2);
CString str3;
int next_pos=m_OpeBodyArray[i].Find(")");
str3=m_OpeBodyArray[i].Mid(cur_pos+4,next_pos-cur_pos-4);
str3.Trim(" ()");
CString token;
token.Format("%s,%s,%s",str1,str2,str3);
m_CreArray.Add(token);
}
}
}
最后一步是检查属性类型,确定是否有相连关系或包含关系。其中下列两种情况算作相连关系:class1 * p_class1;class1 & p_class1。而class1 var_class1 算作包含关系。相关代码如下。
void CAOL02View::Agg(void)
{
for(int i=0;i {
for(int j=0;j {
if(GetThePart(m_AttributeArray[i],4)==GetThePart(m_ClassArray[j],1))
{
CString mul;
if(GetThePart(m_AttributeArray[i],2).Find('[')==-1)mul="ONE";
else mul="MANY";
CString token;
token.Append(GetThePart(m_AttributeArray[i],1));
token.Append(",");
token.Append(GetThePart(m_ClassArray[j],1));
token.Append(",");
token.Append(mul);
m_AggArray.Add(token);
}
}
}
}
void CAOL02View::Ass(void)
{
for(int i=0;i {
if(GetThePart(m_AttributeArray[i],4)[GetThePart(m_AttributeArray[i],4).GetLength()-1]=='*'||GetThePart(m_AttributeArray[i],4)[GetThePart(m_AttributeArray[i],4).GetLength()-1]=='&')
{
CString token=GetThePart(m_AttributeArray[i],4).Left(GetThePart(m_AttributeArray[i],4).GetLength()-1);
for(int j=0;j {
if(token==GetThePart(m_ClassArray[j],1))
{
CString token2;
token2.Append(GetThePart(m_AttributeArray[i],1));
token2.Append(",");
token2.Append(token);
m_AssArray.Add(token2);
}
}
}
}
}
最后的成品界面如下图所示。
其中左侧文本编辑区可以通过手工编辑或者打开文件来获取源代码,提取的信息显示在右侧文本编辑区,可以通过复制或者保存文件保存下来。
第六章 小结
一个多月的毕业设计使我受益匪浅,在指导教员的帮助下,我接触到了这个有开创性的工作。学习到了如何把基础知识应用到实践中来。所的经验主要有以下几点。
首先是准备要充分,不要着急开始动手。需求分析的时间至少要是总开发时间的三分之一以上。只有把问题的来龙去脉和任务要求搞清楚,才能有的放矢,做到事半功倍。在这个项目中,用于代码编辑的时间是较少的,用于分析设计模式具有哪些共同特征的时间是大量的,确定分析方法的时间也使大量的。
另外,程序的构架要合理,并要有一定的可扩展性,而具体功能的实现要灵活。项目初期,许多对具体细节的设想是不科学的,修改在所难免,如果初始框架不可扩展,那代价就是昂贵的。具体的功能实现要灵活,不要拘泥于单一的或经典的形式,而要结合具体任务,多方面考虑。如本项目的信息提取阶段,曾有两种选择摆在面前,各有利弊,最终的考虑是,把两种方法结合起来,取长补短。
最后,是对我影响最深远的一个经验。就是解决问题固然重要,但善于发现问题,提出问题,对做开创性工作,做科研更重要。我曾经学习过面向对象的设计模式,但仅仅限于使用,张志祥教授作为我的指导教师,为我找到了这个领域值得探索,并能做出成绩的突破点,指明了我工作的方向。再次表示深深地感谢。
这个项目总体来说是成功的,但最关键的,也是最需要突破的模式匹配部分,还要留待以后继续开发。