Re: Parser testing while grammar rules are unknown

On Saturday 14 Mar 2009 22:49, 0x0badf00d wrote:
> Let's say, we have language somehow similar to ADA. And we have a parser
> /compiler for this language. And we know it contain bugs.
> We do not have grammar rules for language, instead, we have a tons of
> source code written in this language.
> We would like to test parser against possible bugs. We could take source
> code, alter it slightly and pass to parser and see, if it will return
> error.


You don't have a parser which is known to be correct, or a collection
of source files which are known to be incorrect. You only have a set
of source files which are known to be correct. So, if you alter a
correct source file you will have no way of knowing whether the
altered file is still correct or incorrect. So you have no way of
knowing whether your parsers response (acceptance or error message) is
the correct response.


Currently, your specification of the grammer is "this set of source
files are valid". So, a correct parser simply has to read the source,
compare it against the list of valid source files, and return "valid"
(if the given source is in the list), or "invalid" (if the given
source is not in the list).


"But", you reply, "there are other files, not in the list, which are
also valid". Well, if a correct parser is allowed to return "valid"
for source files not in the list, then the problem is even easier to
solve: simply return "valid" for all source files!


"But", you reply, "there are other files, not in the list, which are
invalid". If you had a large collection of such files, then the
problem becomes: "Find a small grammar which accepts all the files in
the valid list and rejects all the files in the invalid list". This is
a computable problem, but not necessarily an easy one.


But since you have no list of invalid files to work with, you are
stuck!
--
Martin
martin@gkc.org.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/

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