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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
use lr1::core::*;
use grammar::repr::*;
use super::Tracer;
use super::trace_graph::*;
#[cfg(test)] mod test;
impl<'trace, 'grammar> Tracer<'trace, 'grammar> {
pub fn backtrace_reduce(mut self,
item_state: StateIndex,
item: LR0Item<'grammar>)
-> TraceGraph<'grammar>
{
self.trace_reduce_item(item_state, item);
self.trace_graph
}
fn trace_reduce_item(&mut self,
item_state: StateIndex,
item: LR0Item<'grammar>)
{
// We start out with an item
//
// X = ...p (*) ...s
//
// which we can (eventually) reduce, though we may have to do
// some epsilon reductions first if ...s is non-empty. We want
// to trace back until we have (at least) one element of
// context for the reduction.
let nonterminal = item.production.nonterminal; // X
// Add an edge
//
// [X] -{...p,_,...s}-> [X = ...p (*) ...s]
//
// because to reach that item we pushed `...p` from the start
// of `X` and afterwards we expect to see `...s`.
self.trace_graph.add_edge(nonterminal, item, item.symbol_sets());
// Walk back to the set of states S where we had:
//
// X = (*) ...p
let pred_states = self.state_graph.trace_back(item_state, item.prefix());
// Add in edges from [X] to all the places [X] can be consumed.
for pred_state in pred_states {
self.trace_reduce_from_state(pred_state, nonterminal);
}
}
// We know that we can reduce the nonterminal `Y`. We want to find
// at least one element of context, so we search back to find out
// who will consume that reduced value. So search for those items
// that can shift a `Y`:
//
// Z = ... (*) Y ...s
//
// If we find that `...s` is potentially empty, then we haven't
// actually found any context, and so we may have to keep
// searching.
fn trace_reduce_from_state(&mut self,
item_state: StateIndex,
nonterminal: NonterminalString) // "Y"
{
if !self.visited_set.insert((item_state, nonterminal)) {
return;
}
for pred_item in self.states[item_state.0]
.items
.vec
.iter()
.filter(|i| i.can_shift_nonterminal(nonterminal)) {
// Found a state:
//
// Z = ...p (*) Y ...s
//
// If `...s` does not match `\epsilon`, then we are done,
// because `FIRST(...s)` will provide a token of context.
// But otherwise we have to keep searching backwards.
let symbol_sets = pred_item.symbol_sets();
let first_suffix = self.first_sets.first0(symbol_sets.suffix);
let continue_tracing = first_suffix.contains_eof();
if !continue_tracing {
// Add an edge
//
// [Z = ...p (*) Y ...s] -(...p,Y,...s)-> [Y]
//
// and stop.
self.trace_graph.add_edge(pred_item.to_lr0(), nonterminal, symbol_sets);
} else {
// Add an edge
//
// [Z] -{..p}-> [Y]
//
// because we can reduce by consuming `...p`
// tokens, and continue tracing.
self.trace_graph.add_edge(pred_item.production.nonterminal,
nonterminal,
symbol_sets);
self.trace_reduce_item(item_state, pred_item.to_lr0());
}
}
}
}