cdiggins.com

This is the basis for a combinator based recursive descent parsing library in Scheme. It seems to work well so far but it disturbs me how few lines of code it is:

; parse rule r repeatedly until it fails
; always return true
(define (star r)
  (lambda () (if (r) ((star r)) #t)))  

; parse rule r repeated until it fails
; return true only if you parse successfully at least once
(define (plus r)
  (lambda () (if (r) ((star r)) #f)))  

; try to parse rule r once
; return true
(define (opt r)
  (lambda () (if (r) #t #t)))  

; parse rule r1, but if it fails try r2
; return false only if both rules fail
(define (choose r1 r2)
  (lambda () (if (not r1) (r2) #t)))  

; parse rule r1 then r2
; return true only if both rules succeed
(define (seq r1 r2)
   (backtracker (lambda () (if (r1) (r2) #f))))  

; returns true if rule parsing fails
; backtrack if successful
(define (not-at r)
  (lambda () (if ((backtracker r)) #f #t)))  

; Used to ... wait for it .... backtrack
(define (backtracker f)
  (lambda ()
    (let ((tmp input))
      (if (f) #t (begin (set! input tmp) #f)))))  

; sample input
; sorry to use global variables, but it too ugly otherwise
(define input '(0 0 1 0))  

; match something specific in the input
; eventually we will want to match ranges of things
(define (match x) (lambda () (if (null? input) #f
  (if (eq? (car input) x)
     (begin (set! input (cdr input)) #t) #f))))  

; This shows how rules can be combined to parse some stuff
(define (test) (seq (seq (star (match 0)) (match 2))
   (opt (match 0))))