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.
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
Advantages of tree-based interperter over syntax-directed one:
- 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.
- More flexible because of AST as an intermediate representation.
Short language reference
- statements: print, return, if, while, and function call
- literals: integers and strings
- operators: <, ==, +, -, *
- Expressions may contain identifiers.
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)