1 //! Generate valid parse trees.
2
3 use grammar::repr::*;
4 use rand::{self, Rng};
5 use std::iter::Iterator;
6
7 #[derive(PartialEq, Eq)]
8 pub enum ParseTree {
9 Nonterminal(NonterminalString, Vec<ParseTree>),
10 Terminal(TerminalString),
11 }
12
random_parse_tree(grammar: &Grammar, symbol: NonterminalString) -> ParseTree13 pub fn random_parse_tree(grammar: &Grammar, symbol: NonterminalString) -> ParseTree {
14 let mut gen = Generator {
15 grammar,
16 rng: rand::thread_rng(),
17 depth: 0,
18 };
19 loop {
20 // sometimes, the random walk overflows the stack, so we have a max, and if
21 // it is exceeded, we just try again
22 if let Some(result) = gen.nonterminal(symbol.clone()) {
23 return result;
24 }
25 gen.depth = 0;
26 }
27 }
28
29 struct Generator<'grammar> {
30 grammar: &'grammar Grammar,
31 rng: rand::rngs::ThreadRng,
32 depth: u32,
33 }
34
35 const MAX_DEPTH: u32 = 10000;
36
37 impl<'grammar> Generator<'grammar> {
nonterminal(&mut self, nt: NonterminalString) -> Option<ParseTree>38 fn nonterminal(&mut self, nt: NonterminalString) -> Option<ParseTree> {
39 if self.depth > MAX_DEPTH {
40 return None;
41 }
42
43 self.depth += 1;
44 let productions = self.grammar.productions_for(&nt);
45 let index: usize = self.rng.gen_range(0, productions.len());
46 let production = &productions[index];
47 let trees: Option<Vec<_>> = production
48 .symbols
49 .iter()
50 .map(|sym| self.symbol(sym.clone()))
51 .collect();
52 trees.map(|trees| ParseTree::Nonterminal(nt, trees))
53 }
54
symbol(&mut self, symbol: Symbol) -> Option<ParseTree>55 fn symbol(&mut self, symbol: Symbol) -> Option<ParseTree> {
56 match symbol {
57 Symbol::Nonterminal(nt) => self.nonterminal(nt),
58 Symbol::Terminal(t) => Some(ParseTree::Terminal(t)),
59 }
60 }
61 }
62
63 impl ParseTree {
terminals(&self) -> Vec<TerminalString>64 pub fn terminals(&self) -> Vec<TerminalString> {
65 let mut vec = vec![];
66 self.push_terminals(&mut vec);
67 vec
68 }
69
push_terminals(&self, vec: &mut Vec<TerminalString>)70 fn push_terminals(&self, vec: &mut Vec<TerminalString>) {
71 match *self {
72 ParseTree::Terminal(ref s) => vec.push(s.clone()),
73 ParseTree::Nonterminal(_, ref trees) => {
74 for tree in trees {
75 tree.push_terminals(vec);
76 }
77 }
78 }
79 }
80 }
81