Identifying Syntactic Differences between Two Programs
Software - Practice and Experience, 21 (7):
739-755 (July 1991)Abstract
Programmers frequently face the need to identify the differences between two programs, usually two different versions of a program. Text-based tools such as the UNIX utility diff often produce unsatisfactory comparisons because they cannot accurately pinpoint the differences and because they sometimes produce irrelevant differences. Since programs have a rigid syntactic structure as described by the grammar of the programming language in which they are written, we develop a comparison algorithm that exploits knowledge of the grammar. The algorithm, which is based on a dynamic programming scheme, can point out the differences between two programs more accurately than previous text comparison tools. Finally, the two programs are pretty-printed ‘synchronously’ with the differences highlighted so that the differences are easily identified.
