WANTED: Parser testing tools and/or random sentence generator(s).

Thread View: comp.compilers

4 messages

[T] Back to Threads [V] Tree View [G] Group Articles

4 total messages Started by rfg@netcom.com ( Thu, 22 Oct 1992 20:33

#3973

Author: rfg@netcom.com (
Date: Thu, 22 Oct 1992 20:33

38 lines
2099 bytes

Seems to me that sometime in the distant past, I may have read in this
newsgroup about some tool (or tools) which, when given a grammar specifi-
cation, would generate a whole slew of random (ostensibly valid) sentences
conforming to the given grammar.

Such a tool could (in theory) be useful (I suppose) for checking that the
grammar accepted by a given compiler conformed to the grammar which the
relevant language is supposed to have, but I could well imagine that if
the tool accepted the grammar specification as a yacc-style grammar, and
if the compiler being tested had a parser based upon the very same yacc
grammar, then (implicitly) all of the tests would pass, and you would not
learn anything new about the parser component of the compiler under test
(although you might learn some interesting things about some bizzare
semantic situations).

I however would like to obtain such a tool, feed it the grammar taken from
the C++ Annotated Reference Manual (with whatever small modifications
might be needed to get it to be an "acceptable" grammar as far as the tool
was concerned) and then use the randomly generated output sentences as
both syntactic and (perhaps) semantic torture tests for various C++
compilers (none of which are likely to have parsers based directly on the
ARM grammar).

Do such "random sentence generators" exist, or was I just imagining that I
had heard about such things in the past?  If such things exist, is there
(by any chance) one which is in the public domain or which is otherwise
freely available?  If so, how could I obtain a copy of it?  (Anon FTP
would be easiest for me.)

Please E-mail replies to me directly, as I only seem to get caught up on
my netnews reading about once a month these days.  If there are several
responses, I'll summarize those back to comp.compilers.
[This topic came up in March 1990, and there were many referencs to random
sentence generators, but I couldn't find any actual code. -John]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: WANTED: Parser testing tools and/or random sentence generator(s).

#3977

Author: leichter@zodiac.
Date: Fri, 23 Oct 1992 12:27

14 lines
691 bytes

I'm pretty sure there's a random sentence generator in the Icon library;
it may even be an example in the book.  Look around in the anonymous FTP
account on cs.arizona.edu, /pub/icon.

Note that a random sentence generator is perfectly happy with non-LR
grammars, ambiguous grammers, what have you - there's no reason to use a
YACC'ified grammer, just use the "natural" BNF.  (The only restriction is
that you have have to "weight" recursions to keep the expected length of
outputs finite.  This doesn't in any way change the language.)
							-- Jerry-
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: WANTED: Parser testing tools and/or random sentence generator(s).

#3979

Author: Glenn Kasten
Date: Fri, 23 Oct 1992 23:37

19 lines
856 bytes

rfg@netcom.com (Ronald F. Guilmette) writes:
> Seems to me that sometime in the distant past, I may have read in this
> newsgroup about some tool (or tools) which, when given a grammar specifi-
> cation, would generate a whole slew of random (ostensibly valid) sentences
> conforming to the given grammar.

I have written such a tool, called 'gen', and have also collected some
articles and even one person's PhD Thesis on the subject.  If there is
anyone else who has such tools or papers on the subject, please send me
email.  Then in a week or two, I will try to merge it together and post a
summary to this newsgroup.

Glenn Kasten
Ready Systems 470 Potrero Ave. Sunnyvale CA 94086
glenn@ready.com (408) 522-7357
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: WANTED: Parser testing tools and/or random sentence generator(s).

#3985

Author: marick@m.cs.uiuc
Date: Mon, 26 Oct 1992 18:19

37 lines
1884 bytes

One such tool is DGL, by Peter Maurer.  You can find information about
it in the comp.software-eng archives, in the test tool section.
Here's some information about those archives:

The following files are available via anonymous FTP from directory
pub/software-eng on host ftp.qucis.queensu.ca (130.15.1.100).  Log in with
user ID 'anonymous' and use your mailing address as the password. Each file
has a header (in e-mail or news format) that credits the original collector.
If you cannot use FTP, send mail to archive-server@qucis.queensu.ca containing
a line of the form
	send software-eng f1 f2 ...
where f1, f2, and so on are the names of the files from this list; the mail
server should respond within an hour or so plus mailing delays (which can
themselves be substantial if you're not directly on the internet).  If you
want to find out more about the archive server, send mail to the same address
with a line containing the word 'help'; if you do this you can't also request
files in the same message.  If your mailer has trouble with large files, use
the 'size <bytes>' command to set a threshold, above which the server will
split files into several messages.
[...]
  testTools    10 Jun 1992 Tools for testing


Another tool was done by a student I worked with, Georgios
Papagiannakopoulos.  You can fetch its source and documentation from
cs.uiuc.edu:pub/testing/gtt.tar.Z.  It doesn't generate random sentences,
but rather subsets of templates for possible sentences.  You can expand
those templates either randomly or (often better) by using
conditions-to-test from other sources.

Brian Marick, marick@cs.uiuc.edu, uiucdcs!marick, marick@testing.com (pending)
Freeware test coverage tool:  see cs.uiuc.edu:pub/testing/GCT.README
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads