#lang racket

;; File:    parser.rkt
;; Author:  You!
;; A starting point for the unilang parser

(require "tokenizer.rkt")
(require htdp/testing) ;; for  check-expect
(require racket/trace) ;; for  trace

;; Make (only) these functions available to the evaluator.
(provide parse read-parse-print)


;;;;;;;;;;;;;;;;;;;
;; Configuration ;;
;;;;;;;;;;;;;;;;;;;

;; How to prompt the user for input
(define prompt-string "input > ")

;; The input that makes the read-eval-print loop stop.
(define quit-string "quit") 

;; How to label the output of the tokenizer
(define tokens-label "tokens: ")

;; How to label the output of the parser
(define ast-label "ast   : ")

;;;;;;;;;;;;;;;;;;;;
;; Top-Level Loop ;;
;;;;;;;;;;;;;;;;;;;;

;; An interactive read-parse-print loop just for the parser.  It's 
;; not necessary, but it's sort of fun.
;;   NOTE: the name is *not* read-eval-print.
(define (read-parse-print)
  (begin
    (newline)
    (display prompt-string)
    (let* (
          (input-string (read-line))
          )
      (if (equal? input-string quit-string)
          '()                     ;; exit
          (begin
             (parse input-string)
             (read-parse-print)
           ))
      )
    ))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Helper Functions for Parsing ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Function begins-with?
;; input: an element and a list
;; output: #t if the list L begins with the element elem, #f otherwise
;; This function is also defined in the tokenizer, but it's
;;   not exported from that module. (Plus, if you write your
;;   own tokenizer, you might not have defined this function.)
;;   So, we reimplement it here just in case.
(define (begins-with? elem L)
  (if (null? L) 
      #f
      (equal? elem (first L))))


;; All the parse functions return a pair.
;; These helper functions let us refer to the result and the residual,
;;   rather than remembering which is first and second.
(define result first)
(define residual second)


;;;;;;;;;;;;
;; Parser ;;
;;;;;;;;;;;;

;; Note: see the end of this file for some possibly useful
;;   information while debugging your parser.

;; Function: parse
;; input: a string to parse
;; Output: a list of two elements, the same as the parse function
;; Also prints the results to the screen
(define (parse input-string)
  ;; first, tokenize and display the list of tokens.
  (let ((tokens (tokenize input-string)))
    (display tokens-label)
    (print tokens)
    (newline)
    ;; then parse and display the abstract syntax tree
    (let ((parse-result (parse-t tokens)))
       (display ast-label)
       (print (first parse-result))
       (newline)
       (newline)
       ;; finally, return the parse results
       (first parse-result))))

;; Parse the following grammar
;;
;; T -> def V L | L
;; L -> # E | E
;; E -> P + E | P - E | P
;; P -> K * P | K / P | K
;; K -> U ^ I | U
;; U -> ( L ) | - U | Q
;; Q -> D ~ D V* | D V* | V V*
;;    where V* means 0 or more V's
;;
;; I -> <any integer> | - <any integer>
;; D -> any *positive* number
;; V -> any variable name (a string token)

;; function parse-t
;; Input: tokens, a list of tokens
;; output: a list of two elements: ( parse-result  residual )
;;   parse-result: the parse tree
;;   residual: the rest of the tokens in the input list that are not included 
;;      in the parse tree (or an empty list, if all tokens were accounted for).
;; Parse a top level (T) expression using recursive descent parsing.  
;; T -> def V L | L
;; WARNING!!!! right now, this function just calls parse-q, 
;;   which is obviously wrong.  Worse, parse-q isn't fully
;;   implemented yet!
(define (parse-t tokens)
  (cond [(null? tokens) (error "empty input")]
        [else
         (parse-q tokens)]))

;;;;
;; Note: each of the parse-X functions expects a list of
;;   tokens, and returns abstract syntax plus a list
;;   of leftover tokens
;;;;


;; Function: parse-q
;; Q -> D ~ D V* | D V* | V V*
(define (parse-q tokens)
  (cond [(null? tokens) 
         (error "parse-q: unexpected end of input")]
        [(number? (first tokens))
         ;; XXX FIX ME
         (error "I think there should be some different code here")]
        [else 
         (let* (; get V
                [pair (parse-v tokens)]
                [v  (result pair)]
                [after-v (residual pair)]
                ; get Vs
                [pair2 (parse-vs after-v)]
                [vs (result pair2)]
                [after-vs (residual pair2)])
           (list (list 'uql  1 0 (cons v vs) '()) after-vs))])) 

;;;;
;; I think these other parsing functions work OK.
;;;;

;; function: parse-v
;; V -> any variable name (a string token)
;; Note: returns the variable name (a string token) as a racket *symbol*.
(define (parse-v tokens)
  (cond [(null? tokens) 
         (error "Unexpected end of input")]
        [(string? (first tokens)) 
         (list (string->symbol (first tokens)) (rest tokens))]
        [else 
         (error "Expected a variable, but found " (first tokens))]))

;; parse V* (a series of zero or more V's)
;; Just a simple recursive loop, grabbing string tokens
;;   off the front of the list until they run out.
(define (parse-vs tokens)
  (cond [(null? tokens) (list '() tokens) ]
        [(string? (first tokens))
         (let* ([pair (parse-v tokens)]
                [v   (result pair)]
                [after-v (residual pair)]
                [pair2 (parse-vs (rest tokens))]
                [vs  (result pair2)]
                [after-vs (residual pair2)])
           (list (cons v vs) after-vs))]
        [else (list '() tokens) ]))
      


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; WHILE DEBUGGING, YOU MIGHT WANT TO UNCOMMENT SOME OR ALL OF THESE ;;
;; They tell Racket to print the arguments when the specified        ;;
;;   function starts, and print return value when it exits.          ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;(trace parse-d)
;(trace parse-i)
;(trace parse-q)
;(trace parse-u)
;(trace parse-k)
;(trace parse-p)
;(trace parse-e)
;(trace parse-q)
;(trace parse-t)
;(trace parse-l)