branchy

此 crate 提供使用上下文无关文法生成文本字符串和其他序列的基本工具。

文本生成示例

以下示例演示了基于输入符号序列和一组规则随机生成短句，这些规则可以应用于符号序列，直到完全展开。

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

运行时，此示例将打印出类似于以下句子的句子

Alice 是一个铁匠，她来自一个大村庄

Bob 来自一个小镇

Bob 是一个面包师，他来自一个大城镇

如您所见，输入序列和文法规则都是用 Nonterminal（可以进一步展开）和 Terminal 符号来描述的。所有规则在左侧都有一个非终端符号值，在右侧有一个可能包含 Nonterminal 和 Terminal 符号的序列。

“魔法”发生在 Expander 的 expand() 方法中，该方法会反复选择并应用匹配的规则，直到序列完全展开（即只包含终端符号）。

默认情况下，使用 UniformRandomRuleSelector 来选择规则，因此结果是随机的。如以下所示，如果需要，可以通过 ExpanderBuilder 来更改。

使用自定义规则选择器

当构建一个 Expander 时，您可以通过 ExpanderBuilder 的 with_rule_selector() 方法提供您自己的规则选择器。

以下示例定义了一个自定义规则选择器，它始终选择第一条匹配规则，然后用于生成短语。如您所见，规则选择器需要实现来自 RuleSelector 特性的 select_matching_rule() 方法。

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

此示例还通过 with_new_rule() 方法直接在 ExpanderBuilder 上设置语法规则。有关更多辅助方法，请参阅 ExpanderBuilder 的文档。

日志记录

为了帮助您调试语法，branchy 提供了 ExpansionLogger 特性，您可以通过实现它来获取关于扩展进度的通知及其步骤。

例如，为了记录扩展过程中每个步骤选择的规则，您可以实现 on_nonterm_expanded() 方法。以下示例在每一步都通过 println!() 写入消息。

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

此示例生成类似于以下内容的输出

expanded "site_description" to [Nonterminal("adjective"), Nonterminal("site")]
expanded "adjective" to [Terminal("dark")]
expanded "site" to [Terminal("cave")]
expanded "direction" to [Terminal("east")]

生成非文本序列

尽管 branchy 的主要用例是生成文本字符串，但它可以用于生成其他类型序列的语法。任何实现了 Clone + PartialEq 的类型都可以用于非终结符号的值，任何实现了 Clone 的类型都可以用于终结符。请参阅 NonterminalValue 和 TerminalValue 特性。