Skip to main content
Explain what was meant with the word deterministic since I should not have used that word.
Source Link
Guy Coder
  • 5.1k
  • 2
  • 29
  • 65

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.

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.

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.

Tweeted twitter.com/#!/StackCompSci/status/250069077203247104
edited tags
Link
Clarify need of tool to have semantic knowledge.
Source Link
Guy Coder
  • 5.1k
  • 2
  • 29
  • 65

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.

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.

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.

Source Link
Guy Coder
  • 5.1k
  • 2
  • 29
  • 65
Loading