js写的一个简单四则运算解释器

OPY-bbt commented 5 years ago

本文主要分为三个部分

语法定义
词法分析：输入的字符串流变为token
语法分析：将词token变为抽象语法树（abstract syntax tree）
解释执行: 后续遍历ast，执行得出结果

OPY-bbt commented 5 years ago

语法定义

加法可以看成是若干个乘法加上加号或者减号组成，而乘法可以看成是由数字和乘法表达式组成，为了简单，把数字也看成是乘法, 四则运算语法定义如下：

<Expression> ::=
  <AdditiveExpression><EOF>

<AdditiveExpression> ::=
    <MultiplicativeExpression>
    |<AdditiveExpression><+><MultiplicativeExpression>
    |<AdditiveExpression><-><MultiplicativeExpression>

<MultiplicativeExpression> ::=
    <Number>
    |<MultiplicativeExpression><*><Number>
    |<MultiplicativeExpression></><Number>

OPY-bbt commented 5 years ago

词法分析

将字节流变成token流就是词法分析，效果如下：

'1 + 2' => [{type: 'Number', value: 1}, {type: '+', value: '+'}, {type: 'Number', value: 2}];

词法分析有两种方案，状态机和正则表达式。这里会用状态机来实现。用函数表示状态，用if表示状态的迁移，return值表示下一个状态。代码如下：

    const start = char => {
      if (['1', '2', '3', '4', '5', '6', '7', '8', '9', '0'].includes(char)) {
        token.push(char);
        return inNumber;
      }

      // 支持负数
      if (char === '-') {
        if (tokens.length === 0 || ['+', '-', '*', '/'].includes(tokens[tokens.length - 1].type)) {
          token.push(char);
          return inNumber;
        }
      }

      if (['+', '-', '*', '/'].includes(char)) {
        emmitToken(char, char);
        return start
      }

      if (char === ' ') {
        return start;
      }

      if (['\r', '\n'].includes(char)) {
        return start;
      }

      // EOF 表示结束
      if (char === 'EOF') {
        emmitToken(char, char);
        return start;
      }
    }

    const inNumber = char => {
      // 支持小数
      if (['1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '.'].includes(char)) {
        token.push(char);
        return inNumber;
      } else {
        emmitToken("Number", token.join(''));
        token=[];
        return start(char);
      }
    }

接下来运行一下

    const input = '1 + 1 * 2';

    let state = start;

    for(let c of input.split('')) {
      state = state(c);
    }

    state('EOF');

我们会得到如下的token数组

0: {type: "Number", value: "1"}
1: {type: "+", value: "+"}
2: {type: "Number", value: "1"}
3: {type: "*", value: "*"}
4: {type: "Number", value: "2"}
5: {type: "EOF", value: "EOF"}

词法分析到此就结束了，接下来就是根据token流生成ast

OPY-bbt commented 5 years ago

语法分析

这里工作就是根据我们之前定义的语法生成ast，例如加法有三种情况，我们需要三个if来做判断，代码如下：

    /**
    * <AdditiveExpression> ::=
    *     <MultiplicativeExpression>
    *     |<AdditiveExpression><+><MultiplicativeExpression>
    *     |<AdditiveExpression><-><MultiplicativeExpression>
    */
    const AdditiveExpression = (source) => {
      if(source[0].type === "MultiplicativeExpression") {
        let node = {
          type: 'AdditiveExpression',
          children: [source[0]],
        };
        source[0] = node;
        return AdditiveExpression(source);
      }

      if(source[0].type === 'AdditiveExpression' && source[1] && source[1].type === '+') {
        let node = {
          type: 'AdditiveExpression',
          operator: '+',
          children: [source.shift(), source.shift()],
        }
        MultiplicativeExpression(source);
        node.children.push(source.shift());
        source.unshift(node);
        return AdditiveExpression(source);
      }

      if (source[0].type === 'AdditiveExpression' && source[1] && source[1].type === '-') {
        let node = {
          type: 'AdditiveExpression',
          operator: '-',
          children: [source.shift(), source.shift()],
        }
        MultiplicativeExpression(source);
        node.children.push(source.shift());
        source.unshift(node);
        return AdditiveExpression(source);
      }

      if (source[0].type === 'AdditiveExpression') {
        return source[0];
      }

      MultiplicativeExpression(source);
      return AdditiveExpression(source);
    }

乘法也是类似，这里就不贴代码了，在文末会有完整的代码参考。 经过语法分析，我们会得到如下ast, 对照上面的语法定义，这是符合预期的。

{
  children: (2) [{
    children: (3) [{
          type: "AdditiveExpression",
          children: [
              {type: "MultiplicativeExpression", operator: "*", children: [{2..}, {*...}, {1...}]}
           ]}
          {type: "+", value: "+"},
          {type: "MultiplicativeExpression", children: [{type: "Number", value: "1"}],
      }],
      operator: "+"
      type: "AdditiveExpression"
    }, {
      type: "EOF"
      value: "EOF"
  }],
  type: "Expression"
}

OPY-bbt commented 5 years ago

解释执行

得到ast之后，就是解释执行了。后序遍历ast求值即可

    function evaluate(node) {
      if (node.type === 'Expression') {
        return evaluate(node.children[0]);
      }

      if (node.type === 'AdditiveExpression') {
        if(node.operator === '-') {
          return evaluate(node.children[0]) - evaluate(node.children[2]);
        }

        if(node.operator === '+') {
          return evaluate(node.children[0]) + evaluate(node.children[2]);
        }

        return evaluate(node.children[0]);
      }

      if(node.type === 'MultiplicativeExpression') {
        if (node.operator === '*') {
          return evaluate(node.children[0]) * evaluate(node.children[2]);
        }

        if (node.operator === '/') {
          return evaluate(node.children[0]) * evaluate(node.children[2]);
        }

        return evaluate(node.children[0]);
      }

      if (node.type === 'Number') {
        return Number(node.value);
      }
    }

到此为止我们实现了一个支持负数与小数的四则运算编译器。以后还会增加括号功能

OPY-bbt commented 5 years ago

https://gist.github.com/OPY-bbt/8ee387122550326f60592b94b7908d19

OPY-bbt / OPY-bbt.github.io