Wednesday, June 09, 2010

Let's make a shit JavaScript interpreter! Part one.

Let's make a shit javascript interpreter! Part one.

As a learning exercise, I've begun writing a javascript ECMAScript interpreter in python. It doesn't even really exist yet, and when it does it will run really slowly, and not support all js features.

So... let's make a "from scratch", all parsing, all dancing, shit interpreter of our very own!

Teaching something is a great way to learn. Also writing things on my blog always gets good 'comments', hints, tips, plenty of heart, and outright HATE from people. All useful and entertaining :)


So to start with, we need something to turn the .js files into a list of tokens. This type of program is called a tokeniser.

From some javascript like this:
function i_can_has_cheezbrgr () {return 'yum';};
Into a Token list something like this:
Wikipedia has a page on Parsing (also see List_of_unusual_articles for some other background information).

"Tokenization is the process of demarcating and possibly classifying sections of a string of input characters. The resulting tokens are then passed on to some other form of processing. The process can be considered a sub-task of parsing input." -- wikipedia Lexical_analysis#Token page.

We can has vegetarian cheeseburger... but how can we parse javascript?

To the rescue, comes uncle Crockford the javascript guru of jslint fame. He wrote this lovely article: The ideas come from a 1973 paper called "Top Down Operator Precedence". The Crockford article is great, since it is free, short, and well written javascript. Unlike the 1973 paper it gets the ideas from... which is behind a paywall, long, and uses a 1973 language called "(l,(i,(s,(p))))".

As well as being short and simple... Phil Hassey used "Top Down Operator Precedence" and this article on his journey making tinypy.

Goat driven development

Just as Phil did with tinypy, I'm going to use Goat Driven Development. Well, I'm not even sure what Goat Driven Development is... so maybe not.

Another python using dude, Fredrik Lundh, wrote some articles on "Simple Top-Down Parsing in Python" and Top-Down Operator Precedence Parsing.

Also see Eli Bendersky's article on Top Down Operator Precedence.

So where to begin?

After reading those articles a few times... scratching my head 13 times, making 27 hums, a few haaarrrrs, one hrmmmm, and four lalalas...

light bulb: A brilliant plan!

Eli Bendersky implements a full tokeniser, and parser for simple expressions like "1 + 2 * 4".

Let's copy this approach, but simplify it even more. Our first step is to make a tokeniser for a such an expression. That should be easy right?

A Token data structure.

Uncle Doug Crockford uses this structure for a token.

// Produce an array of simple token objects from a string.
// A simple token object contains these members:
// type: 'name', 'string', 'number', 'operator'
// value: string or number value of the token
// from: index of first character of the token
// to: index of the last character + 1

Here's an example token from above:


Writing the tokeniser

Often a tokeniser is generated... or written by hand.

Fredrik Lundh writes a simple tokeniser using a regular expression.

>>> import re
>>> program = "1 + 2"
>>> [(number, operator) for number, operator in
... re.compile("\s*(?:(\d+)|(.))").findall(program)]
[('1', ''), ('', '+'), ('2', '')]

This is a valid approach... but regexen blow up minds. Instead I'm going to write one using a state machine, in a big while loop with lots of ifs and elses.

Our homework

Write a tokeniser for simple expressions like "1 + 2 * 4". Output a list of tokens like the javascript one does... eg.


Until next time...

Really, I have no idea what I'm doing... but that's never stopped me before! It's going to be a shit javascript, but it will be our shit javascript.

Sunday, June 06, 2010

My javascript reading list over the last few months

Over the last few months I've been fairly deep into javascript land. Both in my full time job, and in most of my coding side projects - I've been mostly doing javascript. Of course, like most web programmers I've been dabbling in javascript over the years... but never so intensely. On the way I've been collecting a 'reading list' of videos, articles, books, and projects.

Here are some of the good links from the last few months.

Crockford on javascript videos:!+User+Interface+Blog%29

akihabara arcade:

canvas javascript games:

javascript 3d engine:

Aves Engine: HTML/JavaScript Game Engine (

css animations and transitions

3d video navigation on iphone

apple web app documentation

apple visual effects guide

apple multi touch events

android, and APIs

Safari on iPhone Graphics, Media, and Visual Effects Coding How-To's:

Preparing Your Web Content for iPad:


javascript collision detection

box2d physics javascript:

render engine javascript game engine

vector maths library

wii javascript

game js, pygame alike.


how to detect html5 things:

javascript audio synth

audio with js:
- best one.

using flash from js for sound

cross browser css image rotation

open source iphone game:


a number of interesting projects

image editor

chrome web development extensions

html5 ipad app