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
package cfg;
import java.util.Arrays;
import java.util.Objects;
import cfg.CFG.Nonterminal;
import cfg.CFG.Symbol;
public class EarleyState implements Comparable<EarleyState> {
public Nonterminal lhs;
public Symbol[] rhs;
public int rhsIdx;
public int startIdx;
public EarleyState leftParent;
public EarleyState rightParent;
public EarleyState(Nonterminal lhs, Symbol[] rhs, int rhsIdx, int startIdx) {
this.lhs = lhs;
this.rhs = rhs;
this.rhsIdx = rhsIdx;
this.startIdx = startIdx;
}
public EarleyState(Nonterminal lhs, Symbol[] rhs, int startIdx) {
this(lhs, rhs, 0, startIdx);
}
@Override
public int hashCode() {
return Objects.hash(lhs, Arrays.hashCode(rhs), rhsIdx, startIdx);
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof EarleyState))
return false;
return compareTo((EarleyState) obj) == 0;
}
public int compareTo(EarleyState x) {
// Order rules by state first
if (startIdx + rhsIdx != x.startIdx + x.rhsIdx) {
return (startIdx + rhsIdx) - (x.startIdx + x.rhsIdx);
}
// Completed rules come first
if (isDone() != x.isDone()) {
return (rhs.length - rhsIdx) - (x.rhs.length - x.rhsIdx);
}
// \shrug, give up and arbitrary-compare at this point
return toString().compareTo(x.toString());
}
public EarleyState advance() {
return new EarleyState(this.lhs, this.rhs, this.rhsIdx + 1, this.startIdx);
}
public boolean isDone() {
return this.rhsIdx == this.rhs.length;
}
public Symbol nextSymbol() {
return this.rhs[this.rhsIdx];
}
@Override
public String toString() {
StringBuilder res = new StringBuilder(lhs.toString());
res.append(" ->");
for (int i = 0; i < rhs.length; i++) {
if (i == rhsIdx) {
res.append(" .");
}
res.append(" ").append(rhs[i].toString());
}
res.append(" ").append(startIdx);
return res.toString();
}
}