cfg_predict_sets/
follow.rs

1//! FOLLOW sets.
2//!
3//! Based on LALRPOP's code by Niko Matsakis.
4
5use std::collections::BTreeMap;
6
7use cfg_grammar::Cfg;
8
9use crate::sets::PerSymbolSetVal;
10
11use super::{PerSymbolSets, PredictSets};
12
13/// FOLLOW sets.
14pub struct FollowSets {
15    /// Mapping from nonterminals to FOLLOW sets.
16    map: PerSymbolSets,
17}
18
19impl FollowSets {
20    /// Compute all FOLLOW sets of the grammar.
21    /// Returns FollowSets.
22    pub fn new(grammar: &Cfg, first_sets: &PerSymbolSets) -> Self {
23        let mut this = FollowSets {
24            map: BTreeMap::new(),
25        };
26
27        let mut roots = grammar.roots().to_vec();
28        roots.sort();
29        for rule in grammar.rules() {
30            let follow_set = this
31                .map
32                .entry(rule.lhs)
33                .or_insert_with(PerSymbolSetVal::new);
34            if roots.binary_search(&rule.lhs).is_ok() {
35                follow_set.has_none = true;
36            }
37        }
38
39        let mut changed = true;
40        while changed {
41            changed = false;
42            let terminal_set = grammar.terminal_symbols();
43            for rule in grammar.rules() {
44                let mut follow_set = this
45                    .map
46                    .get(&rule.lhs)
47                    .cloned()
48                    .expect("FOLLOW set not found");
49
50                for &sym in rule.rhs.iter().rev() {
51                    if terminal_set[sym] {
52                        follow_set.clear();
53                        follow_set.push(sym);
54                    } else {
55                        let followed = this.map.get_mut(&sym).unwrap();
56                        let prev_cardinality = followed.len();
57                        followed.extend(follow_set.iter().cloned());
58                        followed.sort_unstable();
59                        followed.dedup();
60                        changed |= prev_cardinality != followed.len();
61
62                        let first_set = first_sets.get(&sym).unwrap();
63                        if !first_set.has_none {
64                            follow_set.clear();
65                        }
66                        follow_set.extend(first_set.iter().cloned());
67                    }
68                }
69            }
70        }
71
72        this
73    }
74}
75
76impl PredictSets for FollowSets {
77    /// Returns a reference to FIRST sets.
78    fn predict_sets(&self) -> &PerSymbolSets {
79        &self.map
80    }
81}
cfg_predict_sets/follow.rs

cfg_predict_sets/
follow.rs
