howforge.com

The second computer science homework at Codenone is to develop a turtle interpreter. In fact, I don't like to write this kind of code. It has been so long since I wrote ultra mini assembler and compiler both manual and using lex and yacc. However, the ruby version inspired me. The ruby code looks very pretty and the author also convinces about how easy in Python. So I would like to try to solve this homework in Python.

Parsing a language consists of 2 essential parts; lexical analyzer and grammar generator. I'm not sure the best tool but the most well-known should be called lex and yacc, respectively. In other words, we need lex and yacc for parsing specific language. For this article, I chose PLY aka Python Lex-Yacc. Actually, it is an implementation of lex and yacc in pure Python and it is only lex and yacc. Nothing else. Don't expect too much.

Let's start at the lexical analyzer as follow. It must be stored in turtlelex.py.

import ply.lex as lex
 
tokens = (
    'NUMERIC_LITERAL',
    'LITERAL',
    'DRAW_FORWARD','MOVE_FORWARD',
    'ROTATE','SAVE_STATE','RECOVER_STATE',
    'CLOCKWISE','COUNTERCLOCKWISE',
    'REPEAT','END_REPEAT',
    'VAR','MUL','ADD','SUB','DIV',
)
 
keywords = ['DRAW_FORWARD','MOVE_FORWARD',
            'ROTATE','SAVE_STATE','RECOVER_STATE',
            'CLOCKWISE','COUNTERCLOCKWISE',
            'REPEAT','END_REPEAT',
            'VAR','MUL','ADD','SUB','DIV']
 
def t_NUMERIC_LITERAL(t):
    r'[+\-]*\d+'
    try:
        t.value = int(t.value)
    except ValueError:
        print 'Line %d: Number %s is too large!' % (t.lineno,t.value)
        t.value = 0
    return t
 
def t_LITERAL(t):
    r'[a-zA-Z_][a-zA-Z0-9_]*'
    if t.value in keywords:
        t.type = t.value
    return t
 
def t_newline(t):
    r'\n+'
    t.lexer.lineno += len(t.value)
 
t_ignore = r' \t'
 
def t_error(t):
    print 'Illegal chararcter "%s"' % t.value[0]
    t.lexer.skip(1)
 
lexer = lex.lex()

Next is the grammar generator in turtleparse.py.

import ply.yacc as yacc
 
from turtlelex import tokens
from ast import Node
 
start = 'program'
 
def p_program(p):
    '''program : statement_list'''
    p[0] = Node('program',p[1].children)
 
def p_statement_list(p):
    '''statement_list : statement statement_list
                      | empty'''
    if len(p) == 3:
        children = [p[1]]+p[2].children
    else:
        children = []
    p[0] = Node('statement_list',children)
 
def p_empty(p):
    '''empty :'''
    pass
 
def p_statement(p):
    '''statement : turtle_action
                 | repeat_statement
                 | variable_declaration
                 | variable_operation'''
    p[0] = p[1]
 
def p_turtle_action(p):
    '''turtle_action : DRAW_FORWARD argument
                     | MOVE_FORWARD argument
                     | ROTATE direction argument
                     | SAVE_STATE
                     | RECOVER_STATE'''
    p[0] = Node(p[1],p[2:])
 
def p_direction(p):
    '''direction : CLOCKWISE
                 | COUNTERCLOCKWISE'''
    p[0] = p[1]
 
def p_repeat_statement(p):
    '''repeat_statement : REPEAT argument statement_list END_REPEAT'''
    p[0] = Node(p[1],p[2:4])
 
def p_variable_declaration(p):
    '''variable_declaration : VAR identifier argument'''
    p[0] = Node(p[1],p[2:])
 
def p_variable_operation(p):
    '''variable_operation : MUL identifier argument
                          | ADD identifier argument
                          | DIV identifier argument
                          | SUB identifier argument'''
    p[0] = Node(p[1],p[2:])
 
def p_argument(p):
    '''argument : identifier
                | integer'''
    p[0] = p[1]
 
def p_identifier(p):
    '''identifier : LITERAL'''
    p[0] = Node('identifier',[p[1]])
 
def p_integer(p):
    '''integer : NUMERIC_LITERAL'''
    p[0] = Node('integer',[p[1]])
 
def p_error(p):
    if not p:
        return
    print 'Syntax error at token %s "%s" at line %d' % (p.type,p.value,p.lineno)
 
parser = yacc.yacc()

Actually, the grammar generator should handle each rule by itself. However, in this case, we are going to develop an interpreter so the given code should be parsed and stored in an easy access form, e.g., Abstract Syntax Tree or AST. The problem is there is no AST in PLY so I have to write it myself. Below code must be stored in ast.py.

class Node:
    def __init__(self,operator,children=[]):
        self.operator = operator
        self.children = children
 
    def __repr__(self):
        return '<%s %s>' % (self.operator,self.children)
 
class Evaluator:
    def evaluate(self,node):
        method = getattr(self,'do_%s' % node.operator,None)
        ret = 0
        if not method:
            print 'unknown',node.operator
        else:
            ret = method(*node.children)
        return ret

So now I'm ready to write the interpreter as follow.

#!/usr/bin/env python
 
import math
from Tkinter import *
 
from turtlelex import lexer
from turtleparse import parser
from ast import Evaluator
 
class TurtleEvaluator(Evaluator):
    def __init__(self,callback,state=None):
        self.vars = {}
        self.state = state or State()
        self.states = []
        self.callback = callback
 
    def do_statement_list(self,*stms):
        for stm in stms:
            self.evaluate(stm)
 
    do_program = do_statement_list
 
    def do_integer(self,n):
        return n
 
    def do_DRAW_FORWARD(self,n):
        n = self.evaluate(n)
        line = self.state.forward(n)
        self.callback(*line)
 
    def do_MOVE_FORWARD(self,n):
        n = self.evaluate(n)
        line = self.state.forward(n)
 
    def do_ROTATE(self,dir,angle):
        angle = self.evaluate(angle)
        self.state.rotate(dir,angle)
 
    def do_SAVE_STATE(self):
        self.states.append(self.state.copy())
 
    def do_RECOVER_STATE(self):
        self.state = self.states.pop()
 
    def do_REPEAT(self,count,stm):
        count = self.evaluate(count)
        for i in range(count):
            self.evaluate(stm)
 
    def do_VAR(self,name,n):
        name = name.children[0]
        n = self.evaluate(n)
        self.vars[name] = n
 
    def do_identifier(self,name):
        return self.vars.get(name,0)
 
    def do_ADD(self,name,n):
        name = name.children[0]
        n = self.evaluate(n)
        self.vars[name] = self.vars.get(name,0)+n
 
    def do_MUL(self,name,n):
        name = name.children[0]
        n = self.evaluate(n)
        self.vars[name] = self.vars.get(name,0)*n
 
    def do_SUB(self,name,n):
        name = name.children[0]
        n = self.evaluate(n)
        self.vars[name] = self.vars.get(name,0)-n
 
    def do_DIV(self,name,n):
        name = name.children[0]
        n = self.evaluate(n)
        self.vars[name] = self.vars.get(name,0)/n
 
class State:
    def __init__(self,x=150,y=300,angle=1.0):
        self.x = x
        self.y = y
        self.angle = angle
 
    def copy(self):
        return State(self.x,self.y,self.angle)
 
    def forward(self,value):
        oldx,oldy = self.x,self.y
        radian = math.pi*self.angle
        self.x += value*math.sin(radian)
        self.y += value*math.cos(radian)
        return oldx,oldy,self.x,self.y
 
    def rotate(self,dir,angle):
        if dir == 'CLOCKWISE':
            self.angle -= angle/180.0
        else:
            self.angle += angle/180.0
 
class TurtleInterpreter:
    def __init__(self,parent):
        self.parse_args()
        self.init(parent)
 
    def parse_args(self):
        import sys
        self.infile = sys.argv[1]
        self.width = 300
        self.height = 300
 
    def init(self,parent):
        self.frame = Frame(parent)
        self.frame.pack()
 
        self.canvas = Canvas(self.frame,width=self.width,height=self.height)
        self.canvas.pack(side=TOP)
 
    def run(self):
        input = open(self.infile).read()
        result = parser.parse(input,lexer=lexer)
        ev = TurtleEvaluator(self.add_line,state=State(self.width/2,self.height))
        ev.evaluate(result)
 
    def add_line(self,x0,y0,x1,y1):
        p = self.canvas.create_line(x0,y0,x1,y1)
        self.frame.update()
 
if __name__ == '__main__':
    root = Tk()
    app = TurtleInterpreter(root)
    app.run()
    root.mainloop()

I have 3 input files to test its functionality.

VAR step 20
MOVE_FORWARD 150
REPEAT 12
    DRAW_FORWARD step
    ROTATE COUNTERCLOCKWISE 90
    DRAW_FORWARD step
    ROTATE COUNTERCLOCKWISE 90
    ADD step 20
END_REPEAT

MOVE_FORWARD 250
ROTATE CLOCKWISE 198
REPEAT 5 DRAW_FORWARD 200 ROTATE COUNTERCLOCKWISE 144 END_REPEAT

MOVE_FORWARD 150
A

Seriously, I like the Ruby version more than my Python version.

Tags: python, lex, yacc, ply, turtle interpreter