1 use crate::grammar::repr::*; 2 use crate::lr1::core::*; 3 use crate::lr1::lookahead::Lookahead; 4 use petgraph::graph::NodeIndex; 5 use petgraph::prelude::*; 6 use petgraph::{EdgeDirection, Graph}; 7 8 // Each state `s` corresponds to the node in the graph with index 9 // `s`. The edges are the shift transitions. 10 pub struct StateGraph { 11 graph: Graph<(), Symbol>, 12 } 13 14 impl StateGraph { new<'grammar, L>(states: &[State<'grammar, L>]) -> StateGraph where L: Lookahead,15 pub fn new<'grammar, L>(states: &[State<'grammar, L>]) -> StateGraph 16 where 17 L: Lookahead, 18 { 19 let mut graph = Graph::new(); 20 21 // First, create the nodes. 22 for i in 0..states.len() { 23 let j = graph.add_node(()); 24 assert_eq!(i, j.index()); 25 } 26 27 // Add in the edges. 28 for (i, state) in states.iter().enumerate() { 29 // Successors of a node arise from: 30 // - shifts (found in the `conflicts` and `tokens` maps) 31 // - gotos (found in the `gotos` map) 32 graph.extend_with_edges( 33 state 34 .shifts 35 .iter() 36 .map(|(terminal, &state)| (Symbol::Terminal(terminal.clone()), state)) 37 .chain( 38 state 39 .gotos 40 .iter() 41 .map(|(nt, &state)| (Symbol::Nonterminal(nt.clone()), state)), 42 ) 43 .map(|(symbol, successor)| { 44 (NodeIndex::new(i), NodeIndex::new(successor.0), symbol) 45 }), 46 ); 47 } 48 49 StateGraph { graph } 50 } 51 52 /// Given a list of symbols `[X, Y, Z]`, traces back from 53 /// `initial_state_index` to find the set of states whence we 54 /// could have arrived at `initial_state_index` after pushing `X`, 55 /// `Y`, and `Z`. trace_back( &self, initial_state_index: StateIndex, initial_symbols: &[Symbol], ) -> Vec<StateIndex>56 pub fn trace_back( 57 &self, 58 initial_state_index: StateIndex, 59 initial_symbols: &[Symbol], 60 ) -> Vec<StateIndex> { 61 let mut stack = vec![(initial_state_index, initial_symbols)]; 62 let mut result = vec![]; 63 while let Some((state_index, symbols)) = stack.pop() { 64 if let Some((head, tail)) = symbols.split_last() { 65 stack.extend( 66 self.graph 67 .edges_directed(NodeIndex::new(state_index.0), EdgeDirection::Incoming) 68 .filter(|edge| edge.weight() == head) 69 .map(|edge| (StateIndex(edge.source().index()), tail)), 70 ); 71 } else { 72 result.push(state_index); 73 } 74 } 75 result.sort(); 76 result.dedup(); 77 result 78 } 79 successors(&self, state_index: StateIndex) -> Vec<StateIndex>80 pub fn successors(&self, state_index: StateIndex) -> Vec<StateIndex> { 81 self.graph 82 .edges_directed(NodeIndex::new(state_index.0), EdgeDirection::Outgoing) 83 .map(|edge| StateIndex(edge.target().index())) 84 .collect() 85 } 86 predecessors(&self, state_index: StateIndex, symbol: Symbol) -> Vec<StateIndex>87 pub fn predecessors(&self, state_index: StateIndex, symbol: Symbol) -> Vec<StateIndex> { 88 self.graph 89 .edges_directed(NodeIndex::new(state_index.0), EdgeDirection::Incoming) 90 .filter(|edge| *edge.weight() == symbol) 91 .map(|edge| StateIndex(edge.source().index())) 92 .collect() 93 } 94 } 95