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

"Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote in message
> 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??


> It is not possible. Not even in exponential time. It is at least as
> hard as deciding whether they will halt (for obvious reasons).
>
> More seriously, I believe that the canonical rearrangement problem IS
> soluble, and I am surprised that there aren't more tools to do it.
> This is because it has two important uses:
>
> 1) Signatures for separately compiled codes, to determine
> whether rebuilding is necessary.
>
> 2) Checking for the inheritance of codes, especially in a
> copyright context.


We have a tool, the Clone "Doctor" that detects "similar" code by
doing rather the sort-of-obvious syntax tree comparisons.
http://www.semdesigns.com/Products/Clone/index.html.


Its purpose is to detect "reused" (copied [stolen?]) code. It seems
to be pretty good at that, even though it has only a tiny
"understanding" of program semantics (it understands "sequences").
We've thought a bit about adding certain types of semantic
equivalences (ignoring accidental statement order in the absence of
dependencies), but for practical purposes syntax-tree compares seem
pretty good.


Other researchers have used dynamic programming to detect similarity
with smallest number of edits.
--
Ira D. Baxter, Ph.D. CTO Semantic Designs, Inc.
http://www.semdesigns.com

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