1 use crate::grammar::repr::*; 2 use crate::lr1::core::*; 3 4 use super::trace_graph::*; 5 use super::Tracer; 6 7 #[cfg(test)] 8 mod test; 9 10 /// A backtrace explaining how a particular shift: 11 /// 12 /// X = ...p (*) Token ... 13 /// 14 /// came to be in the list of items for some state S. This backtrace 15 /// always has a particular form. First, we can walk back over the 16 /// prefix, which will bring us to some set of states S1 all of which 17 /// contain the same item, but with the cursor at the front: 18 /// 19 /// X = (*) ...p Token ... 20 /// 21 /// Then we can walk back within those states some number of epsilon 22 /// moves, traversing nonterminals of the form: 23 /// 24 /// Y = (*) X ...s 25 /// 26 /// (Note that each nonterminal `Y` may potentially have many 27 /// productions of this form. I am not sure yet if they all matter or 28 /// not.) 29 /// 30 /// Finally, either we are in the start state, or else we reach some 31 /// production of the form: 32 /// 33 /// Z = ...p (*) Y ...s 34 /// 35 /// Ultimately this "trace" is best represented as a DAG. The problem 36 /// is that some of those nonterminals could, for example, be 37 /// optional. 38 39 impl<'trace, 'grammar> Tracer<'trace, 'grammar> { backtrace_shift( mut self, item_state: StateIndex, item: LR0Item<'grammar>, ) -> TraceGraph<'grammar>40 pub fn backtrace_shift( 41 mut self, 42 item_state: StateIndex, 43 item: LR0Item<'grammar>, 44 ) -> TraceGraph<'grammar> { 45 let symbol_sets = item.symbol_sets(); 46 47 // The states `S` 48 let pred_states = self.state_graph.trace_back(item_state, symbol_sets.prefix); 49 50 // Add the edge `[X] -{...p,Token,...s}-> [X = ...p (*) Token ...s]` 51 self.trace_graph 52 .add_edge(item.production.nonterminal.clone(), item, symbol_sets); 53 54 for pred_state in pred_states { 55 self.trace_epsilon_edges(pred_state, &item.production.nonterminal); 56 } 57 58 self.trace_graph 59 } 60 61 // Because item.index is 0, we know we are at an index 62 // like: 63 // 64 // Y = (*) ... 65 // 66 // This can only arise if `Y` is the start nonterminal 67 // or if there is an epsilon move from another item 68 // like: 69 // 70 // Z = ...p (*) Y ... 71 // 72 // So search for items like Z. trace_epsilon_edges(&mut self, item_state: StateIndex, nonterminal: &NonterminalString)73 fn trace_epsilon_edges(&mut self, item_state: StateIndex, nonterminal: &NonterminalString) // "Y" 74 { 75 if self.visited_set.insert((item_state, nonterminal.clone())) { 76 for pred_item in self.states[item_state.0].items.vec.iter() { 77 if pred_item.can_shift_nonterminal(nonterminal) { 78 if pred_item.index > 0 { 79 // Add an edge: 80 // 81 // [Z = ...p (*) Y ...s] -(...p,Y,...s)-> [Y] 82 self.trace_graph.add_edge( 83 pred_item, 84 nonterminal.clone(), 85 pred_item.symbol_sets(), 86 ); 87 } else { 88 // Trace back any incoming edges to [Z = ...p (*) Y ...]. 89 let pred_nonterminal = &pred_item.production.nonterminal; 90 self.trace_graph.add_edge( 91 pred_nonterminal.clone(), 92 nonterminal.clone(), 93 pred_item.symbol_sets(), 94 ); 95 self.trace_epsilon_edges(item_state, pred_nonterminal); 96 } 97 } 98 } 99 } 100 } 101 } 102