BNF Example Generator

BNF example generator

The Generator

The BNF language

In this simple generator, a variety of BNF is used which is defined as follows:

each rule is written on a separate line.
each rule is in the form of :
term = expression
an expression can be :
- a sequence separated by spaces, representing a sequence
- a sequence separated by | , representing a selection
- a single word enclosed in { }, representing an iteration.
a word used in a expression which has a matching rule is called a non-terminal. A non-terminal may have only one matching rule.
a word used in an expression which does NOT have a matching rule, or is enclosed in ' ' or " " is a terminal.

Distributions

To provide better control on the generated data, you can also control the random distribution used. This is specified on the same line as the rule, following a #

selections. By default the choice is uniform - the first is as likely to be chosen as the last. However, a more natural set of data is generated if the options are ranked in decreasing order of frequency of occurance, and the letter Z specified as the distribution. This uses the Zipfian distribution, which is a mathematical function which provides quite a good approximation to the distribution of letters in the English language for example. e.g.
```
char = 'E' | 'T' | 'A' | 'O' | 'N' | 'I' |  'S' | 'R' 
       | 'H' | 'L' | 'D' | 'C' | 'U' | 'P' | 'F' | 'M' | 
       'N' | 'W' | 'Y' | 'B' | 'G' | 'V' | 'K' | 'Q' | 'X' | 
       'J' | 'Z'  # Z 
```
iteration. By default the choice of each iteration is the same - 0.5. Thus the distribution of the number of iterations is Binomial. The probability can be altered by specifying B and then a number less than 1 as teh distribution e.g.
```
adverbs = { adverb} # B 0.7
```
Additionally, the { } may be preceeded by an integer - the minimum iterations, and followed by an integer - the maximum number of iterations. If only the minimum is specified, the number of iterations will be the minimum followed by a binomial distribution. If both minimum and maximum are specified, the number of iterations is uniformly distributed between the two values.
```
digits = 3 { digit } 5
```

The BNF definition of BNF

The BNF definition

The random generator program

The program bnf2sent.cgi generates sentences randomly using a grammar defined using BNF. Starting with the first rule in the sequence, rules are expanded. Where there is a selection, a choice is made randomly between the alternatives. Where there is an iteration, the iteration will be repeated a random number of times (actually Binomial with a probability of 0.5 by default). As the sentence is expanded, words are matched to rules. If there is no matching rule for a word, the word itself is printed (as a terminal). If a rule is found (a non-terminal) the associated rule is then used in further expansion.

A version of this program can run in batch to generate a text file. This enables test data to be generated, perhaps to load a database to test for performance.

Examples

Some example BNF definitions