Tree-Based Interpreter for TinyPie language

I’ve been working recently on a tree-based interpreter for a very simple Python-like programming language called TinyPie.
In contrast to Syntax-Directed Intrepreter this one executes source code by constructing Abstract Syntax Tree from homogeneous nodes and walking the tree.

The language is based on Pie language from Language Implementation Patterns Ch.9

To install the interpreter use either pip install (alternatively you can run $ sudo easy_install tinypie)

$ sudo pip install tinypie
$ tinypie factorial.tp

or clone Git repo and run buildout:

$ git clone git://github.com/rspivak/tinypie.git
$ cd tinypie
$ python bootstrap.py 
$ bin/buildout 
$ bin/tinypie factorial.tp

Main interpreter features:

• Implemented in Python
• Regexp-based lexer
• LL(k) recursive-descent parser
• Parser constructs homogeneous Abstract Syntax Tree (AST)
• Static / lexical scope support.
• Interpreter builds complete scope tree during AST construction.
• Interpeter manages global memory space and function space stack
• Implements external AST visitor
• Forward references support

High-level overview:

Advantages of tree-based interperter over syntax-directed one:

1. Symbol definition and symbol resolution happen at different stages:
   • symbol definition is performed during parsing
   • symbol resolution is performed during interpretation

   This allows forward references and simplifies implementation – parser deals with scope tree only and interpreter deals with memory spaces.

2. More flexible because of AST as an intermediate representation.

Language grammar

Short language reference

• statements: print, return, if, while, and function call
• literals: integers and strings
• operators: <, ==, +, -, *
• Expressions may contain identifiers.

Code examples

1. Factorial

    print factorial(6)               # forward reference

    def factorial(x):                # function definition
        if x < 2 return 1            # if statement
        return x * factorial(x - 1)  # return statement
    .                                # DOT marks the block end

2. WHILE loop

    index = 0

    while index < 10:
        print index
        index = index + 1
    .                                # DOT marks the block end

3. IF ELSE

    x = 10
    if x == 10 print 'Yes'
    else print 'No'

4. Variable lookup in different scopes

    x = 1        # global variable
    def foo(x):  # 'foo' is defined in global memory space
        print x  # prints 3 (parameter value)
    .            # DOT marks the block end
    def bar():   # 'bar' is defined in global memory space
        x = 7    # modify global variable
    .            # DOT marks the block end

    foo(3)       # prints 3
    bar()
    print x      # prints 7 ('bar' modified global variable)