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
Header File List
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
