5

What are the best (or any) open source libraries for regular or context-free grammar inference from a set of examples believed to be generated by a common grammar? I'd prefer a good library in Java, Python or Ruby, but of course beggars can't be choosers.

I did some googling, but couldn't find any actual implementations, though I did find plenty of interesting references. This library looks interesting, but I couldn't find it available for download anywhere.

Edit (2011-11-14): For clarity (though I'm not sure how you all misunderstood), the question was about grammar inference, not grammar generation or parsing. In other words, given a set of strings which accord to an unknown grammar, find the most restrictive grammar which they all satisfy.

Anderson Green
  • 30,230
  • 67
  • 195
  • 328
Lucas Wiman
  • 10,021
  • 2
  • 37
  • 41
  • A solution to this problem would require an implementation of a [DFA learning algorithm](https://stackoverflow.com/questions/15512918/grammatical-inference-of-regular-expressions-for-given-finite-list-of-representa/15519725#15519725). – Anderson Green Mar 07 '23 at 19:55

3 Answers3

4

I have not used them yet, but I had this identical question and (after much searching) found these two libraries, at very least:

Unlike the other answers to the question, these are actual grammar inference libraries rather than parser generators.

Stephen Lin
  • 5,470
  • 26
  • 48
  • Link to other question about this: http://stackoverflow.com/questions/15512918/grammatical-inference-of-regular-expressions-for-given-finite-list-of-representa/15529092 – Stephen Lin Mar 20 '13 at 17:51
-2

You can have a look at antlr - http://www.antlr.org/ and see if its what you're looking for.

d-live
  • 7,926
  • 3
  • 22
  • 16
  • That is not to do inference/induction. You are actually supposed to already *have* the language and just specify it there. – Albert Feb 25 '14 at 16:09
-2

Take a look at Parboiled: https://github.com/sirthias/parboiled It doesn't generates any sources, just create a class in your app, define a model in it, and make a call from your code.

Askar Kalykov
  • 2,553
  • 1
  • 22
  • 43