Constructing CFGs from examples. (Christian Collberg)
Wed, 12 Jul 1995 00:47:39 GMT

          From comp.compilers

Related articles
Constructing CFGs from examples. (1995-07-12)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Christian Collberg)
Keywords: question
Organization: Compilers Central
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:
Computer Science Dept | Fax: +64-9-373-7453
University of Auckland | Phone: +64-9-373-7599 x 6137
Private Bag 92019, | WWW:
Auckland, NZ |

Post a followup to this message

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