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:

::= int main() { return 0; }

::= |

::= | | |

|

::= { }

::= if ( )

| if ( ) | if ( ) else

| if ( ) else

| if ( ) else

| if ( ) else ::= while ( )

| while ( ) ::= = ;

::= ;

| ::= | | ::= + | - | * | /

::= int

| double

::=

::=

::= [empty]

|

|

::= [empty]

|

::= [A-Z] | [a-z] | _

::= [0-9]

You will notice that this grammar is a combined phrase and lexical grammar. This is for simplification purposes.

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++ 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.

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;

}

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

};