Uniform Random Sampling of Strings from ContextFree Grammar
In the previous post I talked about how to generate input strings from any given contextfree grammar. While that algorithm is quite useful for fuzzing, one of the problems with that algorithm is that the strings produced from that grammar is skewed toward shallow strings.
For example, consider this grammar:
Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.
To generate inputs, let us load the limit fuzzer from the previous post.
The Fuzzer
The generated strings (which generate random integers) are as follows
As you can see, there are more single digits in the output than longer integers. Almost half of the generated strings are single character. If we modify our grammar as below
and run it again
you will notice a lot more three digit wide binary numbers are produced. In
fact, now, more than one third of the generated strings are likely to be three
digits. This is because of the way the grammar is written. That is, there are
three possible expansions of the <digits>
nonterminal, and our fuzzer
chooses one of the expansions with equal probability. This leads to the skew
in the inputs we see above.
This is interesting, but why is it a problem for practitioners? Consider these
two grammars.
Now, let us look at the generated strings. The first:
And the second:
Notice that both grammars describe exactly the same language, but the first one has a higher proportion of multiplications and divisions while the second one has a higher proportion of additions and subtractions. This means that the effectiveness of our fuzzers is determined to a large extent by the way the contextfree grammar is written. Another case is when one wants to compare the agreement between two grammars. I talked about this before. As you can see from the above cases, the same language can be described by different grammars, and it is undecidable in general whether two contextfree grammars describe the same language ^{1}. So, we will have to go for statistical means. To start with, we need to be able to randomly sample from the strings that can be produced from the grammar. So, the minimal requirement is as follows:

We need to be able to randomly sample a string that can be generated from the grammar. To make this happen, let us split this into two simpler requirements:

We can find the number of strings of a given size that can be produced from the grammar.

We can enumerate the strings that can be produced from the grammar, and pick a specific string given its index in the enumeration. Once we have both these abilities, then we can combine them to provide random sampling of derived strings. So, let us see how to achieve that.
A Naive Implementation.
Counting the number of strings
Let us first implement a way to count the number of strings that can be possibly generated.
We first implement key_get_num_strings()
to
count the number of strings of a given size l_str
generated by a token.
For finding the number we first check if the given token is a terminal
symbol. If it is, then there is only one choice. That symbol is the string.
The constraint is that the length of the string should be as given by l_str
.
if not, the total number of strings that can be generated from this token is
the total number of strings we can generated from each individual expansion.
Next, we implement rule_get_num_strings()
which counts the number of strings
of given size l_str
that can be generated by a rule (an expansion of a nonterminal).
Here, we treat each rule as a head followed by a tail. The token is the first
symbol in the rule. The idea is that, the total number of strings that can be
generated from a rule is the multiplication of the number of strings that can
be generated from the head by the total strings that can be generated by the
tail.
The complication is that we want to generate a specific size string. So, we
split that size (l_str
) between the head and tail and count strings
generated by each possible split.
Using it.
Generation of strings
Let us next implement a way to generate all strings of a given
size. Here, in get_strings_of_length_in_definition()
, we pass in the key,
the grammar and the length of the string expected.
For generating a string from a key, we first check if it is a terminal
symbol. If it is, then there is only one choice. That symbol is the string.
The constraint is that the length of the string should be as given by l_str
.
if not, then we find all the expansion rules of the corresponding definition
and generate strings from each expansion of the given size l_str
; the
concatenation of which is the required string list.
Next, we come to the rule implementation given by get_strings_of_length_in_rule()
Here, we treat each rule as a head followed by a tail. The token is the first
symbol in the rule. The idea is that, the strings that are generated from this
rule will have one of the strings generated from the token followed by one of
the strings generated from the rest of the rule. This also provides us with the
base case. If the rule is empty, we are done.
if it is not the base case, then we first extract the strings from the token
head, then extract the strings from the tail, and concatenate them pairwise.
The complication here is the number of characters expected in the string. We
can divide the number of characters — l_str
between the head and the tail.
That is, if the string from head takes up x
characters, then we can only
have l_str  x
characters in the tail. To handle this, we produce a loop
with all possible splits between head and tail. Of course not all possible
splits may be satisfiable. Whenever we detect an impossible split — by
noticing that s_
is empty, we skip the loop.
Using it.
The problem with these implementations is that it is horribly naive. Each call recomputes the whole set of strings or the count again and again. However, many nonterminals are reused again and again, which means that we should be sharing the results. Let us see how we can memoize the results of these calls.
A Memoized Implementation.
Counting the number of strings
We first define a data structure to keep the key nodes. Such nodes help us to
identify the corresponding rules of the given key that generates strings of
l_str
size.
We also define a data structure to keep the rule nodes. Such rules contain
both the head token
as well as the tail
, the l_str
as well as the count
globals
Populating the linked data structure.
This follows the same skeleton as our previous functions. Firt the keys
Now the rules.
Using it.
We can of course extract the same things from this data structure
Count
Using it.
Strings
Using it.
Random Access
But more usefully, we can now use it to randomly access any particular string
Using it.
Random Sampling
Once we have random access of a given string, we can turn it to random sampling.
This is random sampling from restricted set — the set of derivation strings
of a given length. How do we extend this to lengths up to a given length?
The idea is that for generating strings of length up to n
, we produce and
use nonterminals that generate strings of length up to nx
where x
is the
length of first terminals in expansions. This means that we can build the
key_node
data structures recursively from 1 to n
, and most of the parts
will be shared between the key_node
data structures of different lengths.
Another issue this algorithm has is that it fails when there is left
recursion. However, it is fairly easy to solve as I showed in a previous
post.
The idea is that there is a maximum limit to the number of useful recursions.
Frost et. al.^{2} suggests a limit of m * (1 + s)
where m
is the number of nonterminals in the grammar and s
is the length of input.
So, we use that here for limiting the recursion.
Using it.
What about a leftrecursive grammar? Here is an example:
Using it.
There are a few limitations to this algorithm. The first is that it does not take into account epsilons – that is empty derivations. It can be argued that it is not that big of a concern since any contextfree grammar can be made epsilon free. However, if you are not too much worried about exactness, and only want an approximate random sample, I recommend that you replace empty rules with a rule containing a special symbol. Then, produce your random sample, and remove the special symbol from the generated string. This way, you can keep the structure of the original grammar. The next limitation is bigger. This implementation does not take into account ambiguity in grammar where multiple derivation trees can result in the same string. This means that such strings will be more likely to appear than other strings. While there are a number of papers ^{3} ^{4} ^{5} ^{6} ^{7} that tackle the issue of statistical sampling, with better runtime and space characteristics, we are not aware of any that fixes both issues (Gore et al.^{8} is notable for showing an almost uniform random sampling result). Bertoni et al. shows^{9} shows that for some inherently ambiguous languages, the problem becomes intractable.
The code for this post is available here.
References

BarHillel, Yehoshua, Micha Perles, and Eli Shamir. “On formal properties of simple phrase structure grammars.” STUFLanguage Typology and Universals 14.14 (1961): 143172. ↩

Richard A. Frost, Rahmatullah Hafiz, and Paul C. Callaghan. Modular and efficient topdown parsing for ambiguous left recursive grammars. IWPT 2007 ↩

Madhavan, Ravichandhran, et al. “Automating grammar comparison.” Proceedings of the 2015 ACM SIGPLAN International Conference on ObjectOriented Programming, Systems, Languages, and Applications. 2015. ↩

McKenzie, Bruce. “The Generation of Strings from a CFG using a Functional Language.” (1997). ↩

McKenzie, Bruce. “Generating strings at random from a context free grammar.” (1997). ↩

Harry G. Mairson. Generating words in a contextfree language uniformly at random. Information Processing Letters, 49(2):95{99, 28 January 1994 ↩

Hickey, Timothy, and Jacques Cohen. “Uniform random generation of strings in a contextfree language.” SIAM Journal on Computing 12.4 (1983): 645655. ↩

Gore, Vivek, et al. “A quasipolynomialtime algorithm for sampling words from a contextfree language.” Information and Computation 134.1 (1997): 5974. ↩

Bertoni, Alberto, Massimiliano Goldwurm, and Nicoletta Sabadini. “The complexity of computing the number of strings of given length in contextfree languages.” Theoretical Computer Science 86.2 (1991): 325342. ↩