|Constructing CFGs from examples. email@example.com (1995-07-12)|
|From:||firstname.lastname@example.org (Christian Collberg)|
|Date:||Wed, 12 Jul 1995 00:47:39 GMT|
Has there been any work done on algorithms for
constructing CFGs from example strings? For example,
given strings bb, bab, baab, and baaab, we might
produce a CFG (guessing that an infinite number of
a's is, in fact, OK)
<S> ::= b<A>b
<A> ::= a <A> | empty.
Obviously there are other possibilities, such as
the trivial solution
<S> ::= bb | bab | baab | baaab,
but we'd like to go with the "smallest" grammar with
highest generative power.
I'm guessing this problem is related to work done
in the Machine Learning community, but I'd be
grateful for any relevant references.
Christian Collberg | Email: email@example.com
Computer Science Dept | Fax: +64-9-373-7453
University of Auckland | Phone: +64-9-373-7599 x 6137
Private Bag 92019, | WWW: http://www.cs.auckland.ac.nz/~collberg/
Auckland, NZ |
Return to the
Search the comp.compilers archives again.