Files in this item



application/pdf8924769.pdf (20MB)Restricted to U of Illinois
(no description provided)PDF


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
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
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.
Issue Date:1989
Rights Information:Copyright 1989 Beckman-Davies, Carol Sue
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI8924769
OCLC Identifier:(UMI)AAI8924769

This item appears in the following Collection(s)

Item Statistics