Finding program differences based on syntactic tree structure
Beckman-Davies, Carol Sue
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20697
Description
Title
Finding program differences based on syntactic tree structure
Author(s)
Beckman-Davies, Carol Sue
Issue Date
1989
Doctoral Committee Chair(s)
Campbell, Roy H.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
