I am writing a program in C++ that randomly generates some simple code from the following BNF grammar:
<prog> ::= “int main() { <stat_list> return 0; }”
<stat_list> ::= <stat>
| <stat_list> <stat>
<stat> ::= <cmpd_stat>
| <if_stat>
| <iter_stat>
| <assgn_stat>
| <decl_stat>
<cmpd_stat> ::= { <stat_list> }
<if_stat> ::= if ( <exp> ) <stat>
| if ( <exp> ) <cmpd_stat>
| if ( <exp> ) <stat> else <stat>
| if ( <exp> ) <cmpd_stat> else <stat>
| if ( <exp> ) <stat> else <cmpd_stat>
| if ( <exp> ) <cmpd_stat> else <cmpd_stat>
<iter_stat> ::= while ( <exp> ) <stat>
| while ( <exp> ) <cmpd_stat>
<assgn_stat> ::= <id> = <exp> ;
<decl_stat> ::= <type> <id> ;
| <type> <assgn_stat>
<exp> ::= <exp> <op> <exp>
| <id>
| <const>
<op> ::=+|-|*|/
<type> ::=int
| double
<id> ::= <char><chardigit_seq>
<const> ::= <digit><digit_seq>
<chardigit_seq>::= [empty]
| <char><chardigit_seq>
| <digit><chardigit_seq>
<char> ::= [A-Z] | [a-z] | _
<digit> ::= [0-9]
The output code should create the simple complete program like this (it need to be correct in syntax, but not in semantic):
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;
}
Here is the code I am doing with, could someone please check it and tell me what wrong with it? Thank you very much for help.
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <string>
#include <fstream>
using namespace std;
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() const; // returns one of the rhs choices using
//a random number generator
};
Production::Production() {
lhs = "<prog>"; //first lhs option, all C++ programs start with this
rhs_options.push_back("int main() { <stat_list> return 0; }"); //only
rhs option for <prog>
trans_probs.push_back(1.0); //100% chance of the rhs result for
<prog>, since it is the only option
}
Production::Production(string s) {
lhs = s; //set the lhs to whatever is passed.
}
void Production::add_rhs(string s, double num) {
rhs_options.push_back(s); //each rhs option and probability is added
trans_probs.push_back(num);
}
string Production::expand() const { //returns one of the options from
rhs vector
srand(time(0));
double random = (rand() + 0.0) / RAND_MAX; //generates random number
between 0.0 <= x <= 1.0
for (int i = 0; i < (int)trans_probs.size(); i++) {
if (trans_probs[i] >= random)
return rhs_options[i];
}
return rhs_options[0];
}
//method prototypes
string progm();
string stat_listm();
string statm();
string cmpd_statm();
string if_statm();
string iter_statm();
string assgn_statm();
string decl_statm();
string expm();
string opm();
string typem();
string idm();
string constm();
string char_digit_seqm();
string digit_seqm();
string charm();
string digitm();
string progm() {
Production prog("<prog>");
prog.add_rhs("int main() { " + stat_listm() + " return 0; }", 1.0);
//only rhs option for <prog>, therefore 100% chance
return prog.expand();
}
string stat_listm() {
Production stat_list("<stat_list>");
stat_list.add_rhs(statm(), 0.5);
stat_list.add_rhs(stat_listm() + " " + statm(), 1.0);
return stat_list.expand();
}
string statm() {
Production stat("<stat>");
stat.add_rhs(cmpd_statm(), 0.05); //5%
stat.add_rhs(if_statm(), 0.2); //15% (5+15=20)
stat.add_rhs(iter_statm(), 0.35); //15% (20+15=35)
stat.add_rhs(assgn_statm(), 0.65); //30% (35+30=65)
stat.add_rhs(decl_statm(), 1.0); //35% (65+35=100)
return stat.expand();
}
string cmpd_statm() {
Production cmpd_stat("<cmpd_stat>");
cmpd_stat.add_rhs("{ " + stat_listm() + " }", 1.0);
return cmpd_stat.expand();
}
string if_statm() {
Production if_stat("<if_stat>");
if_stat.add_rhs("if ( " + expm() + " ) " + statm(), 0.3);
if_stat.add_rhs("if ( " + expm() + " ) " + cmpd_statm(), 0.5);
if_stat.add_rhs("if ( " + expm() + " ) " + statm() + " else " +
statm(), 0.7);
if_stat.add_rhs("if ( " + expm() + " ) " + cmpd_statm() + " else " +
statm(), 0.85);
if_stat.add_rhs("if ( " + expm() + " ) " + statm() + " else " +
cmpd_statm(), 0.95);
if_stat.add_rhs("if ( " + expm() + " ) " + cmpd_statm() + " else " +
cmpd_statm(), 1.0);
return if_stat.expand();
}
string iter_statm() {
Production iter_stat("<iter_stat>");
iter_stat.add_rhs("while ( " + expm() + " ) " + statm(), 0.75);
iter_stat.add_rhs("while ( " + expm() + " ) " + cmpd_statm(), 1.0);
return iter_stat.expand();
}
string assgn_statm() {
Production assgn_stat("<assgn_stat>");
assgn_stat.add_rhs(idm() + " = " + expm() + " ;", 1.0);
return assgn_stat.expand();
}
string decl_statm() {
Production decl_stat("<decl_stat>");
decl_stat.add_rhs(typem() + " " + idm() + " ;", 0.75);
decl_stat.add_rhs(typem() + " " + assgn_statm(), 1.0);
return decl_stat.expand();
}
string expm() {
Production exp("<exp>");
exp.add_rhs(expm() + " " + opm() + " " + expm(), 0.5);
exp.add_rhs(idm(), 0.75);
exp.add_rhs(constm(), 1.0);
return exp.expand();
}
string opm() {
Production op("<op>");
op.add_rhs("+", 0.25);
op.add_rhs("-", 0.50);
op.add_rhs("*", 0.75);
op.add_rhs("/", 1.0);
return op.expand();
}
string typem() {
Production type("<type>");
type.add_rhs("int", 0.5);
type.add_rhs("double", 1.0);
return type.expand();
}
string idm() {
Production id("<id>");
id.add_rhs(charm() + char_digit_seqm(), 1.0);
return id.expand();
}
string constm() {
Production constant("<const>");
constant.add_rhs(digitm() + digit_seqm(), 1.0);
return constant.expand();
}
string char_digit_seqm() {
Production char_digit_seq("<char_digit_seq>");
char_digit_seq.add_rhs("", 0.25);
char_digit_seq.add_rhs(charm() + char_digit_seqm(), 0.5);
char_digit_seq.add_rhs(digitm() + char_digit_seqm(), 1.0);
return char_digit_seq.expand();
}
string digit_seqm() {
Production digit_seq("<digit_seq>");
digit_seq.add_rhs("", 0.25);
digit_seq.add_rhs(digitm() + digit_seqm(), 1.0);
return digit_seq.expand();
}
string charm() {
Production character("<char>");
char alpha[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','_'};
for (int i = 0; i < 53; i++)
{
string letter(1, alpha[i]);
character.add_rhs(letter, (1.0/53 + i/53.0));
}
return character.expand();
}
string digitm()
{
Production digit("<digit>");
char nums[] = {'0','1','2','3','4','5','6','7','8','9'};
for (int i = 0; i < 10; i++)
{
string num(1, nums[i]);
digit.add_rhs(num, (1.0/10 + i/10.0));
}
return digit.expand();
}
int main()
{
......
return 0;
}
Aucun commentaire:
Enregistrer un commentaire