blog 编译入门-从零实现中文计算器

编译入门-从零实现中文计算器

Open oyuyue opened this issue 2 years ago • 0 comments

“如果你不知道编译器咋工作的你就不知道电脑是咋工作的。” -- STEVE YEGGE

这篇文章将从零使用语言处理器的方式自己实现一个中文计算器，计算器相信大家都有使用过，但是中文的计算器有没有用过呢？赶紧点击下面链接先体验下这个并没啥用的中文计算器吧。

https://oyuyue.github.io/ccalc/

前言

其实前端开发中，大量使用的编译器相关的知识。比如 webpack 中是怎么知道你的 JS 文件依赖哪些其他 JS 文件？babel 怎么将 es6 代码转成 es5 的代码？怎么实现 js 代码压缩？vue 如何将 template 变成 render 函数？react 如何将 jsx 变成 render 函数？要回答这些问题，就需要了解这篇文章中介绍的各种概念。这篇文章通过实现中文计算器方式，来介绍解释器或编译器中的各种概念。

基本概念

如何执行一个字符串 1+1 呢？在 JS 中，我们可以直接执行 eval('1+1') 就行了，这将会输出 2。如果不能使用 eval 这些函数，那么如何执行这个字符串呢？如何自己实现一个 eval 函数？

执行一个字符串的程序一般称为解释器，实现一个解释器一般需要 3 个步骤。

词法分析。读取字符串，将字符串转换为单词流。
语法分析。读取单词流，根据语法将单词流变成抽象语法树。
解释执行。遍历访问抽象语法树，解释运行。

一般情况就上面 3 个步骤就行了。如果再复杂一点可能会加上语义分析等其他步骤，比如 {a = 1; let a} 这行代码，它的语法是对的，但是它的语义是错的，因为在 a 初始化之前访问了 a。

可能就会有人要问了，为啥要分这么多步骤，我直接一步到位不就行了吗？

function eval(str) { 
    const nums = str.split('+');
    return Number(nums[0]) + Number(nums[1])
}

一些比较简单的程序我是可以这样做。但是比较复杂的，我们还是要用上面提到的几个步骤来做，会更好维护、更轻松一点。

当然不光是解释器中会用到上面的一些步骤，编译器也会用到词法分析和语法分析。

编译器是生成代码，解释器是解释运行。现在解释器和编译器边界有点模糊，很多解释器里面也会使用编译器，比如 v8 引擎可以说它是 js 的解释器，但是其中也会利用编译器将一些 js 代码编译成机器码来加速执行。

现有工具

目前有很多工具可以帮助我们来做词法分析和语法分析。下面列举了其中非常有名的几个工具。

Lex / Yacc

lex是一个产生词法分析器（lexical analyzer，"扫描仪"（scanners）或者"lexers"）的程序，Lex是许多UNIX系统的标准词法分析器产生程序。Lex 常常与 yacc 语法分析器产生程序一起使用。

yacc（Yet Another Compiler Compiler），是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。yacc生成的编译器主要是用C语言写成的语法解析器，需要与词法解析器Lex一起使用，再把两部分产生出来的C程序一并编译。

flex / Bison

flex（快速词法分析产生器，英语：fast lexical analyzer generator）是一种词法分析程序。它是lex的开放源代码版本，以BSD许可证发布。通常与GNU bison一同运作，但是它本身不是GNU计划的一部分。

GNU bison（Bison意为犎牛；而Yacc与意为牦牛的Yak同音）是一个自由软件，用于自动生成语法分析器程序，实际上可用于所有常见的操作系统。GNU bison基本兼容Yacc，并做了一些改进。它一般与flex一起使用。

上面介绍了几个有名的工具，这些工具在其他语言中都有对应的类库，比如 JS 中的 bison 叫 jison。

计算器介绍

当然这篇文章要实现的中文计算器，不会用到上面的工具，而是从零实现一个解释器。这个中文计算器和普通的计算器非常相似，只是不使用 0123456789 而是 零壹贰叁肆伍陆柒捌玖拾佰仟万亿，不使用 +-*/()，而是 加减乘除左括号右括号。可以点击这个链接在线体验 https://woopen.github.io/ccalc/。如果输入 零乘零 那么将返回 零。

词法分析

词法分析只做一件事情，就是将输入的字符串变为单词流。一般会称为 Tokenizer、Lexer 或 Scanner。

我们要把一个字符串分成一个个不同类型的 token。首先就要找到中文计算器中一共有几种类型的 token。

const TokenKind = {
  INT: 0,
  PLUS: "加",
  MINUS: "减",
  MUL: "乘",
  DIV: "除",
  LPAREN: "左括号",
  RPAREN: "右括号"
};

中文计算器中一共有上面 7 种类型的 token。那输入的字符串只能是上面 7 种类型中的一种，否则就会报错不期望的 token，就像下面 js 代码一样。

知道了 token 的类型，下面再定义一个 Token 类，用它来表示不同 token。

class Token {
  constructor(kind, data) {
    this.kind = kind;
    this.data = data || kind;
  }

  is(...kinds) {
    return kinds.includes(this.kind);
  }
}

Token 只有两个属性 kind 表示该 token 的类型，data 是该 token 的值，比如是整数类型 token，那么 data 就是具体的整数值。

基础工作都做完了，下面就让我们开始将字符串变成一个个 token 把。

function isDigit(ch) {
  return "壹贰叁肆伍陆柒捌玖拾佰仟万亿零".includes(ch);
}

class Tokenizer {
  constructor(source) {
    this.source = source;
    this.pos = 0;
    this.max = this.source.length;
    this.tokens = [];
  }

  process() {
    while (this.pos < this.max) {
      const ch = this.source[this.pos];

      if (isDigit(ch)) {
        this.processDigit(ch);
        continue;
      }

      switch (ch) {
        case "加":
          this.pushToken(TokenKind.PLUS);
          break;
        case "减":
          this.pushToken(TokenKind.MINUS);
          break;
        case "乘":
          this.pushToken(TokenKind.MUL);
          break;
        case "除":
          this.pushToken(TokenKind.DIV);
          break;
        case "左":
        case "右":
          this.processParen(ch);
          break;
        case " ":
        case "\t":
        case "\r":
        case "\n":
          this.pos++;
          break;
        default:
          throw new Error(`非法字符 ${ch}`);
      }
    }
    return this.tokens;
  }

  processDigit(ch) {
    let digit = ch;
    while (this.pos < this.max) {
      ch = this.source[++this.pos];
      if (isDigit(ch)) {
        digit += ch;
      } else {
        break;
      }
    }
    this.tokens.push(new Token(TokenKind.INT, digit));
  }

  processParen(ch) {
    if (this.pos + 2 >= this.max) throw new Error(`【${ch}括号】错误长度`);
    const ch1 = this.source[this.pos + 1];
    const ch2 = this.source[this.pos + 2];
    if (ch1 !== "括") throw new Error(`非法单词 ${ch + ch1}`);
    if (ch2 !== "号") throw new Error(`非法单词 ${ch + ch1 + ch2}`);
    this.tokens.push(
      new Token(ch === "左" ? TokenKind.LPAREN : TokenKind.RPAREN)
    );
    this.pos += 3;
  }

  pushToken(kind, data) {
    this.tokens.push(new Token(kind, data));
    this.pos++;
  }
}

语法分析

下一步就是语法分析了。语法分析也只做一件的事，就是把词法分析生成的单词流，转换成抽象语法树。

但是在语法分析之前，我们还需要了解一些概念。

BNF

巴科斯范式以美国人巴科斯(Backus)和丹麦人诺尔(Naur)的名字命名的一种形式化的语法表示方法，用来描述语法的一种形式体系，是一种典型的元语言。又称巴科斯-诺尔形式(Backus-Naur form)。

::- 被定义为或等于
| 或
[] 可选
{} 重复
() 分组
"" 终结符用引号包裹
<> 非终结符用尖括号包裹

<char>   ::= <digit> | <symbol>
<digit>  ::= "0"|"1"|"2"|"3"|“4"|"5"|"6"|"7"|“8"|"9"
<symbol> ::= "+" | "-" | "*" | "/"

其中尖括号包裹为非终结符，双引号包裹为终结符。非终结符可以理解为一个变量，终结符可以理解为一个标量，它不可以再拆分了，就像一个字符串或数字。

EBNF

Extended BNF，扩展的巴科斯范式。由于 BNF 语法有点繁琐，所以就有了 EBNF，它也有很多变种。

char   = <digit> | <symbol>
digit  = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
symbol = "+" | "-" | "*" | "/"

中文计算器将使用 EBNF，它会和正则表达式很像。

抽象语法树

语法分析最终会生成抽象语法树，那什么是抽象语法树呢？

抽象语法树（Abstract Syntax Tree，AST），抽象语法树和普通的树差不太多，因为用它来表示语法所以也被称为语树。之所以加上抽象，是因为它不会表现所有细节。

比如下图是字符串 1 + 2 * (3 + 4) 生成的 AST。

可以发现字符串中的括号并没有与之对应的节点，而是使用树的层级来描述对应的优先级。

中文计算器语法

中文计算器的语法可以用下面 EBNF 来表示。

expr    = term (("+" | "-") term)*
term    = factor (("*" | "/") factor)*
factor  = INT | "(" expr ")" | ("+" | "-") factor

其中 * 就和正则中的一样，表示 0 到多次。

下面几张铁路图可以很好的表达计算器语法。

Parser

下面就来编写代码，将单词流编程 AST吧，一般会称它为 parser。

const NodeType = {
  BinOp: 0,
  UnaryOp: 1,
  Int: 2
};

我们首先声明 AST 节点的类型。一共只有 3 个，分别是的双向运算、单运算和整数节点。

其中 INT 为叶子节点，双向运算和单运算为树枝节点，比如 1 + 2，就是一个双向节点，它的左子节点是 INT(1)，右子节点是的 INT(2)。+3 就是一个单操作节点，它只有一个子节点 INT(3)。

class ASTNode {
  constructor(type) {
    this.type = type;
  }
}

class IntNode extends ASTNode {
  constructor(token) {
    super(NodeType.Int);
    this.token = token;
    this.value = token.data;
  }
}

class BinOpNode extends ASTNode {
  constructor(left, token, right) {
    super(NodeType.BinOp);
    if (!left) throw new Error(`${op.data} 左边不能为空`);
    if (!right) throw new Error(`${op.data} 右边不能为空`);
    this.left = left;
    this.op = token.kind;
    this.right = right;
  }
}

class UnaryOpNode extends ASTNode {
  constructor(token, node) {
    super(NodeType.UnaryOp);
    if (!node) throw new Error(`${token.data} 后面不能为空`);
    this.op = token.kind;
    this.child = node;
  }
}

我们再声明与节点类型对应的节点。下面终于可以来写 parser 了。

class Parser {
  constructor(tokenizer) {
    this.tokenizer = tokenizer;
    this.pos = 0;
  }

  parse() {
    this.tokens = this.tokenizer.process();
  }

  nextToken() {
    this.currentToken = this.tokens[this.pos++];
  }
}

我们首先定义 Parser 基本的架子，它接受一个 tokenizer，pos 是指向单词流中的哪个 token，currentToken 表示当前是哪个 token。

其实写 parser 也非常的简单，我们只需要对着上面定义的 EBNF 语法写就行了。

expr    = term (("+" | "-") term)*
term    = factor (("*" | "/") factor)*
factor  = INT | "(" expr ")" | ("+" | "-") factor

只要对着上面 BENF，不需要思考，就可以轻松编写写出来，下面来试试吧。

将非终结符变成一个方法，也就是等号左边的那几个，一般会在前面加上 eat，所以我们就得到了下面的代码。

class Parser {
  eatExpr() {}
  eatTerm() {}
  eatFactor() {}
}

现在开始填充这些方法的内部代码。把 | 变成 || 操作符，* 变成 while 循环，非终结符变成调用与之对应的方法。比如 eatExpr 就可以这样。

class Parser {
  eatExpr() {
    let node = this.eatTerm();
    while (
      this.currentToken &&
      this.currentToken.is(TokenKind.PLUS, TokenKind.MINUS)
    ) {
      const token = this.currentToken;
      this.nextToken();
      node = new BinOpNode(node, token, this.eatTerm());
    }
    return node;
  }
}

expr = term (("+" | "-") term)* 我们看见这个表达式最前面是一个 term，所以首先我们调用 eatTerm，然后碰到 * 号，所以直接写一个 while 循环，然后 + 号或 - 号，这里用 token.is() 方法进行判断，当条件成功后，我们看到后面又有个 term，所以再次调用 eatTerm 方法，然后创建 BinOpNode。当结束后再返回 node，就完成了该方法。

与 eatExpr 类似，我们再来完成 eatTerm 和 eatFactor。

class Parser {
  eatTerm() {
    let node = this.eatFactor();
    while (
      this.currentToken &&
      this.currentToken.is(TokenKind.MUL, TokenKind.DIV)
    ) {
      const token = this.currentToken;
      this.nextToken();
      node = new BinOpNode(node, token, this.eatFactor());
    }
    return node;
  }

  eatFactor() {
    const token = this.currentToken;
    if (!token) return null;

    this.nextToken();

    if (token.is(TokenKind.INT)) {
      return new NumNode(token);
    }

    if (token.is(TokenKind.LPAREN)) {
      const node = this.eatExpr();
      if (!this.currentToken || !this.currentToken.is(TokenKind.RPAREN)) {
        throw new Error("缺少右括号");
      }
      this.nextToken();
      return node;
    }

    if (token.is(TokenKind.PLUS, TokenKind.MINUS)) {
      return new UnaryOpNode(token, this.eatFactor());
    }

    throw new Error(`不期望的单词 【${token.data}】`);
  }
}

最后再来完善一下 parse 方法，让它返回 AST 节点。

class Parser {
  parse() {
    this.tokens = this.tokenizer.process();
    this.nextToken();
    const node = this.eatExpr();
    this.nextToken();
    if (this.currentToken) {
      throw new Error(`解析后还存在 ${this.currentToken.data}`);
    }
    return node;
  }
}

解释器

完成词法分析，最后一步就是访问 AST，来解释执行输出计算结果。

一般访问 AST 操作，会使用访问者模式，下面是解释器的完整代码。

class Interpreter {
  constructor(parser) {
    this.parser = parser;
  }

  interpret() {
    const ast = this.parser.parse();
    if (!ast) return "";
    return this.visit(ast);
  }

  visit(node) {
    if (!node) throw new Error("节点未空");
    switch (node.type) {
      case NodeType.BinOp:
        return this.visitBinOp(node);
      case NodeType.Unary:
        return this.visitUnaryOp(node);
      case NodeType.Num:
        return this.visitNum(node);
      default:
        throw new Error(`未知节点 ${node}`);
    }
  }

  visitNum(node) {
    return chineseToArabic(node.value);
  }

  visitBinOp(node) {
    const l = this.visit(node.left);
    const r = this.visit(node.right);
    if (node.op === TokenKind.PLUS) return l + r;
    if (node.op === TokenKind.MINUS) return l - r;
    if (node.op === TokenKind.MUL) return l * r;
    if (node.op === TokenKind.DIV) return Math.round(l / r);
  }

  visitUnaryOp(node) {
    if (node.op === TokenKind.PLUS) return this.visit(node.child);
    if (node.op === TokenKind.MINUS) return -this.visit(node.child);
  }
}

可以发现解释器的代码非常简单的。访问 AST 可以直接使用 interpreter 的 visit 方法，它会根据 AST 节点的类型，调用相关的方法，处理对应的逻辑。上面 chineseToArabic 是将中文数字变成阿拉伯数字，这里就不介绍了，感兴趣的同学可以查看相关源码。

总结

这篇文章通过实现中文计算器的方式，来介绍解释器的基本概念。通过词法分析将字符串转换成单词流，使用语法分析将单词流变成 AST，到这里是解释器和编译器通用的步骤，解释器的下一步是解释执行，编译器是生成代码。

源码：https://github.com/oyuyue/ccalc

在线体验：https://oyuyue.github.io/ccalc/

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

手机阅读或接收新文章通知，欢迎订阅微信公众号：羽月技术

Oct 11 '22 12:10 oyuyue

blog blog copied to clipboard

编译入门-从零实现中文计算器

前言

基本概念

现有工具

Lex / Yacc

flex / Bison

计算器介绍

词法分析

语法分析

BNF

EBNF

抽象语法树

中文计算器语法

Parser

解释器

总结

blog
blog copied to clipboard