;;; 6.945 Problem Set #1 - workfile
;;; 02/10/2009
;;; Bryan Newbold <bnewbold@mit.edu>

(load "regexp.scm")


(pp (r:grep (r:seq " "
		   (r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
		   (r:eol))
	    "tests.txt"))

;-------------------------------------------------------------------
; 1.1: define r:* and r:+

(define (r:+ pattern)
  (r:repeat 1 #f pattern))

(define (r:* pattern)
  (r:repeat 0 #f pattern))

(pp (r:grep (r:seq (r:quote "dog")
		   (r:+ (r:quote "cat")))
	    "tests.txt"))

;("[09]. catdogcat" "[11]. dogdogcatdogdog" "[13]. acatdogdogcats")

(pp (r:grep (r:seq (r:quote "cat")
		   (r:+ (r:char-from (string->char-set "ogd")))
		   (r:quote "cat"))
	    "tests.txt"))

;("[09]. catdogcat" "[13]. acatdogdogcats")

(pp (r:grep (r:seq " "
		   (r:+ (r:quote "cat"))
		   (r:eol))
	    "tests.txt"))
; #f

(pp (r:grep (r:* (r:quote "something that isn't there"))
	    "tests.txt"))
; matches all

(pp (r:grep (r:repeat 2 3 (r:* (r:char-from (string->char-set "tca"))))
	    "tests.txt"))
; matches all: nothing repeated several times

(pp (r:grep (r:seq (r:quote "dog")
		   (r:+ (r:quote "cat"))
		   (r:quote "dog"))
	    "tests.txt"))

;("[11]. dogdogcatdogdog")

(pp (r:grep (r:seq (r:quote "dog")
		   (r:* (r:quote "cat"))
		   (r:quote "dog"))
	    "tests.txt"))
#|
("[10]. catcatdogdog" "[11]. dogdogcatdogdog"
                      "[12]. catcatcatdogdogdog"
                      "[13]. acatdogdogcats"
                      "[14]. ifacatdogdogs"
                      "[15]. acatdogdogsme")
|#

;-------------------------------------------------------------------------
; 1.2

(define (r:repeat min max expr)
  (if (not (exact-nonnegative-integer? min))
      (error "Min must be non-negative integer:" min))
  (if max
      (begin
	(if (not (exact-nonnegative-integer? max))
	    (error "Max must be non-negative integer (or null):" max))
	(if (not (<= min max))
	    (error "Min not less than max:" min max))))
  (cond 
   ((not max) (r:seq expr (string-append "\\{" (number->string min) ",\\}")))
   ((= max min) (r:seq expr (string-append "\\{" (number->string min) "\\}")))
   (else (r:seq expr (string-append "\\{" 
				    (number->string min) 
				    "," 
				    (number->string max) 
				    "\\}")))))
#| tests:
(pp (r:grep (r:repeat 2 3 (r:quote "cat"))
	    "tests.txt"))
(pp (r:grep (r:repeat 2 #f (r:quote "cat"))
	    "tests.txt"))
(pp (r:grep (r:repeat 1 1 (r:quote "cat"))
	    "tests.txt"))
(pp (r:grep (r:repeat 4 3 (r:quote "cat"))
	    "tests.txt"))
(r:repeat 2 3 (r:quote "cat"))
|#

;---------------------------------------------------------------------------
; 1.3

(define (r:subexp . exprs)
  (string-append "\\(" (apply string-append exprs) "\\)"))

(define (r:seq . exprs)
  (apply string-append exprs))

(r:seq " " (r:subexp "sdf") "dddd")

(define (r:repeat min max expr)
  (if (not (exact-nonnegative-integer? min))
      (error "Min must be non-negative integer:" min))
  (if max
      (begin
	(if (not (exact-nonnegative-integer? max))
	    (error "Max must be non-negative integer (or null):" max))
	(if (not (<= min max))
	    (error "Min not less than max:" min max))))
  (cond 
   ((not max) (r:seq (r:subexp expr) 
		     (string-append "\\{" (number->string min) ",\\}")))
   ((= max min) (r:seq (r:subexp expr) 
		       (string-append "\\{" (number->string min) "\\}")))
   (else (r:seq (r:subexp expr) 
		(string-append "\\{" 
			       (number->string min) 
			       "," 
			       (number->string max) 
			       "\\}")))))

(define (r:alt . exprs)
  (if (pair? exprs)
      (r:subexp (apply r:seq
		       (cons (car exprs)
			     (append-map (lambda (expr)
					   (list "\\|" expr))
					 (cdr exprs)))))
      (r:seq)))

(r:alt "first thing" "second thing")

;----------------------------------------------------------------------------
; 1.4

(define (r:backref n)
  (string-append "\\" (number->string n)))

;----------------------------------------------------------------------------
; 1.5

; the following are only the expressions which had to be rewritten...

(define (r-grep:seq . exprs)
  (let ((choose-grep (lambda (x)
		      (cond
		       ((string? x) x)
		       ((list? x) ((car x)))))))
  (apply string-append (map choose-grep exprs))))

(define (r-egrep:seq . exprs)
  (let ((choose-egrep (lambda (x)
		      (cond
		       ((string? x) x)
		       ((list? x) ((cadr x)))))))
  (apply string-append (map choose-egrep exprs))))

#| test:
(r-grep:seq "a" "b" '("grep" "egrep"))
; "abgrep"
(r-egrep:seq "a" "b" '("grep" "egrep"))
; "abegrep"
|#

(define (r:seq . exprs)
  (cons (lambda () (apply r-grep:seq exprs)) 
	(cons (lambda () (apply r-egrep:seq exprs)) '())))

#| test:
(r:seq "a" "b" '("grep" "egrep"))
;Value: (#[compound-procedure 14] #[compound-procedure 15])
((car (r:seq "a" "b" '("grep" "egrep"))))
; "abgrep"
((cadr (r:seq "a" "b" '("grep" "egrep"))))
; "abegrep"
|#

(define (r-egrep:alt . exprs)
  (let ((choose-egrep (lambda (x)
		      (cond
		       ((string? x) x)
		       ((list? x) ((cadr x)))))))
  (if (pair? exprs)
      (apply r-egrep:seq
	     (cons (choose-egrep (car exprs))
		   (append-map (lambda (expr)
				 (list "|" (choose-egrep expr)))
			       (cdr exprs))))
      (r-egrep:seq))))

(define (r-grep:alt . exprs)
  (let ((choose-grep (lambda (x)
		      (cond
		       ((string? x) x)
		       ((list? x) ((car x)))))))
    (if (pair? exprs)
	(apply r-grep:seq
	       (cons (choose-grep (car exprs))
		     (append-map (lambda (expr)
				   (list "\\|" (choose-grep expr)))
				 (cdr exprs))))
      (r-grep:seq))))

(define (r:alt . exprs)
  (cons (lambda () (apply r-grep:alt exprs)) 
	(cons (lambda () (apply r-egrep:alt exprs)) '())))

#| test:
(r-egrep:alt "a" (r:dot) "c")
;Value: "a|.|c"
(r:alt "asdf" (r:dot))
;Value: (#[compound-procedure 16] #[compound-procedure 17])
((car (r:alt "asdf" (r:dot))))
;Value: "asdf\\|."
((cadr (r:alt "asdf" (r:dot))))
;Value: "asdf|."
|#

(define (r-grep:repeat min max expr)
  (let ((choose-grep (lambda (x)
		      (cond
		       ((string? x) x)
		       ((list? x) ((car x)))))))
    (if (not (exact-nonnegative-integer? min))
	(error "Min must be non-negative integer:" min))
    (if max
	(begin
	  (if (not (exact-nonnegative-integer? max))
	      (error "Max must be non-negative integer (or null):" max))
	  (if (not (<= min max))
	      (error "Min not less than max:" min max))))
    (cond 
     ((not max) (r-grep:seq (r-grep:subexp (choose-grep expr)) 
		       (string-append "\\{" (number->string min) ",\\}")))
   ((= max min) (r-grep:seq (r-grep:subexp (choose-grep expr)) 
		       (string-append "\\{" (number->string min) "\\}")))
   (else (r-grep:seq (r-grep:subexp (choose-grep expr)) 
		(string-append "\\{" 
			       (number->string min) 
			       "," 
			       (number->string max) 
			       "\\}"))))))


(define (r-egrep:repeat min max expr)
  (let ((choose-egrep (lambda (x)
		      (cond
		       ((string? x) x)
		       ((list? x) ((cadr x)))))))
    (if (not (exact-nonnegative-integer? min))
	(error "Min must be non-negative integer:" min))
    (if max
	(begin
	  (if (not (exact-nonnegative-integer? max))
	      (error "Max must be non-negative integer (or null):" max))
	  (if (not (<= min max))
	      (error "Min not less than max:" min max))))
    (cond 
     ((not max) (r-egrep:seq (r-egrep:subexp (choose-egrep expr)) 
		       (string-append "{" (number->string min) ",}")))
   ((= max min) (r-egrep:seq (r-egrep:subexp (choose-egrep expr)) 
		       (string-append "{" (number->string min) "}")))
   (else (r-egrep:seq (r-egrep:subexp (choose-egrep expr)) 
		(string-append "{" 
			       (number->string min) 
			       "," 
			       (number->string max) 
			       "}"))))))

(define (r:repeat min max expr)
  (cons (lambda () (r-grep:repeat min max expr)) 
	(cons (lambda () (r-egrep:repeat min max expr)) '())))

#| tests:
(r-grep:repeat 1 3 "d")
;Value: "\\(d\\)\\{1,3\\}"
(r-egrep:repeat 1 3 "d")
;Value: "(d){1,3}"
((car (r:repeat 2 2 "asdf")))
;Value: "\\(asdf\\)\\{2\\}"
((cadr (r:repeat 2 2 "asdf")))
;Value: "(asdf){2}"

((cadr (r:repeat 3 #f "asdf")))
;Value: "(asdf){3,}"

(r:+ "asdf")
;Value: (#[compound-procedure 21] #[compound-procedure 22])
((car (r:+ "asdf")))
;Value: "\\(asdf\\)\\{1,\\}"

((car (r:+ (r:+ (r:quote "a")))))
;Value: "\\(\\(a\\)\\{1,\\}\\)\\{1,\\}"

((car (r:seq (r:quote "a"))))
|#

(define (r-grep:subexp . exprs)
  (string-append "\\(" (apply string-append 
			    (map (lambda (x)
				   (cond
				    ((string? x) x)
				    ((pair? x) ((car x)))))
				 exprs)) "\\)"))

(define (r-egrep:subexp . exprs)
  (string-append "(" (apply string-append 
			    (map (lambda (x)
				   (cond
				    ((string? x) x)
				    ((pair? x) ((cadr x)))))
				 exprs)) ")"))

(define (r:subexp . exprs)
  (cons (lambda () (apply r-grep:subexp exprs)) 
	(cons (lambda () (apply r-egrep:subexp exprs)) '())))

#| test:
(r:subexp "a" "b" (r:dot))
;Value: (#[compound-procedure 25] #[compound-procedure 26])
((cadr (r:subexp "a" "b" (r:dot))))
;Value: "(ab.)"
((car (r:subexp "a" "b" (r:dot))))
;Value: "\\(ab.\\)"
|#

(define (r:grep expr filename)
  (r:grep-like "grep" '() ((car expr)) filename))

(define (r:egrep expr filename)
  (if (eq? microcode-id/operating-system 'nt)
      (r:grep-like "grep" '("-E") ((cadr expr)) filename)
      (r:grep-like "egrep" '() ((cadr expr)) filename)))

#| final tests:
(r:seq (r:repeat 2 3 (r:quote "cat")) (r:+ (r:quote "dog")))
;Value: (#[compound-procedure 18] #[compound-procedure 19])
((car (r:seq (r:repeat 2 3 (r:quote "cat")) (r:+ (r:quote "dog")))))
;Value: "\\(cat\\)\\{2,3\\}\\(dog\\)\\{1,\\}"
((cadr (r:seq (r:repeat 2 3 (r:quote "cat")) (r:+ (r:quote "dog")))))
;Value: "(cat){2,3}(dog){1,}"

(pp (r:grep (r:seq (r:repeat 2 3 (r:quote "cat")) (r:+ (r:quote "dog")))
	    "tests.txt"))
; ("[10]. catcatdogdog" "[12]. catcatcatdogdogdog")
(pp (r:egrep (r:seq (r:repeat 2 3 (r:quote "cat")) (r:+ (r:quote "dog")))
	    "tests.txt"))
; ("[10]. catcatdogdog" "[12]. catcatcatdogdogdog")

|#