Csc 4330/6330, Programming Language Concepts (Summer 2020)

Project 1 (Due: 10 July (Friday); Late submission: 15 July (Wednesday))

sudo handin4330 p1 Lisp.py LispLexer.py LispParser.py README

Using Python PLY write an interpreter for the language of "LISP expressions".

A LISP expression is defined as follows:

  1. A number is a LISP expression.
  2. A variable is a LISP expression.
  3. if E1 and E2 are LISP expressions then (+ E1 E2), (- E1 E2), (* E1 E2), and (/ E1 E2) are LISP expressions.
  4. if L is a LIST expression then (car L) is a LISP expression. Intuitively, car returns the first element of the list L.
  5. if x1, ..., xn are variables and E1, ..., En are LISP expressions then (let ((x1 E1) (x2 E2) ... (xn En)) E) is a LISP expression. An intuitive meaning of let-expressions is that they provide values for variables which are then substituted in the LISP expression, E, before it is evaluated.

A LIST expression is defined as follows:

  1. if E1, E2, ..., En are LISP expressions where n>=0 then (E1 E2 ... En) is a LIST expression.
  2. if L is a LIST expression then (cdr L) is a LIST expression. Intuitively, cdr drops the first element of the list L and returns the resulting list.
  3. if E is a LISP expression and L is a LIST expression then (cons E L) is a LIST expression. The cons operator adds one new element in the front of a given list.

Examples of valid LISP expressions:

34
(+ 20 30)
(* (+ 1 2) (/ 8 4))
(* (car (2 4 (+ 2 4) 8)) (/ 27 9))
(+ (car (2 3 4)) (car (cdr (cdr (9 8 7 6)))))
(+ x 4)
(car (2 3 x y))
(let ((x 10) (y (+ 25 (car (20 30)))) (z (+ 10 23)))  (+ x (car (y 20 z))) )
(let ((x 2)(y 4)) (+ x y))
(let ((x 10) (y (+ 25 (car (20 30)))) (z (+ 10 23)))  (+ x (car (y 20 z))) )
(car (cons 2 (cdr (10 20 30))))

Examples of valid LIST expressions:

(10 20 30)
()
(cdr (1 2 3 4))
(cdr (cdr (cons 10 (20 30 (let ((x 2)(y 4)) (+ x y))))))
(cons 24 (30 (+ 20 20) 50))
(cons (+ 3 4) ((+ 1 2) (* 1 2) (/20 2)))
(cons 2 (cdr (10 20 30)))

Here is a sample run.

Data Structure for expressions

Evaluating Let-expressions

Error reporting

Submit the following files: Lisp.py, LispLexer.py, LispParser.py, and README under assignment p1