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:

1. 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.
2. 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

Reference

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