Any tools can randomly generate the source code according to a language grammar?

Question

A C program source code can be parsed according to the C grammar(described in CFG) and eventually turned into many ASTs. I am considering if such tool exists: it can do the reverse thing by firstly randomly generating many ASTs, which include tokens that don't have the concrete string values, just the types of the tokens, according to the CFG, then generating the concrete tokens according to the tokens' definitions in the regular expression.

I can imagine the first step looks like an iterative non-terminals replacement, which is randomly and can be limited by certain number of iteration times. The second step is just generating randomly strings according to regular expressions.

Is there any tool that can do this?

Answer 1

The "Data Generation Language" DGL does this, with the added ability to weight the probabilities of productions in the grammar being output.

In general, a recursive descent parser can be quite directly rewritten into a set of recursive procedures to generate, instead of parse / recognise, the language.

Answer 2

Given a context-free grammar of a language, it is possible to generate a random string that matches the grammar.

For example, the nearley parser generator includes an implementation of an "unparser" that can generate strings from a grammar.

The same task can be accomplished using definite clause grammars in Prolog. An example of a sentence generator using definite clause grammars is given here.