Grammars and Mimicry - Disappearing Cryptography - page 109

7.3.1 Parsing the Output

The code in the class MimicParser handles the job of converting
mimicry back into the bits that generated it. Parsing the output from
a context-free grammar is a well-understood problem and is covered
in depth in the computer science literature. The best parsers can
convert any text from a grammar back into a sequence of produc-
tions that lead to the text. The most general parsing algorithms like
the CYK algorithm are slow.[HU79]
The parsing algorithm implemented in this code is a compro-
mise. It will only work on grammars that are in a limited version
of Greibach Normal Form. This form requires that any variables be
placed at the end of each production. Page 110 shows some exam-
ples. The form required by this parser is even stricter because it must
be easy to determine which choice was made by examining the first
words of a production. This means that no two choices from the
same variable may have the same first

is adjustable, but
the larger it gets, the slower the algorithm can become.
This format makes parsing substantially easier because the parser
only needs to look at the words and phrases. There is no need to
follow the variables and make guesses. The best way to illustrate this
is with a grammar that doesn't follow this rule. Here's a grammar that
is not in the correct format:

n words. n

Start → noun verb

noun → Fred AndFriend Fred Alone

AndFriend → and Barney went fishing where

and Barney went bowling where

Alone → went fishing where

went bowling where

where → in direction state .

→

direction northern southern

→

state Iowa. Minnesota.

Imagine that you are confronted with the sentence “Fred and
Barney went fishing in northern Iowa.” This was produced by the
bits/choices 0000. Parsing this sentence and recovering the bits is
certainly possible, butnot easy. The production “ noun

→ Fred And-

Fred Alone ” does not make it easy to determine which
choice was made. The terminal words at the beginning of each
choice are the same. They both say “Fred”. A parser would need to
examine the results of expanding the variables AndFriend and Alone
to determinewhich pathwas taken. Following these paths is feasible,
but it slows down the algorithm and adds complexity to the result.
Most serious parsers can handle this problem.

Friend