Files in this item
|(no description provided)|
|Title:||Finding program differences based on syntactic tree structure|
|Author(s):||Beckman-Davies, Carol Sue|
|Doctoral Committee Chair(s):||Campbell, Roy H.|
|Department / Program:||Computer Science|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Abstract:||Programmers look at differences between versions of a program to gain information about the program and changes to it. Despite the wide application of syntactic and semantic analysis to other areas, similar analysis has not been applied to finding program differences.
This dissertation describes research into finding differences based on the syntactic tree structure of the program, as represented by a parse tree. The research examines two existing tree comparison algorithms, Selkow's and Tai's, for use with parse trees. Both algorithms require modification and expansion to be usable for parse trees. Adapting the parse trees is also necessary.
The dissertation describes two new methods for finding the differences. Both combine string comparison with the tree structure to organize differences in a way a programmer would wish to see them. The first finds a string of interesting trees, that is, subtrees representing structures of interest to the programmer, and compares them with a string comparison, in a manner analogous to comparing lines of a tile. The second method uses the results of a string or tree comparison to find interesting trees that changed and to determine the relationships between them.
Because of the expense of Selkow's and Tai's tree comparison algorithms, the research investigates methods for selecting subtrees of the parse trees for the comparison and eliminating unchanged subtrees before the comparison. The special nature of changes to parse trees, that is, a change in any node implies a change in a leaf node, allows selection and elimination based on changes to the terminal nodes.
An evaluation of selection, elimination, and five comparison methods indicates that none of the methods produce ideal results. Each method, however, works well for certain uses and for particular ways of displaying the differences.
|Rights Information:||Copyright 1989 Beckman-Davies, Carol Sue|
|Date Available in IDEALS:||2011-05-07|
|Identifier in Online Catalog:||AAI8924769|