{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20697"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20697","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Finding program differences based on syntactic tree structure","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Beckman-Davies, Carol Sue"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Campbell, Roy H."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:46:41Z","date_published":"2011-05-07T12:46:41Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1989 Beckman-Davies, Carol Sue"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI8924769","(UMI)AAI8924769"],"render_values":[{"text":"AAI8924769","href":null,"code":true},{"text":"(UMI)AAI8924769","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20697","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Campbell, Roy H."]},{"key":"dc:creator","label":"Author","values":["Beckman-Davies, Carol Sue"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:46:41Z","10000-01-01","1989"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1989 Beckman-Davies, Carol Sue"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI8924769","(UMI)AAI8924769","http://hdl.handle.net/2142/20697"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T12:46:41Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 8924769.pdf: 20091456 bytes, checksum: a529f7b44fc95aa578dad13967997bf4 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:39Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:15-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Finding program differences based on syntactic tree structure"]}]}],"canonical_facts":{"dc:contributor":["Campbell, Roy H."],"dc:creator":["Beckman-Davies, Carol Sue"],"dc:date":["2011-05-07T12:46:41Z","10000-01-01","1989"],"dc:description":["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.","Made available in DSpace on 2011-05-07T12:46:41Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 8924769.pdf: 20091456 bytes, checksum: a529f7b44fc95aa578dad13967997bf4 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:39Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:15-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI8924769","(UMI)AAI8924769","http://hdl.handle.net/2142/20697"],"dc:language":["eng"],"dc:rights":["Copyright 1989 Beckman-Davies, Carol Sue"],"dc:subject":["Computer Science"],"dc:title":["Finding program differences based on syntactic tree structure"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:16Z"}