Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!decwrl!world!iecc!compilers-sender
From: pg@bsg.com (Peter Garst)
Newsgroups: comp.compilers
Subject: Strings derivable from a grammar
Keywords: yacc, parse, testing
Message-ID: <1991Apr25.015657.1060@iecc.cambridge.ma.us>
Date: 24 Apr 91 15:34:52 GMT
References: <1991Apr23.140427.5416@iecc.cambridge.ma.us>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: pg@bsg.com (Peter Garst)
Organization: Compilers Central
Lines: 29
Approved: compilers@iecc.cambridge.ma.us

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.