#lang racket

(require htdp/testing)
(require (lib "trace.ss"))

; file:  parser1.rkt
; author: Robert Keller
; purpose: Illustrate parsing for a simple grammar
; terminal alphabet: { (, )}
; non-terminal alphabet: {S, L}
; start symbol S
; rules:
;         S -> ( L )
;         L -> S L 
;         L -> empty

; The top-level function, parse, is given an input string.
; The string is converted to a list of characters for parsing.
; The result is reported as one of three kinds of string:
;
;    fully succesful, meaning that the input was completely parsed
;
;    succesful, with residue meaning that a prefix of the input was parsed
;        but there was a non-empty residue
;
;    unsuccesful, meaning that there was no prefix of the string that could
;        be parsed
;

; top-level parse function, returns a string as described above

(define (parse input-string)
  (let* (
        (outcome (parse-S (string->list input-string)))
        (residue (get-residue outcome))
        )
    (cond
      [(and (succeeded? outcome) (null? residue)) "fully successful"]
      [(succeeded? outcome) (string-append "successful, with residue: " 
                                           (list->string residue))]
      [else "unsuccessful"])))
           

; Data abstraction for Outcomes of the parse
; An outcome consists of two parts: 
;    a result indicating success or failure
;    a residue, which is the list of characters left over

; Construct an outcome

(define (make-outcome result residue)
  (list result residue))


; Construct a successful Outcome

(define (succeed residue)
  (make-outcome 'success residue))


; Construct a failure Outcome

(define (fail residue)
  (make-outcome 'failure residue))


; Get the result part of an Outcome

(define (get-result Outcome)
  (first Outcome))


; Get the residue part of an Outcome

(define (get-residue Outcome)
  (second Outcome))


; Determine whether an Outcome is succesful

(define (succeeded? Outcome)
  (equal? 'success (get-result Outcome)))


; Determine whether an Outcome is a failure

(define (failed? Outcome)
  (equal? 'failure (get-result Outcome)))


; Predicates to avoid magic characters in the code

(define (left-paren?  char) (char=? #\( char))
(define (right-paren? char) (char=? #\) char))


;; Parse function for rule S -> ( L )

(define (parse-S input)
  (cond
    [(null? input) (fail input)]
    [(left-paren? (first input)) 
     (let (
          (L1 (parse-L (rest input))) ;; can't fail
          )
       (cond 
         [(null? (get-residue L1)) (fail input)]
         [(right-paren? (first (get-residue L1)))
          (succeed (rest (get-residue L1)))]
         [else (fail input)])
       
       )]
    [else (fail input)]))


; Parse function for rules L -> S L and L -> empty

(define (parse-L input)
  (let (
        (S1 (parse-S input))
        )
    (if (succeeded? S1)
        (let (
             (L2 (parse-L (get-residue S1))) ;; can't fail
             )
          (succeed (get-residue L2))
          )
        (succeed input))))


; Unit tests

(check-expect (parse "()")            "fully successful")
(check-expect (parse "(()())")        "fully successful")
(check-expect (parse "(()()())")      "fully successful")
(check-expect (parse "((())())")      "fully successful")
(check-expect (parse "((())(()))")    "fully successful")
(check-expect (parse "((()())(()))")  "fully successful")
(check-expect (parse "(()()))")       "successful, with residue: )")
(check-expect (parse "()()")          "successful, with residue: ()")
(check-expect (parse "(())()")        "successful, with residue: ()")
(check-expect (parse "(")             "unsuccessful")
(check-expect (parse  ")")            "unsuccessful")
(check-expect (parse  ")(")           "unsuccessful")

(generate-report)