Grammars and Mimicry - Disappearing Cryptography - page 98

Terminal s This is the technical term for the word or sentence frag-
ments that are used to put together the final output. Think of
them as the patterns printed on the puzzle fragments. The ter-
minals will often be called words or phrases .

Var iables These are used as abstract versions of decisions that will
bemade later. They're very similar to the variables that are used
in algebra or programming. They will be typeset in boldface like
this: variable .

Productions These describe how a variable can be converted into
different sets of variables or terminals. The format looks like
this:

variable → words phrase.

That means that a variable can be converted into either words
or a phrase. The arrow (

→ ) stands for conversion and the dou-

ble vertical line ( ) stands for “or”. In this example, the right-

hand side of the equation only holds terminals, but there can
be mixtures of variables as well. You can think of these produc-
tions as rules for fitting puzzle pieces together.

The basic idea is that a grammar describes a set of words known
as terminals and a set of potentially complex rules about how they
go together. In many cases, there is a fair bit of freedom of choice in
each stage of the production.
In this example the variable could be converted into either words
or a phrase. This choice is where the information will be hidden.
The data will drive the choice in much the same way that a random
number generator drives a fake computerized poetry machine. The
data can be recovered through a reverse process known as parsing .
Here's a sample grammar:

Start → noun verb

noun → Fred Barney Fred and Barney

verb → went fishing. went bowling.

By beginning with the Start variable and applying productions to
convert the different variables, the grammar can generate sentences
like “Fred and Barney went fishing.” This is often written with a
squiggly arrow ( ) representing a combination of several different

productions like this: Start Fred and Barney went fishing. Another

way to state the same thing is to say: The sentence “Fred and Barney
went fishing” is in the language generated by the grammar. The order
of the productions is arbitrary and in some cases the order can make
a difference (it doesn't in this basic example).