Re: Syntax Directed Test Generation

Chuck Swart <cswart@glacier.analogy.com> wrote:
>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.
>
>Although 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.


I will suggest "The Icon Programming Language" by Griswold ISBN
0-13-447889-4 as the most useful. There is a section on generating
random sentences in a grammar.


I used these methods to test code generation in a C compiler. Since
most problems occurred in fairly complex constructs we couldn't
exhaust things but simply did large random explorations.


Let me suggest a useful trick in the area. Instrument the compiler so
that when it uses code table entries or tree modification rules it
marks a table and writes the table out on exit. Now keep track of
unmarked table entries and attempt to build tests to mark
everything. We did this at Mark Williams. There were entries we
couldn't seem to hit and on examination every one of them was
associated with a bug.


This experience turned me into a true believer on the subject of
coverage analysis but what needs coverage is not always code.
--

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