Click here to Skip to main content
13,142,065 members (56,685 online)
Click here to Skip to main content

Stats

133.5K views
2.1K downloads
97 bookmarked
Posted 14 Apr 2012

How to write a simple interpreter in JavaScript

, 30 Oct 2014
Introduction to the compiling/interpreting process by making a simple calculator application in JavaScript.
var parse = function (tokens) {
	var symbols = {},
	symbol = function (id, nud, lbp, led) {
		var sym = symbols[id] || {};
		symbols[id] = {
			lbp: sym.lbp || lbp,
			nud: sym.nud || nud,
			led: sym.lef || led
		};
	};

	var interpretToken = function (token) {
		var sym = Object.create(symbols[token.type]);
		sym.type = token.type;
		sym.value = token.value;
		return sym;
	};

	var i = 0, token = function () { return interpretToken(tokens[i]); };
	var advance = function () { i++; return token(); };

	var expression = function (rbp) {
		var left, t = token();
		advance();
		if (!t.nud) throw "Unexpected token: " + t.type;
		left = t.nud(t);
		while (rbp < token().lbp) {
			t = token();
			advance();
			if (!t.led) throw "Unexpected token: " + t.type;
			left = t.led(left);
		}
		return left;
	};

	var infix = function (id, lbp, rbp, led) {
		rbp = rbp || lbp;
		symbol(id, null, lbp, led || function (left) {
			return {
				type: id,
				left: left,
				right: expression(rbp)
			};
		});
	},
	prefix = function (id, rbp) {
		symbol(id, function () {
			return {
				type: id,
				right: expression(rbp)
			};
		});
	};


	symbol(",");
	symbol(")");
	symbol("(end)");

	symbol("number", function (number) {
		return number;
	});
	symbol("identifier", function (name) {
		if (token().type === "(") {
			var args = [];
			if (tokens[i + 1].type === ")") advance();
			else {
				do {
					advance();
					args.push(expression(2));
				} while (token().type === ",");
				if (token().type !== ")") throw "Expected closing parenthesis ')'";
			}
			advance();
			return {
				type: "call",
				args: args,
				name: name.value
			};
		}
		return name;
	});

	symbol("(", function () {
		value = expression(2);
		if (token().type !== ")") throw "Expected closing parenthesis ')'";
		advance();
		return value;
	});

	prefix("-", 7);
	infix("^", 6, 5);
	infix("*", 4);
	infix("/", 4);
	infix("%", 4);
	infix("+", 3);
	infix("-", 3);

	infix("=", 1, 2, function (left) {
		if (left.type === "call") {
			for (var i = 0; i < left.args.length; i++) {
				if (left.args[i].type !== "identifier") throw "Invalid argument name";
			}
			return {
				type: "function",
				name: left.name,
				args: left.args,
				value: expression(2)
			};
		} else if (left.type === "identifier") {
			return {
				type: "assign",
				name: left.value,
				value: expression(2)
			};
		}
		else throw "Invalid lvalue";
	});

	var parseTree = [];
	while (token().type !== "(end)") {
		parseTree.push(expression(0));
	}
	return parseTree;
};

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Peter_Olson
United States United States
I am active on Stack Overflow.

You can contact me via email at peter.e.c.olson+codeproject@gmail.com

You may also be interested in...

Pro
Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170915.1 | Last Updated 30 Oct 2014
Article Copyright 2012 by Peter_Olson
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid