The Battle for Wesnoth  1.15.0+dev
context_free_grammar_generator.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2016 - 2018 by Ján Dugáček
3  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; either version 2 of the License, or
8  (at your option) any later version.
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY.
11 
12  See the COPYING file for more details.
13 */
14 
15 /**
16  * @file
17  * Algorithm to generate names using a context-free grammar, which allows more control
18  * than the usual Markov chain generator
19  */
20 
22 
23 #include "log.hpp"
24 #include "random.hpp"
26 
27 #include <algorithm>
28 
29 #include <boost/algorithm/string.hpp>
30 
32 {
33 }
34 
36 {
37  const char* reading = source.c_str();
38  nonterminal* current = nullptr;
39  std::vector<std::string>* filled = nullptr;
40  std::string buf;
41 
42  while (*reading != 0) {
43  if (*reading == '=') {
44  // Leading and trailing whitespace is not significant, but internal whitespace is
45  std::string key = boost::trim_copy(buf);
46  if(key == "!" || key =="(" || key == ")") {
47  throw name_generator_invalid_exception("[context_free_grammar_generator] Parsing error: nonterminals (, ! and ) may not be overridden");
48  }
49  current = &nonterminals_[key];
50  current->possibilities_.emplace_back();
51  filled = &current->possibilities_.back();
52  buf.clear();
53  } else if (*reading == '\n') {
54  // All whitespace is significant after the =
55  if (filled) filled->push_back(buf);
56  filled = nullptr;
57  current = nullptr;
58  buf.clear();
59  } else if (*reading == '|') {
60  if (!filled || !current) {
61  throw name_generator_invalid_exception("[context_free_grammar_generator] Parsing error: misplaced | symbol");
62  }
63  filled->push_back(buf);
64  current->possibilities_.emplace_back();
65  filled = &current->possibilities_.back();
66  buf.clear();
67  } else if (*reading == '\\' && reading[1] == 'n') {
68  reading++;
69  buf.push_back('\n');
70  } else if (*reading == '\\' && reading[1] == 't') {
71  reading++;
72  buf.push_back('\t');
73  } else {
74  if (*reading == '{') {
75  if (!filled) {
76  throw name_generator_invalid_exception("[context_free_grammar_generator] Parsing error: misplaced { symbol");
77  }
78  filled->push_back(buf);
79  buf.clear();
80  }
81  else if (*reading == '}') {
82  if (!filled) {
83  throw name_generator_invalid_exception("[context_free_grammar_generator] Parsing error: misplaced } symbol");
84  }
85  filled->push_back('{' + boost::trim_copy(buf));
86  buf.clear();
87  } else buf.push_back(*reading);
88  }
89  reading++;
90  }
91  if (filled) filled->push_back(buf);
92 }
93 
94 context_free_grammar_generator::context_free_grammar_generator(const std::map<std::string, std::vector<std::string>>& source)
95 {
96  for(auto rule : source) {
97  std::string key = rule.first; // Need to do this because utils::strip is mutating
98  boost::trim(key);
99  if(key == "!" || key =="(" || key == ")") {
100  throw name_generator_invalid_exception("[context_free_grammar_generator] Parsing error: nonterminals (, ! and ) may not be overridden");
101  }
102  for(std::string str : rule.second) {
103  nonterminals_[key].possibilities_.emplace_back();
104  std::vector<std::string>* filled = &nonterminals_[key].possibilities_.back();
105  std::string buf;
106  // A little code duplication here...
107  for(char c : str) {
108  if (c == '{') {
109  if (!filled) {
110  throw name_generator_invalid_exception("[context_free_grammar_generator] Parsing error: misplaced { symbol");
111  }
112  filled->push_back(buf);
113  buf.clear();
114  }
115  else if (c == '}') {
116  if (!filled) {
117  throw name_generator_invalid_exception("[context_free_grammar_generator] Parsing error: misplaced } symbol");
118  }
119 
120  filled->push_back('{' + boost::trim_copy(buf));
121  buf.clear();
122  } else buf.push_back(c);
123  }
124  if(!buf.empty()) {
125  filled->push_back(buf);
126  }
127  }
128  }
129 }
130 
131 std::string context_free_grammar_generator::print_nonterminal(const std::string& name, uint32_t* seed, short seed_pos) const {
132  if (name == "!") {
133  return "|";
134  }
135  else if (name == "(" ) {
136  return "{";
137  }
138  else if (name == ")" ) {
139  return "}";
140  }
141  else {
142  std::string result = "";
143 
144  std::map<std::string,nonterminal>::const_iterator found = nonterminals_.find(name);
145  if (found == nonterminals_.end()) {
146  lg::wml_error() << "[context_free_grammar_generator] Warning: needed nonterminal" << name << " not defined";
147  return "!" + name;
148  }
149  const context_free_grammar_generator::nonterminal& got = found->second;
150  unsigned int picked = seed[seed_pos++] % got.possibilities_.size();
151  if (seed_pos >= seed_size) seed_pos = 0;
152  if (picked == got.last_) {
153  picked = seed[seed_pos++] % got.possibilities_.size();
154  if (seed_pos >= seed_size) seed_pos = 0;
155  }
156  got.last_ = picked;
157  const std::vector<std::string>& used = got.possibilities_[picked];
158  for (unsigned int i = 0; i < used.size(); i++) {
159  if (used[i][0] == '{') result += print_nonterminal(used[i].substr(1), seed, seed_pos);
160  else result += used[i];
161  }
162  return result;
163  }
164 }
165 
167  uint32_t seed[seed_size];
168  init_seed(seed);
169  return print_nonterminal("main", seed, 0);
170 }
171 
172 void context_free_grammar_generator::init_seed(uint32_t seed[]) const {
173  for (unsigned short int i = 0; i < seed_size; i++) {
175  }
176 }
static const char * name(const std::vector< SDL_Joystick *> &joysticks, const std::size_t index)
Definition: joystick.cpp:48
std::vector< std::vector< std::string > > possibilities_
std::string generate() const override
Generates a possible word in the grammar set before.
std::string print_nonterminal(const std::string &name, uint32_t seed[], short int seed_pos) const
context_free_grammar_generator(const std::string &source)
Initialisation.
std::size_t i
Definition: function.cpp:933
std::stringstream & wml_error()
Use this logger to send errors due to deprecated WML.
Definition: log.cpp:269
rng * generator
This generator is automatically synced during synced context.
Definition: random.cpp:60
std::map< std::string, nonterminal > nonterminals_
Standard logging facilities (interface).
uint32_t next_random()
Provides the next random draw.
Definition: random.cpp:84
mock_char c
static const short unsigned int seed_size