Wed, 12 Jul 1995 00:47:39 GMT

Related articles |
---|

Constructing CFGs from examples. collberg@cs.auckland.ac.nz (1995-07-12) |

Newsgroups: | comp.compilers |

From: | collberg@cs.auckland.ac.nz (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.

Thanks.

Christian

___________________________________________________________________________

Christian Collberg | Email: c_collberg@cs.auckland.ac.nz

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 |

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.