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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
module Lrama
class Counterexamples
class Example
attr_reader :path1, :path2, :conflict, :conflict_symbol
# path1 is shift conflict when S/R conflict
# path2 is always reduce conflict
def initialize(path1, path2, conflict, conflict_symbol, counterexamples)
@path1 = path1
@path2 = path2
@conflict = conflict
@conflict_symbol = conflict_symbol
@counterexamples = counterexamples
end
def type
@conflict.type
end
def path1_item
@path1.last.to.item
end
def path2_item
@path2.last.to.item
end
def derivations1
@derivations1 ||= _derivations(path1)
end
def derivations2
@derivations2 ||= _derivations(path2)
end
private
def _derivations(paths)
derivation = nil
current = :production
lookahead_sym = paths.last.to.item.end_of_rule? ? @conflict_symbol : nil
paths.reverse_each do |path|
item = path.to.item
case current
when :production
case path
when StartPath
derivation = Derivation.new(item, derivation)
current = :start
when TransitionPath
derivation = Derivation.new(item, derivation)
current = :transition
when ProductionPath
derivation = Derivation.new(item, derivation)
current = :production
end
if lookahead_sym && item.next_next_sym && item.next_next_sym.first_set.include?(lookahead_sym)
state_item = @counterexamples.transitions[[path.to, item.next_sym]]
derivation2 = find_derivation_for_symbol(state_item, lookahead_sym)
derivation.right = derivation2
lookahead_sym = nil
end
when :transition
case path
when StartPath
derivation = Derivation.new(item, derivation)
current = :start
when TransitionPath
# ignore
current = :transition
when ProductionPath
# ignore
current = :production
end
else
raise "BUG: Unknown #{current}"
end
break if current == :start
end
derivation
end
def find_derivation_for_symbol(state_item, sym)
queue = []
queue << [state_item]
while (sis = queue.shift)
si = sis.last
next_sym = si.item.next_sym
if next_sym == sym
derivation = nil
sis.reverse_each do |si|
derivation = Derivation.new(si.item, derivation)
end
return derivation
end
if next_sym.nterm? && next_sym.first_set.include?(sym)
@counterexamples.productions[si].each do |next_item|
next if next_item.empty_rule?
next_si = StateItem.new(si.state, next_item)
next if sis.include?(next_si)
queue << (sis + [next_si])
end
if next_sym.nullable
next_si = @counterexamples.transitions[[si, next_sym]]
queue << (sis + [next_si])
end
end
end
end
end
end
end
|
