Re: How to extract grammar from a program?

eodell@pobox.com (Eric O'Dell)
15 Feb 1999 23:04:02 -0500

          From comp.compilers

Related articles
How to extract grammar from a program? rahulj@iitk.ac.in (Rahul Jain) (1999-02-05)
Re: How to extract grammar from a program? cfc@world.std.com (Chris F Clark) (1999-02-10)
Re: How to extract grammar from a program? derekross@fisheracre.freeserve.co.uk (Derek Ross) (1999-02-12)
Re: How to extract grammar from a program? eodell@pobox.com (1999-02-15)
Re: How to extract grammar from a program? dib@dera.gov.uk (David Bruce) (1999-02-15)
Re: How to extract grammar from a program? spencer@cc.gatech.edu (1999-02-15)
Re: How to extract grammar from a program? hunk@alpha1.csd.uwm.edu (1999-02-15)
Re: How to extract grammar from a program? hunk@alpha1.csd.uwm.edu (1999-02-15)
Re: How to extract grammar from a program? x@wins.uva.nl (1999-12-09)
| List of all articles for this month |

From: eodell@pobox.com (Eric O'Dell)
Newsgroups: comp.compilers
Date: 15 Feb 1999 23:04:02 -0500
Organization: Compilers Central
References: 99-02-025 99-02-049
Keywords: parse

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.


Post a followup to this message

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