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

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.


It is not possible. Not even in exponential time. It is at least as
hard as deciding whether they will halt (for obvious reasons).


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


BANG! Sound from up on high:


        Mortal. Do not presume. Solving the Halting Problem is My
        Prerogative.


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.


Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Email: nmm1@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679

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