-1
$\begingroup$

Given a string generated with a valid grammar, how can I find list of all the valid grammar for that particular string?

Problem statement - I'm trying to build a code base scanner, and I'd like to build it independent of language such as javascript / typescript. Instead of writing the grammar rules my self, I wanted to try a challenge of building something that can generate the grammar out of it.

$\endgroup$
10
  • 2
    $\begingroup$ Two comments. First, you certainly do not want all grammars, because that's too many. Second, do you real mean to say that you have a single example? If you can provide many examples, then there ought to be machine-learning tools. $\endgroup$ Oct 13, 2023 at 6:11
  • $\begingroup$ If you want to challenge yourself, why not participate in our (regular) grammar induction challenge https://codalab.lisn.upsaclay.fr/competitions/15096. It's remarkably easy to get started, a basic solution can be written in a few lines of code (although it won't perform well on larger examples). Associated paper: https://arxiv.org/abs/2308.07899. (The overall aim of this work quantification of learning algorithms for programs.) $\endgroup$ Oct 13, 2023 at 10:22
  • $\begingroup$ Note that grammar induction is one of the oldest fields in machine learning, going back, at least, to Gold's 1960s work on Language identification in the limit. $\endgroup$ Oct 13, 2023 at 10:38
  • $\begingroup$ @MartinBerger thanks for the invite. I'm interested ! Rather than writing a script that runs on large code base, I want to build an interface where the logic can be created dynamically and run indefinitely. Looks to me that both this question and that challenge are the same! $\endgroup$
    – Vetrivel
    Nov 26, 2023 at 9:15
  • $\begingroup$ @AndrejBauer I'm trying some ideas for code base size reduction. Generating all the grammar will be redundant, so I'll be throwing up the patterns on an infinite 2d space where I can build interaction to mark a valid grammar, reject / ignore an existing grammar. In other words it is a sub graph detection as well, and idea is to figure out a technique to define a sub graph and let the background script detect such patterns. $\endgroup$
    – Vetrivel
    Nov 26, 2023 at 9:15

1 Answer 1

3
$\begingroup$

You might be interested in Sequitur (given a single string, it compresses it by finding a grammar that generates just that one string) or in grammar induction (given a set of strings, it finds a grammar that can generate all of those strings). See

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.