//PLEASE ANSWER IN PYTHON! THANKS The purpose of this exercise is to write a syn
ID: 3716958 • Letter: #
Question
//PLEASE ANSWER IN PYTHON! THANKS
The purpose of this exercise is to write a syntax generator for a subset of the C++ programming language that will write “random” C++ programs to a file. By writing these random syntactically correct programs, you will further develop your understanding of the difference between syntax and semantics.
Consider the following set of productions that define a subset of the C++ programming language:
<prog> ::= “int main() { <stat_list> return 0; }”
<stat_list> ::= <stat>
| <stat_list> <stat>
::= <cmpd_stat>
| <if_stat>
| <iter_stat>
| <assgn_stat>
| <decl_stat>
<cmpd_stat> ::= { <stat_list> }
<if_stat> ::= if ( <exp> ) <stat>
| if ( ) <cmpd_stat>
| if ( <exp> ) <stat> else <stat>
| if ( ) <cmpd_stat> else
| if ( ) else <cmpd_stat>
| if ( ) <cmpd_stat> else <cmpd_stat>
<iter_stat> ::= while ( )
| while ( ) <cmpd_stat>
<assgn_stat> ::= = ;
<decl_stat> ::= ;
| <assgn_stat>
<exp> ::= <exp> <op> <exp>
| <id>
| <const>
<op> ::= + | - | * | /
<type> ::= int
| double
::= <chardigit_seq>
<const> ::= <digit_seq>
<char_digit_seq> ::= [empty]
| <char><char_digit_seq>
| <digit><char_digit_seq>
<digit_seq> ::= [empty]
| <digit><digit_seq>
<char> ::= [A-Z] | [a-z] | _
<digit> ::= [0-9]
If you are interested in seeing an exhaustive BNF formulation of the C programming language, please view the following: http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf. This contains over 60 productions and may be a little much for the purposes of this exercise.
Problem 1. Write a program in C, C++, C#, Java, or Python (your choice) that starts with the root non-terminal and generates a random syntactically correct C++ program using the productions defined above. You should follow the examples we saw in class where we expand non-terminals recursively until we obtain a sentence consisting of terminal tokens only. In the case where a production contains more than one expansion (i.e., right-hand-side expressions), your program should select one randomly (preferably with non-uniform weighting based on which expansions are more likely to occur in C++). Your program should write the random C++ code to an output file.
Problem 2. Run your generator (possibly a few times) to generate a random syntactically correct C++ program. You will observe that, despite the correct syntax, there are other issues that prevent this program from being correct. Please discuss some of these errors. Suppose you wish to implement a checker for detecting these errors. What sort of approach or algorithm would you use to accomplish this? There is no need to write any code for this problem.
Hint 1: The following is a sample random program that was generated by my solution. I added some white spaces to make it more readable:
int main()
{
int F0Z = 0262;
if (22682 / 525)
double S1;
else
S = U;
while (8 - 594873)
{
while (97942 / 6871573097 * 7261055)
{
while (9307 * M / 4 / 2 + 4 - 7 / K)
{
double A;
}
}
}
return 0;
}
I would recommend that you include white space characters (as appropriate) into the production rules above to make your output random program more readable. Don’t worry about indenting/tabs for the purposes of this assignment. I manually tabbed the code above.
Hint 2: I solved this problem both in C++ and Python. In Python, I was able to write the solution in less than 100 lines of code (it is a really great language). My C++ solution makes use of a class called Production whose instances represent the various productions that define the C/C++ grammar subset above. My definition of the class is shown below:
class Production
{
private:
string lhs;
vector rhs_options; // list of options for expansion
vector trans_probs; // list of probabilities associated
// with each choice
public:
Production();
Production(string);
void add_rhs(string, double); // adds new rhs to the production
string expand() const; // returns one of the rhs choices using
// a random number generator
};
Explanation / Answer
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;
//class Production
class Production {
private:
string lhs;
vector<string> rhs_options; // list of options for expansion
vector<double> trans_probs; // list of probabilities associated
// with each choice
public:
Production();
Production(string);
void add_rhs(string, double); // adds new rhs to the production
string expand(); // returns one of the rhs choices using
// a random number generator
};
//default constructor
Production::Production()
{
lhs="";
}
//parameterized constructor
Production::Production(string non_terminal)
{
lhs=non_terminal;
}
//function to add rhs to lhs
void Production::add_rhs(string terminal, double prob)
{
rhs_options.push_back(terminal);
trans_probs.push_back(prob);
}
//function to return one of rhs choices
string Production::expand()
{
srand(time(NULL));
double prob=(double)rand()/(double)RAND_MAX;
cout<<"expand prob:"<<prob<<endl;
string str="";
int i;
for(i=0 ; i<trans_probs.size();i++)
{
double tp=trans_probs.at(i);
if(tp >= prob)
break;
}
cout<<"i:"<<i<<endl;
str=rhs_options.at(i);
return str;
}
//main function
int main()
{
srand(time(NULL));
Production production("$"); //create a production object with a non-terminal symbol
double prob;
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("int main() { return 0; }$",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("$",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs(" ",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("${ } ",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("if() ",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("if ( ) else",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("while( ) ",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("while( )$",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("=;$;",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("$ ",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("+",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("-",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("*",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("/",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("int",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("double",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("double",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("$$[empty]",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("$[empty]",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("A",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("B",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("C",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("D",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("E",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("F",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("G",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("H",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("I",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("J",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("K",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("L",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("M",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("N",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("O",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("P",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("Q",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("R",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("S",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("T",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("U",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("V",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("W",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("X",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("Y",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("Z",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("a",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("b",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("c",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("d",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("e",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("f",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("g",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("h",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("i",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("j",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("k",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("l",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("m",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("n",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("o",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("p",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("q",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("r",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("s",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("t",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("u",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("v",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("w",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("x",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("y",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("z",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("0",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("1",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("2",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("3",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("4",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("5",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("6",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("7",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("8",prob);
prob=(double)rand()/(double)RAND_MAX;
production.add_rhs("9",prob);
ofstream outfile("output.txt");
while(1)
{
string str=production.expand();
size_t found=str.find("$");
if(found!=string::npos)
outfile<<str.substr(0,found);
else
break;
}
return 0;
}
Output:
int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }int main() { return 0; }
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.