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
|
package grammar
import (
"crypto/sha256"
"encoding/hex"
"fmt"
)
type productionID [32]byte
func (id productionID) String() string {
return hex.EncodeToString(id[:])
}
func genProductionID(lhs symbol, rhs []symbol) productionID {
seq := lhs.byte()
for _, sym := range rhs {
seq = append(seq, sym.byte()...)
}
return productionID(sha256.Sum256(seq))
}
type productionNum uint16
const (
productionNumNil = productionNum(0)
productionNumStart = productionNum(1)
productionNumMin = productionNum(2)
)
func (n productionNum) Int() int {
return int(n)
}
type production struct {
id productionID
num productionNum
lhs symbol
rhs []symbol
rhsLen int
}
func newProduction(lhs symbol, rhs []symbol) (*production, error) {
if lhs.isNil() {
return nil, fmt.Errorf("LHS must be a non-nil symbol; LHS: %v, RHS: %v", lhs, rhs)
}
for _, sym := range rhs {
if sym.isNil() {
return nil, fmt.Errorf("a symbol of RHS must be a non-nil symbol; LHS: %v, RHS: %v", lhs, rhs)
}
}
return &production{
id: genProductionID(lhs, rhs),
lhs: lhs,
rhs: rhs,
rhsLen: len(rhs),
}, nil
}
func (p *production) isEmpty() bool {
return p.rhsLen == 0
}
type productionSet struct {
lhs2Prods map[symbol][]*production
id2Prod map[productionID]*production
num productionNum
}
func newProductionSet() *productionSet {
return &productionSet{
lhs2Prods: map[symbol][]*production{},
id2Prod: map[productionID]*production{},
num: productionNumMin,
}
}
func (ps *productionSet) append(prod *production) {
if _, ok := ps.id2Prod[prod.id]; ok {
return
}
if prod.lhs.isStart() {
prod.num = productionNumStart
} else {
prod.num = ps.num
ps.num++
}
if prods, ok := ps.lhs2Prods[prod.lhs]; ok {
ps.lhs2Prods[prod.lhs] = append(prods, prod)
} else {
ps.lhs2Prods[prod.lhs] = []*production{prod}
}
ps.id2Prod[prod.id] = prod
}
func (ps *productionSet) findByID(id productionID) (*production, bool) {
prod, ok := ps.id2Prod[id]
return prod, ok
}
func (ps *productionSet) findByLHS(lhs symbol) ([]*production, bool) {
if lhs.isNil() {
return nil, false
}
prods, ok := ps.lhs2Prods[lhs]
return prods, ok
}
func (ps *productionSet) getAllProductions() map[productionID]*production {
return ps.id2Prod
}
|
