1
$\begingroup$

In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and is deterministic. The phrase generators I am talking about rely on the grammar of the language as input so that the user does not have to recreate the rules for the grammar into a format acceptable for the tool. The tool must accept a BNF grammar; I don't mind if the grammar has to be factored some for the tool before input. Tools that rely on a seed or generate a random seed are what I want to avoid.

I am aware that one can use PROLOG to generate a parser and then run a query that outputs a set of results that are phrases used for testing. I also know that it is not uncommon for these result sets to have 10**15 answers for basic cases of a grammar like C++.

Does anyone know of such tools? They can be commercial or open-source as I don't plan on using it, I have my own, I just want to verify my knowledge.

EDIT

The tool must encompass sematic knowledge of the compiler. In other words the phrases must be able to be compiled by a compiler, not just pass the syntactic rules.

EDIT

I agree that the comments and answers regarding deterministic are correct and I my use of the word here is not correct.

What I am looking for is a tool that not only takes in a BNF grammar and can use it "as is" which would mean for a grammar like C++ a basic result sets with 10**30 items. That is not an accurate number but a realistic one based on a phrase generator I have that can report the number of results before generating the results. Since that size of a result set is impractical, I have given the tool the ability to enhance the grammar with constraints, thinking tree pruning. This allows one to generate phrases for one particular branch of the grammar, and also prune and limit the sub-braches and number of recursion over those branches. Even with the constraints each result item is a valid C++ file for use as input to a C++ compiler.

I have a proof of concept of this already, but the difference between a proof of concept and useful tool is a lot of work. So while a seed can be reused and create deterministic results, it does not allow the user to determine the conditions.

Improve this question
$\endgroup$
4
  • $\begingroup$ To be clear, you want a tool that generates words a given grammar can create? That should be simple enough to write, if you have a parser for BNF (which is out there, I guess). $\endgroup$
    – Raphael
    Commented Sep 23, 2012 at 16:22
  • $\begingroup$ @Raphael I have written one, for snytax rules only they are a easy. When you start to add sematic rules, etc. they get hard. What I want to know is if anyone has created one that does sematics also and doesn't use or generate a seed. $\endgroup$
    – Guy Coder
    Commented Sep 23, 2012 at 18:18
  • 5
    $\begingroup$ You could look at QuickCheck for either Haskell or Scala. Also, if you have a random phrase generator, if you use the same random number seed on each run, it is effectively deterministic. $\endgroup$
    – Dave Clarke
    Commented Sep 23, 2012 at 18:25
  • $\begingroup$ @DaveClarke That would give him a nice tool/suite to perform the tests, but he would still have to write the generator. $\endgroup$
    – Raphael
    Commented Sep 23, 2012 at 21:24

1 Answer 1

Reset to default
4
$\begingroup$

The tools you refer to are probably already deterministic. Tools that accept a seed probably only employ a pseudorandom generator which is keyed from the seed and nothing else. Therefore, given the seed, everything is completely deterministic. If the seeding process is reasonable, then a seed like $0$ or $1$ should work. For definiteness, I suggest you take your favorite "random" tool and use a fixed seed, say $1$. Now it's completely deterministic.

One reason you'd want a deterministic tool is reproducibility. You want to be able to reproduce phrases on demand. If the tool is random, that's impossible. However, if all the "randomness" is encapsulated in a user-entered seed, the output is reproducible; all you have to do is remember the seed used.

I cannot think of any other reason you'd want your tool to be deterministic, but if there is one, please let us know so that we can understand your question better.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.