1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
//! This crate provides basic tools for generation of text strings and other sequences //! using [context-free grammars](https://en.wikipedia.org/wiki/Context-free_grammar). //! //! ## Text generation example //! //! The following example demonstrates random generation of a short sentence based on a sequence of input symbols //! and a set of rules, which may be applied to the symbol sequence until it is fully expanded. //! //! ``` //! use branchy::{ //! Symbol, //! Rule, //! ExpanderBuilder //! }; //! //! let input = vec![Symbol::Nonterminal("person"), Symbol::Terminal("comes from a"), Symbol::Nonterminal("location")]; //! //! let rules = vec![ //! Rule::new("person", vec![Symbol::Nonterminal("name")]), //! Rule::new( //! "person", //! vec![Symbol::Nonterminal("name"), Symbol::Terminal("the"), Symbol::Nonterminal("occupation")] //! ), //! Rule::new("name", vec![Symbol::Terminal("Alice")]), //! Rule::new("name", vec![Symbol::Terminal("Bob")]), //! Rule::new("occupation", vec![Symbol::Terminal("blacksmith")]), //! Rule::new("occupation", vec![Symbol::Terminal("baker")]), //! Rule::new("location", vec![Symbol::Nonterminal("size"), Symbol::Nonterminal("settlement_type")]), //! Rule::new("size", vec![Symbol::Terminal("small")]), //! Rule::new("size", vec![Symbol::Terminal("big")]), //! Rule::new("settlement_type", vec![Symbol::Terminal("village")]), //! Rule::new("settlement_type", vec![Symbol::Terminal("town")]) //! ]; //! //! let mut expander = ExpanderBuilder::from(rules).build(); //! //! let expansion_result = expander.expand(input); //! assert!(expansion_result.is_ok()); //! //! let expanded_string = expansion_result.unwrap().join(" "); //! println!("{}", expanded_string); //! ``` //! //! When run, this example prints out a sentence, similar to the ones below: //! //! > Alice the blacksmith comes from a big village //! > //! > Bob comes from a small town //! > //! > Bob the baker comes from a big town //! //! As you can see, both the input sequence and the rules of the grammar are described in terms of //! [`Nonterminal`](enum.Symbol.html#variant.Nonterminal) (ones that can be further expanded) //! and [`Terminal`](enum.Symbol.html#variant.Terminal) symbols. //! All of the rules have a non-terminal symbol value on their left-hand side and a sequence which //! may contain both [`Nonterminal`](enum.Symbol.html#variant.Nonterminal) and //! [`Terminal`](enum.Symbol.html#variant.Terminal) symbols on their right-hand side. //! //! The "magic" happens in [`Expander`](struct.Expander.html)'s [`expand()`](struct.Expander.html#method.expand) method, //! which repeatedly selects and applies matching rules until the sequence is fully expanded //! (i.e contains only terminal symbols). //! //! By default, [`UniformRandomRuleSelector`](struct.UniformRandomRuleSelector.html) is used //! to select rules while expanding, therefore the result is randomized. As we'll see below, //! this can be changed, if needed, via [`ExpanderBuilder`](struct.ExpanderBuilder.html). //! //! ## Using a custom rule selector //! //! When constructing an [`Expander`](struct.Expander.html), you can provide your own //! rule selector via [`ExpanderBuilder`](struct.ExpanderBuilder.html)'s //! [`with_rule_selector()`](struct.ExpanderBuilder.html#method.with_rule_selector) method. //! //! The following example defines a custom rule selector, which always chooses the first //! matching rule, and then uses it in generation of a short phrase. //! As you can see, rule selectors need to implement at least the //! [`select_matching_rule()`](trait.RuleSelector.html#method.select_matching_rule) method //! from the [`RuleSelector`](trait.RuleSelector.html) trait. //! //! ``` //! use branchy::{ //! Symbol, //! Rule, //! ExpanderBuilder, //! RuleSelector //! }; //! //! struct AlwaysFirstRuleSelector; //! //! impl<Nt, T> RuleSelector<Nt, T> for AlwaysFirstRuleSelector { //! fn select_matching_rule<'a>(&self, matching_rules: &[&'a Rule<Nt, T>]) -> Option<&'a Rule<Nt, T>> { //! if matching_rules.is_empty() { //! None //! } else { //! Some(matching_rules[0]) //! } //! } //! } //! //! let input = vec![Symbol::Terminal("Have a"), Symbol::Nonterminal("adjective"), Symbol::Nonterminal("time_of_day")]; //! //! let mut expander = ExpanderBuilder::new() //! .with_new_rule("adjective", vec![Symbol::Terminal("wonderful")]) //! .with_new_rule("adjective", vec![Symbol::Terminal("great")]) //! .with_new_rule("time_of_day", vec![Symbol::Terminal("afternoon")]) //! .with_new_rule("time_of_day", vec![Symbol::Terminal("evening")]) //! .with_rule_selector(AlwaysFirstRuleSelector) //! .build(); //! //! let expanded_string = expander.expand(input).unwrap().join(" "); //! //! assert_eq!(expanded_string, "Have a wonderful afternoon"); //! ``` //! This example also sets the rules of the grammar directly on [`ExpanderBuilder`](struct.ExpanderBuilder.html) //! via the [`with_new_rule()`](struct.ExpanderBuilder.html#method.with_new_rule) method. See the documentation //! of [`ExpanderBuilder`](struct.ExpanderBuilder.html) for more helper methods. //! //! ## Logging //! //! To help you debug your grammars, `branchy` provides the [`ExpansionLogger`](trait.ExpansionLogger.html) trait, //! which you can implement in order to be notified of the progress of the expansion and the steps it takes. //! //! For example, in order to log the rules selected at each step of the expansion, you can implement the //! [`on_nonterm_expanded()`](trait.ExpansionLogger.html#method.on_nonterm_expanded) method. The following example //! writes a message via `println!()` on every step. //! //! ``` //! use branchy::{ //! Symbol, //! Rule, //! ExpanderBuilder, //! ExpansionLogger, //! TerminalValue, //! NonterminalValue //! }; //! //! struct StdOutLogger; //! //! impl<Nt, T> ExpansionLogger<Nt, T> for StdOutLogger //! where Nt: NonterminalValue + std::fmt::Debug, //! T: TerminalValue + std::fmt::Debug //! { //! fn on_nonterm_expanded(&mut self, expanded_nonterm_value: &Nt, rule: &Rule<Nt, T>) { //! println!("expanded {:?} to {:?}", expanded_nonterm_value, rule.replacement); //! } //! } //! //! let input = vec![ //! Symbol::Terminal("There is a"), //! Symbol::Nonterminal("site_description"), //! Symbol::Terminal("to the"), //! Symbol::Nonterminal("direction"), //! Symbol::Terminal("of the town.") //! ]; //! //! let rules = vec![ //! Rule::new("site_description", vec![Symbol::Nonterminal("adjective"), Symbol::Nonterminal("site")]), //! Rule::new("adjective", vec![Symbol::Terminal("huge")]), //! Rule::new("adjective", vec![Symbol::Terminal("dark")]), //! Rule::new("site", vec![Symbol::Terminal("forest")]), //! Rule::new("site", vec![Symbol::Terminal("cave")]), //! Rule::new("direction", vec![Symbol::Terminal("north")]), //! Rule::new("direction", vec![Symbol::Terminal("east")]) //! ]; //! //! let mut expander = ExpanderBuilder::from(rules) //! .with_logger(StdOutLogger) //! .build(); //! //! expander.expand(input).unwrap(); //! ``` //! This example produces output similar to the following: //! ```txt //! expanded "site_description" to [Nonterminal("adjective"), Nonterminal("site")] //! expanded "adjective" to [Terminal("dark")] //! expanded "site" to [Terminal("cave")] //! expanded "direction" to [Terminal("east")] //! ``` //! //! ## Generating non-text sequences //! //! Even though the primary use-case for `branchy` is generating text strings, it can be used for //! grammars producing other kinds of sequences. Any type implementing `Clone + PartialEq` can be //! used for values of non-terminal symbols and any type implementing `Clone` can be used for //! terminals. See [`NonterminalValue`](trait.NonterminalValue.html) and //! [`TerminalValue`](trait.TerminalValue.html) traits. mod grammar; mod expansion; pub use grammar::{ NonterminalValue, TerminalValue, Symbol, Rule }; pub use expansion::{ Expander, ExpanderBuilder, RuleSelector, ExpansionLogger, UniformRandomRuleSelector, NullExpansionLogger, Error, ErrorKind, Result };