| 1 |
;;; |
| 2 |
;;; peg.scm - Parser Expression Grammar Parser |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2006 Rui Ueyama ([email protected]) |
| 5 |
;;; Copyright (c) 2008-2024 Shiro Kawai <[email protected]> |
| 6 |
;;; |
| 7 |
;;; Redistribution and use in source and binary forms, with or without |
| 8 |
;;; modification, are permitted provided that the following conditions |
| 9 |
;;; are met: |
| 10 |
;;; |
| 11 |
;;; 1. Redistributions of source code must retain the above copyright |
| 12 |
;;; notice, this list of conditions and the following disclaimer. |
| 13 |
;;; |
| 14 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 15 |
;;; notice, this list of conditions and the following disclaimer in the |
| 16 |
;;; documentation and/or other materials provided with the distribution. |
| 17 |
;;; |
| 18 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 19 |
;;; may be used to endorse or promote products derived from this |
| 20 |
;;; software without specific prior written permission. |
| 21 |
;;; |
| 22 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 23 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 24 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 25 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 26 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 27 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 28 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 29 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 30 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 31 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 32 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 33 |
;;; |
| 34 |
|
| 35 |
(define-module parser.peg |
| 36 |
(use scheme.list) |
| 37 |
(use scheme.charset) |
| 38 |
(use srfi.13) |
| 39 |
(use gauche.collection) |
| 40 |
(use gauche.generator) |
| 41 |
(use gauche.lazy) |
| 42 |
(use text.tree) |
| 43 |
(use util.match) |
| 44 |
(export <parse-error> |
| 45 |
make-peg-parse-error |
| 46 |
|
| 47 |
peg-run-parser |
| 48 |
peg-parse-string peg-parse-port |
| 49 |
peg-parser->generator peg-parser->lseq |
| 50 |
|
| 51 |
parse-success? |
| 52 |
return-result return-failure |
| 53 |
return-failure/expect return-failure/unexpect |
| 54 |
return-failure/message return-failure/compound |
| 55 |
|
| 56 |
$bind $return $fail $expect $lift $lift* $debug |
| 57 |
$let $let* $try $assert $not |
| 58 |
$or $fold-parsers $fold-parsers-right |
| 59 |
$seq $seq0 $list $list* $between |
| 60 |
$many $many1 $many_ $many1_ $repeat $repeat_ |
| 61 |
$many-till $many-till_ |
| 62 |
$optional |
| 63 |
$sep-by $end-by $sep-end-by |
| 64 |
$chain-left $chain-right |
| 65 |
$lazy $parameterize |
| 66 |
|
| 67 |
$cut $raise |
| 68 |
|
| 69 |
$any $eos $. |
| 70 |
|
| 71 |
$string $string-ci |
| 72 |
$char $one-of $none-of |
| 73 |
$satisfy $match1 $match1* |
| 74 |
$binding $lbinding |
| 75 |
|
| 76 |
$->rope $->string $->symbol rope->string rope-finalize |
| 77 |
) |
| 78 |
) |
| 79 |
|
| 80 |
(select-module parser.peg) |
| 81 |
|
| 82 |
;;;============================================================ |
| 83 |
;;; How is EBNF represented in the PEG library? |
| 84 |
;;; |
| 85 |
;;; A ::= B C |
| 86 |
;;; => (define a ($seq b c)) |
| 87 |
;;; If you need values of B and C, use monadic macro $let, or applicative |
| 88 |
;;; combinator $lift |
| 89 |
;;; => (define a ($let ([x b] [y c]) ($return (cons x y)))) |
| 90 |
;;; => (define a ($lift cons b c) |
| 91 |
;;; |
| 92 |
;;; A :: B | C |
| 93 |
;;; => (define a ($or b c)) |
| 94 |
;;; To be precise, this actually mean B / C in PEG; if B fails without |
| 95 |
;;; consuming input, we try C. But if B ever consumes input, we don't |
| 96 |
;;; backtrack and A fails. If you want backtracking, use $try as well. |
| 97 |
;;; => (define a ($or ($try b) c)) |
| 98 |
;;; |
| 99 |
;;; A :: B* |
| 100 |
;;; => (define a ($many b)) |
| 101 |
;;; A :: B+ |
| 102 |
;;; => (define a ($many b 1)) |
| 103 |
;;; A ::= B B | B B B |
| 104 |
;;; => (define a ($many b 2 3)) |
| 105 |
;;; '$many' gathers the semantic values of B into list. One common case |
| 106 |
;;; is that you want a string out of gathered values. $->string is a |
| 107 |
;;; combinator that just translates the semantic value. |
| 108 |
;;; => (define a ($->string ($many b))) |
| 109 |
;;; If the result of a is further gathered, it is wasteful to make it |
| 110 |
;;; a string, since it will be thrown away soon. We have an efficient |
| 111 |
;;; intermediate string representation called rope. Here you can make |
| 112 |
;;; the result of a as rope: |
| 113 |
;;; => (define a ($->rope ($many b))) |
| 114 |
;;; Later, you can concatenate and convert ropes to a string by |
| 115 |
;;; rope->string. |
| 116 |
;;; If you don't need the values, you can use $many_ instead, which |
| 117 |
;;; is more efficient. |
| 118 |
;;; |
| 119 |
;;; A ::= B? |
| 120 |
;;; => (define a ($optional b)) |
| 121 |
;;; |
| 122 |
;;; |
| 123 |
|
| 124 |
|
| 125 |
;;; In this module, we provide various constructors of PARSERs, |
| 126 |
;;; and DRIVER procedures. |
| 127 |
;;; |
| 128 |
;;; A PARSER is merely a closure that takes a list of input (most |
| 129 |
;;; likely it's a lazy sequence of characters, but it can be a |
| 130 |
;;; list of anything), and returns three results: |
| 131 |
;;; |
| 132 |
;;; Status: #f if parse is successful, or a symbol to indicate |
| 133 |
;;; a kind of error. |
| 134 |
;;; Value: parsed value, or error message. |
| 135 |
;;; Next: a list of next input. |
| 136 |
;;; |
| 137 |
;;; That is, |
| 138 |
;;; Parser :: [a] -> (Status, Value, [a]) |
| 139 |
;;; |
| 140 |
;;; Failure status and value |
| 141 |
;;; |
| 142 |
;;; status value |
| 143 |
;;; ------------------------------------------------ |
| 144 |
;;; fail-message string (message) |
| 145 |
;;; fail-expect string (message), char, char-set |
| 146 |
;;; fail-unexpect string (message) |
| 147 |
;;; fail-compound ((Status . Value) ...) |
| 148 |
;;; fail-error (tag (Status . Value ...)) |
| 149 |
;;; |
| 150 |
;;; A DRIVER is a wrapper to take a parser and an input. |
| 151 |
;;; DRIVER applies the parser on the input, and on success, it returns the |
| 152 |
;;; value and the rest of the input. On failure, it translates the error |
| 153 |
;;; status into <parser-error> object and raises it. |
| 154 |
;;; |
| 155 |
|
| 156 |
;;;============================================================ |
| 157 |
;;; Parse result types |
| 158 |
;;; |
| 159 |
|
| 160 |
;; An error object for the external API. Note that a parser won't raise |
| 161 |
;; this error; it just returns a 'failure' value, so that other options |
| 162 |
;; can be tried if there's any. Creating, throwing, and catching an error |
| 163 |
;; is expensive operation compared to the simple call/return. It is the |
| 164 |
;; parser driver that sees the failure as the final result, and constructs |
| 165 |
;; <parse-error> to raise. |
| 166 |
;; NB: 'Token' slot is (car rest) or #<eof>. It's redundant, but kept for |
| 167 |
;; the backward compatibility. |
| 168 |
(define-condition-type <parse-error> <error> #f |
| 169 |
(position) ;stream position |
| 170 |
(type) ;fail type |
| 171 |
(objects) ;expecting/unexpecting items |
| 172 |
(token) ;token that caused error |
| 173 |
(rest)) ;rest of input string, including token |
| 174 |
|
| 175 |
(define-method write-object ((o <parse-error>) out) |
| 176 |
(format out "#<<parse-error> ~S>" (~ o 'message))) |
| 177 |
|
| 178 |
;; Primitive parts to be used inside custom parser. |
| 179 |
;; The user usually doesn't need to use them, as long as he construct |
| 180 |
;; parsers by parser combinators. |
| 181 |
(define-inline (parse-success? x) (not x)) |
| 182 |
|
| 183 |
(define-inline (return-result v s) (values #f v s)) |
| 184 |
(define-hybrid-syntax return-failure |
| 185 |
(^[t v s] (values t v s)) |
| 186 |
;; If type is given as a literal symbol, we statically check it. |
| 187 |
(er-macro-transformer |
| 188 |
(^[f r c] |
| 189 |
(match f |
| 190 |
[(_ ('quote x) v s) |
| 191 |
(unless (memq x '(fail-message fail-expect fail-unexpect |
| 192 |
fail-error fail-compound)) |
| 193 |
(error "Invalid failure type; must be one of fail-message, \ |
| 194 |
fail-expect, fail-unexpect, fail-compund or \ |
| 195 |
fail-error, but got: " x)) |
| 196 |
(quasirename r |
| 197 |
`(values ',x ,v ,s))] |
| 198 |
[(_ t v s) |
| 199 |
(quasirename r |
| 200 |
`(values ,t ,v ,s))] |
| 201 |
[_ f])))) |
| 202 |
(define-inline (return-failure/message v s) (values 'fail-message v s)) |
| 203 |
(define-inline (return-failure/expect v s) (values 'fail-expect v s)) |
| 204 |
(define-inline (return-failure/unexpect v s) (values 'fail-unexpect v s)) |
| 205 |
(define-inline (return-failure/compound v s) (values 'fail-compound v s)) |
| 206 |
(define (return-error-from-failure tag failure payload s) |
| 207 |
(case failure |
| 208 |
[(fail-error) (match-let1 (_ . alist) payload |
| 209 |
(values 'fail-error `(,tag . ,alist) s))] |
| 210 |
[else (values 'fail-error `(,tag (,failure . ,payload)) s)])) |
| 211 |
|
| 212 |
(define (make-peg-parse-error type objs pos seq) |
| 213 |
(define (flatten-compound-error objs) |
| 214 |
(append-map (^e (if (eq? (car e) 'fail-compound) |
| 215 |
(flatten-compound-error (cdr e)) |
| 216 |
(list e))) |
| 217 |
objs)) |
| 218 |
(define (analyze-compound-error objs pos) |
| 219 |
(let1 grps (map (^g (cons (caar g) (map cdr g))) |
| 220 |
(group-collection (flatten-compound-error objs) :key car)) |
| 221 |
(let ([msgs (assoc-ref grps 'fail-message)] |
| 222 |
[exps (assoc-ref grps 'fail-expect)] |
| 223 |
[unexps (assoc-ref grps 'fail-unexpect)]) |
| 224 |
(tree->string |
| 225 |
(cons (or-concat (cond-list |
| 226 |
[exps (compound-exps exps)] |
| 227 |
[unexps (compound-unexps unexps)] |
| 228 |
[msgs msgs])) |
| 229 |
(format " at ~a" pos)))))) |
| 230 |
(define (or-concat lis) |
| 231 |
(define (rec lis) |
| 232 |
(match lis |
| 233 |
[(x y) `("(",x") or (",y")")] |
| 234 |
[(x . more) `("(",x"), ",@(rec more))])) |
| 235 |
(match lis |
| 236 |
[() '()] |
| 237 |
[(x) `(,x)] |
| 238 |
[xs (rec xs)])) |
| 239 |
(define (compound-exps exps) |
| 240 |
(match (delete-duplicates exps equal?) |
| 241 |
[(x) (format "expecting ~s" x)] |
| 242 |
[(xs ...) (format "expecting one of ~s" xs)])) |
| 243 |
(define (compound-unexps unexps) |
| 244 |
(match (delete-duplicates unexps equal?) |
| 245 |
[(x) (format "not expecting ~s" x)] |
| 246 |
[(xs ...) (format "not expecting any of ~s" xs)])) |
| 247 |
(define pos-fmt |
| 248 |
(if (sequence-position? pos) |
| 249 |
(format "~s:~a:~a" |
| 250 |
(or (sequence-position-source pos) "(unknown input)") |
| 251 |
(sequence-position-line pos) |
| 252 |
(sequence-position-column pos)) |
| 253 |
pos)) |
| 254 |
(define (message objs pos nexttok) |
| 255 |
(case type |
| 256 |
[(fail-message) (format "~a at ~a" objs pos-fmt)] ;objs is a string message |
| 257 |
[(fail-expect) |
| 258 |
(if (char? objs) |
| 259 |
(format "expecting ~s at ~a, but got ~s" objs pos-fmt nexttok) |
| 260 |
(format "expecting ~a at ~a, but got ~s" objs pos-fmt nexttok))] |
| 261 |
[(fail-unexpect) |
| 262 |
(if (char? objs) |
| 263 |
(format "expecting but ~s at ~a, and got ~s" objs pos-fmt nexttok) |
| 264 |
(format "expecting but ~a at ~a, and got ~s" objs pos-fmt nexttok))] |
| 265 |
[(fail-compound) (analyze-compound-error objs pos)] |
| 266 |
[(fail-error) (analyze-compound-error (cdr objs) pos)] ;car is a tag |
| 267 |
[else (format "unknown parser error at ~a: ~a" pos-fmt objs)] ;for safety |
| 268 |
)) |
| 269 |
(let ([nexttok (if (pair? seq) (car seq) (eof-object))]) |
| 270 |
(make-condition <parse-error> |
| 271 |
'position pos 'type type 'objects objs |
| 272 |
'token nexttok 'rest seq |
| 273 |
'message (message objs pos nexttok)))) |
| 274 |
|
| 275 |
(define (%get-input-pos head s) |
| 276 |
(or (lseq-position s) |
| 277 |
(let loop ([c 0] [head head]) |
| 278 |
(cond [(eq? head s) c] |
| 279 |
[(null? head) "(unknown position)"] |
| 280 |
[else (loop (+ c 1) (cdr head))])))) |
| 281 |
|
| 282 |
(define (construct-peg-parser-error r v s s1) |
| 283 |
(make-peg-parse-error r v (%get-input-pos s s1) s1)) |
| 284 |
|
| 285 |
;; API |
| 286 |
;; Default driver. Returns parsed value and next stream |
| 287 |
(define (peg-run-parser parser s) |
| 288 |
(receive (r v s1) (parser s) |
| 289 |
(if (parse-success? r) |
| 290 |
(values (rope-finalize v) s1) |
| 291 |
(raise (construct-peg-parser-error r v s s1))))) |
| 292 |
|
| 293 |
;; Coerce something to lseq. accepts generator. |
| 294 |
;; We check applicability of x->lseq first, since an object can be both |
| 295 |
;; passed to x->lseq and applicable as a thunk, but x->lseq should take |
| 296 |
;; precedence. |
| 297 |
;; NB: This is not abstract enough---the gory details should be hidden |
| 298 |
;; in gauche.lazy module. |
| 299 |
(define (%->lseq obj) |
| 300 |
(cond [(eq? (class-of obj) <pair>) obj] ;avoid forcing a lazy pair |
| 301 |
[(applicable? x->generator (class-of obj)) |
| 302 |
(generator->lseq (x->generator obj))] |
| 303 |
[(applicable? obj) (generator->lseq obj)] |
| 304 |
[else (error "object cannot be used as a source of PEG parser:" obj)])) |
| 305 |
|
| 306 |
;; API |
| 307 |
;; NB: We can consolidate peg-parse-string and peg-parse-port via |
| 308 |
;; x->generator, but should we? |
| 309 |
(define (peg-parse-string parser str :optional (cont #f)) |
| 310 |
(check-arg string? str) |
| 311 |
(receive (r rest) (peg-run-parser parser (x->lseq str)) |
| 312 |
(if cont |
| 313 |
(cont r rest) |
| 314 |
r))) |
| 315 |
;; API |
| 316 |
(define (peg-parse-port parser port :optional (cont #f)) |
| 317 |
(check-arg input-port? port) |
| 318 |
(receive (r rest) (peg-run-parser parser (x->lseq port)) |
| 319 |
(if cont |
| 320 |
(cont r rest) |
| 321 |
r))) |
| 322 |
|
| 323 |
;; API |
| 324 |
;; Returns a generator |
| 325 |
(define (peg-parser->generator parser src) |
| 326 |
(let1 s (%->lseq src) |
| 327 |
(^[] (if (null? s) |
| 328 |
(eof-object) |
| 329 |
(receive (r v s1) (parser s) |
| 330 |
(cond [(not (parse-success? r)) |
| 331 |
(raise (construct-peg-parser-error r v s s1))] |
| 332 |
[(eof-object? v) (set! s '()) v] |
| 333 |
[else (set! s s1) (rope-finalize v)])))))) |
| 334 |
|
| 335 |
;; API |
| 336 |
;; Returns an lseq |
| 337 |
;; Input position info is propagated if available |
| 338 |
(define (peg-parser->lseq parser src) |
| 339 |
(let1 s (%->lseq src) |
| 340 |
(generator->lseq |
| 341 |
(^[] (if (null? s) |
| 342 |
(eof-object) |
| 343 |
(receive (r v s1) (parser s) |
| 344 |
;; TODO: Refactor this part and similar part above |
| 345 |
(let1 val (cond [(not (parse-success? r)) |
| 346 |
(raise (construct-peg-parser-error r v s s1))] |
| 347 |
[(eof-object? v) (set! s '()) v] |
| 348 |
[else (set! s s1) (rope-finalize v)]) |
| 349 |
(if-let1 pos (lseq-position s) |
| 350 |
(values val pos) |
| 351 |
val)))))))) |
| 352 |
|
| 353 |
;;;============================================================ |
| 354 |
;;; Lazily-constructed string |
| 355 |
;;; |
| 356 |
|
| 357 |
(define-inline (make-rope obj) |
| 358 |
(cons 'rope obj)) |
| 359 |
|
| 360 |
(define-inline (rope? obj) |
| 361 |
(and (pair? obj) (eq? (car obj) 'rope))) |
| 362 |
|
| 363 |
(inline-stub |
| 364 |
(define-cfn rope2string_int (obj p) ::void :static |
| 365 |
(label restart) |
| 366 |
(cond [(SCM_STRINGP obj) (SCM_PUTS obj p)] |
| 367 |
[(SCM_CHARP obj) (SCM_PUTC (SCM_CHAR_VALUE obj) p)] |
| 368 |
[(SCM_PAIRP obj) |
| 369 |
(when (SCM_EQ (SCM_CAR obj) 'rope) |
| 370 |
(set! obj (SCM_CDR obj)) (goto restart)) |
| 371 |
(for-each (lambda (elt) |
| 372 |
(cond [(SCM_STRINGP elt) (SCM_PUTS elt p)] |
| 373 |
[(SCM_CHARP elt) (SCM_PUTC (SCM_CHAR_VALUE elt) p)] |
| 374 |
[else (rope2string_int elt p)])) |
| 375 |
obj)] |
| 376 |
[(not (or (SCM_NULLP obj) (SCM_FALSEP obj))) |
| 377 |
(Scm_Error "rope->string: unknown object to write: %S" obj)])) |
| 378 |
|
| 379 |
(define-cproc rope->string (obj) |
| 380 |
(let* ([p (Scm_MakeOutputStringPort TRUE)]) |
| 381 |
(rope2string_int obj p) |
| 382 |
(return (Scm_GetOutputString (SCM_PORT p) 0)))) |
| 383 |
) |
| 384 |
|
| 385 |
;;;============================================================ |
| 386 |
;;; Primitives |
| 387 |
;;; |
| 388 |
|
| 389 |
(define-inline ($return val) (^s (return-result val s))) |
| 390 |
|
| 391 |
(define ($fail msg) (^s (return-failure/message msg s))) |
| 392 |
|
| 393 |
(define $raise |
| 394 |
(case-lambda |
| 395 |
[(tag msg) |
| 396 |
(^s (return-failure 'fail-error `(,tag (fail-message . ,msg)) s))] |
| 397 |
[(msg) |
| 398 |
(^s (return-failure 'fail-error `(error (fail-message . ,msg)) s))])) |
| 399 |
|
| 400 |
;; return a parser that tries PARSE. On success, returns what it |
| 401 |
;; returned. On failure, returns 'fail-expect with MSG. |
| 402 |
(define ($expect parse msg) |
| 403 |
(^s (receive (r v ss) (parse s) |
| 404 |
(if (parse-success? r) |
| 405 |
(return-result v ss) |
| 406 |
(return-failure/expect msg ss))))) |
| 407 |
|
| 408 |
;; A convenience utility to check the upper bound, allowing unlimited |
| 409 |
;; upper bound by #f. |
| 410 |
(define-inline (>=? count max) (and max (>= count max))) |
| 411 |
|
| 412 |
;;;============================================================ |
| 413 |
;;; Combinators |
| 414 |
;;; |
| 415 |
|
| 416 |
;; API |
| 417 |
;; p :: Parser |
| 418 |
;; f :: Value -> Parser |
| 419 |
;; $bind :: Parser, (Value -> Parser) -> Parser |
| 420 |
(define-inline ($bind p f) |
| 421 |
(^s (receive [r v s1] (p s) |
| 422 |
(if (parse-success? r) |
| 423 |
((f v) s1) |
| 424 |
(return-failure r v s1))))) |
| 425 |
|
| 426 |
;; API |
| 427 |
;; $lift :: (a,...) -> b, (Parser,..) -> Parser |
| 428 |
;; ($lift f parser) == ($let ([x parser]) ($return (f x))) |
| 429 |
;; |
| 430 |
;; $lift* is like $lift, but f gets semantic values as a single list. |
| 431 |
;; |
| 432 |
;; The number of parsers is almost always fixed, and we macro-expand into |
| 433 |
;; chain of parser calls in such cases. |
| 434 |
|
| 435 |
;; Aux function for macro expander |
| 436 |
(define (expand-$lift *?) |
| 437 |
) |
| 438 |
|
| 439 |
(define-hybrid-syntax $lift |
| 440 |
(^[f . parsers] |
| 441 |
;; We don't use the straightforward definition (using $let or $bind) |
| 442 |
;; to reduce closure construction. |
| 443 |
(^s (let accum ([s s] [parsers parsers] [vs '()]) |
| 444 |
(if (null? parsers) |
| 445 |
(return-result (apply f (reverse vs)) s) |
| 446 |
(receive [r v s1] ((car parsers) s) |
| 447 |
(if (parse-success? r) |
| 448 |
(accum s1 (cdr parsers) (cons v vs)) |
| 449 |
(return-failure r v s1))))))) |
| 450 |
(er-macro-transformer |
| 451 |
(^[f r c] |
| 452 |
(define (generate-1 fn vs ps s) |
| 453 |
(if (null? ps) |
| 454 |
(quasirename r `(return-result (,fn ,@(reverse vs)) ,s)) |
| 455 |
(let* ([v1 (gensym "v")] |
| 456 |
[inner (generate-1 fn (cons v1 vs) (cdr ps) s)]) |
| 457 |
(quasirename r `(receive [res ,v1 ,s] (,(car ps) ,s) |
| 458 |
(if (parse-success? res) |
| 459 |
,inner |
| 460 |
(return-failure res ,v1 ,s))))))) |
| 461 |
(match f |
| 462 |
[(_ fn . ps) |
| 463 |
(let1 s (r's) |
| 464 |
(quasirename r |
| 465 |
`(^[,s] ,(generate-1 fn '() ps s))))] |
| 466 |
[_ f])))) |
| 467 |
|
| 468 |
(define-hybrid-syntax $lift* |
| 469 |
(^[f . parsers] |
| 470 |
(^s (let accum ([s s] [parsers parsers] [vs '()]) |
| 471 |
(if (null? parsers) |
| 472 |
(return-result (f (reverse vs)) s) |
| 473 |
(receive [r v s1] ((car parsers) s) |
| 474 |
(if (parse-success? r) |
| 475 |
(accum s1 (cdr parsers) (cons v vs)) |
| 476 |
(return-failure r v s1))))))) |
| 477 |
(er-macro-transformer |
| 478 |
(^[f r c] |
| 479 |
(define (generate-1 fn vs ps s) |
| 480 |
(if (null? ps) |
| 481 |
(quasirename r `(return-result (,fn (list ,@(reverse vs))) ,s)) |
| 482 |
(let* ([v1 (gensym "v")] |
| 483 |
[inner (generate-1 fn (cons v1 vs) (cdr ps) s)]) |
| 484 |
(quasirename r `(receive [res ,v1 ,s] (,(car ps) ,s) |
| 485 |
(if (parse-success? res) |
| 486 |
,inner |
| 487 |
(return-failure res ,v1 ,s))))))) |
| 488 |
(match f |
| 489 |
[(_ fn . ps) |
| 490 |
(let1 s (r's) |
| 491 |
(quasirename r |
| 492 |
`(^[,s] ,(generate-1 fn '() ps s))))] |
| 493 |
[_ f])))) |
| 494 |
|
| 495 |
;; API |
| 496 |
;; For debugging |
| 497 |
(define ($debug name parser) |
| 498 |
(^s (format (current-error-port) "#?parser(~a)<~,,,,v:s\n" |
| 499 |
name (debug-print-width) s) |
| 500 |
(receive [r v s] (parser s) |
| 501 |
(debug-print-post (list r v s)) |
| 502 |
(values r v s)))) |
| 503 |
|
| 504 |
;; API |
| 505 |
;; Convert failure to error |
| 506 |
(define $cut |
| 507 |
(case-lambda |
| 508 |
[(tag parser) (^s (receive (r v s) (parser s) |
| 509 |
(if (parse-success? r) |
| 510 |
(return-result v s) |
| 511 |
(return-error-from-failure tag r v s))))] |
| 512 |
[(parser) ($cut 'error parser)])) |
| 513 |
|
| 514 |
;; API |
| 515 |
;; $let (bind ...) body ... |
| 516 |
;; where |
| 517 |
;; bind := (var parser) |
| 518 |
;; | (parser) |
| 519 |
;; | parser |
| 520 |
;; var's are visible from body ... (but not from parser) |
| 521 |
(define-syntax $let |
| 522 |
(er-macro-transformer |
| 523 |
(^[f r c] |
| 524 |
(match f |
| 525 |
[(_ (bind ...) body ...) |
| 526 |
(let1 vars&parsers |
| 527 |
(map (^b (match b |
| 528 |
[(var parser) `(,var ,(gensym "parser") ,parser)] |
| 529 |
[(parser) `(,(gensym "_") ,(gensym "parser") ,parser)] |
| 530 |
[parser `(,(gensym "_") ,(gensym "parser") ,parser)])) |
| 531 |
bind) |
| 532 |
(quasirename r |
| 533 |
`(let (,@(map (^b `(,(cadr b) ,(caddr b))) vars&parsers)) |
| 534 |
,@(let loop ([vars&parsers vars&parsers]) |
| 535 |
(if (null? vars&parsers) |
| 536 |
body |
| 537 |
(match-let1 [(var pvar _) . rest] vars&parsers |
| 538 |
(quasirename r |
| 539 |
`(($bind ,pvar (^[,var] ,@(loop rest)))))))))))] |
| 540 |
[_ (error "Malformed $let:" f)])))) |
| 541 |
|
| 542 |
;; API |
| 543 |
;; $let* (bind ...) body ... |
| 544 |
;; where |
| 545 |
;; bind := (var parser) |
| 546 |
;; | (parser) |
| 547 |
;; | parser |
| 548 |
;; var's are visible from subsequent bind and body |
| 549 |
(define-syntax $let* |
| 550 |
(er-macro-transformer |
| 551 |
(^[f r c] |
| 552 |
(match f |
| 553 |
[(_ () body ...) (quasirename r `(begin ,@body))] |
| 554 |
[(_ ((var parser) bind ...) body ...) |
| 555 |
(quasirename r |
| 556 |
`($bind ,parser (^[,var] ($let* ,bind ,@body))))] |
| 557 |
[(_ ((parser) bind ...) body ...) |
| 558 |
(quasirename r |
| 559 |
`($bind ,parser (^[,(gensym "_")] ($let* ,bind ,@body))))] |
| 560 |
[(_ (parser bind ...) body ...) |
| 561 |
(quasirename r |
| 562 |
`($bind ,parser (^[,(gensym "_")] ($let* ,bind ,@body))))] |
| 563 |
[_ (error "Malformed $let*:" f)])))) |
| 564 |
|
| 565 |
;; API |
| 566 |
;; ($parameterize ((param expr) ..) parser ...) |
| 567 |
;; Returns a parser that run parser ... while altering the parameter values |
| 568 |
;; like parameterize. The parser ... are run as if in $seq. |
| 569 |
;; Suggested by Saito Atsushi |
| 570 |
(define-syntax $parameterize |
| 571 |
(er-macro-transformer |
| 572 |
(^[f r c] |
| 573 |
(match f |
| 574 |
[(_ ((p e) ...) parser ...) |
| 575 |
(let1 tmp (gensym) |
| 576 |
(quasirename r |
| 577 |
`(let1 ,tmp ($seq ,@parser) |
| 578 |
(^[s] (parameterize (,@(map list p e)) |
| 579 |
(,tmp s))))))])))) |
| 580 |
|
| 581 |
;; API |
| 582 |
;; $or p1 p2 ... |
| 583 |
;; $or p1 p2 ... :else pz |
| 584 |
;; Ordered choice. |
| 585 |
;; When all of p1 p2 ... fail without consuming input, returns compound |
| 586 |
;; failure of all of them, except in the latter form, where all the failures |
| 587 |
;; before pz is discarded. Usually, pz is ($fail ...) to give a nicer |
| 588 |
;; failure message than the compound one. |
| 589 |
(define ($or . parsers) |
| 590 |
(define (fail vs s) |
| 591 |
(match vs |
| 592 |
[((r . v)) (values r v s)] ;; no need to create compound error |
| 593 |
[vs (return-failure/compound (reverse vs) s)])) |
| 594 |
(match parsers |
| 595 |
[() (^s (return-failure/message "empty $or" s))] |
| 596 |
[(p) p] |
| 597 |
[(ps ...) |
| 598 |
(^s (let loop ([vs '()] [ps ps]) |
| 599 |
(if (eq? (car ps) :else) |
| 600 |
(if (null? (cdr ps)) |
| 601 |
(error "$or - no parsers after :else") |
| 602 |
(loop '() (cdr ps))) ;discard previous errors |
| 603 |
(receive (r v s1) ((car ps) s) |
| 604 |
(cond [(parse-success? r) (values r v s1)] |
| 605 |
[(eq? r 'fail-error) (values r v s1)] |
| 606 |
[(null? (cdr ps)) |
| 607 |
(if (eq? s s1) |
| 608 |
(fail (acons r v vs) s1) |
| 609 |
(return-failure r v s1))] ; last branch consumed input |
| 610 |
[(eq? s s1) (loop (acons r v vs) (cdr ps))] |
| 611 |
[else (fail (acons r v vs) s1)])))))])) |
| 612 |
|
| 613 |
;; API |
| 614 |
;; $fold-parsers proc seed parsers |
| 615 |
;; $fold-parsers-right proc seed parsers |
| 616 |
;; Apply parsers sequentially, passing around seed value. |
| 617 |
;; Note: $fold-parsers can be written much simpler (only shown in |
| 618 |
;; recursion branch): |
| 619 |
;; ($let ([v (car ps)]) ($fold-parsers proc (proc v seed) (cdr ps))) |
| 620 |
;; but it needs to create closures at parsing time, rather than construction |
| 621 |
;; time. Interestingly, $fold-parsers-right can be written simply |
| 622 |
;; without this disadvantage. |
| 623 |
(define ($fold-parsers proc seed ps) |
| 624 |
(if (null? ps) |
| 625 |
($return seed) |
| 626 |
(lambda (s) |
| 627 |
(let loop ((s s) (ps ps) (seed seed)) |
| 628 |
(if (null? ps) |
| 629 |
(return-result seed s) |
| 630 |
(receive (r1 v1 s1) ((car ps) s) |
| 631 |
(if (parse-success? r1) |
| 632 |
(loop s1 (cdr ps) (proc v1 seed)) |
| 633 |
(return-failure r1 v1 s1)))))))) |
| 634 |
|
| 635 |
;; API |
| 636 |
(define ($fold-parsers-right proc seed ps) |
| 637 |
(match ps |
| 638 |
[() ($return seed)] |
| 639 |
[(p . ps) ($lift proc p ($fold-parsers-right proc seed ps))])) |
| 640 |
|
| 641 |
;; API |
| 642 |
;; $seq P ... Pz |
| 643 |
;; Matches P ... Pz sequentially, and returns the result of Pz. |
| 644 |
;; To get all the results of p1, p2, ... in a list, use $lift list p1 p2 ... |
| 645 |
(define ($seq . parsers) |
| 646 |
($fold-parsers (^[v s] v) #f parsers)) |
| 647 |
|
| 648 |
;; API |
| 649 |
;; $seq0 P0 P ... |
| 650 |
;; Matches P0 P ..., and returns the result of P. |
| 651 |
(define ($seq0 parse . followers) |
| 652 |
(apply $lift (^[v . _] v) parse followers)) |
| 653 |
|
| 654 |
;; API |
| 655 |
;; $list P ... |
| 656 |
;; $list* P ... |
| 657 |
;; Same as ($lift list P ...) and ($list list* P ...), but we see them |
| 658 |
;; a lot, so it's worth to have them. |
| 659 |
(define-inline ($list . parsers) (apply $lift list parsers)) |
| 660 |
(define-inline ($list* . parsers) (apply $lift list* parsers)) |
| 661 |
|
| 662 |
;; API |
| 663 |
;; $try parser |
| 664 |
;; Try to match parsers. If it fails, backtrack to |
| 665 |
;; the starting position of the stream. So, |
| 666 |
;; ($or ($try a) |
| 667 |
;; ($try b) |
| 668 |
;; ...) |
| 669 |
;; would try a, b, ... even some of them consumes the input. |
| 670 |
(define-inline ($try p) |
| 671 |
(^[s0] (receive (r v s) (p s0) |
| 672 |
(cond [(parse-success? r) (return-result v s)] |
| 673 |
[(eq? r 'fail-error) (return-failure r v s)] |
| 674 |
[else (return-failure r v s0)])))) |
| 675 |
|
| 676 |
;; API |
| 677 |
;; $assert parser |
| 678 |
;; Match parser, but never consumes the result. |
| 679 |
;; On success, the value of the parser is returned. |
| 680 |
(define-inline ($assert p) |
| 681 |
(^s (receive (r v s1) (p s) |
| 682 |
(values r v s)))) |
| 683 |
|
| 684 |
;; API |
| 685 |
;; $not parser |
| 686 |
;; Succeeds when the input does not matches parser. The value is #t. |
| 687 |
;; If the input matches P, unexpected failure results. |
| 688 |
;; Never consumes input. |
| 689 |
(define ($not p) |
| 690 |
(^s (receive (r v s1) (p s) |
| 691 |
(if (parse-success? r) |
| 692 |
(return-failure/unexpect v s) |
| 693 |
(return-result #f s))))) |
| 694 |
|
| 695 |
;; API |
| 696 |
(define-syntax $lazy |
| 697 |
(syntax-rules () |
| 698 |
[(_ parse) |
| 699 |
(let ((p (delay parse))) |
| 700 |
(lambda (s) ((force p) s)))])) |
| 701 |
|
| 702 |
;; alternative $lazy possibility (need benchmark!) |
| 703 |
;(define-syntax $lazy |
| 704 |
; (syntax-rules () |
| 705 |
; ((_ parse) |
| 706 |
; (letrec ((p (lambda (s) (set! p parse) (p s)))) |
| 707 |
; (lambda (s) (p s)))))) |
| 708 |
|
| 709 |
;; Utility |
| 710 |
(define (%check-min-max min max) |
| 711 |
(when (or (negative? min) |
| 712 |
(and max (> min max))) |
| 713 |
(error "invalid argument:" min max))) |
| 714 |
|
| 715 |
;; API |
| 716 |
;; $many p :optional min max |
| 717 |
;; $many_ p :optional min max |
| 718 |
;; $many1 p :optional max |
| 719 |
;; $many1_ p :optional max |
| 720 |
(define-inline ($many parse :optional (min 0) (max #f)) |
| 721 |
(%check-min-max min max) |
| 722 |
(lambda (s) |
| 723 |
(let loop ([vs '()] [s s] [count 0]) |
| 724 |
(if (>=? count max) |
| 725 |
(return-result (reverse! vs) s) |
| 726 |
(receive (r v s1) (parse s) |
| 727 |
(cond [(parse-success? r) (loop (cons v vs) s1 (+ count 1))] |
| 728 |
[(and (eq? s s1) (<= min count)) |
| 729 |
(return-result (reverse! vs) s1)] |
| 730 |
[else (return-failure r v s1)])))))) |
| 731 |
|
| 732 |
(define-inline ($many_ parse :optional (min 0) (max #f)) |
| 733 |
(%check-min-max min max) |
| 734 |
(lambda (s) |
| 735 |
(let loop ([s s] [count 0]) |
| 736 |
(if (>=? count max) |
| 737 |
(return-result #t s) |
| 738 |
(receive (r v s1) (parse s) |
| 739 |
(cond [(parse-success? r) (loop s1 (+ count 1))] |
| 740 |
[(and (eq? s s1) (<= min count)) |
| 741 |
(return-result #t s1)] |
| 742 |
[else (return-failure r v s1)])))))) |
| 743 |
|
| 744 |
(define-inline ($many1 parse :optional (max #f)) ($many parse 1 max)) |
| 745 |
(define-inline ($many1_ parse :optional (max #f)) ($many_ parse 1 max)) |
| 746 |
|
| 747 |
;; API |
| 748 |
;; $repeat p n |
| 749 |
;; $repeat_ p n |
| 750 |
;; Exactly n time of P. Same as ($many p n n) |
| 751 |
(define ($repeat parse n) ($many parse n n)) |
| 752 |
(define ($repeat_ parse n) ($many_ parse n n)) |
| 753 |
|
| 754 |
;; API |
| 755 |
;; $many-till P E :optional min max |
| 756 |
;; $many-till_ P E :optional min max |
| 757 |
(define ($many-till parse end . args) |
| 758 |
(apply $many ($seq ($not end) parse) args)) |
| 759 |
(define ($many-till_ parse end . args) |
| 760 |
(apply $many_ ($seq ($not end) parse) args)) |
| 761 |
|
| 762 |
;; API |
| 763 |
;; $optional p :optional fallback |
| 764 |
;; Try P. If not match, use FALLBACK as the value. |
| 765 |
;; Does not backtrack by default; if P may consume some input and |
| 766 |
;; you want to backtrack later, wrap it with $try. |
| 767 |
(define ($optional parse :optional (fallback #f)) |
| 768 |
($or parse ($return fallback))) |
| 769 |
|
| 770 |
;; API |
| 771 |
;; $sep-by p sep :optional min max |
| 772 |
;; P sparated by SEP, e.g. P SEP P SEP P. Returns list of values of P. |
| 773 |
;; If SEP consumes input then fails, or the following P fails, then the |
| 774 |
;; entire $sep-by fails. |
| 775 |
(define ($sep-by parse sep :optional (min 0) (max #f)) |
| 776 |
(define rep |
| 777 |
($let ([x parse] |
| 778 |
[xs ($many ($seq sep parse) |
| 779 |
(clamp (- min 1) 0) |
| 780 |
(and max (- max 1)))]) |
| 781 |
($return (cons x xs)))) |
| 782 |
(cond |
| 783 |
[(and max (zero? max)) ($return '())] |
| 784 |
[(> min 0) rep] |
| 785 |
[else ($or rep ($return '()))])) |
| 786 |
|
| 787 |
;; API |
| 788 |
;; $end-by p sep :optional min max |
| 789 |
;; Matches repetition of P SEP. Returns a list of values of P. |
| 790 |
;; This one doesn't set backtrack point, so for example the input is |
| 791 |
;; P SEP P SEP P Q, the entire match fails. |
| 792 |
(define ($end-by parse sep . args) |
| 793 |
(apply $many ($try ($let ([v parse] sep) ($return v))) args)) |
| 794 |
|
| 795 |
;; API |
| 796 |
;; $sep-end-by p sep min max |
| 797 |
;; The last SEP is optional. The definition is a bit involved |
| 798 |
;; for performance. |
| 799 |
(define ($sep-end-by parse sep :optional (min 0) (max #f)) |
| 800 |
(%check-min-max min max) |
| 801 |
(^s (let loop ([vs '()] [s s] [count 0]) |
| 802 |
(if (>=? count max) |
| 803 |
(return-result (reverse vs) s) |
| 804 |
(receive (r v s.) (parse s) |
| 805 |
(cond [(parse-success? r) |
| 806 |
(receive (r. v. s..) (sep s.) |
| 807 |
(cond [(parse-success? r.) |
| 808 |
(loop (cons v vs) s.. (+ count 1))] |
| 809 |
[(and (eq? s.. s.) (<= min (+ count 1))) |
| 810 |
(return-result (reverse (cons v vs)) s.)] |
| 811 |
[else (return-failure r. v. s..)]))] |
| 812 |
[(and (eq? s s.) (<= min count)) |
| 813 |
(return-result (reverse vs) s)] |
| 814 |
[else (return-failure r v s.)])))))) |
| 815 |
|
| 816 |
;; API |
| 817 |
;; $between A B C |
| 818 |
;; Matches A B C, and returns the result of B. |
| 819 |
(define ($between open parse close) |
| 820 |
($let (open [v parse] close) ($return v))) |
| 821 |
|
| 822 |
;; API |
| 823 |
;; $chain-left P OP |
| 824 |
(define ($chain-left parse op) |
| 825 |
(lambda (st) |
| 826 |
(receive (r v s) (parse st) |
| 827 |
(if (parse-success? r) |
| 828 |
(let loop ([r1 r] [v1 v] [s1 s]) |
| 829 |
(receive (r2 v2 s2) (($let ([proc op] [v parse]) |
| 830 |
($return (proc v1 v))) |
| 831 |
s1) |
| 832 |
(if (parse-success? r2) |
| 833 |
(loop r2 v2 s2) |
| 834 |
(return-failure r1 v1 s1)))) |
| 835 |
(return-failure r v s))))) |
| 836 |
|
| 837 |
;; API |
| 838 |
;; $chain-right P OP |
| 839 |
(define ($chain-right parse op) |
| 840 |
(rec (loop s) |
| 841 |
(($let ([h parse]) |
| 842 |
($or ($try ($let ([proc op] |
| 843 |
[t loop]) |
| 844 |
($return (proc h t)))) |
| 845 |
($return h))) |
| 846 |
s))) |
| 847 |
|
| 848 |
;; API |
| 849 |
;; $satisfy PRED EXPECT [RESULT]) |
| 850 |
;; - Returns a parser such that ... |
| 851 |
;; - If the head of input stream satisfies PRED, |
| 852 |
;; call (RESULT head (PRED head)) and let its result |
| 853 |
;; as the value of successulf parsing. |
| 854 |
;; - Otherwise, returns failure with EXPECT as the expected input. |
| 855 |
(define-inline ($satisfy pred expect :optional (result #f)) |
| 856 |
(^s (if-let1 v (and (pair? s) (pred (car s))) |
| 857 |
(return-result (if result |
| 858 |
(result (car s) v) |
| 859 |
(car s)) |
| 860 |
(cdr s)) |
| 861 |
(return-failure/expect expect s)))) |
| 862 |
|
| 863 |
;; API |
| 864 |
;; $match1 PATTERN [(=> FAIL)] [RESULT] |
| 865 |
;; $match1* PATTERN [(=> FAIL)] [RESULT] |
| 866 |
;; - Run util.match#match against the input stream. |
| 867 |
;; - $match1 takes one item from stream and see if it matches |
| 868 |
;; with PATTERN. |
| 869 |
;; - $match1* applys PATTERN on the entire input stream. |
| 870 |
;; - If matched, RESULT is evaluated in the environment where pattern |
| 871 |
;; variables in PATTERN are bound, and its result becomes the result |
| 872 |
;; value of the parser. |
| 873 |
;; - If RESULT is omitted, the matched item is returned. |
| 874 |
;; - If (=> FAIL) is given, FAIL (must be an identifier) is bound to |
| 875 |
;; a closure to be called (FAIL message) to return a failure. |
| 876 |
;; NB: Unlinke the (=> FAIL) in match (util.match), FAIL is not |
| 877 |
;; a continuation but just a procedure, so it must be called at |
| 878 |
;; the tail position of RESULT. |
| 879 |
|
| 880 |
(define-syntax $match1* |
| 881 |
(er-macro-transformer |
| 882 |
(^[f r c] |
| 883 |
(define (=>? x) (c (r'=>) (r x))) |
| 884 |
(define fail-mark (gensym)) |
| 885 |
(define (build-fail-decl fail) |
| 886 |
(if fail |
| 887 |
(quasirename r |
| 888 |
`((define (,fail msg) (cons ',fail-mark msg)))) |
| 889 |
'())) |
| 890 |
(define (build-return result fail tail) |
| 891 |
(if fail |
| 892 |
(quasirename r |
| 893 |
`(let ((r ,result)) |
| 894 |
(if (and (pair? r) (eq? (car r) ',fail-mark)) |
| 895 |
(return-failure/message (cdr r) s) |
| 896 |
(return-result r ,tail)))) |
| 897 |
(quasirename r |
| 898 |
`(return-result ,result ,tail)))) |
| 899 |
;; If pat is (x ...), add a rest var: (x ... . rest) |
| 900 |
;; Returns the pattern and the rest var. |
| 901 |
(define (make-match-pattern pat) |
| 902 |
(if (pair? pat) |
| 903 |
(if (null? (cdr (last-pair pat))) |
| 904 |
(let1 rest (gensym) |
| 905 |
(values (append pat rest) rest)) |
| 906 |
(values pat '())) |
| 907 |
(values pat '()))) |
| 908 |
(define (build-parser pat result fail) |
| 909 |
(receive (match-pat tail) (make-match-pattern pat) |
| 910 |
(quasirename r |
| 911 |
`(lambda (s) |
| 912 |
,@(build-fail-decl fail) |
| 913 |
(match s |
| 914 |
[,match-pat ,(build-return result fail tail)] |
| 915 |
[_ (return-failure/expect ,(write-to-string pat) s)]))))) |
| 916 |
(match f |
| 917 |
[(_ pat ((? =>?) fail) result) |
| 918 |
(build-parser pat result fail)] |
| 919 |
[(_ pat result) |
| 920 |
(build-parser pat result #f)] |
| 921 |
[(_ pat) |
| 922 |
(build-parser pat |
| 923 |
(if-let1 n (length+ pat) |
| 924 |
(quasirename r |
| 925 |
`(take s ,n)) |
| 926 |
(r 's)) |
| 927 |
#f)])))) |
| 928 |
|
| 929 |
(define-syntax $match1 |
| 930 |
(er-macro-transformer |
| 931 |
(^[f r c] |
| 932 |
(define (=>? x) (c (r'=>) (r x))) |
| 933 |
(define fail-mark (gensym)) |
| 934 |
(define (build-fail-decl fail) |
| 935 |
(if fail |
| 936 |
(quasirename r |
| 937 |
`((define (,fail msg) (cons ',fail-mark msg)))) |
| 938 |
'())) |
| 939 |
(define (build-return result fail) |
| 940 |
(if fail |
| 941 |
(quasirename r |
| 942 |
`(let ((r ,result)) |
| 943 |
(if (and (pair? r) (eq? (car r) ',fail-mark)) |
| 944 |
(return-failure/message (cdr r) s) |
| 945 |
(return-result r (cdr s))))) |
| 946 |
(quasirename r |
| 947 |
`(return-result ,result (cdr s))))) |
| 948 |
(define (build-parser pat result fail) |
| 949 |
(quasirename r |
| 950 |
`(lambda (s) |
| 951 |
,@(build-fail-decl fail) |
| 952 |
(if (pair? s) |
| 953 |
(match (car s) |
| 954 |
[,pat ,(build-return result fail)] |
| 955 |
[_ (return-failure/expect ,(write-to-string pat) s)]) |
| 956 |
(return-failure/expect ,(write-to-string pat) s))))) |
| 957 |
(match f |
| 958 |
[(_ pat ((? =>?) fail) result) |
| 959 |
(build-parser pat result fail)] |
| 960 |
[(_ pat result) |
| 961 |
(build-parser pat result #f)] |
| 962 |
[(_ pat) |
| 963 |
(build-parser pat (quasirename r `(car s)) #f)] |
| 964 |
)))) |
| 965 |
|
| 966 |
;; $binding <peg-bind-expression> ... [(=> FAIL)] <body> |
| 967 |
;; $lbinding <peg-bind-expression> ... [(=> FAIL)] <body> |
| 968 |
;; EXPERIMENTAL |
| 969 |
;; <peg-bind-expression> is an expression that yields a parser, |
| 970 |
;; but allowed to contain a form ($: var <peg-bind-expression>). |
| 971 |
;; When inner <peg-bind-expression> accepts an input, its semantic |
| 972 |
;; value is set to var. |
| 973 |
;; |
| 974 |
;; The parser runs as if ($seq <peg-bind-expression> ...), then |
| 975 |
;; if it succeeds, evaluate <body> with all such |
| 976 |
;; vars to be bound. If a branch of <peg-bind-expression> isn't |
| 977 |
;; tried, vars included in it is bound to #<undef>. |
| 978 |
;; |
| 979 |
;; $lbinding is similar to $binding, except that it behaves as if |
| 980 |
;; entire expression is enclosed in $lazy. |
| 981 |
;; |
| 982 |
;; An obvious translation is to create an enclosing scope, binds all |
| 983 |
;; vars to some default value, and convert ($: var expr) to |
| 984 |
;; ($lift (^x (set! var x) x) expr). However, it causes allocation |
| 985 |
;; of closures for each parser combinator every time the entire parser |
| 986 |
;; is called, which incurs performance overhead. |
| 987 |
;; |
| 988 |
;; Instead we rely on dynamic environment. All closure allocation is |
| 989 |
;; static. The main parser sets up a vector for the storage in a parameter, |
| 990 |
;; and each $: form store the value to the corresponding slot. |
| 991 |
;; If match succeeds, the stored values are retrieved and bound to VARs. |
| 992 |
;; |
| 993 |
;; If (=> FAIL) form is given, FAIL, which should be an identifier, is |
| 994 |
;; bound to a closure that can be called as (FAIL message). If you |
| 995 |
;; determine that the parser should fail inside <body>, you can call FAIL |
| 996 |
;; at a tail position, with a suitable message. |
| 997 |
;; |
| 998 |
;; Limitation - since $binding walks code, it can't be statically nested. |
| 999 |
|
| 1000 |
(define %binding-storage |
| 1001 |
(make-parameter 'accessing-binding-storage-out-of-context)) |
| 1002 |
|
| 1003 |
(define-syntax $lbinding |
| 1004 |
(syntax-rules () |
| 1005 |
([_ x ...] ($lazy ($binding x ...))))) |
| 1006 |
|
| 1007 |
(define-syntax $binding |
| 1008 |
(er-macro-transformer |
| 1009 |
(^[f r c] |
| 1010 |
(define $:? (let1 $:. (r'$:) (^x (c $:. (r x))))) |
| 1011 |
(define =>? (let1 =>. (r'=>) (^x (c =>. (r x))))) |
| 1012 |
(define fail-mark (gensym)) |
| 1013 |
;; walk down form, gather variables and modify $: forms. |
| 1014 |
;; returns modified form and list of (var . index) |
| 1015 |
(define (walk f vs) |
| 1016 |
(match f |
| 1017 |
[((? $:?) var expr) |
| 1018 |
(unless (identifier? var) |
| 1019 |
(error "($: var expr) form requires an identifier as var, but got:" |
| 1020 |
var)) |
| 1021 |
(receive (expr_ vs) (walk expr vs) |
| 1022 |
(receive (vs ind) (add-var var vs) |
| 1023 |
(values (quasirename r |
| 1024 |
`($lift (^[x] (set! (vector-ref (%binding-storage) ,ind) x) x) |
| 1025 |
,expr_)) |
| 1026 |
vs)))] |
| 1027 |
[(xs ...) (map-accum walk vs xs)] |
| 1028 |
[obj (values obj vs)])) |
| 1029 |
(define (add-var var vs) ; returns var-alist and index |
| 1030 |
(if-let1 p (assq var vs) |
| 1031 |
(values vs (cdr p)) |
| 1032 |
(let1 ind (length vs) |
| 1033 |
(values (acons var ind vs) ind)))) |
| 1034 |
(define (build-fail-decl fail) |
| 1035 |
(if fail |
| 1036 |
(quasirename r |
| 1037 |
;; NB: We can't optimize dynamically created case-lambda yet. |
| 1038 |
;; `((define ,fail |
| 1039 |
;; (case-lambda |
| 1040 |
;; ((msg) (list* ',fail-mark #f msg)) |
| 1041 |
;; ((tag msg) (list* ',fail-mark tag msg))))) |
| 1042 |
;; With the following definition, the branch is likely |
| 1043 |
;; to be optimized out when call to fail is inlined: |
| 1044 |
`((define (,fail a . b) |
| 1045 |
(if (null? b) |
| 1046 |
(list* ',fail-mark #f a) ;a=msg |
| 1047 |
(list* ',fail-mark a (car b)))))) ;a=tag, (car b)=msg |
| 1048 |
'())) |
| 1049 |
(define (build-return result fail tail) |
| 1050 |
(if fail |
| 1051 |
(quasirename r |
| 1052 |
`(let ((r ,result)) |
| 1053 |
(if (and (pair? r) (eq? (car r) ',fail-mark)) |
| 1054 |
(if (symbol? (cadr r)) |
| 1055 |
(return-error-from-failure (cadr r) 'fail-message (cddr r) s) |
| 1056 |
(return-failure/message (cddr r) s)) |
| 1057 |
(return-result r ,tail)))) |
| 1058 |
(quasirename r |
| 1059 |
`(return-result ,result ,tail)))) |
| 1060 |
|
| 1061 |
(define (build-parser parsers vs body fail) |
| 1062 |
(quasirename r |
| 1063 |
`(let ([parser ($seq ,@parsers)]) |
| 1064 |
(^[s] |
| 1065 |
,@(build-fail-decl fail) |
| 1066 |
(let1 storage (make-vector ,(length vs)) |
| 1067 |
(parameterize ((%binding-storage storage)) |
| 1068 |
(receive (rr v s) (parser s) |
| 1069 |
(if (parse-success? rr) |
| 1070 |
,(build-return |
| 1071 |
(quasirename r |
| 1072 |
`(let ,(map |
| 1073 |
(^p (let ([var (car p)] |
| 1074 |
[ind (cdr p)]) |
| 1075 |
(quasirename r |
| 1076 |
`(,var (vector-ref storage ,ind))))) |
| 1077 |
vs) |
| 1078 |
,body)) |
| 1079 |
fail |
| 1080 |
(r's)) |
| 1081 |
(return-failure rr v s))))))))) |
| 1082 |
|
| 1083 |
;; optimization - if all the variable binding form is in the first level, |
| 1084 |
;; e.g. |
| 1085 |
;; ($binding ($: x parser1) |
| 1086 |
;; ($: y parser2) |
| 1087 |
;; body) |
| 1088 |
;; We can simply use $lift. |
| 1089 |
;; ($lift (lambda (x y) body) parser1 parser2) |
| 1090 |
;; This saves setting up value vector. |
| 1091 |
;; NB: we can't do this optimization if (=> fail) is used. |
| 1092 |
|
| 1093 |
;; check if lift optimization is possible. note that duplicate vars |
| 1094 |
;; are allowed, but that can be detected with the following, for |
| 1095 |
;; vars are deduped. |
| 1096 |
(define (liftable? first-level-parsers vars) |
| 1097 |
(= (length vars) |
| 1098 |
(count (^p (match p |
| 1099 |
[((? $:?) v _) #t] |
| 1100 |
[_ #f])) |
| 1101 |
first-level-parsers))) |
| 1102 |
|
| 1103 |
(define (build-lift-form first-level-parsers body) |
| 1104 |
;; ((var . parser) ...). |
| 1105 |
(define vars&parsers (map (^p (match p |
| 1106 |
[((? $:?) v p) `(,v . ,p)] |
| 1107 |
[p `(,(gensym) . ,p)])) |
| 1108 |
first-level-parsers)) |
| 1109 |
(quasirename r |
| 1110 |
`($lift (lambda ,(map car vars&parsers) ,body) |
| 1111 |
,@(map cdr vars&parsers)))) |
| 1112 |
|
| 1113 |
(define (bad) (error "Malformed $binding:" f)) |
| 1114 |
|
| 1115 |
(let loop ([forms (cdr f)] [ps '()]) |
| 1116 |
(match forms |
| 1117 |
[(((? =>?) fail) body) |
| 1118 |
(receive (parsers. vars) (walk (reverse ps) '()) |
| 1119 |
(build-parser parsers. vars body fail))] |
| 1120 |
[(((? =>?) fail) body ...) (bad)] |
| 1121 |
[(body) |
| 1122 |
(receive (parsers. vars) (walk (reverse ps) '()) |
| 1123 |
(if (liftable? ps vars) |
| 1124 |
(build-lift-form (reverse ps) body) |
| 1125 |
(build-parser parsers. vars body #f)))] |
| 1126 |
[(parser . rest) (loop rest (cons parser ps))] |
| 1127 |
[() (bad)]))))) |
| 1128 |
|
| 1129 |
;;;============================================================ |
| 1130 |
;;; String parsers |
| 1131 |
;;; |
| 1132 |
|
| 1133 |
(define-inline ($->rope parser . more-parsers) |
| 1134 |
(if (null? more-parsers) |
| 1135 |
($lift make-rope parser) |
| 1136 |
(apply $lift* make-rope parser more-parsers))) |
| 1137 |
(define-inline ($->string parser . more-parsers) |
| 1138 |
(if (null? more-parsers) |
| 1139 |
($lift ($ rope->string $ make-rope $) parser) |
| 1140 |
(apply $lift* ($ rope->string $ make-rope $) parser more-parsers))) |
| 1141 |
(define-inline ($->symbol parser . more-parsers) |
| 1142 |
(if (null? more-parsers) |
| 1143 |
($lift ($ string->symbol $ rope->string $ make-rope $) parser) |
| 1144 |
(apply $lift* ($ string->symbol $ rope->string $ make-rope $) |
| 1145 |
parser more-parsers))) |
| 1146 |
|
| 1147 |
(define (rope-finalize obj) |
| 1148 |
(cond [(rope? obj) (rope->string obj)] |
| 1149 |
[(pair? obj) |
| 1150 |
(let ((ca (rope-finalize (car obj))) |
| 1151 |
(cd (rope-finalize (cdr obj)))) |
| 1152 |
(if (and (eq? ca (car obj)) (eq? cd (cdr obj))) |
| 1153 |
obj |
| 1154 |
(cons ca cd)))] |
| 1155 |
[else obj])) |
| 1156 |
|
| 1157 |
;; NB: On success, we know the matched input is the same as STR, |
| 1158 |
;; so we don't need to bother to collect matched chars. |
| 1159 |
(define-inline ($string str) |
| 1160 |
(if (= (string-length str) 1) |
| 1161 |
(let1 ch (string-ref str 0) |
| 1162 |
(^s |
| 1163 |
(if (and (pair? s) (eqv? (car s) ch)) |
| 1164 |
(return-result str (cdr s)) |
| 1165 |
(return-failure/expect str s)))) |
| 1166 |
(let1 lis (string->list str) |
| 1167 |
(^[s0] |
| 1168 |
(let loop ([s s0] [lis lis]) |
| 1169 |
(if (null? lis) |
| 1170 |
(return-result str s) |
| 1171 |
(if (and (pair? s) (eqv? (car s) (car lis))) |
| 1172 |
(loop (cdr s) (cdr lis)) |
| 1173 |
(return-failure/expect str s0)))))))) |
| 1174 |
|
| 1175 |
(define ($string-ci str) |
| 1176 |
(let1 lis (string->list str) |
| 1177 |
(^[s0] |
| 1178 |
(let loop ([r '()] [s s0] [lis lis]) |
| 1179 |
(if (null? lis) |
| 1180 |
(return-result (make-rope (reverse! r)) s) |
| 1181 |
(if (and (pair? s) |
| 1182 |
(char? (car s)) |
| 1183 |
(char-ci=? (car s) (car lis))) |
| 1184 |
(loop (cons (car s) r) (cdr s) (cdr lis)) |
| 1185 |
(return-failure/expect str s0))))))) |
| 1186 |
|
| 1187 |
(define-inline ($char c) |
| 1188 |
(assume-type c <char>) |
| 1189 |
($satisfy (cut eqv? c <>) c)) |
| 1190 |
|
| 1191 |
(define ($char-ci c) |
| 1192 |
(assume-type c <char>) |
| 1193 |
($satisfy (^x (and (char? x) (char-ci=? c x))) |
| 1194 |
(list->char-set c (char-upcase c) (char-downcase c)))) |
| 1195 |
|
| 1196 |
;; Anything except end of stream. |
| 1197 |
(define-inline ($any) |
| 1198 |
(^s (if (pair? s) |
| 1199 |
(return-result (car s) (cdr s)) |
| 1200 |
(return-failure/unexpect "end of input" s)))) |
| 1201 |
|
| 1202 |
(define-inline ($eos) |
| 1203 |
(^s (if (pair? s) |
| 1204 |
(return-failure/expect "end of input" s) |
| 1205 |
(return-result (eof-object) s)))) |
| 1206 |
|
| 1207 |
;; Parse one item---a char, a string or a charset. |
| 1208 |
(define-inline ($. item) |
| 1209 |
(cond |
| 1210 |
[(char-set? item) ($one-of item)] |
| 1211 |
[(char? item) ($char item)] |
| 1212 |
[(string? item) ($string item)] |
| 1213 |
[(symbol? item) ($satisfy (cut eq? <> item) item)] |
| 1214 |
[else (error "Bad item: $. requires a char, a char-set, a string, \ |
| 1215 |
or a symbol, but got:" item)])) |
| 1216 |
|
| 1217 |
(define-hybrid-syntax $one-of |
| 1218 |
(^[items] |
| 1219 |
(cond |
| 1220 |
[(char-set? items) |
| 1221 |
($satisfy (^x (and (char? x) (char-set-contains? items x))) |
| 1222 |
items)] |
| 1223 |
[(list? items) ($expect (apply $or (map $. items)) items)] |
| 1224 |
[else (error "$one-of requires a charset or a list of items, \ |
| 1225 |
but got:" items)])) |
| 1226 |
(er-macro-transformer |
| 1227 |
(^[f r c] |
| 1228 |
(match f |
| 1229 |
[(_ (? char-set? items)) |
| 1230 |
(quasirename r |
| 1231 |
`($satisfy (^[x] (and (char? x) (char-set-contains? ,items x))) |
| 1232 |
',items))] |
| 1233 |
[(_ ('quote (items ...))) |
| 1234 |
(if (every (^x (or (char? x) (symbol? x))) items) |
| 1235 |
(quasirename r |
| 1236 |
`($satisfy (^[x] (memv x ',items)) ',items)) |
| 1237 |
f)] |
| 1238 |
[_ f])))) |
| 1239 |
|
| 1240 |
;; NB: $none-of can't be generalized like $one-of, for the value to return |
| 1241 |
;; on success is ambiguous except the case we're matching a single character. |
| 1242 |
;; The asymmetry doesn't look good... we may drop $none-of in future. |
| 1243 |
(define ($none-of charset) |
| 1244 |
(assume-type charset <char-set>) |
| 1245 |
($satisfy (^x (or (not (char? x)) (not (char-set-contains? charset x)))) |
| 1246 |
`(none-of ,charset))) |