grammar_utils/lr0/
table.rs

1use std::collections::HashMap;
2
3use crate::*;
4use super::*;
5
6#[derive(Debug)]
7pub struct ParseTable<'g> {
8    grammar: &'g Grammar,
9    pub(crate) states: Vec<State<'g>>,
10    pub(crate) actions: HashMap<(StateIndex, Option<Symbol<'g>>), Vec<Action<'g>>>,
11}
12
13#[derive(Debug)]
14#[derive(Clone, Copy, PartialEq, Eq)]
15pub enum Action<'g> {
16    Shift(StateIndex),
17    Reduce(Rule<'g>),
18    Halt,
19}
20
21#[derive(Clone)]
22pub struct Conflict<'g, 't> {
23    table: &'t ParseTable<'g>,
24    state: StateIndex,
25    symbol: Option<Symbol<'g>>,
26    actions: Vec<Action<'g>>,
27}
28
29impl<'g> std::fmt::Debug for State<'g> {
30    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31        write!(f, "{:?}", &self.itemset().items())
32    }
33}
34
35impl<'g> ParseTable<'g> {
36    pub fn build(grammar: &'g Grammar, start_rule: Rule<'g>) -> ParseTable<'g> {
37        let states = Self::build_states(&grammar, start_rule);
38        let actions = Self::build_actions(&grammar, &states, start_rule);
39
40        ParseTable {
41            grammar,
42            states,
43            actions,
44        }
45    }
46
47    pub fn grammar(&self) -> &'g Grammar {
48        self.grammar
49    }
50
51    fn build_states(grammar: &'g Grammar, start_rule: Rule<'g>) -> Vec<State<'g>> {
52        let mut states = vec![];
53        let start_state = State::new(ItemSet::singleton(Item::new(start_rule, 0)));
54        let mut states_remaining = vec![start_state];
55
56        while let Some(state) = states_remaining.pop() {
57            for symbol in grammar.symbols() {
58                let next_state = State::new(state.itemset().follow(symbol));
59
60                if next_state.itemset().is_empty() {
61                    continue;
62                }
63
64                if !states.contains(&next_state) {
65                    states_remaining.push(next_state);
66                }
67            }
68
69            states.push(state);
70        }
71
72        states
73    }
74
75    fn build_actions(
76        grammar: &'g Grammar,
77        states: &[State<'g>],
78        start_rule: Rule<'g>,
79    ) -> HashMap<(StateIndex, Option<Symbol<'g>>), Vec<Action<'g>>> {
80
81        let mut actions = HashMap::new();
82
83        // Pre-allocate an empty list for all (state_i, maybe_symbol)-pairs
84        for (src_state_index, _src_state) in states.iter().enumerate() {
85            let src_state_index = StateIndex(src_state_index);
86            for symbol in grammar.symbols() {
87                let key = (src_state_index, Some(symbol));
88                actions.insert(key, vec![]);
89            }
90            actions.insert((src_state_index, None), vec![]);
91        }
92
93        for (src_state_index, src_state) in states.iter().enumerate() {
94            let src_state_index = StateIndex(src_state_index);
95            for src_item in src_state.itemset().items() {
96                match src_item.next_symbol() {
97                    Some(symbol) => {
98                        let dst_state = src_state.itemset().follow(symbol);
99                        let dst_state_index = Self::state_index(&dst_state, states);
100                        let key = (src_state_index, Some(symbol));
101                        let actions_for = actions.get_mut(&key).unwrap();
102
103                        let action = Action::Shift(StateIndex(dst_state_index));
104                        if !actions_for.contains(&action) {
105                            actions_for.push(action);
106                        }
107
108                    }
109                    None => {
110                        for symbol in grammar.symbols() {
111                            let key = (src_state_index, Some(symbol));
112                            let actions_for = actions.get_mut(&key).unwrap();
113                            actions_for.push(Action::Reduce(src_item.rule()));
114                        }
115
116                        let key = (src_state_index, None);
117                        let actions_for = actions.get_mut(&key).unwrap();
118                        actions_for.push(Action::Reduce(src_item.rule()));
119                    }
120                }
121            }
122        }
123
124        let key = (StateIndex(0), Some(start_rule.lhs()));
125        actions.get_mut(&key).unwrap().insert(0, Action::Halt);
126
127        actions
128    }
129
130    fn state_index(itemset: &ItemSet, itemsets: &[State]) -> usize {
131        itemsets
132            .iter()
133            .enumerate()
134            .find_map(|(j, st)| {
135                if itemset == st.itemset() {
136                    Some(j)
137                } else {
138                    None
139                }
140            })
141            .unwrap()
142    }
143
144    pub fn conflicts(&self) -> Vec<Conflict> {
145        let mut conflicts = vec![];
146        for (state_index, _state) in self.states.iter().enumerate() {
147            let state_index = StateIndex(state_index);
148            for symbol in self.grammar.symbols() {
149                let key = (state_index, Some(symbol));
150                let actions = &self.actions[&key];
151                if actions.len() > 1 {
152                    conflicts.push(Conflict {
153                        table: self,
154                        state: state_index,
155                        symbol: Some(symbol),
156                        actions: actions.clone(),
157                    });
158                }
159            }
160        }
161        conflicts
162    }
163}
164
165impl<'g, 't> std::fmt::Debug for Conflict<'g, 't> {
166    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
167        let state_id = self.state;
168        let symbol = self.symbol;
169        let actions = &self.actions;
170        write!(f, "Conflict(state={state_id:?}, symbol={symbol:?}, actions={actions:?})")?;
171        Ok(())
172    }
173}
174
175impl<'g, 't> Conflict<'g, 't> {
176    pub fn table(&self) -> &'t ParseTable<'g> {
177        self.table
178    }
179
180    pub fn state(&self) -> &'t State {
181        &self.table.states[usize::from(self.state)]
182    }
183
184    pub fn symbol(&self) -> Option<Symbol<'g>> {
185        self.symbol
186    }
187
188    pub fn actions(&self) -> &[Action<'g>] {
189        &self.actions
190    }
191}
grammar_utils/lr0/table.rs

grammar_utils/lr0/
table.rs
