;; Data Definitions provided by abs.ss

  ;; Token := number | (make-delimiter symbol) | (make-operator symbol) 
  ;;        | (make-primitive symbol) | (make-keyword symbol) 
  ;;        | (make-variable symbol)

  ;: Exp := (make-bool-exp boolean) | (make-null-exp) | (make-num-exp number)
  ;;      | (make-id-exp symbol) | (make-prim-exp symbol) 
  ;;      | (make-uop-exp symbol Exp) | (make-biop-exp symbol Exp Exp) | 
  ;;      | (make-map-exp (list-of symbol) Exp) | (make-app-exp Exp (list-of Exp)) 
  ;;      | (make-if-exp Exp Exp Exp) | (make-let-exp (list-of id-defn) Exp) |
  ;;      | (make-block-exp (list-of Exp))  ;; not used yet !

  ;; id-defn := (make-id-defn symbol Exp)

  ;; Stream := -> Token [with side effect of advancing the cursor in the Stream]

;; Addtional methods provided by abs.ss

   ;; deconvert: Exp -> List
   ;; tostring: Exp -> String

;; Data Definitions to Support the Interpreters

  ;; Value := Integer | Boolean | (list-of Value) | closure
  ;; GenValue := Value | Thunk
  ;; Thunk := -> Value

  ;; Env ::= (list-of binding)

  ;; (make-binding Symbol GenValue)
  (define-struct binding (var val))

  ;; (make-closure (list-of Symbol) AST Env)
  (define-struct closure (parms body env))

  ;; Eval : = { 'value | 'name | 'need ) -> Value

;; parser tables

(define BINOP (list '+ '- '* '/ '= '< '<= '> '>= '!= '& '\|))
(define UOP (list '+ '- '~))

;; parser auxiliary functions

;; Token -> boolean
;; (if? token) returns true if the token is the keyword 'if
(define (if? token) (and (keyword? token) (eq? (keyword-sym token) 'if)))

;; Token -> boolean
;; (let? token) returns true if the token is the keyword 'let
(define (let? token) (and (keyword? token) (eq? (keyword-sym token) 'let)))

;; Token -> boolean
;; (map? token) returns true if the token is the keyword 'map
(define (map? token) (and (keyword? token) (eq? (keyword-sym token) 'map)))

;; Token -> boolean
;; (to? token) returns true if the token is the keyword 'to
(define (to? token) (and (keyword? token) (eq? (keyword-sym token) 'to)))

;; Token -> boolean
;; (then? token) returns true if the token is the keyword 'then
(define (then? token) (and (keyword? token) (eq? (keyword-sym token) 'then)))

;; Token -> boolean
;; (else? token) returns true if the token is the keyword 'else
(define (else? token) (and (keyword? token) (eq? (keyword-sym token) 'else)))

;; Token -> boolean
;; (in? token) returns true if the token is the keyword 'in
(define (in? token) (and (keyword? token) (eq? (keyword-sym token) 'in)))

;; Token -> boolean
;; (binop? token) returns true if the token is a binary operator
(define (binop? token) (and (operator? token) (member (operator-sym token) BINOP)))

;; Token -> boolean
;; (unop? token) returns true if the token is a unary operator
(define (unop? token) (and (operator? token) (member (operator-sym token) UOP)))

;; Token -> boolean
;; (assign? token) returns true if the token is the operator ':=
(define (assign? token) (and (operator? token) (eq? (operator-sym token) ':=)))

;; Token -> boolean
;; (left-paren? token) returns true if the token is the operator '(
(define (left-paren? token) (and (delimiter? token) (eq? (delimiter-sym token) '\()))

;; Token -> boolean
;; (right-paren? token) returns true if the token is the operator ')
(define (right-paren? token) (and (delimiter? token) (eq? (delimiter-sym token) '\))))

;; Token -> boolean
;; (semi-colon? token) returns true if the token is the delimiter ';
(define (semi-colon? token) (and (delimiter? token) (eq? (delimiter-sym token) '\;)))

;; Token -> boolean
;; (comma? token) returns true if the token is the delimiter ',
(define (comma? token) (and (delimiter? token) (eq? (delimiter-sym token) '\,)))

;; string -> Exp
;; (parse-file file-name) reads the program text from file file-name and parses it into an Exp
;;   leaves cursor at end-of-file
(define parse-file  (lambda (file-name)  (parse (make-file-lexer file-name))))

;; string -> Exp
;; (parse-string string) reads the program text from string and parses it into an Exp
;;   leaves cursor at end-of-file
(define parse-string (lambda (string) (parse (make-string-lexer string))))

;; string -> Exp
;; (parse input) reads the program text from token stream input and parses it into an Exp
;;   leaves cursor at end-of-file
(define parse
  (lambda (input)
    (local 
        [(define token (input))]
      (if (eof-object? token)     ; empty stream
          (error 'parse "empty input stream")
          (local
              [(define result (Parse-exp token input))
               (define extra (input))]
            (if (eof-object? extra)
                result
                (error 'parse "unexpected trailing input: ~a" extra)))))))

;; Token Stream -> Exp
;; (Parse-exp t s) reads an <exp> from Stream t,s and parses it into an Exp
;;                 leaves the cursor immediately following the last token of <exp>
(define Parse-exp 

  (lambda (token stream)  

  ; The following grammar defines the form of an <exp>

  ;   <exp> ::= if <exp> then <exp> else <exp>
  ;           | let <def>+ in <exp>
  ;           | map { <prop-id-list> } to <exp>
  ;           | <term> { <binop> <exp> } 

    (cond
      [(if? token) (Parse-if stream)]
      [(let? token) (Parse-let stream)]
      [(map? token) (Parse-map stream)]
      [else 
       (local 
           [(define term (Parse-term token stream))
            (define op (stream 'peek))]
         (if (binop? op)
             (begin (stream) ; skip past BINOP
                    (local [(define exp (Parse-exp (stream) stream))]
                      (make-biop-exp (operator-sym op) term exp)))
             term))])))

;; Token Stream -> Exp
;; (Parse-term t s) reads a <term> from from stream t,s and parses it into an Exp
;;                 leaves the cursor immediately following the last token of <term>
(define Parse-term
  
  (lambda (token stream)
    
  ; The following grammar defines the form of a <term>
  ;  <term> ::= <int>
  ;	      | <null> 
  ;	      | <bool>
  ;           | <factor> { ( <exp-list> ) }   ;; this line is an optional-app
  ;           | <unop> <term>
  
    (cond 
      [(number? token) (make-num-exp token)]
      [(keyword? token)
       (local [(define sym (keyword-sym token))]
         (cond 
           [(eq? sym 'null) (make-null-exp)]
           [(member sym (list 'true 'false)) (make-bool-exp sym)]
           [else ;; sym is a keyword that is not a term
            (error 'Parse-term "keyword ~a is not a legal term prefix")]))]
      [(unop? token) (make-uop-exp (operator-sym token) (Parse-exp (stream) stream))]
      [else ;; token must be first token in a factor
       (parse-optional-app (Parse-factor token stream) stream)])))

;; Exp Stream -> Exp
;; (parse-optional-app f s) reads an optional application following the <factor> f 
;;    in Stream s (the cursor in s points to the first token following f)
;;    and returns the factor f with the optional application
;;    leaves the cursor immediately following the last token of optional application
(define parse-optional-app

  (lambda (factor stream)
  ;;    The optional application has the form { ( <exp-list> ) }  
    (local [(define next-token (stream 'peek))]
      (if (left-paren? next-token) 
          (begin
            (stream) ;; consume LEFT-PAREN
            (let
              [(result (make-app-exp factor (Parse-exps stream)))
               (trailer (stream))]
            (if (right-paren? trailer)
                result
                (error 'Parse-exp "`~a' found where `)' expected following <exp-list>" 
                       trailer))))
          factor))))

;; Token Stream -> Exp
;; (Parse-factor t s) reads a <factor> from from stream t,s and parses it into an Exp
;;   leaves the cursor immediately following the last token of <factor>
(define Parse-factor
  (lambda (token stream)
    ; The following grammar defines the form of a <factor>

    ;  <factor> ::= ( <exp> ) | <prim> | <id>
  
    (cond
      [(left-paren? token) 
       (local 
	   [(define exp (Parse-exp (stream) stream))
            (define token (stream))]
         (if (right-paren? token) 
             exp 
             (error 'Parse-factor "~a found instead of expected right parenthesis" token)))]
      [(primitive-token? token) (make-prim-exp (primitive-token-sym token))] 
      [(variable? token) (make-id-exp (variable-sym token))]
      [else (error 'Parse-factor "~a found instead of first token of a factor" token)]))) 


;; Stream -> Exp
;; (Parse-factor t s) reads a map-expression from from stream 'map,s and parses it into an Exp
;;   leaves the cursor immediately following the last token of the map-expression
(define Parse-map ; "map" has already been read
  (lambda (stream)
    ; Note: "map" has already been consumed; stream holds the remaining tokens.
    ; The following grammar defines the form of a map-expression

    ; map { <prop-id-list> } to <exp>
    
    (local [(define bound-vars (Parse-vars stream))
            (define token (stream))]
      (if (to? token)
          (make-map-exp bound-vars (Parse-exp (stream) stream))
          (error 'Parse-map 
                 "`~a' found instead of `to' following bound <vars> in map" token)))))

;; Stream -> (list-of Symbol)
;; (Parse-vars s) reads an <id-list> from from stream s and parses it into a (list-of Symbol)
;;   leaves the cursor immediately following the last token of <id-list>
(define Parse-vars
  (lambda (stream)
    ; The following grammar defines the form of an <id-list>
    ;  <id-list>       ::= { <prop-id-list> }
    ;  <prop-exp-list> ::= <exp>   | <exp> , <prop-exp-list> 

    (local
        [(define p-var (stream 'peek))
         (define var-error
           (lambda (token) 
             (error 'Parse-vars "illegal token ~a in map parameter list" token)))
         (define parse-more-vars
           (lambda ()
             (local
                 [(define p-comma (stream 'peek))]
               (if (comma? p-comma) 
                   (begin (stream) ; skip past COMMA
                          (local
                              [(define var (stream))]
                            (if (variable? var)
                                (cons (variable-sym var) (parse-more-vars))
                                (var-error var))))
                   null))))]
      (if (variable? p-var)
          (begin (stream) (cons (variable-sym p-var) (parse-more-vars)))
          null))))

;; Stream -> (list-of Symbol)
;; (Parse-exps s) reads an <exp-list> from from stream s and parses it into a (list-of Symbol)
;;   leaves the cursor immediately following the last token of <exp-list>
(define Parse-exps
  (lambda (stream)
    ; The following grammar defines the form of a <exp-list>
    ;  <exp-list>      ::= { <prop-exp-list> }
    ;  <prop-exp-list> ::= <exp>   | <exp> , <prop-exp-list> 
    
    (local
        [(define p-token (stream 'peek))
         (define parse-more-exps
           (lambda ()
             (local
                 [(define p-comma (stream 'peek))]
               (if (comma? p-comma) 
                   (begin (stream) ; skip past COMMA
                          (cons (Parse-exp (stream) stream) (parse-more-exps)))
                   null))))]
      (if (right-paren? p-token)
          null
          (cons (Parse-exp (stream) stream) (parse-more-exps))))))

;; Stream -> Exp
;; (Parse-let s) reads a let-expression from from stream 'let,s and parses it into an Exp
;;   leaves the cursor immediately following the last token of the let-expression
(define Parse-let ; "let " has already been read
  (lambda (stream)  
    ;; Note: "let" has already been consumed; stream holds the remaining tokens.
    ;; The following phrase defines the form of a let-expression:
    ;
    ; let <def>+ in <exp>

    (local 
        [(define defns (cons (Parse-defn stream) (Parse-defns stream))) 
         (define token (stream))]
      (if (in? token)
          (make-let-exp defns (Parse-exp (stream) stream))
          (error 'Parse-let "'in expected instead of ~a following defns in let"
                 token)))))

;; Stream -> (list-of id-defn)
;; (Parse-defns s) reads <def>* from from stream s and parses it into a (list-of id-defn)
;;   leaves the cursor immediately following the last token of <def>*
(define Parse-defns 
  (lambda (stream)
    (local
        [(define ptoken (stream 'peek))]
      (if (in? ptoken)
          '()
          (cons (Parse-defn stream) (Parse-defns stream))))))

;; Stream -> id-defn
;; (Parse-defn s) reads a <def> from from stream s and parses it into a id-defn
;;   leaves the cursor immediately following the last token of <def>
(define Parse-defn 
  (lambda (stream)
    ; The following grammar describes the form of a <def>
    ;
    ;  <def> ::= <id> := <exp> ;
    ; the semicolon at the end of the previous line is part of a <def>

    (local
        [(define var (stream))]
      (if (variable? var)
          (local
              [(define token (stream))]
            (if (assign? token)
                (local
                    [(define exp (Parse-exp (stream) stream))
                     (define delimiter (stream))]
                  (if (semi-colon? delimiter)
                      (make-id-defn (variable-sym var) exp)
                      (error 'Parse-defn "`;' expected instead of `~a' to close defn" 
                             delimiter)))
                (error 'Parse-defn "`:=' expected instead of ~a in defn" token)))
          (error 'Parse-defn "Illegal local variable name ~a" var)))))


;; Stream -> Exp
;; (Parse-if s) reads an if-expression from from stream 'if, s and parses it into a Exp
;;   leaves the cursor immediately following the last token of the if-expression
(define Parse-if ; "if" has already been read                 
  (lambda (stream)  
    ; Note: "if" has already been consumed; stream holds the remaining tokens.
    ; The following phrase defines the form of an if expression
    ;
    ; if <exp> then <exp> else <exp>
    
    (local [(define test (Parse-exp (stream) stream))
            (define token (stream))]
      (if (then? token)
          (local
              [(define conseq (Parse-exp (stream) stream))
               (define token (stream))]
            (if (else? token)
                (make-if-exp test conseq (Parse-exp (stream) stream))
                (error 'Parse-if "`else' expected instead of `~a' following consequent of if"
                       token)))
          (error 'Parse-if "`then' expected instead of `~a' following test of if"
                 token)))))

;; string -> lexer
;; (make-debug-string-lexer s) constructs a lexer for string s that prints each token as it is read
(define (make-debug-string-lexer s)
  (local [(define l (make-string-lexer s))]
    (lambda args (local [(define t (apply l args))]
                   (printf "token ~a ~a~n" t (if (null? args) 'read 'peeked))
                   t))))