乐趣区

关于javascript:实现JavaScript语言解释器二

作者：

jiezi

在

前言

在上一篇文章中我为大家介绍了Simpe我的项目的一些背景常识以及如何应用无限状态机来实现词法解析，在本篇文章中我将会为大家介绍语法分析的相干内容，并且通过设计一门外部DSL语言来实现Simple语言的语法解析。

什么是语法解析

词法解析过后，字符串的代码会被解析生成一系列Token串，例如上面是代码let a = 'HelloWorld';的词法解析输入：

[
  {
    "type": "LET",
    "value": "let",
    "range": {
      "start": {
        "line": 1,
        "column": 1
      },
      "end": {
        "line": 1,
        "column": 3
      }
    }
  },
  {
    "type": "IDENTIFIER",
    "value": "a",
    "range": {
      "start": {
        "line": 1,
        "column": 5
      },
      "end": {
        "line": 1,
        "column": 5
      }
    }
  },
  {
    "type": "ASSIGN",
    "value": "=",
    "range": {
      "start": {
        "line": 1,
        "column": 7
      },
      "end": {
        "line": 1,
        "column": 7
      }
    }
  },
  {
    "type": "STRING_LITERAL",
    "value": "'HelloWorld'",
    "range": {
      "start": {
        "line": 1,
        "column": 9
      },
      "end": {
        "line": 1,
        "column": 20
      }
    }
  },
  {
    "type": "SEMICOLON",
    "value": ";",
    "range": {
      "start": {
        "line": 1,
        "column": 21
      },
      "end": {
        "line": 1,
        "column": 21
      }
    }
  }
]

在语法解析（Syntax Analysis）阶段，Simple解释器会依据定义的语法规定来剖析单词之间的组合关系，从而输入一棵形象语法树（Abstract Syntax Tree），这也就咱们常听到的AST了。那么为什么说这棵语法树是形象的呢？这是因为在语法解析阶段一些诸如分号和左右括号等用来组织代码用的token会被去掉，因而生成的语法树没有蕴含词法解析阶段生成的所有token信息，所以它是形象的。在语法解析阶段，如果Simple解释器发现输出的Token字符串不能通过既定的语法规定来解析，就会抛出一个语法错误（Syntax Error），例如赋值语句没有右表达式的时候就会抛出Syntax Error。

从下面的形容能够看出，词法解析阶段的重点是拆散单词，而语法解析阶段最重要的是依据既定的语法规定来组合单词。那么对于Simple解释器来说，它的语法规定又是什么呢？

Simple语言的语法

咱们后面说到Simple语言其实是JavaScript的一个子集，所以Simple的语法也是JavaScript语法的一个子集。那么Simple的语法规定都有哪些呢？在进入到应用业余的术语表白Simple语法规定之前，咱们能够先用中文来表白一下Simple的语法规定：

  • 变量定义：let, const或者var前面接一个identifier，而后是可选的等号初始化表达式：

    let a;
// 或者
let a = 10;

  • if条件判断：if关键字前面加上由左右括号包裹起来的条件，条件能够是任意的表达式语句，接着会跟上花括号括起来的语句块。if语句块前面能够选择性地跟上另外一个else语句块或者else if语句块：

    if (isBoss) {
  console.log('niu bi');
} else {
  console.log('bu niu bi');
};

  • while循环：while关键字前面加上由左右括号包裹起来的条件，条件能够是任意的表达式语句，接着是由花括号包裹起来的循环体：

    while(isAlive) {
  console.log('coding');
};

    …

仔细的你可能发现在下面的例子中所有语句都是以分号;结尾的，这是因为为了简化语法解析的流程，Simple解释器强制要求每个表达式都要以分号结尾，这样咱们才能够将重点放在把握语言的实现原理而不是拘泥于JavaScript灵便的语法规定上。

下面咱们应用了最直白的中文表白了Simple语言的一小部分语法规定，在理论工程外面咱们必定不能这么干，咱们个别会应用巴克斯范式（BNF）或者扩大巴克斯范式（EBNF）来定义编程语言的语法规定。

BNF

咱们先来看一个变量定义的巴科斯范式例子：

在下面的巴科斯范式中，每条规定都是由左右两局部组成的。在规定的右边是一个非终结符，而左边是终结符和非终结符的组合。非终结符示意这个符号还能够持续细分，例如varModifier这个非终结符能够被解析为let，const或var这三个字符的其中一个，而终结符示意这个符号不能持续细分了，它个别是一个字符串，例如if，while，(或者)等。无论是终结符还是非终结符咱们都能够对立将其叫做模式（pattern）。

在BNF的规定中，除了模式符号，还有上面这些示意这些模式呈现次数的符号，上面是一些咱们在Simple语言实现中用到的符号：

符号 作用
[pattern] 是option的意思，它示意括号里的模式呈现0次或者一次，例如变量初始化的时候前面的等号会呈现零次或者1次，因为初始值是可选的
pattern1 pattern2 是or的意思，它示意模式1或者模式2被匹配，例如变量定义的时候能够应用let，const或者var
{ pattern } 是repeat的意思， 示意模式至多反复零次，例如if语句前面能够跟上0个或者多个else if

要实现Simple语言下面这些规定就够用了，如果你想理解更多对于BNF或者EBNF的内容，能够自行查阅相干的材料。

如何实现语法解析

在咱们编写完属于咱们语言的BNF规定之后，能够应用Yacc或者Antlr等开源工具来将咱们的BNF定义转化成词法解析和语法解析的客户端代码。在实现Simple语言的过程中，为了更好地学习语法解析的原理，我没有间接应用这些工具，而是通过编写一门灵便的用来定义语法规定的畛域专用语言（DSL）来定义Simple语言的语法规定。可能很多同学不晓得什么是DSL，不要焦急，这就为大家解释什么是DSL。

DSL的定义

身为程序员，我置信大家都或多或少据说过DSL这个概念，即便你没听过，你也必定用过。在理解DSL定义之前咱们先来看一下都有哪些罕用的DSL：

  • HTML
  • CSS
  • XML
  • JSX
  • Markdown
  • RegExp
  • JQuery
  • Gulp
    …

我置信作为一个程序员特地是前端程序员，大家肯定不会对下面的DSL感到生疏。DSL的全称是Domain-Specific Language，翻译过去就是畛域特定语言，和JavaScrpt等通用编程语言（GPL – General-Purpose Language）最大的区别就是：DSL是为特定畛域编写的，而GPL能够用来解决不同畛域的问题。举个例子，HTML是一门DSL，因为它只能用来定义网页的构造。而JavaScript是一门GPL，因而它能够用来解决很多通用的问题，例如编写各式各样的客户端程序和服务端程序。正是因为DSL只须要关怀以后畛域的问题，所以它不须要图灵齐备，这也意味着它能够更加靠近人类的思维形式，让一些不是专门编写程序的人也能够参加到DSL的编写中（设计师也能够编写HTML代码）。

DSL的分类

DSL被分成了两大类，一类是外部DSL，一类是内部DSL。

外部DSL

外部DSL是建设在某个宿主语言（通常是一门GPL，例如JavaScript）之上的非凡DSL，它具备上面这些特点：

  • 和宿主语言共享编译与调试等基础设施，对那些会应用宿主语言的开发者来说，应用该宿主语言编写的DSL的门槛会很低，而且外部DSL能够很容易就集成到宿主语言的利用外面去，它的应用办法就像援用一个内部依赖一样简略，宿主欢送只须要装置就能够了。
  • 它能够视为应用宿主语言对特定工作（特定畛域）的一个封装，使用者能够很容易应用这层封装编写出可读性很高的代码。例如JQuery就是一门外部DSL，它外面封装了很多对页面DOM操作的函数，因为它的性能很有局限性，所以它能够封装出更加合乎人们直觉的API，而且它编写的代码的可读性会比间接应用浏览器原生的native browser APIS要高很多。

上面是一个别离应用浏览器原生API和应用JQuery API来实现同样工作的例子：

内部DSL

和外部DSL不同，内部DSL没有依赖的宿主环境，它是一门独立的语言，例如HTML和CSS等。因为内部DSL是齐全独立的语言，所以它具备上面这些特点：

  • 不能享受现有语言的编译和调试等工具，如有须要要本人实现，老本很高
  • 如果你是语言的实现者，须要本人设计和实现一门全新的语言，对本人的要求很高。如果你是语言的学习者就须要学习一门新的语言，比外部DSL具备更高的学习老本。而且如果语言的设计者本身程度不够，他们弄出来的DSL一旦被用在了我的项目外面，前面可能会成为妨碍我的项目倒退的一个大坑
  • 同样也是因为内部DSL没有宿主语言环境的束缚，所以它不会受任何现有语言的解放，因而它能够针对以后须要解决的畛域问题来定义更加灵便的语法规定，和外部DSL相比它有更小的来自于宿主语言的语言噪声

上面是一个内部DSL的例子 – Mustache

Simple语言的语法解析DSL

后面说到了外部DSL和内部DSL的一些特点和区别，因为咱们的语法解析逻辑要和之前介绍的词法解析逻辑串联起来，所以我在这里就抉择了宿主环境是TypeScript的外部DSL来实现

DSL的设计

如何从头开始设计一门外部DSL呢？咱们须要从要解决的畛域特定问题登程，对于Simple语言它就是：将Simple语言的BNF语法规定应用TypeScipt表达出来。在下面BNF的介绍中，咱们晓得BNF次要有三种规定：option，repeat和or。每个规定之间能够互相组合和嵌套，等等，相互组合和嵌套？你想到了什么JavaScript语法能够表白这种场景？没错就是函数的链式调用。

对于程序员来说最清晰的解释应该是间接看代码了，所以咱们能够来看一下Simple语言语法解析的代码局部。和词法解析相似，Simple的语法规定放在lib/config/Parser这个文件中，上面是这个文件的示例内容：

// rule函数会生成一个依据定义的语法规定解析Token串从而生成AST节点的Parser实例，这个函数会接管一个用来生成对应AST节点的AST类，所有的AST节点类定义都放在lib/ast/node这个文件夹下
const ifStatement = rule(IfStatement)
ifStatement
  // if语句应用if字符串作为结尾
  .separator(TOKEN_TYPE.IF)
  // if字符串前面会有一个左括号
  .separator(TOKEN_TYPE.LEFT_PAREN)
  // 括号外面是一个执行后果为布尔值的binaryExpression
  .ast(binaryExpression)
  // 右括号
  .separator(TOKEN_TYPE.RIGHT_PAREN)
  // if条件成立后的执行块
  .ast(blockStatement)
  // 前面的内容是可选的
  .option(
    rule().or(
      // else if语句
      rule().separator(TOKEN_TYPE.ELSE).ast(ifStatement),
      // else语句
      rule().separator(TOKEN_TYPE.ELSE).ast(blockStatement)
    )
  )

下面就是Simple的if表达式定义了，因为应用了DSL进行封装，ifStatement的语法规定十分通俗易懂，而且非常灵便。试想一下如果咱们忽然要扭转ifStatement的语法规定：不容许if前面加else if。要满足这个扭转咱们只须要将rule().separator(TOKEN_TYPE.ELSE).ast(ifStatement)这个规定去掉就能够了。接着就让咱们深刻到下面代码的各个函数和变量的定义中去：

rule函数

这个函数是一个用来生成对应AST节点Parser的工厂函数，它会接管一个AST节点的构造函数作为参数，而后返回一个对应的Parser类实例。

// lib/ast/parser/rule
const rule = (NodeClass?: new () => Node): Parser => {
  return new Parser(NodeClass)
}
Parser类

Parser类是整个Simple语法解析的外围。它通过函数链式调用的办法定义以后AST节点的语法规定，在语法解析阶段依据定义的语法规定耗费词法解析阶段生成的Token串，如果语法规定匹配它会生成对应AST节点，否则Token串的光标会重置为规定开始匹配的地位（回溯）从而让父节点的Parser实例应用下一个语法规定进行匹配，当父节点没有任何一个语法规定满足条件时，会抛出Syntax Error。上面是Parser类的各个函数的介绍：

办法 作用
.separator(TOKEN) 定义一个终结符语法规定，该终结符不会作为以后AST节点的子节点，例如if表达式的if字符串
.token(TOKEN) 定义一个终结符语法规定，该终结符会被作为以后AST节点的子节点，例如算术表达式中的运算符(+，-，*，/)
.option(parser) 定义一个可选的非终结符规定，非终结符规定都是一个子Parser实例，例如下面if表达式定义中的else if子表达式
.repeat(parser) 定义一个呈现0次或者屡次的非终结符规定，例如数组外面的元素可能是0个或者多个
.or(…parser TOKEN) or外面的规定有且呈现一个，例如变量定义的时候可能是var，let或者const
.expression(parser, operatorsConfig) 非凡的用来示意算术运算的规定
.parse(tokenBuffer) 这个函数会接管词法解析阶段生成的tokenBuffer串作为输出，而后应用以后Parser实例的语法规定来耗费TokenBuffer串的内容，如果有齐全匹配就会依据以后Parser节点的AST构造函数生成对应的AST节点，否则会将TokenBuffer重置为以后节点规定开始匹配的起始地位（setCursor）而后返回到父级节点
AST节点类的定义

Simple语言所有的AST节点定义都放在lib/ast/node这个文件夹底下。对于每一种类型的AST节点，这个文件夹下都会有其对应的AST节点类。例如赋值表达式节点的定义是AssignmentExpression类，if语句的定义是IfStatement类等等。这些节点类都有一个对立的基类Node，Node定义了所有节点都会有的节点类型属性（type），节点生成规定create函数，以及以后节点在代码执行阶段的计算规定evaluate函数。上面是示例代码：

// lib/ast/node/Node
class Node {
  // 节点类型
  type: NODE_TYPE
  // 节点的起始地位信息，不便产生语法错误时给开发者进行定位
  loc: {
    start: ILocation,
    end: ILocation
  } = {
    start: null,
    end: null
  }

  // 节点的生成规定，以后节点会依据其子节点的内容生成
  create(children: Array<Node>): Node {
    if (children.length === 1) {
      return children[0]
    } else {
      return this
    }
  }

  // 节点的运算规定，节点在运算时会传进以后的环境变量，每个节点都须要实现本人的运算规定，下一篇文章会具体开展
  evaluate(env?: Environment): any {
    throw new Error('Child Class must implement its evaluate method')
  }
}

当初咱们来看一下IfStatement这个AST节点类的定义

class IfStatement extends Node {
  // 该节点的类型是if statement
  type: NODE_TYPE = NODE_TYPE.IF_STATEMENT
  // if的判断条件，必须是是一个BinaryExpression节点
  test: BinaryExpression = null
  // if条件成立的条件下的执行语句，是一个BlockStatement节点
  consequent: BlockStatement = null
  // else的执行语句
  alternate: IfStatement|BlockStatement = null

  // Parser会解析出if语句的所有children节点信息来结构以后的IfStatement节点，children节点的内容和定义由lib/config/Parser文件定义
  create(children: Array<Node>): Node {
    this.test = children[0] as BinaryExpression
    this.consequent = children[1] as BlockStatement
    this.alternate = children[2] as IfStatement|BlockStatement
    return this
  }

  evaluate(env: Environment): any {
    // 前面文章会讲
  }
}

AST

介绍完Parser类和AST节点类后你当初就可以看懂lib/config/Parser的语法规定定义了，这个文件外面蕴含了Simple所有语法规定的定义，其中包含根节点的定义：

// 列举了所有可能的statement
statement
  .or(
    breakStatement,
    returnStatement,
    expressionStatement,
    variableStatement,
    assignmentExpression,
    whileStatement,
    ifStatement,
    forStatement,
    functionDeclaration,
  )
const statementList = rule(StatementList)
  .repeat(
    rule()
      .ast(statement)
      .throw('statement must end with semi colon')
      .separator(TOKEN_TYPE.SEMI_COLON)

// 一个程序其实就是很多statement的组合
const program = statementList

最初就是将上一章的词法解析和语法解析串联起来，代码在lib/parser这个文件外面：

// tokenBuffer是词法解析的后果
const parse = (tokenBuffer: TokenBuffer): Node => {
  // parser是lib/config/Parser的根节点（program节点），rootNode对应的就是形象语法树AST
  const rootNode = parser.parse(tokenBuffer)

  if (!tokenBuffer.isEmpty()) {
    // 如果到最初还有没有被解析完的Token就表明编写的代码有语法错误，须要报错给开发者
    const firstToken = tokenBuffer.peek()
    throw new SyntaxError(`unrecognized token ${firstToken.value}`, firstToken.range.start)
  }

  return rootNode
}

咱们来看一下rootNode的具体内容，如果开发者写了以下的代码：

console.log("Hello World");

会生成上面的AST：

{
  "loc": {
    "start": {
      "line": 1,
      "column": 1
    },
    "end": {
      "line": 1,
      "column": 26
    }
  },
  "type": "STATEMENT_LIST",
  "statements": [
    {
      "loc": {
        "start": {
          "line": 1,
          "column": 1
        },
        "end": {
          "line": 1,
          "column": 26
        }
      },
      "type": "EXPRESSION_STATEMENT",
      "expression": {
        "loc": {
          "start": {
            "line": 1,
            "column": 1
          },
          "end": {
            "line": 1,
            "column": 26
          }
        },
        "type": "CALL_EXPRESSION",
        "callee": {
          "loc": {
            "start": {
              "line": 1,
              "column": 1
            },
            "end": {
              "line": 1,
              "column": 11
            }
          },
          "type": "MEMBER_EXPRESSION",
          "object": {
            "loc": {
              "start": {
                "line": 1,
                "column": 1
              },
              "end": {
                "line": 1,
                "column": 7
              }
            },
            "type": "IDENTIFIER",
            "name": "console"
          },
          "property": {
            "loc": {
              "start": {
                "line": 1,
                "column": 9
              },
              "end": {
                "line": 1,
                "column": 11
              }
            },
            "type": "IDENTIFIER",
            "name": "log"
          }
        },
        "arguments": [
          {
            "loc": {
              "start": {
                "line": 1,
                "column": 13
              },
              "end": {
                "line": 1,
                "column": 25
              }
            },
            "type": "STRING_LITERAL",
            "value": "Hello World"
          }
        ]
      }
    }
  ]
}

小结

在本篇文章中我介绍了什么是语法解析，以及给大家入门了畛域专用语言的一些基本知识，最初解说了Simple语言是如何利用外部DSL来实现其语法解析机制的。

在下一篇文章中我将会为大家介绍Simple语言的运行时是如何实现的，会包含闭包如何实现以及this绑定等内容，大家敬请期待！

集体技术动静

文章首发于我的博客平台

欢送关注公众号进击的大葱一起学习成长

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章