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

//! FOLLOW sets.

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

use grammar::{ContextFree, ContextFreeRef};
use prediction::{FirstSets, PerSymbolSets};
use rule::GrammarRule;
use symbol::{Symbol, SymbolBitSet};

/// 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: &FirstSets) -> Self
        where G: ContextFree,
              &'a G: ContextFreeRef<'a, Target = G>
    {
        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.first_sets().get(&sym).unwrap();
                        if !first_set.contains(&None) {
                            follow_set.clear();
                        }
                        follow_set.extend(first_set.iter().cloned());
                    }
                }
            }
        }

        this
    }

    /// Returns a reference to FOLLOW sets.
    pub fn follow_sets(&self) -> &PerSymbolSets {
        &self.map
    }
}