Re: Parser testing while grammar rules are unknown

0x0badf00d <0x0badf00d@gmail.com> writes:


> 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.


This sounds like you are considering "mutation testing".


It is one way to attempt to validate a parser. In the end, you will
eventually end up defining a grammar for your language, whether
consciously or not.


As the other poster comments "machine learning" of a grammar is
diificult, with most of the papers in the field showing "negative
results" i.e. proving you cannot automatically learn langauges beyond
trivial complexity from samples even when you have both positive and
negative cases, unless one makes other extremely strong assumptions.


The side-effect of this, is that you really won't know how good your
parser is solely by mutation testing. All you can be certain if you
pass a set of tests is that you haven't found the bugs yet.


On the other hand, there isn't something better than mutation testing
to use in its place if you have an unknown (unformalized) language.
If you consciously attempt to formalize the language (i.e. attempt to
write down an unambiguous grammar for it), review the grammar, and
test it as you describe, that's about as good as you are going to do.
The good news is that if you formalize the grammar, you have "written
down the law", so that the things which make the legal system work:
precedent, appeals, et al will apply.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

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