Re: Parser testing while grammar rules are unknown

Chris F Clark <>
Sun, 15 Mar 2009 21:28:20 -0400

          From comp.compilers

Related articles
Parser testing while grammar rules are unknown (0x0badf00d) (2009-03-15)
Re: Parser testing while grammar rules are unknown (russell kym horsell) (2009-03-15)
Re: Parser testing while grammar rules are unknown (Chris F Clark) (2009-03-15)
Re: Parser testing while grammar rules are unknown (Martin Ward) (2009-03-16)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Sun, 15 Mar 2009 21:28:20 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 09-03-061
Keywords: parse, testing
Posted-Date: 15 Mar 2009 21:57:23 EDT

0x0badf00d <> 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 Clark Internet:
Compiler Resources, Inc. or:
23 Bailey Rd Web Site:
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

Post a followup to this message

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