Generating samples from grammar

[mlajtos]

Hello,

would it make sense for other people if there was a way to generate samples from the grammar?

In the editor (or dev env) I have samples that I know that should be (un)parsable, however I would like to be able to see what kind of weird cases grammar allows and then either disallow them or further explore them if they make sense.

Have you thought about this before? Would it be valuable to you?

[pdubroy]

In general, yes — imo this is something that's interesting and valuable!

It's actually something that we experimented with in the past. You can see a brief description of what we did in the Ongoing work section of our paper Language Hacking in a Live Programming Environment. As mentioned there, one of the challenges of a purely-generative approach is how to generate the most useful examples. Maybe there are some useful techniques from fuzz-testing tools like afl that could be adopted (just a guess though).

The code that support generating examples from removed from the code base a while back as it wasn't being used anywhere, but I'd be happy to point you to it, and if we could resurrect it in a useful way (e.g. actually exposing the functionality in the editor or behind an API) I'd be happy to.

[mlajtos]

Oh, I have never read that paper, really nice ideas in the on-going part, I dig the vertical visualization.

I was thinking along the same line as your proposed madlibs algorithm. Provide bottom values and generate all possible trees. You say that the generated examples are not as interesting, or what problem have you encountered with them please?

Edit: You mention "most useful examples". For me that just means that I want to see all minimal examples and whatever catch my attention, that is most useful. However, I don't know how to express that algorithmically.

Related: Yesterday I was trying ChatGPT to generate grammar (it sucks, makes lot of mistakes) and generate some examples (pretty okay). However probably not worth pursuing.

[pdubroy]

What I meant by "useful" is that there is a very large state space, and you ideally want the generated examples to be the most interesting/insightful. With the approach described in the paper — augmenting and recombining user-provided examples — we assume that the user provided examples are interesting, and that simple combinations are also likely to be interesting...but you still have the same problem to some degree.