next up previous
Next: Exercise 3 Up: The Assignment Previous: Exercise 1

Exercise 2

The goal of this exercise is to write an interpreter for a very small LISP language. The sentences of a LISP language are called S-expressions. We define them in the following informal manner. A LISP interpreter is a sort of desk calculator that processes S-expressions. In our very small LISP language, three operations are possible.
cons.
The syntax is
(cons S1 S2)
where S1 is an S-expression and S2 is a list. The result is a list whose first element is S1 followed by all S-expression's in S2 in the same order.
cdr.
The syntax is
(cdr S1)
where S1 is a list. The result is a list consisting of all S-expression's in S1 except the first one (which is omitted) in the same order as in S1. By convention (cdr ()) returns ().
car.
The syntax is
(car S1)
where S1 is a list. The result is the first S-expression occurring in S1. If S1 the empty list then an error is produced.

Questions.

  1. Write a grammar for this very small LISP language.
  2. Write an interpreter for it.
Here's a session with such a LISP interpreter. The prompt for the input line is ? and the prompt for the output line is =.
? (cons a ())
= (a)
? (cons (a) (b))
= ((a) b)
? (car ((a) b ))
= (a)
? (cdr (a b (c d)))
= (b (c d))
? (car ((a b) (c d)))
= (a b)
? (cdr ((a b) (c d)))
= ((c d))


next up previous
Next: Exercise 3 Up: The Assignment Previous: Exercise 1
Marc Moreno Maza
2004-12-01