Csc 4330/6330, Programming Language Concepts (Summer 2020)
Data structure returned by parser
Here is a proposed data structure to hold the LISP and LISP expressions. It is strongly recommended that you use this. We shall use recursive lists as illustrated with examples below:
LISP Expression | Python List |
---|---|
34 | ['num',34] |
x | ['var','x'] |
(+ (* 2 x) 9) | ['+',['*',['num',2],['var','x']],['num',9]] |
(car (2 3)) | ['car', [['num', 2.0], [['num', 3.0], []]]] |
(let ((x 2)(y 4)) (+ x y)) | ['let', [['x', ['num', 2.0]], ['y', ['num', 4.0]]], ['+', ['var', 'x'], ['var', 'y']]] |
LIST Expression | Python List |
---|---|
(1 2 x 4) | [['num', 1.0], [['num', 2.0], [['var', 'x'], [['num', 4.0], []]]]] |
(2 4 (+ 2 4) 8) | [['num', 2.0], [['num', 4.0], [['+', ['num', 2.0], ['num', 4.0]], [['num', 8.0], []]]]] |
(1 (car (2 3)) 4) | [['num', 1.0], [['car', [['num', 2.0], [['num', 3.0], []]]], [['num', 4.0], []]]] |
(cdr (10 20 30)) | ['cdr', [['num', 10.0], [['num', 20.0], [['num', 30.0], []]]]] |
(cons 2 (cdr (10 20 30))) | [['num', 2.0], ['cdr', [['num', 10.0], [['num', 20.0], [['num', 30.0], []]]]]] |
The data structure for a LIST expression is not the standard Python list we are used to. We use a structure borrowed from the implementation of functional programming languages such as LISP that stores the first item (referred to as the car) and a list of remaining items (referred to as cdr) in a Python list in a recursive manner as shown in the examples above. Also note that we go ahead and execute the "cons" operation while constructing the data structure itself.