面向对象程序等价转换技术的研究与应用
|
摘要
程序的等价转换技术在程序的分析评价中有着广泛的应用前景。由于目前程序分析评价主要停留在程序输出结果的比较阶段,未深入到程序的结构层次分析,以发现程序之间存在的语义差异。另外,在已有相关方面的研究中,程序分析评价的目标语言仅限于函数式语言或命令式语言,尚未涉及到面向对象语言的等价转换研究。
本文研究基于面向对象程序的等价转换技术及其在程序分析评价中的应用。程序的等价转换技术是以程序语义等价性为理论基础,程序语义的等价性包括执行语义等价、结构语义等价和似结构语义等价。具有等价似结构语义的源程序之间可以作相互转换。
由于使用面向对象语言设计的程序具有明显的层次性,在对这类程序进行等价转换时,分以下三个层次进行:程序级等价转换、类级等价转换和方法级等价转换。程序级等价转换主要是针对程序中类之间存在继承关系而进行的程序标准化处理过程,通过对继承关系的消除,可以显式地表达每个类所包含的所有信息。类级等价转换主要是针对每个类中的成员方法之间的相互调用关系进行的程序标准化处理过程,通过对调用关系的消除,可以直观表达每个成员方法中所包含的所有信息,同时,还需要消除类中存在的冗余方法,简化类的构成。方法级等价转换主要是针对程序在语句表达上的多样化而进行的程序标准化处理过程,通过对程序中的语句进行赋值标准化、表达式标准化和控制结构标准化来消除每个方法中语句表达的多样化问题。
在面向对象程序等价转换技术的基础上,提出了一个JAVA程序自动测评系统的框架,并实现了系统原型。在该系统中,使用ANTLRWORKS构造一个以AST为中间代码的JAVA语言解析器。在AST基础上,对程序结构进行分析,并引入C&K和MOOD等著名的面向对象的度量体系对程序进行度量,并生成用于分析程序的各种图形表示。然后按程序级保留语义的等价转换、类级保留语义的等价转换和方法级保留语义的等价转换共三个层次对程序进行保留语义的等价转换,最终生成在语义上可以比较的程序依赖图,应用相关算法实现对程序的比较与评价。
Program equivalence transformation technology has extensive application prospects in program analysis and assessment technology. Nowadays, the program analysis technology mainly concentrates on comparison of program outputs. It can't find out semantic differences through analysing structures of programs. At present, research results made of which target language is functional language or injunctive language. However, there are few research on equivalance transformation for object-oriented language.
In the thesis, we do research in program equivalence transformation technology and its application in program analysis and assessment. Semantic equivalence of program is theoretical foundation of program equivalence transformation technology. Semantic equivalence of program contains execution semantic equivalence, structure semantic equivalence and similar structure semantic equivalence. If the similar structure semantics of two source program are equivalent, one source program can be transformed into another source program.
Due to obvious hierarchy of object-oriented program, there are three levels equivalence transformation, which contains program level equivalence transformation, class level equivalence transformation and function level equivalence transformation, for object-oriented program. Program level equivalence transformation is used to show all the information which existed in each class through eliminating inheritance relation between all classes in the program. Class level equivalence transformation is used to show all the information which existed in each function through eliminating method calls between all methods in each class. Meanwhile, the structures of all class are simplified by eliminating redundant methods. Function level equivalence transformation is used to eliminating the diversification of sentence expression through standardizing assignments, expressions and control structures.
Based on object-oriented program equivalence transformation technology, we propose a new framework of JAVA porgram automatic assessment system, and implement the prototype. In the system, we use ANTLRWORK to construct a JAVA parser, which is able to generate Abstract Syntax Tree as intermediate language. At the analysis of program structure, we make use of C&K and MOOD software metrics to compute and visualize the metrics information of programs, and generate several graph expression of programs. At equivalence transformation of program, we propose a new method which implements semantically preserving equivalence transformation by three levels that are transformation at program level seperately, transformation at class level, transformation at method level. After equivalence transformation, the program dependance graphs are constructed and the comparison and assessment algorithm is apply to identifying the semantic differences ot two programs and giving an analysis and assessment report.
本文研究基于面向对象程序的等价转换技术及其在程序分析评价中的应用。程序的等价转换技术是以程序语义等价性为理论基础,程序语义的等价性包括执行语义等价、结构语义等价和似结构语义等价。具有等价似结构语义的源程序之间可以作相互转换。
由于使用面向对象语言设计的程序具有明显的层次性,在对这类程序进行等价转换时,分以下三个层次进行:程序级等价转换、类级等价转换和方法级等价转换。程序级等价转换主要是针对程序中类之间存在继承关系而进行的程序标准化处理过程,通过对继承关系的消除,可以显式地表达每个类所包含的所有信息。类级等价转换主要是针对每个类中的成员方法之间的相互调用关系进行的程序标准化处理过程,通过对调用关系的消除,可以直观表达每个成员方法中所包含的所有信息,同时,还需要消除类中存在的冗余方法,简化类的构成。方法级等价转换主要是针对程序在语句表达上的多样化而进行的程序标准化处理过程,通过对程序中的语句进行赋值标准化、表达式标准化和控制结构标准化来消除每个方法中语句表达的多样化问题。
在面向对象程序等价转换技术的基础上,提出了一个JAVA程序自动测评系统的框架,并实现了系统原型。在该系统中,使用ANTLRWORKS构造一个以AST为中间代码的JAVA语言解析器。在AST基础上,对程序结构进行分析,并引入C&K和MOOD等著名的面向对象的度量体系对程序进行度量,并生成用于分析程序的各种图形表示。然后按程序级保留语义的等价转换、类级保留语义的等价转换和方法级保留语义的等价转换共三个层次对程序进行保留语义的等价转换,最终生成在语义上可以比较的程序依赖图,应用相关算法实现对程序的比较与评价。
Program equivalence transformation technology has extensive application prospects in program analysis and assessment technology. Nowadays, the program analysis technology mainly concentrates on comparison of program outputs. It can't find out semantic differences through analysing structures of programs. At present, research results made of which target language is functional language or injunctive language. However, there are few research on equivalance transformation for object-oriented language.
In the thesis, we do research in program equivalence transformation technology and its application in program analysis and assessment. Semantic equivalence of program is theoretical foundation of program equivalence transformation technology. Semantic equivalence of program contains execution semantic equivalence, structure semantic equivalence and similar structure semantic equivalence. If the similar structure semantics of two source program are equivalent, one source program can be transformed into another source program.
Due to obvious hierarchy of object-oriented program, there are three levels equivalence transformation, which contains program level equivalence transformation, class level equivalence transformation and function level equivalence transformation, for object-oriented program. Program level equivalence transformation is used to show all the information which existed in each class through eliminating inheritance relation between all classes in the program. Class level equivalence transformation is used to show all the information which existed in each function through eliminating method calls between all methods in each class. Meanwhile, the structures of all class are simplified by eliminating redundant methods. Function level equivalence transformation is used to eliminating the diversification of sentence expression through standardizing assignments, expressions and control structures.
Based on object-oriented program equivalence transformation technology, we propose a new framework of JAVA porgram automatic assessment system, and implement the prototype. In the system, we use ANTLRWORK to construct a JAVA parser, which is able to generate Abstract Syntax Tree as intermediate language. At the analysis of program structure, we make use of C&K and MOOD software metrics to compute and visualize the metrics information of programs, and generate several graph expression of programs. At equivalence transformation of program, we propose a new method which implements semantically preserving equivalence transformation by three levels that are transformation at program level seperately, transformation at class level, transformation at method level. After equivalence transformation, the program dependance graphs are constructed and the comparison and assessment algorithm is apply to identifying the semantic differences ot two programs and giving an analysis and assessment report.
引文
[1]M.Ghosh,B.Verma,and A.Nguyen,"An Automatic Assessment Marking and Plagiarism Detection",First International Conference on Information Technology and Applications(ICITA 2002),Bathurst,Australia,(2002).
[2]Michael Blumenstein,Steve Green,Ann Nguyen and Vallipuram Muthukkumarasamy.GAME:A Generic Automated Marking Environment for Programming Assessment.Proceedings of the International Conference on Information Technology:Coding and Computing(ITCC' 04).
[3]Graham H.B.Roberts and Janet L.M.Verbyla.An Online Programming Assessment Tool.Australasian Computing Education Conference (ACE2003),Adelaide,Australia.Conferences in Research and Practice in Information Technology,Vol.20.
[4]Brenda Cheanga,Andy Kurniaa,Andrew Limb,Wee-Chong Oonc.On automated grading of programming assignments in an academic institution.Computers & Education 41(2003)121-131.
[5]Christopher Douce,David Livingstone,James Orwell,Steve Grindle and Justin Cobb.A Technical Perspective on ASAP - Automated System for Assessment of Programming.9th International Conference on Computer Aided Assessment,July,Loughborough,(2005).
[6]林阿龙.C源程序分析及理解的辅助工具--CAAT.小型微型计算机系统,13(1),1992.
[7]樊敏.程序作业自动测评的研究与实现.广东工业大学工学硕士学位论文.2005.
[8]李广强.基于转换的程序分析技术的研究与应用.广东工业大学工学硕士学位论文.2007
[9]Songwen Xu and Yam san Chee.IPLeS-Ⅱ:An Automatic Program Diagnosis System for Programming Learning Environments.Proceedings of AI-ED 99:9th International Conference on Artificial Intelligence in Education,Le Mans,France,pp.397-404.
[10]Songwen Xu and Yam san Chee.Transformation-based Diagnosis of Students Programs for Programming Tutoring Systems.IEEE Transactions on Software Engineering,Volume 29,Issue 4(April 2003).Pages:360-384.
[11]Hristova,M.,Micra,A.,Rutter,M.and Mercuri,R.(2003):Identifying and Correcting Java Programming Errors for Introductory Computer Science Students.Proc.the 34th SIGCSE technical symposium on Computer science education,Reno,Nevada,USA,34:153-156,ACM Press.
[12]George C.Necula,Scott McPeak,S.P.Rahul and Westley Weimer.CIL:Intermediate Language and Tools for Analysis and Transformation of C Programs.Proceedings of Conference on Comp]ier Construction,2002.
[13]代码多样化消除规则的研究.王宇颖,李永浩,孙志刚,苏小红.哈尔滨工业大学学报.2005,37(4):526-529
[14]石学林.Cobo 12Java源代码翻译关键技术研究.中科院计算所博士学位论文.2003.
[15]Chidamber,Shyam & Kemerer,Chris F." A Metrics Suite for Object-Oriented Design" IEEE Transactions on Software Engineering 20,6(June 1994):476-493.
[16]Harrisan R,Counsell S.J,Nithi R,V.An Evaluation Of the MOOD Set Of Object-Oriented Software Metrics[J].IEEE Trans.Software Eng.,June,1998:491-496.
[17]Brito F.,Abreu E.MOOD-Metric for Object-Oriented design.OO PSLA94workshop on Pragmatic and Theoretical Directions in Object-oriented Software Metric,Portland,OR,1994
[18]Parr,T.:ANTLR,http://www.antlr.org.2006.
[19]李必信编著,程序切片技术及其应用.北京:科学出版社,2006.
[20]钱树人.程序设计语言的语义理解及语境分析.计算机研究与发展.1994,31 (7):37-42
[21]Wuu Yang,Susan Horwitz,Thomas Reps.Detecting Program Components With Equivalent Behaviors,TR 840,Computer Sciences Dept.,Univ.of Wisconsin,Madison,WI,1989.
[22]John C.Mitchell著,冯建华等译.程序设计语言概念.清华大学出版社,2005.
[23]McCabe&Associates,McCabe Object Oriented Tool User's Instructions,1994.
[24]黄柏素,梅宏译,软件工程-实践者的研究方法(第四版)[M]北京:机械工业出版社,2001.
[25]Fenton.ME,Software Metrics,A rigorous approach,New York:Chapman&Hall,1991.
[26]Halstead,M,Elements of Software science,North Holland,1977.
[27]Lorenz M.Object-Oriented Software Development:A Practical Guide.Prentice Hall,NJ,1993
[28]J.Y.Chen,J.F.Liu.A new metric for object-oriented design,Information and software technology,1993,35(4),233-239
[29]Leach,R.J.(1995):Using metrics to evaluate student programs.ACM SIGCSE Bulletin,27(2):41-43.
[30]Li,Wei & Henry,Salley."Maintenance Metrics for the Object Oriented Paradigm," pp.52-60.Proceedings:First International Software Metrics Symposium.Baltimore,Maryland,May 21-22,1993.Los Alamitos,alifomia:IEEE Computer Society Press,1993.
[31]Supporting Program Comprehension Using Semantic and Structural Information Jonathan I.Maletic,Andrian Marcus Division of Computer Science Department of Mathematical Sciences The University of Memphis Campus Box 523240 Memphis,TN 38152,USA
[32]任凌燕.类层次图的研究.西安电子科技大学工学硕士论文.2003.
[33]J.Ferrante,K.Ottenstein,and J.Warren,"The Program Dependence Graph and its Use in Optimization," ACM Transactions on Programming Languages,Vol.9,no.3,pp.319-349,1987.
[34]W.Yang,S.Horwitz,and T.Reps,"A Program Integration Algorithm that Accommodates Semantics-preserving Transformations," ACM Transactions on Software Engineering and Methodology,Vol.1,no.3,pp.310-354,1992.
[35]Andrew W.Appel等著,陈明等译,程虎审校.现代编译器的Java实现(第二版)[M].机械工业出版社,2004.
[36]Steven S.Muchnick著,赵克佳 等译.高级编译器设计与实现[M].机械工业出版社,2005.
[2]Michael Blumenstein,Steve Green,Ann Nguyen and Vallipuram Muthukkumarasamy.GAME:A Generic Automated Marking Environment for Programming Assessment.Proceedings of the International Conference on Information Technology:Coding and Computing(ITCC' 04).
[3]Graham H.B.Roberts and Janet L.M.Verbyla.An Online Programming Assessment Tool.Australasian Computing Education Conference (ACE2003),Adelaide,Australia.Conferences in Research and Practice in Information Technology,Vol.20.
[4]Brenda Cheanga,Andy Kurniaa,Andrew Limb,Wee-Chong Oonc.On automated grading of programming assignments in an academic institution.Computers & Education 41(2003)121-131.
[5]Christopher Douce,David Livingstone,James Orwell,Steve Grindle and Justin Cobb.A Technical Perspective on ASAP - Automated System for Assessment of Programming.9th International Conference on Computer Aided Assessment,July,Loughborough,(2005).
[6]林阿龙.C源程序分析及理解的辅助工具--CAAT.小型微型计算机系统,13(1),1992.
[7]樊敏.程序作业自动测评的研究与实现.广东工业大学工学硕士学位论文.2005.
[8]李广强.基于转换的程序分析技术的研究与应用.广东工业大学工学硕士学位论文.2007
[9]Songwen Xu and Yam san Chee.IPLeS-Ⅱ:An Automatic Program Diagnosis System for Programming Learning Environments.Proceedings of AI-ED 99:9th International Conference on Artificial Intelligence in Education,Le Mans,France,pp.397-404.
[10]Songwen Xu and Yam san Chee.Transformation-based Diagnosis of Students Programs for Programming Tutoring Systems.IEEE Transactions on Software Engineering,Volume 29,Issue 4(April 2003).Pages:360-384.
[11]Hristova,M.,Micra,A.,Rutter,M.and Mercuri,R.(2003):Identifying and Correcting Java Programming Errors for Introductory Computer Science Students.Proc.the 34th SIGCSE technical symposium on Computer science education,Reno,Nevada,USA,34:153-156,ACM Press.
[12]George C.Necula,Scott McPeak,S.P.Rahul and Westley Weimer.CIL:Intermediate Language and Tools for Analysis and Transformation of C Programs.Proceedings of Conference on Comp]ier Construction,2002.
[13]代码多样化消除规则的研究.王宇颖,李永浩,孙志刚,苏小红.哈尔滨工业大学学报.2005,37(4):526-529
[14]石学林.Cobo 12Java源代码翻译关键技术研究.中科院计算所博士学位论文.2003.
[15]Chidamber,Shyam & Kemerer,Chris F." A Metrics Suite for Object-Oriented Design" IEEE Transactions on Software Engineering 20,6(June 1994):476-493.
[16]Harrisan R,Counsell S.J,Nithi R,V.An Evaluation Of the MOOD Set Of Object-Oriented Software Metrics[J].IEEE Trans.Software Eng.,June,1998:491-496.
[17]Brito F.,Abreu E.MOOD-Metric for Object-Oriented design.OO PSLA94workshop on Pragmatic and Theoretical Directions in Object-oriented Software Metric,Portland,OR,1994
[18]Parr,T.:ANTLR,http://www.antlr.org.2006.
[19]李必信编著,程序切片技术及其应用.北京:科学出版社,2006.
[20]钱树人.程序设计语言的语义理解及语境分析.计算机研究与发展.1994,31 (7):37-42
[21]Wuu Yang,Susan Horwitz,Thomas Reps.Detecting Program Components With Equivalent Behaviors,TR 840,Computer Sciences Dept.,Univ.of Wisconsin,Madison,WI,1989.
[22]John C.Mitchell著,冯建华等译.程序设计语言概念.清华大学出版社,2005.
[23]McCabe&Associates,McCabe Object Oriented Tool User's Instructions,1994.
[24]黄柏素,梅宏译,软件工程-实践者的研究方法(第四版)[M]北京:机械工业出版社,2001.
[25]Fenton.ME,Software Metrics,A rigorous approach,New York:Chapman&Hall,1991.
[26]Halstead,M,Elements of Software science,North Holland,1977.
[27]Lorenz M.Object-Oriented Software Development:A Practical Guide.Prentice Hall,NJ,1993
[28]J.Y.Chen,J.F.Liu.A new metric for object-oriented design,Information and software technology,1993,35(4),233-239
[29]Leach,R.J.(1995):Using metrics to evaluate student programs.ACM SIGCSE Bulletin,27(2):41-43.
[30]Li,Wei & Henry,Salley."Maintenance Metrics for the Object Oriented Paradigm," pp.52-60.Proceedings:First International Software Metrics Symposium.Baltimore,Maryland,May 21-22,1993.Los Alamitos,alifomia:IEEE Computer Society Press,1993.
[31]Supporting Program Comprehension Using Semantic and Structural Information Jonathan I.Maletic,Andrian Marcus Division of Computer Science Department of Mathematical Sciences The University of Memphis Campus Box 523240 Memphis,TN 38152,USA
[32]任凌燕.类层次图的研究.西安电子科技大学工学硕士论文.2003.
[33]J.Ferrante,K.Ottenstein,and J.Warren,"The Program Dependence Graph and its Use in Optimization," ACM Transactions on Programming Languages,Vol.9,no.3,pp.319-349,1987.
[34]W.Yang,S.Horwitz,and T.Reps,"A Program Integration Algorithm that Accommodates Semantics-preserving Transformations," ACM Transactions on Software Engineering and Methodology,Vol.1,no.3,pp.310-354,1992.
[35]Andrew W.Appel等著,陈明等译,程虎审校.现代编译器的Java实现(第二版)[M].机械工业出版社,2004.
[36]Steven S.Muchnick著,赵克佳 等译.高级编译器设计与实现[M].机械工业出版社,2005.