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 READMEUsing Python PLY write an interpreter for the language of "LISP expressions".
A LISP expression is defined as follows:
- A number is a LISP expression.
- A variable is a LISP expression.
- if E1 and E2 are LISP expressions then (+ E1 E2), (- E1 E2), (* E1 E2), and (/ E1 E2) are LISP expressions.
- if L is a LIST expression then (car L) is a LISP expression. Intuitively, car returns the first element of the list L.
- 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:
- if E1, E2, ..., En are LISP expressions where n>=0 then (E1 E2 ... En) is a LIST expression.
- 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.
- 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
Submit the following files: Lisp.py, LispLexer.py, LispParser.py, and README under assignment p1