I am trying to write a program which can induce a grammar from an example of the code(really more of a corpus than an example).

I'm ignoring the decision problem, because I am doing two things that I foresee bringing that issue into play: Tokens are separated by spaces and any production rule is terminated at the newline character, and the grammar is context-free(not necessarily unambiguous).

However, the grammars being produced are inefficient because the start state goes to things like $$ S\rightarrow a bc \vee abcd \vee abce $$ The start rule contains all of the terminals, and it does so without breaking it down into anything more efficient.

Is there an algorithm that can attempt to extract the grammar in a better form(with smaller production rules)?

Or does this attempt turn into something utterly within the decidability problem?

  • $\begingroup$ What algorithm do you use to infer the grammar? If you have $n$ string $\omega_1,\ldots,\omega_n$, then "inferring" the grammer "$S \to \omega_1 \lor \omega_2 \lor \ldots \lor \omega_n$" is trivial, and rather meaningless... $\endgroup$ – fgp May 4 '14 at 20:16
  • $\begingroup$ That however is the problem, wikipedia does not link to any algorithms that do this other than ADIOS. What it attempts to do is build a table of structures that it has seen, however, in most contexts, it produces a finite grammar which only accepts the input. My algorithm is broken, which would you suggest then? $\endgroup$ – jaked122 May 4 '14 at 20:19
  • 1
    $\begingroup$ This paper seems to say that the algorithm works quite well, so maybe you've made a mistake somewhere. Or maybe the algorithm has some parameters that you have to adjust to your circumstances. In any case, the way you wrote your question you're basically asking "How do I do grammar inference". That's a far too broad and too hard question for this forum I think. I suggest you rewrite your question, and turn it into a reference request instead. People might be able to point you to publications, but they won't have a read-made answer. $\endgroup$ – fgp May 4 '14 at 21:29
  • $\begingroup$ You've answered as I had hoped. Thank you $\endgroup$ – jaked122 May 4 '14 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.