This is part 3 of the 3-part Exercise 7-0. Click here to see the other parts.

Exercise Exercise 7-0 (Part 3 / 3)

Use a combination of associative arrays and random number generator to generate a set of random sentences, based on a set of predefined Grammar Rules.

Background

This is one of my current favourite exercise – quite hard to understand at first, but once you’ve got it, all becomes so clear (and that burst of satisfying laughter when things clicked in the end – “Wow this is so cool!”). This exercise is about generating a random sentence, based on an input “Grammar” definition that we provide to the program. The input Grammar definition table (as per S7.4/129) is displayed below – column 1 lists the categories, and column 2 the corresponding rules.

<noun>          cat
<noun>          dog
<noun>          table
<noun-phrase>   <noun>
<noun-phrase>   <adjective> <noun-phrase>
<adjective>     large
<adjective>     brown
<adjective>     absurd
<verb>          jumps
<verb>          sits
<location>      on the stairs
<location>      under the sky
<location>      wherever it wants
<sentence>      the <noun-phrase> <verb> <location>

The program generates a random sentence based on the category “<sentence>” – it then recursively expand the associating rules in a “random” manner.

My aim of this post is to summarise all the C++ source and header files (in the form of a complete Code::Block project), run the program, and confirms that the program works as expected. As Andrew Koeing / Barbara Moo (Authors of the book) have already gone through a great deal on explaining how this entire program works, I believe it is appropriate, rather than repeat explaining how this program works here, to just simply suggest to refer to the text book – see Section 7.4 (Page 129) for the detail explanation.

A Note on Random Number Generator

The source code nrand.cpp contains a very clever approach to generate a random number within a desirable range in an evenly distributed manner. The Author has compared this approach with an alternative “not-as-good” approach that uses modulus – % (which generate random number in a non-evenly distributed manner. i.e. some random number are “more likely” than the others.). See S7.4.4/135 for details. One thing to note is that the code uses rand() – i.e. running the program 100 times result in generating the same set of “random” results. This feature actually is as designed – as it enables the program easier to debug. Only when the program is fully tested, we then add a srand() at the top of the program ti make the whole thing to appear even more “random” – i.e. the results in multiple program run are likely to differ.

In this post I will include two main programs – one without the srand (like the example in the book – so each job run gives the same set of random results), and one with the srand (to show that results can differ from multiple job run). The srand() “seeds” a new form of randomness every time when the program is run – dependent on the system clock time.

In addition, there are many “C++ Random Number Generator” related article online (a simple Google search will return lots of good articles). I have found a few that are quite interesting – but all in all, I think all these solutions eventually sort of converge back to the method described by the Accelerated C++ text book!

The Project

Here wraps up all the source codes that I use – I have modified the original main program by adding a for loop – so instead of creating just one sentence, it generates multiple sentences – to demonstrate / give us a better “feel” on randomness. I have included here two main programs – one without a srand(), and the other with a srand(). I shall test both main programs accordingly – but effectively, the one without srand() will create the same set of “random results” in every job run. Whereas the one with the srand() will create different sets of “random results” in every job run.

Source File List

main.cpp – by default without srand for Test 1. Uncomment the srand for Test 2.
bracketed.cpp
gen_aux.cpp
gen_sentence.cpp
nrand.cpp
read_grammar.cpp
split.cpp

Source Files

main.cpp

(Simply uncomment the srand() for Test 2 – with srand)

#include <iostream>          // std::cin, std::cout, std::endl
#include <string>            // std::string
#include <vector>            // std::vector

#include "read_grammar.h"    // read_grammar
#include "gen_sentence.h"    // gen_sentence

#include <ctime>             // Added. std::time
#include <cstdlib>           // Added. std::srand

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

using std::srand;
using std::time;

int main()
{
  srand(time(NULL));   // Added. Seed new form of randomness.

  Grammar grammar = read_grammar(cin);

  for (int i = 0; i != 100; ++i) {

    // generate the sentence
    vector<string> sentence = gen_sentence(grammar);

    // write the first word, if any
    vector<string>::const_iterator it = sentence.begin();
    if (!sentence.empty()) {
      cout << *it;
      ++it;
    }

    // write the rest of the words, each preceded by a space
    while (it != sentence.end()) {
      cout << " " << *it;
      ++it;
    }

    cout << endl;
  }

  return 0;
}

bracketed.cpp

#include <string>     // std::string

using std::string;

// Determine whether a string is surrounded by brackets <>
// (S7.4.3/132)
bool bracketed(const string& s)
{
  return s.size() > 1 &&
         s[0] == '<' &&
         s[s.size() - 1] == '>';
}

gen_aux.cpp

#include <string>            // std::string
#include <vector>            // std::vector
#include <stdexcept>         // logic_error

#include "read_grammar.h"    // Grammar, Rule, Rule_collection
#include "bracketed.h"       // bracketed
#include "nrand.h"           // nrand

using std::string;
using std::vector;
using std::logic_error;

// Look up the input Grammar, and expand
// (S7.4.3/132)
void gen_aux(const Grammar& g, const string& word, vector<string>& ret)
{
  if (!bracketed(word)) {
    ret.push_back(word);
  } else {
    // locate the rule that corresponds to word
    Grammar::const_iterator it = g.find(word);
    if (it == g.end())
      throw logic_error("empty rule");

    // fetch the set of possible rules
    const Rule_collection& c = it->second;

    // from which we select one at random
    const Rule& r = c[nrand(c.size())];

    // recursively expand the selected rule
    for (Rule::const_iterator i = r.begin(); i != r.end(); ++i)
      gen_aux(g, *i, ret);
  }
}

gen_sentence.cpp

#include <vector>             // std::vector
#include <string>             // std::string
#include "read_grammar.h"     // Grammar
#include "gen_aux.h"          // gen_aux

using std::vector;
using std::string;

// Generate a sentence based on a Grammer object
// (S7.4.3/132)
vector<string> gen_sentence(const Grammar& g)
{
  vector<string> ret;
  gen_aux(g, "<sentence>", ret);
  return ret;
}

nrand.cpp

#include <stdexcept>    // std::domain_error
#include <cstdlib>      // rand(), RAND_MAX

using std::domain_error;
using std::rand;


// return a random integer in the range [0, n)
// (S7.4.4/135)
int nrand(int n)
{
  if (n <= 0 || n > RAND_MAX)
    throw domain_error("Argument to nrand is out of range");

  const int bucket_size = RAND_MAX / n;
  int r;

  do r = rand() / bucket_size;
  while (r >= n);

  return r;
}

read_grammar.cpp

#include "read_Grammar.h"    // Grammar, Rule
#include <istream>           // std::istream
#include <string>            // std::string
#include <vector>            // std::vector
#include "split.h"           // split

using std::istream;
using std::string;
using std::vector;
using std::map;

// Read a Grammar from a given input stream
// (S7.4.1/131)
Grammar read_grammar(istream& in)
{
  Grammar ret;
  string line;

  // read the input
  while (getline(in, line)) {

    // split the input into words
    vector<string> entry = split(line);

    if (!entry.empty())
      // use the category to store the associated rule
      ret[entry[0]].push_back(Rule(entry.begin() + 1, entry.end()));

  }
  return ret;
}

split.cpp

#include <string>    // string
#include <vector>    // vector
#include <cctype>    // isspace
#include <algorithm>  // find_if

using std::vector;
using std::string;
using std::isspace;
using std::find_if;

// true if the argument is whitespace, false otherwise
// (S6.1.1/103)
bool space(char c)
{
  return isspace(c);
}

// false if the argument is whitespace, true otherwise
// (S6.1.1/103)
bool not_space(char c)
{
  return !isspace(c);
}

// Scan a line and split into words. Return a vector that contains these words.
// (S6.1.1/103)
vector<string> split(const string& str)
{
  typedef string::const_iterator iter;
  vector<string> ret;

  iter i = str.begin();
  while (i != str.end()) {

    // Ignore leading blanks
    i = find_if(i, str.end(), not_space);

    // Find end of next word
    iter j = find_if(i, str.end(), space);

    // Copy the characters in ([i, j)
    if (i != str.end())
      ret.push_back(string(i, j));

    // Re-initialize
    i = j;
  }
  return ret;
}

Header Files

bracketed.h

#ifndef GUARD_BRACKETED_H
#define GUARD_BRACKETED_H

// bracketed.h

#include <string>

bool bracketed(const std::string&);

#endif // GUARD_BRACKETED_H

gen_aux.h

#ifndef GUARD_GEN_AUX_H
#define GUARD_GEN_AUX_H

// gen_aux.h

#include <string>             // std::string
#include <vector>             // std::vector
#include "read_grammar.h"     // Grammar

void gen_aux(const Grammar&, const std::string&, std::vector<std::string>&);

#endif // GUARD_GEN_AUX_H

gen_sentence.h

#ifndef GUARD_GEN_SENTENCE_H
#define GUARD_GEN_SENTENCE_H

// gen_sentence.h

#include <string>            // std::string
#include <vector>            // std::vector
#include "read_grammar.h"    // Grammar

std::vector<std::string> gen_sentence(const Grammar&);

#endif // GUARD_GEN_SENTENCE_H

nrand.h

#ifndef GUARD_NRAND_H
#define GUARD_NRAND_H

// nrand.h

int nrand(int);

#endif // GUARD_NRAND_H

read_grammar.h

#ifndef GUARD_READ_GRAMMAR_H
#define GUARD_READ_GRAMMAR_H

// read_grammar.h

#include <vector>      // std::vector
#include <string>      // std::string
#include <map>         // std::map
#include <istream>     // std::istream

typedef std::vector<std::string> Rule;
typedef std::vector<Rule> Rule_collection;
typedef std::map<std::string, Rule_collection> Grammar;

Grammar read_grammar(std::istream&);

#endif // GUARD_READ_GRAMMAR_H

split.h

#ifndef GUARD_SPLIT_H
#define GUARD_SPLIT_H

// split.h

#include <vector>
#include <string>

std::vector<std::string> split(const std::string&);

#endif // GUARD_SPLIT_H

Test Program

I have two set of tests. Test 1 uses main.cpp (without srand), and Test 2 uses main.cpp (with srand). For each test, I shall submit the same Grammar rules:

<noun>          cat
<noun>          dog
<noun>          table
<noun-phrase>   <noun>
<noun-phrase>   <adjective> <noun-phrase>
<adjective>     large
<adjective>     brown
<adjective>     absurd
<verb>          jumps
<verb>          sits
<location>      on the stairs
<location>      under the sky
<location>      wherever it wants
<sentence>      the <noun-phrase> <verb> <location>

Test 1 – main.cpp (without srand)

Because this version does not has a srand() at the top, each usage of rand() relies on the same “seed” – i.e. same set of “random results” in every job run.

Job-run 0

the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Job-run 1

the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Job-run 2

the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Test 2 – main.cpp (with srand)

Because this version has a srand() at the top, each usage of rand() relies on the a new “seed” – i.e. new set of “random results” in every job run. All subsequent job runs may produce differnt results.

Job-run 0

the dog jumps wherever it wants
the brown cat jumps under the sky
the cat jumps on the stairs
the brown absurd large table sits wherever it wants
the table jumps under the sky

Job-run 1

the table sits under the sky
the cat sits under the sky
the absurd brown table sits on the stairs
the brown absurd large absurd large table jumps under the sky
the brown table sits wherever it wants

Job-run 2

the dog sits wherever it wants
the absurd dog jumps under the sky
the table sits wherever it wants
the absurd cat sits under the sky
the dog jumps on the stairs

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000

M	T	W	T	F	S	S
« Aug				Oct »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Mathalope

Accelerated C++ Solution to Exercise 7-0 (Part 3 / 3)

Exercise Exercise 7-0 (Part 3 / 3)

Background

A Note on Random Number Generator

The Project

Source File List

Header File List

Source Files

main.cpp

bracketed.cpp

gen_aux.cpp

gen_sentence.cpp

nrand.cpp

read_grammar.cpp

split.cpp

Header Files

bracketed.h

gen_aux.h

gen_sentence.h

nrand.h

read_grammar.h

split.h

Test Program

Test 1 – main.cpp (without srand)

Job-run 0

Job-run 1

Job-run 2

Test 2 – main.cpp (with srand)

Job-run 0

Job-run 1

Job-run 2

Reference

A Scientific Programming Sketchbook

Exercise Exercise 7-0 (Part 3 / 3)

Background

A Note on Random Number Generator

The Project

Source File List

Header File List

Source Files

main.cpp

bracketed.cpp

gen_aux.cpp

gen_sentence.cpp

nrand.cpp

read_grammar.cpp

split.cpp

Header Files

bracketed.h

gen_aux.h

gen_sentence.h

nrand.h

read_grammar.h

split.h

Test Program

Test 1 – main.cpp (without srand)

Job-run 0

Job-run 1

Job-run 2

Test 2 – main.cpp (with srand)

Job-run 0

Job-run 1

Job-run 2

Reference

Share this:

A Scientific Programming Sketchbook