grammar_utils/lr1/
table.rs1use 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> ParseTable<'g> {
30 pub fn build(grammar: &'g Grammar, start_rule: Rule<'g>) -> ParseTable<'g> {
31 let analysis = GrammarAnalysis::build(grammar);
32 let states = Self::build_states(&grammar, &analysis, start_rule);
33 let actions = Self::build_actions(&grammar, &analysis, &states, start_rule);
34
35 ParseTable {
36 grammar,
37 states,
38 actions,
39 }
40 }
41
42 pub fn grammar(&self) -> &'g Grammar {
43 self.grammar
44 }
45
46 fn build_states(
47 grammar: &'g Grammar,
48 analysis: &GrammarAnalysis<'g>,
49 start_rule: Rule<'g>,
50 ) -> Vec<State<'g>> {
51 let mut states = vec![];
52 let start_state = State::new(ItemSet::singleton(Item::new(start_rule, 0, vec![None].into_iter().collect()), analysis));
53 let mut states_remaining = vec![start_state];
54
55 while let Some(state) = states_remaining.pop() {
56 for symbol in grammar.symbols() {
57 let next_state = State::new(state.itemset().follow(analysis, symbol));
58
59 if next_state.itemset().is_empty() {
60 continue;
61 }
62
63 if !states.contains(&next_state) {
64 states_remaining.push(next_state);
65 }
66 }
67
68 states.push(state);
69 }
70
71 states
72 }
73
74 fn build_actions(
75 grammar: &'g Grammar,
76 analysis: &GrammarAnalysis<'g>,
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 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(&analysis, 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 src_item.lookahead() {
111 let key = (src_state_index, *symbol);
112 let actions_for = actions.get_mut(&key).unwrap();
113 actions_for.push(Action::Reduce(src_item.rule()));
114 }
115 }
116 }
117 }
118 }
119
120 let key = (StateIndex(0), Some(start_rule.lhs()));
121 actions.get_mut(&key).unwrap().insert(0, Action::Halt);
122
123 actions
124 }
125
126 fn state_index(itemset: &ItemSet, itemsets: &[State]) -> usize {
127 itemsets
128 .iter()
129 .enumerate()
130 .find_map(|(j, st)| {
131 if itemset == st.itemset() {
132 Some(j)
133 } else {
134 None
135 }
136 })
137 .unwrap()
138 }
139
140 pub fn conflicts(&self) -> Vec<Conflict> {
141 let mut conflicts = vec![];
142 for (state_index, _state) in self.states.iter().enumerate() {
143 let state_index = StateIndex(state_index);
144 for symbol in self.grammar.symbols() {
145 let key = (state_index, Some(symbol));
146 let actions = &self.actions[&key];
147 if actions.len() > 1 {
148 conflicts.push(Conflict {
149 table: self,
150 state: state_index,
151 symbol: Some(symbol),
152 actions: actions.clone(),
153 });
154 }
155 }
156 }
157 conflicts
158 }
159
160 pub fn get(&self, state_index: StateIndex, symbol: Option<Symbol<'g>>) -> Vec<Action<'g>> {
161 let key = (state_index, symbol);
162 self.actions.get(&key).unwrap().to_vec()
163 }
164
165 pub fn dump(&self) {
166 for (state_index, state) in self.states.iter().enumerate() {
167 let state_index = StateIndex(state_index);
168 eprintln!("{state_index:?}");
169 eprintln!("{state:?}");
170
171 for symbol in self.grammar.symbols() {
172 eprintln!(" {symbol:?} => {:?}", self.get(state_index, Some(symbol)));
173 }
174 eprintln!(" None => {:?}", self.get(state_index, None));
175 eprintln!();
176 }
177 }
178}
179
180impl<'g, 't> std::fmt::Debug for Conflict<'g, 't> {
181 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
182 let state_id = self.state;
183 let symbol = self.symbol;
184 let actions = &self.actions;
185 write!(f, "Conflict(state={state_id:?}, symbol={symbol:?}, actions={actions:?})")?;
186 Ok(())
187 }
188}
189
190impl<'g, 't> Conflict<'g, 't> {
191 pub fn table(&self) -> &'t ParseTable<'g> {
192 self.table
193 }
194
195 pub fn state(&self) -> &'t State {
196 &self.table.states[usize::from(self.state)]
197 }
198
199 pub fn symbol(&self) -> Option<Symbol<'g>> {
200 self.symbol
201 }
202
203 pub fn actions(&self) -> &[Action<'g>] {
204 &self.actions
205 }
206}