Exercise 7-5
Reimplement the grammar program using a list as the data structure in which we build the sentence.
Solution
This exercise is somewhat similar to Exercise 5-2 / 5-3 / 5-4, in which our objective is to replace all the relevant vector with list.
Here is the solution strategy:
- Make a copy of the entire project as per Solution to Exercise 7-0 (Part 3 / 3) – i.e. the textbook Grammar / Generate Sentence program.
- Replace all the vector with list, in main.cpp, gen_sentence.cpp/.h, gen_aux.cpp/.h.
The main.cpp function
Start with the main program – we notice the:
#include <vector> // Some codes.... using std::vector; // Some codes.... vector<string> sentence = gen_sentence(grammar); // Some codes.... vector<string>::const_iterator it = sentence.begin();
We simply need to replace all the vector with list.
Here we can see the return type of the function gen_sentence needs to be changed from vector<string> to list<string>.
The gen_sentence function
We need to replace all the vector with list in the gen_sentence.cpp (source file) and gen_sentence.h (header file).
gen_sentence.cpp
#include <vector>
// Some codes....
using std::vector;
// Some codes....
list<string> gen_sentence(const Grammar& g)
{
list<string> ret;
gen_aux(g, "<sentence>", ret);
return ret;
}
gen_sentence.h
// Some codes.... #include <vector> std::vector<std::string> gen_sentence(const Grammar&); // Some codes....
From this we see that we may need to adjust the gen_aux function to cater for the vector-to-list change.
The gen_aux function
Looking at the gen_aux.cpp (source file) and gen_aux.h (header file) reveals that we need to replace the vector with list.
gen_aux.cpp
#include <vector>
// Some codes....
using std::vector;
// Some codes....
void gen_aux(const Grammar& g, const string& word, vector<string>& ret)
{
// Some codes....
}
gen_aux.h
// Some codes.... #include <vector> void gen_aux(const Grammar&, const std::string&, std::vector<std::string>&); // Some codes....
The Project
Just simply make a copy of the entire project as per Solution to Exercise 7-0 (Part 3 / 3), and do the vector-to-list replacement as mentioned above.
i.e. use the following (list version) files as replacement of the original (vector version) files:
Source File List (to change)
- main.cpp
- gen_sentence.cpp
- gen_aux.cpp
Header File List (to change)
- gen_sentence.h
- gen_aux.h
Source Files (to change)
main.cpp
#include <iostream> // std::cin, std::cout, std::endl
#include <string> // std::string
#include <list> // std::list
#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::list;
using std::srand;
using std::time;
int main()
{
// Uncomment thhe below srand() to seed new randomness in new job-runs.
// srand(time(NULL));
Grammar grammar = read_grammar(cin);
for (int i = 0; i != 5; ++i) {
// generate the sentence
list<string> sentence = gen_sentence(grammar);
// write the first word, if any
list<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;
}
gen_sentence.cpp
#include <list> // std::list
#include <string> // std::string
#include "read_grammar.h" // Grammar
#include "gen_aux.h" // gen_aux
using std::list;
using std::string;
// Generate a sentence based on a Grammer object
// (S7.4.3/132)
list<string> gen_sentence(const Grammar& g)
{
list<string> ret;
gen_aux(g, "<sentence>", ret);
return ret;
}
gen_aux.cpp
#include <string> // std::string
#include <list> // std::list
#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::list;
using std::logic_error;
// Look up the input Grammar, and expand
// (S7.4.3/132)
void gen_aux(const Grammar& g, const string& word, list<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.h
#ifndef GUARD_GEN_SENTENCE_H #define GUARD_GEN_SENTENCE_H // gen_sentence.h #include <string> // std::string #include <list> // std::list #include "read_grammar.h" // Grammar std::list<std::string> gen_sentence(const Grammar&); #endif // GUARD_GEN_SENTENCE_H
gen_aux.h
#ifndef GUARD_GEN_AUX_H #define GUARD_GEN_AUX_H // gen_aux.h #include <string> // std::string #include <list> // std::list #include "read_grammar.h" // Grammar void gen_aux(const Grammar&, const std::string&, std::list<std::string>&); #endif // GUARD_GEN_AUX_H
Test Program
Following replace all the vector-to-list replacements, and resubmit the program with the same input, we get the results as expected. In my case:
<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> ^Z 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