|How to verify a parser from the language grammar email@example.com (Shahid Alam) (2007-01-09)|
|Re: How to verify a parser from the language grammar cfc@shell01.TheWorld.com (Chris F Clark) (2007-01-11)|
|Re: How to verify a parser from the language grammar firstname.lastname@example.org (2007-01-11)|
|Date:||11 Jan 2007 09:04:28 -0500|
|Organization:||Department of Computer Science, University of Copenhagen|
|Posted-Date:||11 Jan 2007 09:04:28 EST|
Shahid Alam <email@example.com> writes:
> Does anybody know of any tool that lets you validate and verify your
> parser (hand implemented) from the BNF grammar of the language.
> [I doubt it. It's wouldn't be hard to contrive test cases that
> exercise all of the rules in a BNF grammar, but how are you going to
> test that the parser rejects everything that's not in the grammar?
And it would, in fact, be impossible. If you could do the above, you
could decide equivalence of grammars, which isn't computable.
The next best thing is to use the grammar to generate a lot of correct
strings and test them on your parser. That would, however, not reveal
if the parser accepts strings not defined by the grammar. To test
such false positives, you could try a number of random strings on both
the parser and the grammar, but you are unlikely to reveal subtle
errors that way. A slightly better approach would be to "mutate"
strings generated by the grammar and see if the parser and grammar
agree on these.
Return to the
Search the comp.compilers archives again.