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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

//! FIRST sets.

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

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

/// FIRST sets.
pub struct FirstSets {
    map: PerSymbolSets,
}

impl FirstSets {
    /// Compute all FIRST sets of the grammar.
    ///
    /// We define a binary relation FIRST(N, S), in which N is related to S
    /// if the grammar has a production of the form `N ⸬= α S β`, where
    /// α is a nullable string of symbols.
    ///
    /// We compute the transitive closure of this relation.
    pub fn new<'a, G>(grammar: &'a G) -> Self
        where G: ContextFree,
              &'a G: ContextFreeRef<'a, Target = G>
    {
        let mut this = FirstSets { map: BTreeMap::new() };

        let mut lookahead = vec![];
        let mut changed = true;
        while changed {
            changed = false;
            let terminal_set = SymbolBitSet::terminal_set(&grammar);
            for rule in grammar.rules() {
                this.first_set_collect(&terminal_set, &mut lookahead, rule.rhs());
                let first_set = this.map.entry(rule.lhs()).or_insert_with(BTreeSet::new);
                let prev_cardinality = first_set.len();
                first_set.extend(lookahead.iter().cloned());
                lookahead.clear();
                changed |= first_set.len() != prev_cardinality;
            }
        }

        this
    }

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

    /// Compute a FIRST set.
    fn first_set_collect(&self,
                         terminal_set: &SymbolBitSet,
                         vec: &mut Vec<Option<Symbol>>,
                         rhs: &[Symbol]) {
        for &sym in rhs {
            let mut nullable = false;
            if terminal_set.has_sym(sym) {
                vec.push(Some(sym));
            } else {
                match self.map.get(&sym) {
                    None => {
                        // This should only happen during set construction; it
                        // corresponds to an entry that has not yet been
                        // built. Otherwise, it would mean a nonterminal with
                        // no productions. Either way, the resulting first set
                        // should be empty.
                    }
                    Some(set) => {
                        for &opt_terminal in set {
                            if opt_terminal.is_some() {
                                vec.push(opt_terminal);
                            } else {
                                nullable = true;
                            }
                        }
                    }
                }
            }
            if !nullable {
                return;
            }
        }
        vec.push(None);
    }
}