cfg_predict/
follow.rs

1//! FOLLOW sets.
2
3use std::collections::{BTreeMap, BTreeSet};
4
5use cfg_symbol::Symbol;
6
7use cfg_grammar::symbol::set::SymbolBitSet;
8use cfg_grammar::RuleContainer;
9
10use super::{PerSymbolSets, PredictSets};
11
12/// FOLLOW sets.
13pub struct FollowSets {
14    /// Mapping from nonterminals to FOLLOW sets.
15    map: PerSymbolSets,
16}
17
18impl FollowSets {
19    /// Compute all FOLLOW sets of the grammar.
20    /// Returns FollowSets.
21    pub fn new<'a, G>(grammar: &'a G, start_sym: Symbol, first_sets: &PerSymbolSets) -> Self
22    where
23        G: RuleContainer,
24    {
25        let mut this = FollowSets {
26            map: BTreeMap::new(),
27        };
28
29        for rule in grammar.rules() {
30            let follow_set = this.map.entry(rule.lhs).or_insert_with(BTreeSet::new);
31            if rule.lhs == start_sym {
32                follow_set.insert(None);
33            }
34        }
35
36        let mut changed = true;
37        while changed {
38            changed = false;
39            let terminal_set = SymbolBitSet::terminal_set(grammar);
40            for rule in grammar.rules() {
41                let mut follow_set = this.map.get(&rule.lhs).unwrap().clone();
42
43                for &sym in rule.rhs.iter().rev() {
44                    if terminal_set.has_sym(sym) {
45                        follow_set.clear();
46                        follow_set.insert(Some(sym));
47                    } else {
48                        let followed = this.map.get_mut(&sym).unwrap();
49                        let prev_cardinality = followed.len();
50                        followed.extend(follow_set.iter().cloned());
51                        changed |= prev_cardinality != followed.len();
52
53                        let first_set = first_sets.get(&sym).unwrap();
54                        if !first_set.contains(&None) {
55                            follow_set.clear();
56                        }
57                        follow_set.extend(first_set.iter().cloned());
58                    }
59                }
60            }
61        }
62
63        this
64    }
65}
66
67impl PredictSets for FollowSets {
68    /// Returns a reference to FIRST sets.
69    fn predict_sets(&self) -> &PerSymbolSets {
70        &self.map
71    }
72}
cfg_predict/follow.rs

cfg_predict/
follow.rs
