pg@bsg.com (Peter Garst) (04/24/91)
Ed King asks about generating strings described by a grammar. Our grammar tool, ydb, does this, using approximately the following method: 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 terminal strings). 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 derivable strings. 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. Peter Garst pg@bsg.com -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.