earley/grammar/
mod.rs

1pub mod production;
2pub mod rule;
3#[macro_use]
4pub mod macros;
5
6use group_by::GroupByExt;
7use token::{Terminal, NonTerminal};
8use item_table::ItemTable;
9use std::collections::BTreeMap;
10use parse::parse;
11pub use grammar::production::{Production};
12pub use grammar::rule::Rule;
13
14pub struct Grammar<T> {
15    starting_rule: &'static str,
16    rules: BTreeMap<&'static str, Rule<T>>,
17}
18
19impl<T> Grammar<T> {
20    pub fn new(productions: Vec<Box<Production<T>>>) -> Grammar<T> {
21        let first_rule_name = {
22            productions.get(0).expect("grammar must have at least one rule").get_name()
23        };
24
25        let mut rules = productions
26            .into_iter()
27            .group_by(|p| p.get_name())
28            .map(|(name, productions)| (name, Rule::new(name, productions)))
29            .collect();
30
31        mark_nullable(&mut rules);
32
33        Grammar {
34            starting_rule: first_rule_name,
35            rules: rules
36        }
37    }
38
39    pub fn get_starting_rule_name(&self) -> &'static str {
40        self.starting_rule
41    }
42
43    pub fn get_rule(&self, name: &str) -> Option<&Rule<T>> {
44        self.rules.get(name)
45    }
46
47    pub fn productions_for_starting_rule(&self) -> &[Box<Production<T>>] {
48        &self.rules[self.starting_rule].get_productions()
49    }
50
51    pub fn productions_for(&self, name: &str) -> &[Box<Production<T>>] {
52        &self.rules[name].get_productions()
53    }
54
55    pub fn build_table<'a>(&'a self, input: &'a str) -> ItemTable<'a, T> where T: 'a {
56        ItemTable::build(self, input)
57    }
58
59    pub fn parse<'a>(&'a self, input: &'a str) -> Option<T> where T: 'a {
60        let table = self.build_table(input);
61        parse(&table)
62    }
63}
64
65fn mark_nullable<T>(rules: &mut BTreeMap<&'static str, Rule<T>>) {
66    loop {
67        let mut found_nullable_rule = false;
68        for (_, rule) in rules.iter() {
69            if rule.is_nullable() {
70                continue;
71            } else {
72                let nullable = rule.get_productions().iter().any(|production| {
73                    production.get_tokens().len() == 0 || production.get_tokens().iter().all(|token| {
74                        match token {
75                            &Terminal(_) => false,
76                            &NonTerminal(name) => rules[name].is_nullable()
77                        }
78                    })
79                });
80                if nullable {
81                    rule.mark_as_nullable();
82                    found_nullable_rule = true;
83                }
84            }
85        }
86        if !found_nullable_rule { break }
87    }
88}
earley/grammar/mod.rs

earley/grammar/
mod.rs
