> ## Content Index
> Fetch the complete content index at: https://blog.hacking.pub/llms.txt
> Use this file to discover other available public pages before exploring further.

# js 四则运算解释器
- URL: https://blog.hacking.pub/2016/11/23/js-si-ze-yun-suan-jie-shi-qi/
- Published: 2016-11-23T08:57:13.000Z
- Updated: 2020-07-11T11:47:02.000Z
- Author: chainhelen
- Tags: js, 四则运算, 编译原理, 解释器, 编译器

#### 流程

![compiler](https://blog.hacking.pub/qiniu/js_compiler/js_compiler.png)

#### 词法分析

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

#### 语法分析

###### BNF范式

先讲一下，BNF范式

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

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

那么一个上下文无关法可以包括

1. 一个终止符号集合
2. 一个非终止符号集合
3. 一个产生式集合
4. 一个非终止符为开始符号

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

##### 递归下降法

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

那么我们的四则运算的产生式是啥，下面我用EBNF范式写个基本的  
![js_sizeyunsuan4.png](https://blog.hacking.pub/qiniu/js_sizeyunsuan/js_sizeyunsuan4.png)  
细心的人会发现，加减与乘除的运算优先级没有直接区别，所以改成  
![js_sizeyunsuan4.png](https://blog.hacking.pub/qiniu/js_sizeyunsuan/js_sizeyunsuan5.png)

##### LL(1)

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

##### 左递归

上面的产生式，在实际代码中是有问题的  
形如\\(A = A\\alpha|\\beta\\)，我们把它称为左递归(当然还有隐式的)  
这个exp，会不停的递归下去，因为它还来不及向前看，就被右边的第一个exp匹配走了  
解决方案  
![js_sizeyunsuan7.png](https://blog.hacking.pub/qiniu/js_sizeyunsuan/js_sizeyunsuan7.png)  
想了好久用数字严格证明，但是脑子不够用  
这里说一下思想吧，其实可以知道 \\(A\\) 的右边不断出现\\(\\alpha\\)，直到\\(A\\)本身是\\(\\beta\\)  
那么其实\\(A\\)的展开正则表达式是\\(/\\beta\\alpha\*/\\)  
再观察随后的两个式子，\\( A^{'}\\)本质上就是\\(\\alpha\* \\)，但是它是个右递归

那么原先整个产生式，就变成了  
![js_sizeyunsuan6.png](https://blog.hacking.pub/qiniu/js_sizeyunsuan/js_sizeyunsuan6.png)

##### 括号

支持括号，那么表达式继续改变  
![js_sizeyunsuan8.png](https://blog.hacking.pub/qiniu/js_sizeyunsuan/js_sizeyunsuan8.png)

```displaynone
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"

```

#### 源代码

```js
//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/](https://blog.hacking.pub/2016/11/23/js-si-ze-yun-suan-jie-shi-qi/)