cfg_predict_sets/
first.rs

1//! FIRST sets.
2//!
3//! Based on LALRPOP's code by Niko Matsakis.
4
5use std::collections::BTreeMap;
6
7use cfg_grammar::{Cfg, SymbolBitSet};
8use cfg_symbol::Symbol;
9
10use crate::sets::PerSymbolSetVal;
11
12use super::{PerSymbolSets, PredictSets};
13
14/// Collector of FIRST sets.
15pub struct FirstSets {
16    pub(super) map: PerSymbolSets,
17    lookahead: PerSymbolSetVal,
18    changed: bool,
19    terminal_set: SymbolBitSet,
20}
21
22// struct FirstSets;
23
24// impl FirstSets {
25//     fn new(grammar: &Cfg) -> Self {
26//         FirstSets2
27//     }
28// }
29
30impl FirstSets {
31    /// Compute all FIRST sets of the grammar.
32    ///
33    /// We define a binary relation FIRST(N, S), in which N is related to S
34    /// if the grammar has a production of the form `N ⸬= α S β`, where
35    /// α is a nullable string of symbols.
36    ///
37    /// We compute the transitive closure of this relation.
38    pub fn new(grammar: &Cfg) -> Self {
39        let mut this = FirstSets {
40            map: BTreeMap::new(),
41            lookahead: PerSymbolSetVal::new(),
42            changed: true,
43            terminal_set: grammar.terminal_symbols(),
44        };
45
46        this.collect_from(grammar);
47        this
48    }
49
50    /// Calculates a FIRST set for a string of symbols.
51    pub fn first_set_for_string(&self, string: &[Symbol]) -> PerSymbolSetVal {
52        let mut result = vec![];
53        for &sym in string {
54            if self.terminal_set[sym] {
55                result.push(sym);
56                break;
57            } else {
58                let first_set = self
59                    .map
60                    .get(&sym)
61                    .expect("FIRST set not found in PerSymbolSets");
62                result.clone_from(&first_set.list);
63                if !result.is_empty() {
64                    break;
65                }
66            }
67        }
68        PerSymbolSetVal {
69            has_none: result.is_empty(),
70            list: result,
71        }
72    }
73
74    fn collect_from(&mut self, grammar: &Cfg) {
75        while self.changed {
76            self.changed = false;
77            for rule in grammar.rules() {
78                let set_changed = self.process_rule(rule.lhs, &rule.rhs[..]);
79                self.changed |= set_changed;
80            }
81        }
82    }
83
84    fn process_rule(&mut self, lhs: Symbol, rhs: &[Symbol]) -> bool {
85        self.first_set_collect(rhs);
86        let first_set = self.map.entry(lhs).or_insert_with(PerSymbolSetVal::new);
87        let prev_cardinality = first_set.len();
88        first_set.list.extend(self.lookahead.list.iter().cloned());
89        first_set.list.sort_unstable();
90        first_set.list.dedup();
91        first_set.has_none |= self.lookahead.has_none;
92        self.lookahead.list.clear();
93        self.lookahead.has_none = false;
94        prev_cardinality != first_set.len()
95    }
96
97    /// Compute a FIRST set.
98    fn first_set_collect(&mut self, rhs: &[Symbol]) {
99        for &sym in rhs {
100            let mut nullable = false;
101            if self.terminal_set[sym] {
102                self.lookahead.list.push(sym);
103                self.lookahead.list.sort_unstable();
104                self.lookahead.list.dedup();
105            } else {
106                match self.map.get(&sym) {
107                    None => {
108                        // This should only happen during set construction; it
109                        // corresponds to an entry that has not yet been
110                        // built. Otherwise, it would mean a nonterminal with
111                        // no productions. Either way, the resulting first set
112                        // should be empty.
113                    }
114                    Some(&PerSymbolSetVal { has_none, ref list }) => {
115                        self.lookahead.list.extend(list.iter().copied());
116                        self.lookahead.list.sort_unstable();
117                        self.lookahead.list.dedup();
118                        if has_none {
119                            nullable = true;
120                        }
121                    }
122                }
123            }
124            if !nullable {
125                // Successfully found a FIRST symbol.
126                return;
127            }
128        }
129        self.lookahead.has_none = true;
130    }
131}
132
133impl PredictSets for FirstSets {
134    /// Returns a reference to FIRST sets.
135    fn predict_sets(&self) -> &PerSymbolSets {
136        &self.map
137    }
138}
cfg_predict_sets/first.rs

cfg_predict_sets/
first.rs
