|Syntax Directed Test Generation email@example.com (1997-04-22)|
|Re: Syntax Directed Test Generation firstname.lastname@example.org (Charles Fiterman) (1997-04-30)|
|Re: Syntax Directed Test Generation email@example.com (1997-05-03)|
|Re: Syntax Directed Test Generation firstname.lastname@example.org (1997-05-04)|
|Syntax Directed Test Generation Dave@occl-cam.demon.co.uk (Dave Lloyd) (1997-05-04)|
|Re: Syntax Directed Test Generation email@example.com (1997-05-08)|
|Re: Syntax Directed Test Generation firstname.lastname@example.org (1997-05-08)|
|From:||email@example.com (James Jones)|
|Date:||8 May 1997 00:56:41 -0400|
|Organization:||Microware Systems Corp., Des Moines, Iowa|
firstname.lastname@example.org (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
>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.
Return to the
Search the comp.compilers archives again.