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 :)

Tokenising

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:
[
{"type":"name",
"value":"function",
"from":0,
"to":8},
{"type":"name",
"value":"i_can_has_cheezbrgr",
"from":9,
"to":28},
{"type":"operator",
"value":"(",
"from":29,
"to":30},
{"type":"operator",
"value":")",
"from":30,
"to":31},
{"type":"operator",
"value":"{",
"from":32,
"to":33},
{"type":"name",
"value":"return",
"from":33,
"to":39},
{"type":"string",
"value":"yum",
"from":40,
"to":45},
{"type":"operator",
"value":";",
"from":45,
"to":46},
{"type":"operator",
"value":"}",
"from":46,
"to":47},
{"type":"operator",
"value":";",
"from":47,
"to":48}
]
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: http://javascript.crockford.com/tdop/tdop.html. 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:

{"type":"name",
"value":"i_can_has_cheezbrgr",
"from":9,
"to":28}



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.

{"type":"name",
"value":"i_can_has_cheezbrgr",
"from":9,
"to":28}


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:
http://www.yuiblog.com/blog/2010/04/08/video-crockonjs-5/?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+YahooUserInterfaceBlog+%28Yahoo!+User+Interface+Blog%29

akihabara arcade:
http://www.kesiev.com/akihabara/

canvas javascript games:
http://www.benjoffe.com/code/

javascript 3d engine:
http://github.com/mrdoob/three.js

Aves Engine: HTML/JavaScript Game Engine (youtube.com)
http://www.youtube.com/watch?v=Ol3qQ4CEUTo
http://ajaxian.com/archives/aves-game-engine?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+ajaxian+%28Ajaxian+Blog%29

css animations and transitions
http://webkit.org/blog/130/css-transforms/
http://webkit.org/blog/138/css-animation/

3d video navigation on iphone
http://ajaxian.com/archives/iads

apple web app documentation
http://developer.apple.com/safari/library/referencelibrary/GettingStarted/GS_iPhoneWebApp/index.html#//apple_ref/doc/uid/TP40008134
http://developer.apple.com/safari/library/samplecode/FingerTips/Introduction/Intro.html

apple visual effects guide
http://developer.apple.com/safari/library/documentation/InternetWeb/Conceptual/SafariVisualEffectsProgGuide/Introduction/Introduction.html#//apple_ref/doc/uid/TP40008032

apple multi touch events
http://developer.apple.com/safari/library/documentation/AppleApplications/Reference/SafariWebContent/HandlingEvents/HandlingEvents.html#//apple_ref/doc/uid/TP40006511-SW22

android, and APIs
http://www.thesearethedroids.com/2009/12/15/creating-android-apps-with-html-css-and-javascript/
http://www.phonegap.com/
http://developer.android.com/resources/articles/using-webviews.html

Safari on iPhone Graphics, Media, and Visual Effects Coding How-To's:
http://developer.apple.com/safari/library/codinghowtos/Mobile/GraphicsMediaAndVisualEffects/index.html

Preparing Your Web Content for iPad:
http://developer.apple.com/safari/library/technotes/tn2010/tn2262.html

gamequery
http://gamequery.onaluf.org/

javascript collision detection
http://www.lukewallin.co.uk/?go=engine

box2d physics javascript:
http://box2d-js.sourceforge.net/index2.html

render engine javascript game engine
http://www.renderengine.com/

vector maths library
http://sylvester.jcoglan.com/

wii javascript
http://en.wikipedia.org/wiki/Wii_Opera_SDK

game js, pygame alike.
http://code.google.com/p/gamejs/

physics:
http://www.queness.com/post/3296/8-amazing-javascript-experiments-of-physic-and-gravity-simulation

how to detect html5 things:
http://diveintohtml5.org/everything.html

javascript audio synth
http://acko.net/blog/javascript-audio-synthesis-with-html-5

audio with js:
http://www.phon.ucl.ac.uk/home/mark/audio/play.htm
- best one.
http://www.javascripter.net/faq/sound/play.htm
http://simplythebest.net/sounds/sound_guide.html

using flash from js for sound
http://www.schillmania.com/content/projects/soundmanager2/

cross browser css image rotation
http://samuli.hakoniemi.net/cross-browser-rotation-transformation-with-css/
http://snook.ca/archives/html_and_css/css-text-rotation

open source iphone game:
http://ajaxian.com/archives/golingo-a-great-titanium-mobile-web-game-open-sourced-for-you?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+ajaxian+%28Ajaxian+Blog%29

jsdom.
http://github.com/tmpvar/jsdom
http://www.yuiblog.com/blog/2010/05/20/video-insua/?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+YahooUserInterfaceBlog+%28Yahoo!+User+Interface+Blog%29

a number of interesting projects
http://www.bramstein.com/projects/

image editor
http://pixlr.com/

chrome web development extensions
https://chrome.google.com/extensions/featured/web_dev

html5 ipad app
http://mir.aculo.us/2010/06/04/making-an-ipad-html5-app-making-it-really-fast/

particles
http://spielzeugz.de/html5/liquid-particles.html