Compilers - Grammar development by example

Author

Grammar development by example

Oliver Zeigermann

2006-07-16, 4:00 am

Hi, folks!

I am looking for any work done in the field of grammar development by
example. This is about the user providing certain sentences of a
language which we want a grammar for. Maybe some more interactive work
is required.

Any hints?

Cheers and thanks in advance

Oliver

Chris F Clark

2006-07-18, 4:01 am

I believe what your are looking for is mostly categorized under the
title "machine learning". I looked at the relevant papers in that
area in the late 90's. However, as I recall much of the work is in
the negative form, i.e. "one cannot learn grammars of the form xyz
without qrst." A typical result is that one cannot even learn
complicated regular expressions without "negative examples" (examples
that say, this isn't a valid sentence)--I believe that is a correct
result. It is certainly a significant area of research in its own
right.

Hope this helps,
-Chris

****************************************
*************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

alpanad@gmail.com

2006-07-18, 4:01 am

Hi,

Following link may of interest to you:

http://www.cse.iitk.ac.in/users/alpanad/thesis.html

This talks about the extraction of grammar rules when an incompete
grammar and a set of example programs are given as input. Example
programs involve new constructs and the above work identifies the
grammar rule corresponding to new constructs.

Additionally, you can refer following work:

http://www.cis.uab.edu/softcom/GenParse/

Above work uses genetic programming model for developing grammar of a
domain specific langauge from example programs.

Best,
Alpana

Oliver Zeigermann wrote:
> Hi, folks!
>
> I am looking for any work done in the field of grammar development by
> example. This is about the user providing certain sentences of a
> language which we want a grammar for. Maybe some more interactive work
> is required.

Sylvain Schmitz

2006-07-18, 4:01 am

Oliver Zeigermann wrote:
> I am looking for any work done in the field of grammar development by
> example. This is about the user providing certain sentences of a
> language which we want a grammar for. Maybe some more interactive work
> is required.

This sounds a lot like grammatical inference (or grammar induction, or
automatic language learning). It is a fairly old subject in artificial
intelligence. A search on the Internet will bring many results that
should interest you, though I don't think what you are asking for is
possible as such.

--
Hope that helps,

Sylvain

Sponsored Links