Csc 4330/6330, Programming Language Concepts (Spring 2018)

Homework 1 (Due: 2 February (Friday))

Using ANTLR4 system, write an interpreter for the language of "LISP expressions".

A LISP expression is defined as follows:

1. A number is a LISP expression. (We can assume positive integers)
2. if E1 and E2 are LISP expressions then so are (+ E1 E2), (- E1 E2), (* E1 E2), and (/ E1 E2).
3. if L is a ListExpression (defined below) then (car L) is a LISP expression.

A ListExpression is defined as follows:

1. if E1, E2, ..., En are LISP expressions where n>0 then (E1 E2 ... En) is a ListExpression.
2. if L is a ListExpression then (cdr L) is a ListExpression.

Here are 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)))))

Here is a sample run:

MacBook-Pro:lisp raj$ java LISP
LISP> 34;

The value is 34.0

LISP> (+ 20 30);

The value is 50.0

LISP> (/ 9 (- 2 2));

EVALUATION ERROR: Divide by zero

LISP> (* (+ 1 2) (/ 8 4));

The value is 6.0

LISP> (* (car (2 4 (+ 2 4) 8)) (/ 27 9));

The value is 6.0

LISP> (+ (car (2 3 4)) (car (cdr (cdr (9 8 7 6)))));

The value is 9.0

LISP> (+ 2 3 4);

SYNTAX ERROR

LISP> (* (car 4) 22);
line 1:8 no viable alternative at input '4'

SYNTAX ERROR

LISP> (+ 3 (car (cdr (cdr (cdr (1 2))))));

EVALUATION ERROR: CDRs produce an empty list

LISP> exit;
MacBook-Pro:lisp raj$