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
|
package grammar
import (
"crypto/sha256"
"encoding/hex"
"fmt"
"github.com/nihei9/vartan/grammar/symbol"
)
type productionID [32]byte
func (id productionID) String() string {
return hex.EncodeToString(id[:])
}
func genProductionID(lhs symbol.Symbol, rhs []symbol.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.Symbol
rhs []symbol.Symbol
rhsLen int
}
func newProduction(lhs symbol.Symbol, rhs []symbol.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.Symbol][]*production
id2Prod map[productionID]*production
num productionNum
}
func newProductionSet() *productionSet {
return &productionSet{
lhs2Prods: map[symbol.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.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
}
|
