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