Re: How to verify a parser from the language grammar

Shahid Alam <salam3@connect.carleton.ca> 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?
> -John]


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.


Torben

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