前言
在上一篇文章中我为大家介绍了 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 绑定 等内容，大家敬请期待！
集体技术动静
文章首发于我的博客平台
欢送关注公众号 进击的大葱 一起学习成长