Re: Syntax Directed Test Generation

cswart@glacier.analogy.com (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.
>
>Altthough there are some interesting issues (such as how to deal with
>terminals, iterations in EBNF, unreachable productions, and
>productions which can't yield terminal strings, etc,) this seems like
>a fairly obvious problem which probably has already been investigated.


Charles Wetherell wrote a paper on something like this for *Computing
Surveys* back in the early 1980s that might be of interest. I believe
that he attached probabilities to the alternatives in productions.


(At this point I can't resist saying that I regret losing my copy of
Wetherell's lovely book *Programming Etudes*, and wish he'd consider
coming out with an updated edition.)


Back about that time, I wrote a parser for BNF extended with what I've
seen called the "shuffle operator," which if I remember rightly is
purely a convenience, i.e. a <shuffle> b is equivalent to ab | ba,
though with enough things being shuffled, the convenience increases
considerably. :-) Once the grammar was parsed, the program would
generate a random sentence with it. It was easy enough to put
together, admittedly ignoring some of the issues you mention.


James Jones
--

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