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.
• An S-expression is either an atom or a list.
• A list
• starts with an opening parenthesis,
• then continues with zero, one or more S-expression's separated by one or more blank characters,
• and ends with a closing parenthesis.
• An atom is either a signed integer, or a unsigned integer or a symbol
• A symbol is an identifier or a keyword
• A keyword is one of the words car, cons, cdr and may only appear just after an opening parenthesis (possibly followed by white space).
• An identifier is a word over the alphanumeric characters different from the keyword's and that starts with an alphabetic character.
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: Exercise 3 Up: The Assignment Previous: Exercise 1
Marc Moreno Maza
2004-12-01