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
use grammar::repr::*;
use lr1::core::*;
use lr1::lookahead::Lookahead;
use petgraph::{EdgeDirection, Graph};
use petgraph::graph::NodeIndex;
// Each state `s` corresponds to the node in the graph with index
// `s`. The edges are the shift transitions.
pub struct StateGraph {
graph: Graph<(), Symbol>
}
impl StateGraph {
pub fn new<'grammar, L>(states: &[State<'grammar, L>]) -> StateGraph
where L: Lookahead
{
let mut graph = Graph::new();
// First, create the nodes.
for i in 0..states.len() {
let j = graph.add_node(());
assert_eq!(i, j.index());
}
// Add in the edges.
for (i, state) in states.iter().enumerate() {
// Successors of a node arise from:
// - shifts (found in the `conflicts` and `tokens` maps)
// - gotos (found in the `gotos` map)
graph.extend_with_edges(
state.shifts
.iter()
.map(|(&terminal, &state)| {
(Symbol::Terminal(terminal), state)
})
.chain(
state.gotos
.iter()
.map(|(&nt, &state)| (Symbol::Nonterminal(nt), state)))
.map(|(symbol, successor)| {
(NodeIndex::new(i), NodeIndex::new(successor.0), symbol)
}));
}
StateGraph { graph: graph }
}
/// Given a list of symbols `[X, Y, Z]`, traces back from
/// `initial_state_index` to find the set of states whence we
/// could have arrived at `initial_state_index` after pushing `X`,
/// `Y`, and `Z`.
pub fn trace_back(&self,
initial_state_index: StateIndex,
initial_symbols: &[Symbol])
-> Vec<StateIndex> {
let mut stack = vec![(initial_state_index, initial_symbols)];
let mut result = vec![];
while let Some((state_index, symbols)) = stack.pop() {
if let Some((head, tail)) = symbols.split_last() {
stack.extend(
self.graph.edges_directed(NodeIndex::new(state_index.0),
EdgeDirection::Incoming)
.filter(|&(_, symbol)| symbol == head)
.map(|(pred, _)| (StateIndex(pred.index()), tail)));
} else {
result.push(state_index);
}
}
result.sort();
result.dedup();
result
}
pub fn successors(&self,
state_index: StateIndex)
-> Vec<StateIndex> {
self.graph.edges_directed(NodeIndex::new(state_index.0),
EdgeDirection::Outgoing)
.map(|(succ, _)| StateIndex(succ.index()))
.collect()
}
pub fn predecessors(&self,
state_index: StateIndex,
symbol: Symbol)
-> Vec<StateIndex> {
self.graph.edges_directed(NodeIndex::new(state_index.0),
EdgeDirection::Incoming)
.filter(|&(_, s)| *s == symbol)
.map(|(pred, _)| StateIndex(pred.index()))
.collect()
}
}