<p>You might be interested in <a href="https://en.wikipedia.org/wiki/Sequitur_algorithm" rel="nofollow noreferrer">Sequitur</a> (given a single string, it compresses it by finding a grammar that generates just that one string) or in <a href="https://en.wikipedia.org/wiki/Grammar_induction" rel="nofollow noreferrer">grammar induction</a> (given a set of strings, it finds a grammar that can generate all of those strings).
See</p>
<ul>
<li><p><a href="https://cstheory.stackexchange.com/q/41926/5038">What is the current state of the art in black-box grammar induction?</a>,</p>
</li>
<li><p><a href="https://cs.stackexchange.com/q/64556/755">https://cs.stackexchange.com/q/64556/755</a>,</p>
</li>
<li><p><a href="https://cs.stackexchange.com/q/53279/755">https://cs.stackexchange.com/q/53279/755</a>.</p>
</li>
</ul>

CC BY-SA 4.0
2023-10-13T08:00:29.720Z
2023-10-13T10:02:56.637Z
2023-10-13T10:02:56.637Z
D.W.
<p>Given a string generated with a valid grammar, how can I find list of all the valid grammar for that particular string?</p>
<p>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.</p>

CC BY-SA 4.0
2023-10-13T06:11:47.120Z
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.
Andrej Bauer
CC BY-SA 4.0
2023-10-13T10:22:02.423Z
If you want to challenge yourself, why not participate in our (regular) grammar induction challenge [https://codalab.lisn.upsaclay.fr/competitions/15096](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](https://arxiv.org/abs/2308.07899). (The overall aim of this work quantification of learning algorithms for programs.)
Martin Berger
CC BY-SA 4.0
2023-10-13T10:38:11.100Z
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*](https://en.wikipedia.org/wiki/Language_identification_in_the_limit).
Martin Berger
CC BY-SA 4.0
2023-11-26T09:15:37.990Z
@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!
Vetrivel
CC BY-SA 4.0
2023-11-26T09:15:52.757Z
@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.
Vetrivel
CC BY-SA 4.0
2023-11-26T09:15:56.563Z
I have had a little progress on this, instead of solving this problem, I tried to solve how to trace the control flow and data flow in a code base. I have been running in circles, and I realised, if I trace the source of a data from a leaf, the problem is sovled, in the sense, If I click on a variable, the tracer will trace back code in reverse to find where it imported its data from.
Vetrivel
CC BY-SA 4.0
2023-11-26T09:28:31.477Z
@MartinBerger the place has too much information there and mis direct me. In my opinion, input+function = output is conventional programming. input+output = function is machine learning. so the technique is irrelevant because solving problem then applying the technique will result in a simple solution.
Vetrivel
CC BY-SA 4.0
2023-11-26T13:12:06.297Z
@Vetrivel I don't understand what you mean by *"place has too much information there and mis direct me"*. Our challenge is *exactly* about building grammars (in this case regular grammars) from example strings.
Martin Berger
CC BY-SA 4.0
2023-11-28T07:11:37.897Z
@MartinBerger I meant to say, It took me some years to adjust with stackoverflow interface. and I'm finding it difficult to read information because of the visual interface.
Vetrivel
CC BY-SA 4.0
2023-11-28T12:54:18.373Z
@Martinberger I solved the problem I wanted to solve in a different way. Instead of reducing code base size alternatively if I trace the data source or the data flow in reverse I can fetch all the lines at different time of order of execution. That was just a piece of a bigger problem
Vetrivel
<graph-algorithms><fl.formal-languages><pl.programming-languages><grammars><compilers>
Generating grammar from a string
Vetrivel
# Generating grammar from a string

(Asked by: username_0 on 2023-10-13)

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.

**Tags:** graph-algorithms, fl.formal-languages, pl.programming-languages, grammars, compilers
> **Comments:**
> **username_1**: 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.  
> **username_2**: If you want to challenge yourself, why not participate in our (regular) grammar induction challenge [https://codalab.lisn.upsaclay.fr/competitions/15096](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](https://arxiv.org/abs/2308.07899). (The overall aim of this work quantification of learning algorithms for programs.)  
> **username_2**: 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*](https://en.wikipedia.org/wiki/Language_identification_in_the_limit).  
> **username_0**: @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!  
> **username_0**: @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.  
> **username_0**: I have had a little progress on this, instead of solving this problem, I tried to solve how to trace the control flow and data flow in a code base. I have been running in circles, and I realised, if I trace the source of a data from a leaf, the problem is sovled, in the sense, If I click on a variable, the tracer will trace back code in reverse to find where it imported its data from.  
> **username_0**: @MartinBerger the place has too much information there and mis direct me. In my opinion, input+function = output is conventional programming. input+output = function is machine learning. so the technique is irrelevant because solving problem then applying the technique will result in a simple solution.  
> **username_2**: @Vetrivel I don't understand what you mean by *"place has too much information there and mis direct me"*. Our challenge is *exactly* about building grammars (in this case regular grammars) from example strings.  
> **username_0**: @MartinBerger I meant to say, It took me some years to adjust with stackoverflow interface. and I'm finding it difficult to read information because of the visual interface.  
> **username_0**: @Martinberger I solved the problem I wanted to solve in a different way. Instead of reducing code base size alternatively if I trace the data source or the data flow in reverse I can fetch all the lines at different time of order of execution. That was just a piece of a bigger problem  

---

## 1 answers

### Answer by username_3 on 2023-10-13. Score: 3

You might be interested in [Sequitur](https://en.wikipedia.org/wiki/Sequitur_algorithm) (given a single string, it compresses it by finding a grammar that generates just that one string) or in [grammar induction](https://en.wikipedia.org/wiki/Grammar_induction) (given a set of strings, it finds a grammar that can generate all of those strings).
See

* [What is the current state of the art in black-box grammar induction?](https://cstheory.stackexchange.com/q/41926/5038),
* <https://cs.stackexchange.com/q/64556/755>,
* <https://cs.stackexchange.com/q/53279/755>.


---

