js 四则运算解释器

流程

词法分析

这里不讲那么复杂的正则表达式、DFA和NFA（后面的blog再介绍）,或者各种证明啥的.
毕竟我们只需要写一个四则运算的解析器
我们的要写的东西，会不断地匹配输入的每一个字符流
而我们输入的字符流类型分为几种: '+', '-', '*', '/'和数字
将其转化为token流，由于js动态语言的灵活和我们程序很简单
我们只需要用变量token就可以存下来字符流的信息，无需为token定义一个复杂的类
详见next()函数中，对每一个类型的取值　　

语法分析

BNF范式

先讲一下，BNF范式

BNF是描述编程语言的文法。自然语言存在不同程度的二义性。
这种模糊、不确定的方式无法精确定义一门程序设计语言，必须设计一种准确无误地描述程序设计语言的语法结构，这种严谨、简洁、易读的形式规则描述的语言结构模型称为文法
比方说，具体看一下BNF对应的一些产生式

左侧都是些非终止符，右侧可以是终止符（对应词法里面的符号流）和非终止符的结合 例如上叙非终止符B是由"y"字符构成的，C由两种方式中的一种构成

那么一个上下文无关法可以包括
1. 一个终止符号集合
2. 一个非终止符号集合
3. 一个产生式集合
4. 一个非终止符为开始符号

注意，产生式左侧一定是非终止符号，否则就不一定是上下文无关文法

递归下降法

什么是自上而下 什么是自下而上 我按我的理解画了两幅图(当然理解，不一定是正确的)

那么我们的四则运算的产生式是啥，下面我用EBNF范式写个基本的

细心的人会发现，加减与乘除的运算优先级没有直接区别，所以改成

LL(1)

我们的文法每一次匹配的时候，实际都向看了一下，LL(1)，比方说上面的式１
当存在前面的字符串已经合成A之后，怎么是用前一个方式产生C，还是后一种
只要我们提前看了A后面的字符是"+"还是"x"就知道了

左递归

上面的产生式，在实际代码中是有问题的 形如\(A = A\alpha|\beta\)，我们把它称为左递归(当然还有隐式的)
这个exp，会不停的递归下去，因为它还来不及向前看，就被右边的第一个exp匹配走了
解决方案

想了好久用数字严格证明，但是脑子不够用
这里说一下思想吧，其实可以知道 \(A\) 的右边不断出现\(\alpha\)，直到\(A\)本身是\(\beta\)
那么其实\(A\)的展开正则表达式是\(/\beta\alpha*/\)
再观察随后的两个式子，\( A^{'}\)本质上就是\(\alpha* \)，但是它是个右递归

那么原先整个产生式，就变成了

括号

支持括号，那么表达式继续改变

exp       =  exp_tail  
exp_tail  =  "+" term exp_tail |  
             "-" term exp_tail |
             ϵ
term      =  term_tail  
term_tail =  "*" factor term_tail |  
             "/" factor term_tail |
             ϵ
factor    =  number, {number} | "(" exp ")"  
number    =  "0" | "1" | "2" | "3" | "4" |  
             "5" | "6" | "7" | "8" | "9"

源代码

//arithmetic.js
"use strict";

let process = require("process");

let token = null;  
let para = null;  
let len = null;  
let p = 0;

function expr() {  
    let value = term();
    let res = expr_tail(value);
    return res;
}

function expr_tail(lvalue) {  
    if('+' == token) {
        match('+');
        return expr_tail(lvalue + term());
    } else if('-' == token) {
        match('-');
        return expr_tail(lvalue - term());
    } else {
        return lvalue;
    }
} 

function term() {  
    return term_tail(factor());
}

function term_tail(value) {  
    if('*' == token) {
        match('*');
        return term_tail(value * factor());
    } else if('/' == token){
        match('/');
        return term_tail(value / factor());
    } else {
        return value;
    }
}

function factor() {  
    if('(' == token) {
        match('(');
        let lvalue = expr();
        match(')');
        return lvalue;
    } else if("number" == typeof token) {
        let lvalue = token;
        match(token);
        return lvalue;
    } else {
        console.log("\n\texpect token is number or '(', but get the token is ", token, '\n');
        process.exit();
    }
}


function next() {  
    if(p >= len) {
        token = null;
        return ;
    }
    let cur_token = para[p++];
    if(cur_token >= '0' && cur_token <= '9') {
        let num = 0;
        while(cur_token >= '0' && cur_token <= '9') {
            num = num * 10 + parseInt(cur_token);
            cur_token = para[p];
            p++;
        }
        p--;
        token = num;
        return ;
    } else if(cur_token == '+') {
        token = '+';
        return ;
    } else if(cur_token == '-') {
        token = '-';
        return ;
    } else if(cur_token == '*') {
        token = '*';
        return ;
    } else if(cur_token == '/') {
        token = '/';
        return ;
    } else if(cur_token == '(') {
        token = '(';
        return ;
    } else if(cur_token == ')') {
        token = ')';
        return ;
    } else {
        console.log("\n\tunknow token !!! ", cur_token, '\n');
        process.exit();
    }
}

function match(tk) {  
    if(tk != token) {
        console.log("\n\terror match the token !!!\n", tk, '\n');
        process.exit();
    }
    next();
}

//get the parameter
para = process.argv.splice(2)[0];  
if("undefined" == typeof para) {  
    console.log("\n\tplease input the express !!!!\n");
    process.exit();
}

len = para.length;  
p = 0;  
next();  
console.log(expr());  

match是每次匹配消耗一个符号，para是输入的字符串，p是指向下一个字符的位置，token代表当前的字符
例如：1 + 2 * 3
当匹配到数字2的时候，即token等于2；而p是*的位置，即para[p]等于*
match消耗掉一个标记流，那么token等于*，p自增1，指向para中3的位置，此时para[p]等于3

$ node test.js 1+4/4
3

//bash里面需要对"("和")"转义，即\(和\)
$ node test.js 2*\(5+6\)
22  

后续

使用jshint检查

npm install -g jshint  
jshint --config ./jshintrc ./main.js

//其中.jshintrc如下
//{
//    "esversion" : 6,
//    "node" : true
//}

测试

mocha大法好

//./test/test.js
"use strict"

let co = require('co');  
let mocha  = require('mocha');  
let expect = require('chai').expect;

function getResultIfInputExpress(str) {  
    let exec = require('child_process').exec;
    let ctr = exec("node  ./test.js " + str);

    return function(cb) {
        ctr.stdout.on('data', (data) => {
            cb(null, data.replace(/(^\s*)|(\s*$)/g,''));
        });

        ctr.stderr.on('data', (data) => {
            cb(new Error(data));
        });
    }
}

describe("test [main.js]", () => {  
    it("if input is right", (done) => {
        co( function *() {
            let res = null;
            res = yield getResultIfInputExpress('1+2');
            expect(res).to.equal('3');

            res = yield getResultIfInputExpress('1+2*3');
            expect(res).to.equal('7');

            res = yield getResultIfInputExpress('9*\\(1+3\\)');
            expect(res).to.equal('36');

            done();
        }).catch( (err) => {
            done(err);
        });
    });


    it("if input is wrong", (done) => {
        co( function *() {
            let res = null;
            res = yield getResultIfInputExpress('1+2*');
            expect((res.indexOf("expect token is number or '(', but get the token is") >= 0)).to.be.true;

            res = yield getResultIfInputExpress('o+2');
            expect((res.indexOf("unknow token !!") >= 0)).to.be.true;

            res = yield getResultIfInputExpress('');
            expect((res.indexOf("please input the express") >= 0)).to.be.true;

            done();
        }).catch( (err) => {
            done(err);
        });
    });
});

//package.json
{
  "name": "arithmetic",
  "version": "1.0.0",
  "description": "",
  "scripts": {
    "test": "node ./node_modules/mocha/bin/mocha",
    "start": "node ./test/test.js"
  },
  "author": "chainhelen",
  "license": "MIT",
  "devDependencies": {
    "chai": "^3.5.0",
    "co": "^4.6.0",
    "mocha": "^3.1.2"
  },
}

未经授权，禁止转载
作者：chainhelen
本文原地址 http://blog.hacking.pub/2016/11/23/js-si-ze-yun-suan-jie-shi-qi/