parser.js

var tokenRules = [
	['number', /^\d+/],
	['space', /^ +/],
	'+', '-', '*', '/'
]

var str = '1 + 2 * 3 + 33 / 3'

function lex(str, tokenRules) {
	var tokens = []
	var tmp
	while (str) {
		for (var i = 0, a; a = tokenRules[i]; i++) {
			if (typeof a == 'string' && str.substr(0, a.length) == a) {
				// 字符串
				tokens.push([a, a])
				str = str.substr(a.length)
			}
			else if (a[1] && a[1].exec) {
				// 正则
				if (tmp = a[1].exec(str)) {
					if (a[0] != 'space') tokens.push([a[0], tmp[0]])
					str = str.substr(tmp[0].length)
				}
			}
		}
	}
	return tokens
}

var grammarRules = [
	['number1', ['number * number', 'number / number'], function(a, op, b) {
		return op == '*' ? a * b : a / b
	}],
	['number2', ['number + number', 'number - number'], function(a, op, b) {
		return op == '-' ? a - b : +a + +b // fuck str...
	}],
	['number', ['number1', 'number2']]
]

function parser(tokens, grammarRules) {
	var stack = []
	var bnf = grammarRules.map(function(rule) {
		return rule[1].join('  ')
	})
	//console.log(bnf)
	while (tokens.length) {
		stack.push(tokens.shift())
		tryMatch()
	}	

	function tryMatch() {
		for (var i = 0, a; a = grammarRules[i]; i++) {
			// a[1] = ['number * number', 'number / number']
			for (var j = 0, b; b = a[1][j]; j++) {
				var len = b.split(' ').length
				if (stack.length >= len) {
					// 要足够匹配, 从后面开始匹配, 取出stack后面len个
					var tests = stack.slice(stack.length - len)
					var str = tests.map(function(a) {
						return a[0]
					}).join(' ')
					//console.log(str)
					if (str == b) {
						// 匹配成功
						// 判断优先级
						var lookahead = getLookahead(stack[stack.length - 1][0])
						// i是规约的等级
						var reduceLevel
						if (tokens.length && lookahead.length) {
							// 如果可能移近的话
							for (var k = 0, c; c = lookahead[k]; k++) {
								if (c[0] == tokens[0][0]) {
									reduceLevel = c[1]
								}
							}
						}
						//console.log(reduceLevel, i)
						if (reduceLevel !== undefined && reduceLevel < i) {
							// 应该移近							
							stack.push(tokens.shift())
						} else {
							// 规约
							var fn = a[2] || function(a) {return a} // 没有就是返回自己
							var q = tests.map(function(a) {
								return a[1]
							})
							var val = fn.apply(null, q)
							console.log(q, val) // 显示结果
							var newToken = [a[0], val]
							stack.splice(stack.length - len, len, newToken)
							tryMatch() // try again when we reduce
							//console.log(newToken)
						}
					}
				}
			}
		}		
	}



	function getLookahead(x) {
		var reg = new RegExp(x + ' (\\S+)', 'g')
		var lookahead = [], ret
		for (var i = 0; i < bnf.length; i++) {
			while (ret = reg.exec(bnf[i])) {
				lookahead.push([ret[1], i])
			}
		}
		return lookahead
	}

}

var tokens = lex(str, tokenRules)
parser(tokens, grammarRules)

这个是想干什么，还引入编译原理