-
Notifications
You must be signed in to change notification settings - Fork 6
/
combinators.cljc
164 lines (138 loc) · 3.45 KB
/
combinators.cljc
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
(ns jasentaa.parser.combinators
(:require
[jasentaa.parser.basic :refer [match]]
[jasentaa.monad :as m :refer [>>=]]
[jasentaa.collections :refer [join]])
#?(:cljs (:require-macros
[jasentaa.monad :as m :refer [do*]])))
(defn and-then
"(ab)"
[p1 p2]
(m/do*
(r1 <- p1)
(r2 <- p2)
(m/return (join r1 r2))))
(defn or-else
"(a|b)
Non-deterministic choice (++) operator. Applies both parsers
to the argument string, and appends their list of results."
[p1 p2]
(fn [input]
(lazy-cat (m/bind input p1) (m/bind input p2))))
(defn choice
"(a|b)
Deterministic choice (+++) operator. Has the same behaviour
as `or-else`, except that at most one result is returned."
[p1 p2]
(fn [input]
(let [[x & xs] (m/bind input (or-else p1 p2))]
(if (nil? x)
[]
[x]))))
(declare plus)
(declare optional)
(defn many
"(a*)
Parse repeated applications of a parser; the many combinator
permits zero or more applications of the parser."
[p]
(optional (plus p)))
(defn plus
"(a+) is equivalent to (aa*)
Parse repeated applications of a parser; the plus combinator
permits one or more applications of the parser."
[p]
(m/do*
(a <- p)
(as <- (many p))
(m/return (cons a as))))
(defn optional
"(a?)
Parse zero or one applications of a parser."
[p]
(or-else p (m/return nil)))
(defn any-of [& ps]
"(a|b|c|...)
Parse application any of the given parsers."
(reduce or-else ps))
(def space
"Parse a single space, tab, newline or carriage-return."
(any-of
(match " ")
(match "\t")
(match "\n")
(match "\r")))
(def spaces
"Parse a string of (zero or more) spaces, tabs, and newlines."
(many space))
(defn string
"Parse a specific string."
[input]
(reduce and-then (map (comp match str) input)))
(defn token
"Parse a token using a parser p, throwing away any trailing space."
[p]
(m/do*
(a <- p)
spaces
(m/return a)))
(def symb
"Parse a symbolic token."
(comp token string))
(defn chain-left
"Parse repeated applications of a parser p, separated by
applications of a parser op whose result value is an
operator that is assumed to associate to the left, and
which is used to combine the results from the p parsers."
([p op a]
(choice
(chain-left p op)
(m/return a)))
([p op]
(m/do*
(a <- p)
(rst <- (many
(m/do*
(f <- op)
(b <- p)
(m/return [f b]))))
(m/return
(reduce
(fn [acc [f b]] (f acc b))
a
rst)))))
(defn chain-right
"Parse repeated applications of a parser p, separated by
applications of a parser op whose result value is an
operator that is assumed to associate to the right, and
which is used to combine the results from the p parsers.
"
([p op a]
(choice
(chain-right p op)
(m/return a)))
([p op]
(m/do*
(scan <- (many
(m/do*
(a <- p)
(f <- op)
(m/return [f a]))))
(b <- p)
(m/return
(reduce
(fn [acc [f a]] (f a acc))
b
(reverse scan))))))
(defn separated-by
"Parse repeated applications of a parser p, separated by
applications of a parser sep whose result values are
thrown away.
This parser will process at least one application of p.
For a list of zero or more, use:
(optional (separated-by p sep))"
[p sep]
(m/do*
(fst <- p)
(rst <- (many (m/do* sep p)))
(m/return (cons fst rst))))