Re: Syntax Directed Test Generation

, Chuck Swart writes:
> I am interested in the following problem: Given a grammar in BNF (or
> perhaps EBNF) automatically generate a set of test cases which will
> cause all productions in the grammar to be used when these test cases
> are parsed.
>


I wrote a tool to do this a while ago. It had two phases:


1. Generate a lot of symbol strings that have full production
coverage. Start by building a mapping from symbols to the productions
that use them, which is really just your grammar (forgive me, this is
just a trivial data structure thing.) Begin with the start symbol in
a string (list, whatever) and begin a bredth first visitation of all
the productions it maps to. Apply the production to the string and
spawn the result into a new "thread." For each resultant string
repeat this process, using any production applicable to any
nonterminal in the string. Keep production visitation statistics, and
avoid applying any production that has already been used n times (I
used n=2 just to be extra thorough.) Store any string that has
reached a dead end (ie. it is all terminals, or any applicable
productions have already been used.) This process could be likened to
a game space search, where we store off the leaf nodes.


2. For each nonterminal in the grammar, build a mapping to a string of
terminals. (Or for speed's sake, just do this for the set of
nonterminals found in the strings generated in part 1.) Avoiding the
bredth first search done in part 1, I went with a heuristic search.
For each string in the tree (starting from the nonterminal being
mapped,) I calculated a weight (w = 2n + t, where w is the weight, n
is the number of nonterminals in the string, and t is the number of
terminals) for each string. Sorting a list of strings (each one a
thread in our search) by this weight, I would spawn strings from only
the first string on the list (the one with the lowest weight.) I
stopped when I found a string of all terminals, and entered the string
in my map. In later iterations of this process I apply any terminal
string substitutions already found in the map. Finally, I apply the
mapping to all nonterminals in all the strings generated in part one.


I'm sure there are more efficient ways, and I am sure there are ways
capable of generating prettier terminal symbol strings, but hey, it
worked. The problem I had with this (in terms of overall compiler
testing) was that the semantics would get me when I ran this through
anything but syntax analysis state machines. (I got good coverage in
the state machine though.)


I hope this helps, and wish I could make this clearer.


Jon
--

Return to the comp.compilers page.
Search the comp.compilers archives again.