Re: How to extract grammar from a program?

On 10 Feb 1999 18:13:45 -0500, Chris F Clark <cfc@world.std.com>
wrote:


>There are formal theories that address this. However, their results
>are far from encouraging. The essential problem is that given a finite
>set of programs, there is a trivial regular expression which recognizes
>exactly those set of programs and no others. Namely,
>regexp: program-1 | program-2 | ... | program-n;


Perhaps not useful for languages, but I have been interested lately in
exactly this problem, or something similar to it. I want to be able to
take an arbitrary set of strings and automagically generate a regular
expression that matches all of them. The idea is not to come up with a
regexp that matches _only_ the set members, but which matches the set
members _and_ similar strings.


I imagine everything hinges on the kind and degree of similarity,
which is where I'm stuck. Fuzzy matching techniques seem to work
fairly well for determining degree of similarity to a single string,
but I haven't seen anyone try to do a fuzzy match against a set of
strings.


Does anyone have any pointers to papers or theses on this subject?




-E.

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