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
125
126
127
|
// Package main shows an example of how to add precedence climbing to a Participle parser.
//
// Precedence climbing is an approach to parsing expressions that efficiently
// produces compact parse trees.
//
// In contrast, naive recursive descent expression parsers produce parse trees proportional in
// complexity to the number of operators supported. This impacts both readability and
// performance.
//
// It is based on https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing
package main
import (
"fmt"
"os"
"strconv"
"strings"
"github.com/alecthomas/repr"
"github.com/alecthomas/participle/v2"
"github.com/alecthomas/participle/v2/lexer"
)
type opInfo struct {
RightAssociative bool
Priority int
}
var info = map[string]opInfo{
"+": {Priority: 1},
"-": {Priority: 1},
"*": {Priority: 2},
"/": {Priority: 2},
"^": {RightAssociative: true, Priority: 3},
}
type Expr struct {
Terminal *int
Left *Expr
Op string
Right *Expr
}
func (e *Expr) String() string {
if e.Left != nil {
return fmt.Sprintf("(%s %s %s)", e.Left, e.Op, e.Right)
}
return fmt.Sprintf("%d", *e.Terminal)
}
func (e *Expr) Parse(lex *lexer.PeekingLexer) error {
*e = *parseExpr(lex, 0)
return nil
}
// (1 + 2) * 3
func parseExpr(lex *lexer.PeekingLexer, minPrec int) *Expr {
lhs := parseAtom(lex)
for {
tok := peek(lex)
if tok.EOF() || !isOp(rune(tok.Type)) || info[tok.Value].Priority < minPrec {
break
}
op := tok.Value
nextMinPrec := info[op].Priority
if !info[op].RightAssociative {
nextMinPrec++
}
lex.Next()
rhs := parseExpr(lex, nextMinPrec)
lhs = parseOp(op, lhs, rhs)
}
return lhs
}
func parseAtom(lex *lexer.PeekingLexer) *Expr {
tok := peek(lex)
if tok.Type == '(' {
lex.Next()
val := parseExpr(lex, 1)
if peek(lex).Value != ")" {
panic("unmatched (")
}
lex.Next()
return val
} else if tok.EOF() {
panic("unexpected EOF")
} else if isOp(rune(tok.Type)) {
panic("expected a terminal not " + tok.String())
} else {
lex.Next()
n, err := strconv.ParseInt(tok.Value, 10, 64)
if err != nil {
panic("invalid number " + tok.Value)
}
in := int(n)
return &Expr{Terminal: &in}
}
}
func isOp(rn rune) bool {
return strings.ContainsRune("+-*/^", rn)
}
func peek(lex *lexer.PeekingLexer) *lexer.Token {
return lex.Peek()
}
func parseOp(op string, lhs *Expr, rhs *Expr) *Expr {
return &Expr{
Op: op,
Left: lhs,
Right: rhs,
}
}
var parser = participle.MustBuild[Expr]()
func main() {
e, err := parser.ParseString("", strings.Join(os.Args[1:], " "))
fmt.Println(e)
repr.Println(e)
if err != nil {
panic(err)
}
}
|
