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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

use std::collections::BTreeMap;
use std::hash::Hash;

use crate::BuildError;

use super::parser::Parser;

impl<Term: Clone + Ord + Hash + Eq, NonTerm: Clone + Hash + Eq> Parser<Term, NonTerm> {
    /// merge states with same core ruleset.
    /// this builds LALR(1) parser from LR(1) parser
    pub fn optimize_lalr(&mut self) -> Result<(), BuildError<'_, Term, NonTerm>> {
        // group of states with same core ruleset
        let state_groups: Vec<_> = {
            let mut ruleset_state_map = BTreeMap::new();
            for (idx, state) in self.states.iter().enumerate() {
                // lalr consider two states same if core ruleset is same
                // lr(1) consider both core ruleset + lookaheads
                let ruleset: Vec<_> = state.ruleset.rules.keys().collect();
                ruleset_state_map
                    .entry(ruleset)
                    .or_insert_with(Vec::new)
                    .push(idx);
            }
            ruleset_state_map.into_values().collect()
        };

        // map from old state index to new state index
        let mut state_old_to_new = vec![0; self.states.len()];
        for (group_idx, state_group) in state_groups.iter().enumerate() {
            for s in state_group.iter() {
                state_old_to_new[*s] = group_idx;
            }
        }

        // redirect state index
        for state in self.states.iter_mut() {
            for (_, goto) in state.shift_goto_map_term.iter_mut() {
                *goto = state_old_to_new[*goto];
            }
            for (_, goto) in state.shift_goto_map_nonterm.iter_mut() {
                *goto = state_old_to_new[*goto];
            }
        }

        let mut new_states = Vec::with_capacity(state_groups.len());
        for state_group in state_groups.into_iter() {
            let mut new_state = self.states[state_group[0]].clone();
            for s in state_group.into_iter().skip(1) {
                let state = &mut self.states[s];

                // merge lookaheads
                for (rule, lookahead) in state.ruleset.rules.iter_mut() {
                    new_state
                        .ruleset
                        .rules
                        .get_mut(rule)
                        .unwrap()
                        .append(lookahead);
                }

                // merge goto map
                for (term, goto) in state.shift_goto_map_term.iter() {
                    if let Some(old) = new_state.shift_goto_map_term.insert(term.clone(), *goto) {
                        if old != *goto {
                            // this never happens
                            unreachable!("merging shift/goto map failed");
                        }
                    }
                }
                for (nonterm, goto) in state.shift_goto_map_nonterm.iter() {
                    if let Some(old) = new_state
                        .shift_goto_map_nonterm
                        .insert(nonterm.clone(), *goto)
                    {
                        if old != *goto {
                            // this never happens
                            unreachable!("merging shift/goto map failed");
                        }
                    }
                }

                // merge reduce map
                for (term, ruleid) in state.reduce_map.iter() {
                    if let Some(old) = new_state.reduce_map.insert(term.clone(), *ruleid) {
                        if old != *ruleid {
                            return Err(BuildError::ReduceReduceConflict {
                                lookahead: term.clone(),
                                rule1: old,
                                rule2: *ruleid,
                                rules: &self.rules,
                            });
                        }
                    }
                }
            }
            new_states.push(new_state);
        }

        self.main_state = state_old_to_new[self.main_state];
        self.states = new_states;

        Ok(())
    }
}