epsil / gll Goto Github PK

#lang racket

(struct success (val remaining) #:transparent)
(struct failure (remaining) #:transparent)

;; ================
;; TERMINAL PARSERS
;; ================
#|
(1) They are calles terminal parsers, because they match against terminal expressions in the underlying grammar.
(2) They are parser generators, because they return parsers.
|#


;; paper: `result`
(define (succeed val)
  (lambda (str)
    (success val str)))

;; paper: instead of matching single characters, a whole prefix is matched
;; paper: `sat` or `satisfies`
(define (string prefix-to-match)
  (lambda (str)
    (let* ([prefix-len (min (string-length prefix-to-match)
                         (string-length str))]
           [str-prefix (substring str 0 prefix-len)]
           [str-suffix (substring str prefix-len)])
      (if (string=? str-prefix prefix-to-match)
          (success str-prefix str-suffix)
          (failure str)))))

;; ==================
;; PARSER COMBINATORS
;; ==================
#|They make use of parsers combining them in useful ways to enable more complex functionality.|#

;; PAPER: `plus`
(define (alternative alt-1 alt-2)
  (lambda (str)
    (let ([alt-1-result (alt-1 str)])
      (match alt-1-result
        [(success val remaining) remaining]
        [failure (alt-2 str)]))))

;; PAPER: `bind`
(define (bind a-parser a-parser-generator)
  (lambda (str)
    (match (a-parser str)
      [(success val remaining) ((a-parser-generator val) remaining)]
      [failure failure])))

;; PAPER: seq
(define (seq parser-1 parser-2)
  (bind parser-1
        (lambda (inp-1)
          (bind parser-2
                (lambda (inp-2)
                  (succeed (list inp-1 inp-2)))))))

(define article
  (alternative (string "the ")
       (string "a ")))

(define noun
  (alternative (string "student ")
       (string "professor ")))

(define verb
  (alternative (string "studies ")
       (string "lectures ")))

(define noun-phrase
  (seq article noun))

(define verb-phrase
  (seq verb noun-phrase))

(define sentence
  (seq noun-phrase verb-phrase))

(sentence "the professor lectures the student ")