cfg-predict 0.0.1

Library for manipulating context-free grammars.
Documentation 
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

//! FOLLOW sets.

use std::collections::{BTreeMap, BTreeSet};

use cfg_symbol::Symbol;

use cfg_grammar::symbol::set::SymbolBitSet;
use cfg_grammar::RuleContainer;

use super::{PerSymbolSets, PredictSets};

/// FOLLOW sets.
pub struct FollowSets {
    /// Mapping from nonterminals to FOLLOW sets.
    map: PerSymbolSets,
}

impl FollowSets {
    /// Compute all FOLLOW sets of the grammar.
    /// Returns FollowSets.
    pub fn new<'a, G>(grammar: &'a G, start_sym: Symbol, first_sets: &PerSymbolSets) -> Self
    where
        G: RuleContainer,
    {
        let mut this = FollowSets {
            map: BTreeMap::new(),
        };

        for rule in grammar.rules() {
            let follow_set = this.map.entry(rule.lhs).or_insert_with(BTreeSet::new);
            if rule.lhs == start_sym {
                follow_set.insert(None);
            }
        }

        let mut changed = true;
        while changed {
            changed = false;
            let terminal_set = SymbolBitSet::terminal_set(grammar);
            for rule in grammar.rules() {
                let mut follow_set = this.map.get(&rule.lhs).unwrap().clone();

                for &sym in rule.rhs.iter().rev() {
                    if terminal_set.has_sym(sym) {
                        follow_set.clear();
                        follow_set.insert(Some(sym));
                    } else {
                        let followed = this.map.get_mut(&sym).unwrap();
                        let prev_cardinality = followed.len();
                        followed.extend(follow_set.iter().cloned());
                        changed |= prev_cardinality != followed.len();

                        let first_set = first_sets.get(&sym).unwrap();
                        if !first_set.contains(&None) {
                            follow_set.clear();
                        }
                        follow_set.extend(first_set.iter().cloned());
                    }
                }
            }
        }

        this
    }
}

impl PredictSets for FollowSets {
    /// Returns a reference to FIRST sets.
    fn predict_sets(&self) -> &PerSymbolSets {
        &self.map
    }
}