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