Skip to content

Latest commit

 

History

History
65 lines (49 loc) · 2.54 KB

1.md

File metadata and controls

65 lines (49 loc) · 2.54 KB
Raw

Part 1: parsing

The language we are making is an interpreted one. This means that we basically need to implement two things: a parser and an evaluator. In this first part, we implement the parser.

The job of the parser is to convert the program into something the evaluator understands. The evaluator evaluates whatever the parser produces, and returns the result. Here is a nice diagram to explain everything:


            +-----------+        +-------------+
    text    |           |  AST   |             |  result
  +-------->|  parser   |+------>|  evaluator  |+-------->
            |           |        |             |
            +-----------+        +-------------+

The format produced by the parser is called the abstract syntax tree (AST) of the program.

Our AST

So what do our AST look like? Lets have a sneak peek.

>>> from diylisp.parser import parse
>>> program = """
...   (define fact 
...       ;; Factorial function
...       (lambda (n) 
...           (if (eq n 0) 
...               1 ; Factorial of 0 is 1, and we deny 
...                 ; the existence of negative numbers
...               (* n (fact (- n 1))))))
... """))
>>> parse(program)
['define', 'fact', ['lambda', ['n'], ['if', ['eq', 'n', 0], 1, ['*', 'n', ['fact', ['-', 'n', 1]]]]]]

The AST, then, is created as follows:

  • Comments are removed.
  • Symbols are represented as strings.
    • "foo" parses to "foo"
  • The symbols #t and #f are represented by Python's True and False, respectively.
    • "#t" parses to True
  • Integers are represented as Python integers.
    • "42" parses to 42
  • The Lisp list expressions are represented as Python lists. "(foo #f 100)" parses to ["foo", False, 100]
  • Nested expressions are parsed accordingly.
    • "((+ (- 1 2) (* (- 4 1) 42)))" parses to [['+', ['-', 1, 2], ['*', ['-', 4, 1], 42]]]

Your turn

The parsing is done in parser.py. It is your job to implement the parse function here. A lot of the gritty work of counting parentheses and such has been done for you, but you must stitch everything together.

  • Have a look at the provided functions in diylisp/parser.py before you start. These should prove useful.

  • The following command run the tests, stopping at the first one failed.

    nosetests tests/test_1_parsing.py --stop

  • Run the tests and hack away until the tests are passing. Each test has a description, and you should probably read it if you get stuck.

What's next?

Go to part 2 where we evaluate some simple expressions.