;; The first three lines of this file were inserted by DrRacket. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname R0) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f))) ;; Here is the code written (almost) entirely in lecture, ;; including the R0 parser. (require "student-extras.rkt") (require "scanner.rkt") (provide (all-defined-out)) #| Expr → Num | BinOp | Paren | Parity BinOp → | Expr Expr Op | Op → ;) | ;( | xD ; addition, subtr, mult resp. Paren → < Expr > Parity → / Expr Expr Expr \ ; if first expr is even, return the 2nd, else the third |# ; An Expr is: ; - a number ; - (make-binop [Expr] [Expr] [string-of-length-2]) ; - (make-paren [Expr]) (define-struct binop (left right op)) (define-struct paren (e)) (define-struct parity (if-even then else)) ; Examples of Expr: 34 (make-paren 34) (make-binop 3 4 ";)") (make-binop (make-paren 34) (make-binop 3 4 ";)") ";(") (make-parity 3 7 9) (make-parity (make-paren 34) (make-binop (make-paren 34) (make-binop 3 4 ";)") ";(") (make-parity 3 7 9)) (check-expect (parse! (create-scanner "34")) 34) (check-expect (parse! (create-scanner "-34")) -34) (check-expect (parse! "34") 34) (check-expect (parse! "<34>") (make-paren 34)) (check-expect (parse! "| 3 4 ;) |") (make-binop 3 4 ";)")) (check-expect (parse! "| <34> | 3 4 ;) | ;( |") (make-binop (make-paren 34) (make-binop 3 4 ";)") ";(")) (check-expect (parse! "/ 3 7 9 \\") (make-parity 3 7 9)) (check-expect (parse! "/ <34> | <34> | 3 4 ;) | ;( | / 3 7 9 \\ \\") (make-parity (make-paren 34) (make-binop (make-paren 34) (make-binop 3 4 ";)") ";(") (make-parity 3 7 9))) ; parse! : (scanner OR string) -> Expr ; given a scanner, read one R0 expression off the front of it ; (consuming scanner), ; and ; return the corresponding parse-tree. ; Use recursive-descent parsing. ; (define (parse! s) (cond [(string? s) (parse! (create-scanner s))] ; overload: scanner *or* string. [(number? (peek s)) (pop! s)] [(string=? "|" (peek s)) (let* {[opening-pipe (pop! s)] [lefty (parse! s)] [righty (parse! s)] [oppy (parse-op! s)] [closing-pipe (pop! s)]} (make-binop lefty righty oppy))] [(string=? "<" (peek s)) (let* {[_ (pop! s)] [ey (parse! s)] [_ (pop! s)] ; the closing-angle-bracket } (make-paren ey))] [(string=? "/" (peek s)) (let* {[_ (pop! s)] ; throw away the opening "/" [if-eveny (parse! s)] [thenny (parse! s)] [elsey (parse! s)] [_ (pop! s)] ; throw away the closing "\" } (make-parity if-eveny thenny elsey))] [else (error 'parse! "something has gone awry! Seeing " (pop! s))])) ; all known arithmetic operators: (define OPS (list ";)" ";(" "xD")) ; parse-op! : scanner -> (one-of OPS) ; Pop one operator off the front of s and return it. ; (define (parse-op! s) (cond [(string? s) (parse-op! (create-scanner s))] ; overload: scanner *or* string. [(member? (peek s) OPS) (pop! s)] [(string=? (peek s) ";") (let* {[full-operator (string-append (pop! s) (pop! s))]} ; do an error-check, before returning `full-operator` (if (member? full-operator OPS) full-operator (error 'parse-op! "Unknown winky operator: " full-operator)))] [else (error 'parse-op! (format "token ~v not a known op (expected one of ~v)" (peek s) OPS))])) (check-expect (parse-op! ";)") ";)") (check-expect (parse-op! ";) and further tokens") ";)") (check-expect (parse-op! ";)etc etc") ";)") (check-expect (parse-op! " ;(etc)") ";(") (check-expect (parse-op! "xD") "xD") (check-expect (parse-op! "xD etc") "xD") ; Your code doesn't need to check for errors. ; However, the defensive programming might actually save us time overall: (check-error (parse-op! ":0")) (check-error (parse-op! ":0 etc")) (check-error (parse-op! ";0 etc")) (check-error (parse-op! ";! blah")) (check-error (parse-op! ";abc blah")) ; eval : Expr -> Num ; Return the value which this Expr evaluates to. ; In R0, the only type of value is a Num. ; (define (eval e) (cond [(number? e) e] [(paren? e) (eval (paren-e e))] [(binop? e) (let* {[left-val (eval (binop-left e))] [right-val (eval (binop-right e))] [the-op (binop-op e)]} (cond [(string=? ";)" the-op) (+ left-val right-val)] [(string=? ";(" the-op) (- left-val right-val)] [(string=? "xD" the-op) (* left-val right-val)] [else (error 'eval "unknown operator " the-op)]))] [(parity? e) (if (even? (eval (parity-if-even e))) (eval (parity-then e)) (eval (parity-else e)))] [else (error 'eval "unknown type of expr" (expr->string e))])) (check-expect (eval 34) 34) (check-expect (eval (parse! "<34>")) 34) (check-expect (eval (parse! "| 3 4 ;)|")) 7) (check-expect (eval (parse! "| 3 4 ;(|")) -1) (check-expect (eval (parse! "| 3 4 xD|")) 12) (check-expect (eval (parse! "/ 3 4 5 \\")) 5) (check-expect (eval (parse! "/ 2 4 5 \\")) 4) (check-expect (eval (parse! "/ 2 |3 4 ;)| 5 \\")) 7) ; expr->string : Expr -> string ; Return a string-representation of `e`. ; (define (expr->string e) (cond [(number? e) (number->string (if (integer? e) e (exact->inexact e)))] [(paren? e) (string-append "<" (expr->string (paren-e e)) ">")] [(binop? e) (string-append "|" (expr->string (binop-left e)) " " (expr->string (binop-right e)) " " (binop-op e) "|")] [(parity? e) (string-append "/" (expr->string (parity-if-even e)) " " (expr->string (parity-then e)) " " (expr->string (parity-else e)) "\\")] [else (error 'expr->string (format "unknown type of expr: ~v" e))])) (check-expect (expr->string (parse! "34")) "34") (check-expect (expr->string (parse! "<34>")) "<34>") (check-expect (expr->string (parse! "| 3 4 ;)|")) "|3 4 ;)|") (check-expect (expr->string (parse! "| 3 4 ;(|")) "|3 4 ;(|") (check-expect (expr->string (parse! "| 3 4 xD|")) "|3 4 xD|") (check-expect (expr->string (parse! "/ 3 4 5 \\")) "/3 4 5\\") (check-expect (expr->string (parse! "/ 2 |3 4 ;)| 5 \\")) "/2 |3 4 ;)| 5\\") #| (check-expect (eval 34) 34) (check-expect (eval (make-paren 34)) 34) (check-expect (eval (make-binop 3 4 ";)")) 7) (check-expect (eval (parse! "| <34> | 3 4 ;) | ;( |")) 27) (check-expect (expr->string (parse! "| <34> | 3 4 ;) | ;( |")) "| <34> |3 4 ;)| ;( |") |#