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

thp@cs.ucr.edu
20 Dec 2001 00:46:16 -0500

          From comp.compilers

Related articles
Are there any tools that can compare two source files satyanandam_g@hotmail.com (2001-12-07)
Re: Are there any tools that can compare two source files joachim_d@gmx.de (Joachim Durchholz) (2001-12-11)
Re: Are there any tools that can compare two source files sarath_kumar@mentorg.com (Sarath Kumar) (2001-12-15)
Re: Are there any tools that can compare two source files nmm1@cus.cam.ac.uk (2001-12-19)
Re: Are there any tools that can compare two source files joachim_d@gmx.de (Joachim Durchholz) (2001-12-20)
Re: Are there any tools that can compare two source files torbenm@eir.diku.dk (2001-12-20)
Re: Are there any tools that can compare two source files Martin.Ward@durham.ac.uk (2001-12-20)
Re: Are there any tools that can compare two source files thp@cs.ucr.edu (2001-12-20)
Re: Are there any tools that can compare two source files idbaxter@semdesigns.com (Ira D. Baxter) (2001-12-22)
Re: Are there any tools that can compare two source files tej@melbpc.org.au (Tim Josling) (2001-12-22)
| List of all articles for this month |

From: thp@cs.ucr.edu
Newsgroups: comp.compilers
Date: 20 Dec 2001 00:46:16 -0500
Organization: University of California, Riverside
References: 01-12-027 01-12-058
Keywords: theory
Posted-Date: 20 Dec 2001 00:46:16 EST

Sarath Kumar <sarath_kumar@mentorg.com> wrote:
: 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.


: If there is one such tool then send them down, i will love to look
: at it.


: 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.
: [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]


Not only is semantic equivalence not possible to test in polynomial
time, but it is equivalent to the halting problem (which can be viewed
as a test for a specific semantics).


There are however tests for equivalent syntactic structure. UC
Berkeley has a very interesting system MOSS (Measure of Software
Similarity) that many universities use to catch plagiarism on
programming homework assignments. ;-)


Tom Payne


Post a followup to this message

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