forked from evylang/pratt
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
119 lines (102 loc) · 1.77 KB
/
main.go
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
package main
import (
_ "embed"
"flag"
"fmt"
evyStr "github.com/gozeloglu/pratt/internal/string"
)
func main() {
right := flag.Bool("r", false, "right associative")
left := flag.Bool("l", false, "left associative")
flag.Parse()
input := "1 * 2 + 3 * 4"
if len(flag.Args()) > 0 {
input = flag.Arg(0)
}
tokens := newTokens(input)
var ast any
if *right {
ast = parseR(tokens)
} else if *left {
ast = parseL(tokens)
} else {
ast = parse(tokens, lowest)
}
fmt.Println(ast)
}
// tokens is a token iterator
type tokens struct {
toks []string
curIdx int
}
func newTokens(input string) *tokens {
return &tokens{toks: evyStr.SplitByOperators(input)}
}
func (t *tokens) done() bool {
return t.curIdx >= len(t.toks)
}
func (t *tokens) cur() string {
if t.done() {
panic("no more tokens")
}
return t.toks[t.curIdx]
}
func (t *tokens) next() string {
token := t.cur()
t.curIdx++
return token
}
func (t *tokens) curPrec() int {
prec, ok := precedence[t.cur()]
if !ok {
panic("no precedence for " + t.cur())
}
return prec
}
const (
lowest = iota
comp
sum
product
)
var precedence = map[string]int{
"<": comp,
"+": sum,
"-": sum,
"*": product,
"/": product,
}
// expr is a node in the AST
type expr struct {
left any
op string
right any
}
func parseR(t *tokens) any {
left := t.next()
if t.done() {
return left
}
op := t.next()
right := parseR(t)
return expr{left, op, right}
}
func parseL(t *tokens) any {
var left any = t.next()
for !t.done() {
op := t.next()
right := t.next()
left = expr{left, op, right}
}
return left
}
func parse(t *tokens, prec int) any {
var left any = t.next()
for !t.done() && prec < t.curPrec() {
p := t.curPrec()
op := t.next()
right := parse(t, p)
left = expr{left, op, right}
}
return left
}