Comp 210 Lab 6: Parsing Expressions (optional)

For the stout of heart and free of time, here are some approaches you could take if you wanted to extend the calculator example.

Table of Contents

  • Input form
  • Internal (parse) form
  • get-expr
  • Even Further?
    • A project for further parsing: We will handle parentheses in our calculator language. We'll assume that digits have have already been parsed into numbers. The input is a list of symbols and numbers, organized as follows:

    Input format (before parsing):

    An expression is:
  • term
  • term op expression
    • A term is:
  • number
  • 'open E 'close, where E is an expression.
    • op is one of 'plus, 'minus, 'times, 'divide, 'raise.

    Examples: 

    (define expr2 (list 7 'plus 'open 2 `minus 3 'close))
(define expr3 (list 'open 2 'minus 3 'close 'times 7))
(define expr4 (list 'open 'open 2 'minus 3 'close 'minus 4 'close 'times 7))

    Internal form (after parsing)

    A term is:
  • a number, or
  • (make-inParen E), where E is an expression We therefore are defining one type of structure: 
    (define-structure (inParen expr))
    • An expression is:
  • (cons T (cons op E)), where T is a term, E an expression, and op is one of 'plus, 'minus, 'times, 'divide, 'raise
  • (list T) where T is a term

    • get-expr

    For each type of beast that we need to parse (in this case, terms and expressions), we'll have two functions: one to retrieve the first of that type of thing from the input list, and one to remove such a thing from the front of the input list. Here is the function get-expr: 
    ;; (get-expr in)
;; "in" is an input list of symbols/numbers
;; return the first "expr" in "in"
;;
(define get-expr
  (lambda (in)
    (let ((trm       (get-term in))
	  (leftover (remove-term in)))
      (cond ((or (null? leftover)
		 (not (isOp? (car leftover))))
	     ;; the simple "term" case
	     (list trm))
	    (else
	     ;; term op expr
	     (cons pt (cons (car leftover)
			    (get-expr (cdr leftover)))))))))



(define op-list (list 'plus 'minus 'times 'divide 'raise))
(define isOp?
  (lambda (op)
    (member op op-list)))
    Your can think about writing the remaining functions get-term, remove-term, remove-expr (all of these are a little easier than get-expr).

    Even Further?

    Further work? It is easy to imagine more: For instance, 
    (define unary-ops 'sin 'cos 'tan 'invert 'factorial 'change-sign)
(list 23 'plus 'sin 4 'times 'cos 'invert 'factorial 17 'plus 1)
    where 'cos 'invert 'factorial 17 would be parsed into a single term, which will eventually correspond to (cos (invert (factorial 17))).

    And of course, finally you might want to write a function which takes parsed input, and actually evaluates it (at which point you'll have written your own calculator!)

    Back to Lab 6
    Back to Comp 210 Home