lalrpop 0.4.0

convenient LR(1) parser generator
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

//! First set construction and computation.

use grammar::repr::*;
use std::collections::{HashMap, HashSet};
use util::{map};

use super::Lookahead;

#[cfg(test)]
mod test;

pub struct FirstSets {
    map: HashMap<NonterminalString, FirstSet>
}

pub type FirstSet = HashSet<Option<TerminalString>>;

impl FirstSets {
    pub fn new(grammar: &Grammar) -> FirstSets {
        let mut this = FirstSets { map: map() };
        let mut changed = true;
        while changed {
            changed = false;
            for production in grammar.productions.values().flat_map(|p| p.iter()) {
                let nt = production.nonterminal;
                let lookahead = this.first(&production.symbols, Lookahead::EOF);
                let first_set = this.map.entry(nt).or_insert_with(|| HashSet::new());
                let cardinality = first_set.len();
                first_set.extend(
                    lookahead.into_iter()
                             .map(|la| match la {
                                 Lookahead::EOF => None,
                                 Lookahead::Terminal(t) => Some(t),
                             }));
                changed |= (cardinality != first_set.len());
            }
        }
        this
    }

    pub fn first(&self, symbols: &[Symbol], lookahead: Lookahead) -> Vec<Lookahead> {
        let mut result = vec![];

        for symbol in symbols {
            match *symbol {
                Symbol::Terminal(t) => {
                    result.push(Lookahead::Terminal(t));
                    return result;
                }

                Symbol::Nonterminal(nt) => {
                    let mut empty_prod = false;
                    match self.map.get(&nt) {
                        None => {
                            // This should only happen during set
                            // construction; it corresponds to an
                            // entry that has not yet been
                            // built. Otherwise, it would mean a
                            // terminal with no productions. Either
                            // way, the resulting first set should be
                            // empty.
                        }
                        Some(set) => {
                            for &opt_terminal in set {
                                if let Some(terminal) = opt_terminal {
                                    result.push(Lookahead::Terminal(terminal));
                                } else {
                                    empty_prod = true;
                                }
                            }
                        }
                    }
                    if !empty_prod {
                        return result;
                    }
                }
            }
        }

        result.push(lookahead);
        result
    }
}