1. Chapter 7 Using associative containers ¶

상기에서는 map >의 형태로 구현해야한다. 그러나 <adjective>, <location>, <noun>과 같이 동일한 키 값에 대해서 규칙이 여러개가 존재하는 경우를 다루기 위해서 map > > 의 타입을 이용한다.

~cpp 
  // typedef 를 이용해서 좀더 읽기에 수월하도록 형을 지정하는 것이 가능하다.
typedef vector<string> Rule;
typedef vector<Rule> Rule_collection;
typedef map<string, Rule_collection> Grammar;
 

~cpp 
Grammar read_grammar(istream& in) {
	Grammar ret;
	string line;
	while (getline(in, line)) {
		vector<string> entry = split(line); // split 함수를 이용해서 입력된 문자열을 ' '를 기존으로 tokenize 한다.
		if (!entry.empty())
			ret[entry[0]].push_back(
				Rule(entry.begin() + 1, entry.end()));
			//vector<string>의 첫번째 요소를 entry의 키값으로 이용한다. 2번째 요소부터 마지막 요소까지는 entry의 값으로 저장한다.
	}
	return ret;
}
 

~cpp 
vector<string> gen_sentence(const Grammar& g) {
	vector<string> ret;
	gen_aux(g, "<sentence>", ret);
	return ret;
}
 

g:Grammar map에서 <sentence> 키값으로 실제의 문장에 관한 문법을 읽어들인다.

~cpp 
bool bracketed(const string& s) {
	return s.size() > 1 && s[0] == '<' && s[s.size()-1] == '>';
}

//Recursive function call 재귀 함수의 이용
void gen_aux(const Grammar& g, const string& word, vector<string>& ret) {
	if (!bracketed(word)) {
		ret.push_back(word);		// 실제로 ret:vector<string> 에 값이 저장되고 재귀 함수가 끝이 나는 조건식이 된다.
	} else {
		Grammar::const_iterator it = g.find(word);		// g[word]로 참조를 할경우 map 컨테이너의 특성상 새로운 map이 생성된다.
		if (it == g.end())
			throw logic_error("empty rule");                // 규직이 존재하지 않는 다면 word로 전달된 규칙이 존재하지 않는 다는 말이된다.
                                                                        // 즉 입력이 잘못된 경우가 된다.

		const Rule_collection& c = it->second;                 

		const Rule& r = c[nrand(c.size())];

		// <noun-phrase> 와 같이 연결된 문법이 <noun> 인경우에는 재귀적 함수 호출을 통해서 마지막 단어까지 내려간다.
		// 마지막 단어까지 내려갓을 경우 재귀 함수를 호출하고 bracketed = false 의 조건이 되기 때문에 재귀 함수가 종료된다.
		for(Rule::const_iterator i = r.begin(); i != r.end(); ++i) 
			gen_aux(g, *i, ret);
	}
}
 

map<class T>.find(K) : 주어진 키를 갖는 요소를 찾고, 있다면 그 요소를 가리키는 반복자를 리턴한다. 없다면 map<class T>.end()를 리턴한다.
nrand(c.size()) : 7.4.4 절에서 설명함. pseudo rand 함수를 통해서 [0, c.size()) 의 범위를 갖는 가상적 임의의 수를 리턴한다.
재귀함수의 호출은 반드시 함수의 내부에 재귀호출을 탈출 할 수 잇는 코드가 존재해야한다. 그렇지 않을 경우 stack_overflow가 발생한다.

~cpp 
int main()
{
	// generate the sentence
	vector<string> sentence = gen_sentence(read_grammar(cin));

	// 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;
}
 

~cpp 
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;
}
 

rand() 는 C Standard Library <cstdlib> 라이브러리에 존재한다. 일반적으로 cstdlib 에 정의된 RAND_MAX보다 작은 값을 임의적으로 리턴한다.
RAND_MAX % n를 이용해서 임의의 수를 구할 경우 Pseudo 임의 값의 한계로 인해서 문제점이 발생한다.

• n 이 작은 경우: rand()함수는 홀수 짝수를 번갈아 출력하는 성질이 있기 때문에 n이 2일경우 0과 1이 반복적으로 출력된다.
  
• n 이 너무 큰 경우에도 특정한 수가 반복적으로 나타나게 된다.
  

따라서 우리는 RAND_MAX를 n으로 나누어서 전체 RAND_MAX를 bucket이라는 단위로 나눈뒤에 이 bucket으로 rand()가 발생시키는 난수를 나누어 줌으로써 우리가 원하는 [0, n) 의 임의의 수를 얻을 수 있다.

~cpp 
//grammar.cpp
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <stdexcept>
#include <string>
#include <vector>

#include "split.h"
#include <time.h>

using std::istream;           using std::cin;
using std::copy;              using std::cout;
using std::endl;              using std::find;
using std::getline;           using std::logic_error;
using std::map;               using std::string;
using std::vector;            using std::domain_error;
using std::rand;

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

// read a grammar from a given input stream
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;
}

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

int nrand(int);

vector<string> gen_sentence(const Grammar& g)
{
	vector<string> ret;
	gen_aux(g, "<sentence>", ret);
	return ret;
}

bool bracketed(const string& s)
{
	return s.size() > 1 && s[0] == '<' && s[s.size() - 1] == '>';
}

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);
	}
}

int main()
{
	// generate the sentence
	vector<string> sentence = gen_sentence(read_grammar(cin));

	// 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;
}

// return a random integer in the range `[0,' `n)'
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;
}