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.
Asked By : Guy Coder
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/4692
0 comments:
Post a Comment
Let us know your responses and feedback