Parsing style [Was: [plt-scheme] proof checking: a subproblem]

On Fri, Jan 20, 2006 at 08:16:39AM -0300, andrew cooke wrote:
> Vague cultural question - is recursive descent parsing with combinators
> not that common in the scheme world?

Probably not, but this is indeed purely a cultural issue. S-expression
syntax is perfectly suited for recursive descent parsing.

Although bottom-up parsing is quite feasible with proper tools,
recursive descent still has the advantage that it is easy to integrate
with the standard reader.

For the sake of example, attached is the core of a simple LL1 parsing
library (somewhat reminiscent of Parsec for Haskell) that I threw
together the other day for my own purposes. It's relatively easy to
use, since you use ordinary sequencing and binding, and there's no need
to use monads. Note that it depends heavily on mzscheme's guaranteed
left-to-right evaluation order in function application.


Lauri
-------------- next part --------------
(module ll1 mzscheme

;; A simple library for LL1 parsing. It is up to the user to make sure that a
;; parse cannot fail once it has consumed an input character.

(require (lib "string.ss" "srfi" "13"))

(provide (all-defined-except current-fail-k))

(define current-fail-k (make-parameter #f))

;; Must be called before something is read from the input port.
;; This indicates that we can no longer jump back to other alternatives.
(define (commit) (current-fail-k #f))

(define (fail . args)
  (let ((k (current-fail-k)))
    (if k
        (k)
        (apply error 'parse args))))

(define (alt-aux thunk1 thunk2)
  ((let/cc k
     (lambda ()
       (parameterize ((current-fail-k (lambda ()
                                        (k thunk2))))
         (thunk1))))))

(define-syntax alt
  (syntax-rules ()
    ((_ e1 e2) (alt-aux (lambda () e1) (lambda () e2)))))

;; Common combinators

;; Always use this instead of plain read-char.
(define (any-char) (commit) (read-char))

(define (satisfy f?)
  (let ((c (peek-char)))
    (if (and (char? c) (f? c))
        (any-char)
        (fail "satisfy ~s ~s" f? c))))

(define (char c) (satisfy (lambda (x) (eq? x c))))
(define (many p) (alt (many1 p) '()))
(define (many1 p) (cons (p) (many p)))

(define (many_ p) (alt (many1_ p) #t))
(define (many1_ p) (p) (many_ p))
(define (maybe p) (alt (p) #t))
(define (any-of str)
  (satisfy (lambda (c) (string-index str c))))
(define (any-not-of str)
  (satisfy (lambda (c) (not (string-index str c)))))

)