Re: Are there any tools that can compare two source files

Sarath Kumar <sarath_kumar@mentorg.com>:


> Generalizing the problem refers to the problem of finding the
> semantic equivalence of two programs. Is this possible?? As the
> theorists go this is very tough and not possible in polynomial time.


Determining (denotational) semantic equivalence of two programs
is not possible in *any* amount of time: it is non-computable,
not just NP-complete.


> Satyanandam Gullapudi wrote:
> > I am looking for some tool which is more than simple text diff. I am
> > looking for a tool which can generate the structure trees for the
> > source file and compare them. It should not throw errors if the
> > structure is just re-arragned.


The FermaT Transformation System can generate structure trees
from source files and compare them. You would need to do
a bit of extra work to detect re-arranged structures.


> [Seems to me that, like with many NP-complete problems, even though
> it's impractical to get a perfect result, it could be very useful to
> get an approximate result. -John]


You can get useful approximate results to uncomputable problems too!


Martin


Martin.Ward@durham.ac.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/

Return to the comp.compilers page.
Search the comp.compilers archives again.