前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >手写一个四则运算表达式转换成AST的方法(上)

手写一个四则运算表达式转换成AST的方法(上)

作者头像
WecTeam
发布2019-12-16 14:37:49
1.5K0
发布2019-12-16 14:37:49
举报
文章被收录于专栏:WecTeam

0 前言

晓强哥在他的上篇文章 Javascript抽象语法树上篇(基础篇) 里介绍了 Javascript 抽象语法树里面「提到获得抽象语法树的过程为:代码 => 词法分析 => 语法分析 => AST」,抱着深究技术细节的目的,我决定研究这里的词法分析和语法分析,写一个简单的四则运算表达式转换成 AST 的方法,于是就有了下面的内容。

1 人类和计算机对于表达式的看法是不同的

人类习惯 a + b 这种表达叫做「中序表达式」,优点是比较简单直观,缺点是要用一堆括号来确定优先级 (a + b) * (c + d)

这里说简单直观是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。

为了计算机计算方便,我们需要将中序表达式转换成树形结构,也就是「抽象语法树 AST」。

2 javascript 与抽象语法树 AST

我们知道,几乎任何语言中,代码在 "编译"(解释型语言在运行时也有编译的过程) 的过程中,都会生成一种树状的中间状态,这就是 AST。有些语言会直接把类似 AST 的语法暴露给程序员(例如:lisp、elixir、python 等)。但是 javascript 并没有这个能力,但是我们可以用 javascript 自身实现这个过程。

获得抽象语法树的过程为:代码(字符串) => 词法分析(Lexer)=> Tokens => 语法分析(Parser) => AST。

3 词法分析(Lexer)

词法分析有点像中文的分词,就是将字符串流根据规则生成一个一个的有具体意义的 Token ,形成 Token 流,然后流入下一步。

我们看一个简单的例子,

代码语言:javascript
复制
1 + 2.3

很明显这个表达式是可以分成三个 Token ,分别是 1 , + , 2.3

词法分析这里,我们可以用有限状态机来解决。

3.1 有限状态机

绝大多数语言的词法部分都是用状态机实现的,我们下面就画出有限状态机的图形,然后根据图形直观地写出解析代码,总体图大概是这样。

下面拆开细看。

3.2 开始(start)状态

状态机的初始状态是 start

start 状态下输入数字(0 ~ 9)就会迁移到 inInt 状态。

start 状态下输入符号(.)就会迁移到 inFloat 状态。

start 状态下输入符号(+ - * /)就会输出 「符号 Token」 ,并回到 start 状态。

start 状态下输入 EOF 就会输出 「EOF Token」 ,并回到 start 状态。

代码大概是这个样子:

代码语言:javascript
复制
  start(char) {
    // 数字
    if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
      this.token.push(char);
      return this.inInt;
    }
    // .
    if (char === "."){
      this.token.push(char);
      return this.inFloat;
    }
    // 符号
    if (["+","-","*","/"].includes(char)) {
      this.emmitToken("SIGN", char);
      return this.start;
    }
    // 结束符
    if (char === EOF){
      this.emmitToken("EOF", EOF);
      return this.start;
    }
  }

3.3 在整数(inInt)状态

start 状态下输入输入数字(0 ~ 9)就会迁移到 inInt 状态。

inInt 状态下输入输入符号(.)就会迁移到 inFloat 状态。

inInt 状态下输入数字(0 ~ 9)就继续留在 inInt 状态。

inInt 状态下输入非数字和.(0 ~ 9 .)就会就会输出 「整数 Token」 ,并迁移到 start 状态。

代码:

代码语言:javascript
复制
  inInt(char) {
    if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
      this.token.push(char);
      return this.inInt;
    } else if (char === '.') {
      this.token.push(char);
      return this.inFloat;
    } else {
      this.emmitToken("NUMBER", this.token.join(""));
      this.token = [];
      return this.start(char); // put back char
    }
  }

3.4 在浮点数(inFloat)状态

start 状态下输入符号(.)就会迁移到 inFloat 状态。

inInt 状态下输入输入符号(.)就会迁移到 inFloat 状态。

inFloat 状态下输入数字(0 ~ 9)就继续留在 inFloat 状态。

inFloat 状态下输入非数字(0 ~ 9 )就会就会输出 「浮点数 Token」,并迁移到 start 状态。

代码:

代码语言:javascript
复制
  inFloat(char) {
    if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
      this.token.push(char);
      return this.inFloat;
    } else if (char === ".") {
      throw new Error("不能出现`..`");
    } else {
      if (this.token.length === 1  && this.token[0] === ".") throw new Error("不能单独出现`.`");
      this.emmitToken("NUMBER", this.token.join(""));
      this.token = [];
      return this.start(char); // put back char
    }
  }

3.5 输出的 Token 种类 和定义

我将 「浮点数 Token」「整数 Token」 合并为 [NUMBER Token] , 其他的 Token 还有 「SIGN Token」「EOF Token」

Token 的 定义:

代码语言:javascript
复制
  interface Token{
    type:String,
    value:String,
  }

3.6 完整的 Lexer 代码

代码语言:javascript
复制
  const EOF = Symbol('EOF');

  class Lexer {
    constructor(){
      this.token = []; // 临时 token 字符存储
      this.tokens = []; // 生成的正式 token
      // state 默认是 start 状态,后面通过 push 函数实现状态迁移
      this.state = this.start;
    }
    start(char) {
      // 数字
      if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
        this.token.push(char);
        return this.inInt;
      }
      // .
      if (char === "."){
        this.token.push(char);
        return this.inFloat;
      }
      // 符号
      if (["+","-","*","/"].includes(char)) {
        this.emmitToken("SIGN", char);
        return this.start;
      }
      // 结束符
      if (char === EOF){
        this.emmitToken("EOF", EOF);
        return this.start;
      }
    }
    inInt(char) {
      if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
        this.token.push(char);
        return this.inInt;
      } else if (char === '.') {
        this.token.push(char);
        return this.inFloat;
      } else {
        this.emmitToken("NUMBER", this.token.join(""));
        this.token = [];
        return this.start(char); // put back char
      }
    }
    inFloat(char) {
      if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
        this.token.push(char);
        return this.inFloat;
      } else if (char === ".") {
        throw new Error("不能出现`..`");
      } else {
        if (this.token.length === 1  && this.token[0] === ".") throw new Error("不能单独出现`.`");
        this.emmitToken("NUMBER", this.token.join(""));
        this.token = [];
        return this.start(char); // put back char
      }
    }
    emmitToken(type, value) {
      this.tokens.push({
        type,
        value,
      })
    }
    push(char){
      // 每次执行 state 函数都会返回新的状态函数,实现状态迁移
      this.state = this.state(char);
      return this.check();
    }
    end(){
      this.state(EOF);
      return this.check();
    }
    check(){
      // 检测是否有 token 生成并返回。
      const _token = [...this.tokens];
      this.tokens = [];
      return _token;
    }
    clear(){
      this.token = [];
      this.tokens = [];
      this.state = this.start;
    }
  }

  const lexer = new lexer();

  const input = `1 + 2.3`;

  let tokens = [];

  for (let c of input.split('')){
    tokens = [...tokens,...lexer.push(c)];
  }

  tokens = [...tokens,...lexer.end()];

效果如下图:

3.7 小结

自此,我们利用「用有限状态机」成功实现了「词法分析」,后面将进入到「语法分析」。

敬请期待下篇,「手写一个四则运算表达式转换成 AST 的方法(下)」。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-10-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 WecTeam 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 0 前言
  • 1 人类和计算机对于表达式的看法是不同的
  • 2 javascript 与抽象语法树 AST
  • 3 词法分析(Lexer)
    • 3.1 有限状态机
      • 3.2 开始(start)状态
        • 3.3 在整数(inInt)状态
          • 3.4 在浮点数(inFloat)状态
            • 3.5 输出的 Token 种类 和定义
              • 3.6 完整的 Lexer 代码
                • 3.7 小结
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档