|Strings derivable from a grammar email@example.com (1991-04-24)|
|From:||firstname.lastname@example.org (Peter Garst)|
|Keywords:||yacc, parse, testing|
|Date:||Wed, 24 Apr 91 08:34:52 PDT|
Ed King asks about generating strings described by a grammar.
Our grammar tool, ydb, does this, using approximately the following
For each rule and symbol in the grammar, keep track length of the
shortest derivable string. It is 1 for terminals; then you can do all rules
with only terminals on the right hand side; and so on. Just keep going
through the grammar until each one is labeled with a length. (If there
are unlabeled items and you can't get any more, they don't derive
Then for any nonterminal it's a simple matter to get some derived strings.
For any rule defining the nonterminal, for each nonterminal on the
right hand side of the rule, you can pick a rule which you know will
lead to a terminal string eventually. This method leads to shortest
If you want to generate lots of strings for a symbol, a search algorithm
using a stack of partial derivations would be appropriate.
We've found this idea to be very useful for debugging grammars; when
you have a grammar with problems it's handy to check if the rules
really describe what you think they do.
Return to the
Search the comp.compilers archives again.