手摸手实现一个编译器（上）
认识 PEG.js
PEG.js 是一个简单的 JavaScript 解析器生成器，可以生成具有出色错误报告的快速解析器。您可以使用它来处理复杂的数据或计算机语言，并轻松构建转换器、解释器、编译器和其他工具。
我们先简单了解解释器和编译器的定义：
解释器（
interpreter）是一种计算机程序，能够把解释型语言解释执行。解释器就像一位“中间人”。解释器逐行边解释边执行，因此依赖于解释器的程序运行速度比较缓慢。解释器的好处是它不需要重新编译整个程序，从而减轻了每次程序更新后编译的负担。 编译器（compiler）是一种计算机程序，它会将某种编程语言写成的源代码（原始语言）转换成另一种编程语言（目标语言）。
二者的区别主要有：
- 编译器将一个程序作为一个整体进行翻译，而解释器则是一行一行地翻译；
- 在编译器的情况下生成中间代码或目标代码。而解释器不创建中间代码；
- 编译器比解释器要快得多，因为编译器一次完成整个程序，而解释器则是依次编译每一行代码；
- 由于要生成目标代码，编译器比解释器需要更多的内存；
- 在编译器中，当程序中出现错误时，它会停止翻译，并在删除错误后重新翻译整个程序。相反，当解释器中发生错误时，它会阻止其翻译，在删除错误后，翻译将继续；
- 编译器用于编程语言，如
c、c++、c#、Scala等。另一个解释器用于PHP、Ruby、Python、JavaScript等语言。
How?
PEG.js 可用于 node 和浏览器环境，安装就跟普通的包没有任何区别：
# 通过 CLI 去生成编译器
npm install -g pegjs
# 通过 JavaScript API 去生成编译器时选择本地安装，因为你要引入包
npm install pegjs
本文就只演示 CLI 去生成编译器的用法，JavaScript API 在官方文档中有说明，参数都是一致的。新建一个 simple-arithmetics.pegjs 文件，写入官方 DEMO 的规则：
// Simple Arithmetics Grammar
// ==========================
//
// Accepts expressions like "2 * (3 + 4)" and computes their value.
Expression
= head:Term tail:(_ ("+" / "-") _ Term)* {
return tail.reduce(function(result, element) {
if (element[1] === "+") { return result + element[3]; }
if (element[1] === "-") { return result - element[3]; }
}, head);
}
Term
= head:Factor tail:(_ ("*" / "/") _ Factor)* {
return tail.reduce(function(result, element) {
if (element[1] === "*") { return result * element[3]; }
if (element[1] === "/") { return result / element[3]; }
}, head);
}
Factor
= "(" _ expr:Expression _ ")" { return expr; }
/ Integer
Integer "integer"
= _ [0-9]+ { return parseInt(text(), 10); }
_ "whitespace"
= [ \t\n\r]*
然后执行以下命令：
pegjs simple-arithmetics.pegjs
就会在当前目录下生成一个 simple-arithmetics.js 文件：
/*
* Generated by PEG.js 0.10.0.
*
* http://pegjs.org/
*/
"use strict";
function peg$subclass(child, parent) {
function ctor() { this.constructor = child; }
ctor.prototype = parent.prototype;
child.prototype = new ctor();
}
function peg$SyntaxError(message, expected, found, location) {
// ...
}
peg$subclass(peg$SyntaxError, Error);
peg$SyntaxError.buildMessage = function(expected, found) {
// ...
};
function peg$parse(input, options) {
// ...
}
module.exports = {
SyntaxError: peg$SyntaxError,
parse: peg$parse
};
省略了大部分核心代码，看下输出代码的结构，用 CJS 导出了 parse 和 SyntaxError 函数。我们再新建一个 test.js 文件引用这个编译器去解析我们的表达式：
const { parse } = require('./simple-arithmetics')
console.log(parse('2*(3+4)')) // 14
到这里，一个支持简单算术运算的编译器就完成了。我们先在解读具体的语法和词法解析前，先来了解一下输出编译器的参数：
--allowed-start-rules
默认值以 Grammer 第一条规则作为起始解析。参数格式是数组，在 CLI 中用 , 连接多个规则开头名称，举个例子，我们有一下的 Grammer 定义：
middle
= end '*'
start
= [a-z] middle
end
= [1-9]
如果我们生成 parser 不传 --allowed-start-rules 时，即直接执行下面命令：
pegjs ./simple-arithmetics.pegjs
那么生成的解析器会以 middle 作为语法入口，我们测试一下：
const { parse } = require('./simple-arithmetics')
console.log(parse('1*')) // [ '1', '*' ]
console.log(parse('a1*')) // peg$SyntaxError: Expected [1-9] but "a" found.
可以看出，解析是从第一行开始的（即 middle 规则）。如果想要达到我们的预期，比如 start-middle-end 顺序，那么我们可以加上 --allowed-start-rules 参数并且指定 start：
pegjs --allowed-start-rules start ./simple-arithmetics.pegjs
生成的解析器再来解析上述代码：
const { parse } = require('./simple-arithmetics')
// ⚠️ 这里的顺序跟上面有区别，因为解析失败之后会throw Error，所以正确的语法提上来
console.log(parse('a1*')) // [ 'a', [ '1', '*' ] ]
console.log(parse('1*')) // peg$SyntaxError: Expected [a-z] but "1" found.
--cache
让解析器缓存解析结果，优化性能。
--dependency
指定解析器的外部依赖。比如指定了 --dependency ast:./ast.js ，那么生成的解析器中就会引入 ast.js 文件，你可以使用模块中的导出的任意方法。
--export-var
当没有检测到模块加载器时解析器对象被分配到的全局变量的名称。
--extra-options
指定传给 peg.generate 函数的参数。
--extra-options-file
如果参数太多，在 CLI 中输入确实很不方便，也不够直观。这时通过指定一个 JSON 格式的文件作为 peg.generate 参数。
--format
指定生成器的格式，支持 amd、commonjs、globals、umd，其中 commonjs 是默认值。
--optimize
在优化生成的解析器的解析速度 ( speed) 或代码大小 ( size) 之间进行选择（默认值： speed）
--plugin
指定 PEG.js 使用具体的插件。
--trace
配置这个参数之后，支持让解析器在解析的过程中显示详细的进度。
编译参数用的不多，简单了解一下即可。
语法和语义
下面我们来解读一下官方的算术解析，从而认识语法和语义和一些表达式的使用。
// Simple Arithmetics Grammar
// ==========================
//
// Accepts expressions like "2 * (3 + 4)" and computes their value.
Expression
= head:Term tail:(_ @("+" / "-") _ @Term)* {
return tail.reduce(function(result, element) {
if (element[0] === "+") return result + element[1];
if (element[0] === "-") return result - element[1];
}, head);
}
Term
= head:Factor tail:(_ @("*" / "/") _ @Factor)* {
return tail.reduce(function(result, element) {
if (element[0] === "*") return result * element[1];
if (element[0] === "/") return result / element[1];
}, head);
}
Factor
= "(" _ @Expression _ ")"
/ Integer
Integer "integer"
= _ [0-9]+ { return parseInt(text(), 10); }
_ "whitespace"
= [ \t\n\r]*
首先，定义了 5 个规则，每个规则都有自己的名称（比如 Expression 即表达式）和对应的解析表达式。输入文本如果匹配上了表达式，就会执行后面的 JS 函数。像 Integer "integer" 还有明确的错误消息，啥意思呢？举个例子：
middle "middle"
= end '*'
start
= [a-z] middle
end
= [1-9]
基于上述规则生成一个 parser 去解析 "a1!"，我们获取的错误信息是：
peg$SyntaxError: Expected middle but "1" found.
上述这个 Expected middle 就是我们设置的可读的错误信息。如果去掉 middle，那么就会报下面的错误：
peg$SyntaxError: Expected "*" but "!" found.
这也是 PEG.js 的特性之一，它能准确的给出匹配表达式的错误。为了更好地学习表达式类型，上述算术的 Grammer 可能不太合适，接下来我们一起来看另外一个例子——解析 JSON串：
// JSON Grammar
// ============
//
// Based on the grammar from RFC 7159 [1].
//
// Note that JSON is also specified in ECMA-262 [2], ECMA-404 [3], and on the
// JSON website [4] (somewhat informally). The RFC seems the most authoritative
// source, which is confirmed e.g. by [5].
//
// [1] http://tools.ietf.org/html/rfc7159
// [2] http://www.ecma-international.org/publications/standards/Ecma-262.htm
// [3] http://www.ecma-international.org/publications/standards/Ecma-404.htm
// [4] http://json.org/
// [5] https://www.tbray.org/ongoing/When/201x/2014/03/05/RFC7159-JSON
// ----- 2. JSON Grammar -----
// value 的表达式是任意空格加value，处理函数直接返回value
// 函数体内的 value 是表达式 value:value 的前者，后者从其他规则中获取
JSON_text
= ws value:value ws { return value; }
begin_array = ws "[" ws
begin_object = ws "{" ws
end_array = ws "]" ws
end_object = ws "}" ws
name_separator = ws ":" ws
value_separator = ws "," ws
// ws 有一个别名 whitespace，在报错时更加语义化
ws "whitespace" = [ \t\n\r]*
// ----- 3. Values -----
// 表达式的 / 表示优先匹配 false
// 匹配不成功就匹配 null
// 再不成功就匹配 true
// ...依次匹配
// 匹配到 string 都没有匹配成功就认为失败
value
= false
/ null
/ true
/ object
/ array
/ number
/ string
// 如果是以下字符串，则会做去字符串化
false = "false" { return false; }
null = "null" { return null; }
true = "true" { return true; }
// ----- 4. Objects -----
// 匹配对象，优先匹配一个 {
// 内部结构体也就是 members 的匹配表达式是
// 先是一个 member，即 {name: "xx", value: "yy"} 结构
// 然后 * 表示匹配 0 或多次，就是说 {name: "xx", value: "yy"},{name: "xx2", value: "yy2"} 匹配多次
// 然后调用函数去转成 { "xx": "yy", "xx2": "yy2" } 的结构
// 再接下来就是一个 ?，表示尝试匹配表达式。如果匹配成功，返回匹配结果，否则返回null。与正则表达式不同，没有回溯。
// 最后就是 }
// 整个表达式再做 members 是否为空的判断，是的话置为 {}
object
= begin_object
members:(
head:member
tail:(value_separator m:member { return m; })*
{
var result = {};
[head].concat(tail).forEach(function(element) {
result[element.name] = element.value;
});
return result;
}
)?
end_object
{ return members !== null ? members: {}; }
// 对象中的成员的匹配表达式，举例如： “name”: "小余"
// 一个字符串 + : + 一个 value 值
// 最后返回 {name, value} 的结构
member
= name:string name_separator value:value {
return { name: name, value: value };
}
// ----- 5. Arrays -----
// 匹配数组的表达式 [1, 2, 3, a, b, c, {a: 1}]
// 先是一个 [
// 紧接着匹配类型是 value 的 head
// 然后匹配多次 :
array
= begin_array
values:(
head:value
tail:(value_separator v:value { return v; })*
{ return [head].concat(tail); }
)?
end_array
{ return values !== null ? values : []; }
// ----- 6. Numbers -----
// 匹配数字
// 如果有 - 号，负数情况
// 整数
// 小数点
// 指数位
// 返回匹配文本
number "number"
= minus? int frac? exp? { return parseFloat(text()); }
// 小数点
decimal_point
= "."
digit1_9
= [1-9]
// 指数标记、e或者E
e
= [eE]
// 指数位
exp
= e (minus / plus)? DIGIT+
// 小数位
frac
= decimal_point DIGIT+
// 整数，0 或者 1-9 再匹配 0-9 零次或多次
int
= zero / (digit1_9 DIGIT*)
// 减号
minus
= "-"
// 加号
plus
= "+"
// 匹配 0
zero
= "0"
// ----- 7. Strings -----
// 匹配字符串
// 双引号
// 零次或多次字符
// 双引号
// 返回将匹配到的 chars 结果拼接成字符串
string "string"
= quotation_mark chars:char* quotation_mark { return chars.join(""); }
// 匹配字符
// 所有非转义字符、分隔符
char
= unescaped
/ escape
sequence:(
'"'
/ "\\"
/ "/"
/ "b" { return "\b"; }
/ "f" { return "\f"; }
/ "n" { return "\n"; }
/ "r" { return "\r"; }
/ "t" { return "\t"; }
/ "u" digits:$(HEXDIG HEXDIG HEXDIG HEXDIG) {
return String.fromCharCode(parseInt(digits, 16));
}
)
{ return sequence; }
// 转义字符
escape
= "\\"
// 双引号
quotation_mark
= '"'
// https://regex101.com/r/EAogfy/1
// 非转义字符
unescaped
= [^\0-\x1F\x22\x5C]
// ----- Core ABNF Rules -----
// See RFC 4234, Appendix B (http://tools.ietf.org/html/rfc4234).
DIGIT = [0-9]
// 十六进制
HEXDIG = [0-9a-f]i
上述 Grammer 基本覆盖了文档中 80% 以上的解析表达式类型。我们从上到下开始看：
"literal" | 'literal'
双引号或者单引号括起来的字面量都表示精确匹配，比如：
begin_array = ws "[" ws
数组的开头匹配是 [，当然前后可以有空格。
expression1 / expression2 / ... / expressionn
// 表达式的 / 表示优先匹配 false
// 匹配不成功就匹配 null
// 再不成功就匹配 true
// ...依次匹配
// 匹配到 string 都没有匹配成功就认为失败
value
= false
/ null
/ true
/ object
/ array
/ number
/ string
JSON 的值可以是上述这些规则，⚠️ 这里是有顺序的。前面的匹配不成功，才会匹配下一个。
expression { action }
这个就基本都会用上了，比如：
false = "false" { return false; }
字符串中包含 "false"，则会返回布尔值的 false。{ ... } 内的就是 JavaScript 代码，获取匹配结果，这里就做任何的转换操作。函数体内有四个可以调用的函数：
text：匹配表达式的文本内容；expected：使解析器抛出异常，支持两个参数，分别是对当前位置预期内容的描述和可选的位置信息；error：同样是使解析器抛出异常，支持两个参数，分别是错误消息和可选的位置信息；location：返回位置信息，如下所示的对象：
{
start: { offset: 23, line: 5, column: 6 },
end: { offset: 25, line: 5, column: 8 }
}
expression1 expression2 ... expressionn
frac
= decimal_point DIGIT+
举个例子，比如 '.123' 匹配 frac 规则后，会返回 ['.', '123'] 数组。
label : expression
label 表达式也基本会用上，label 的值能够在函数体内去获取表达式。
member
= name:string name_separator value:value {
// name 是 name:string 中的 label
// value 是 value:value 中前面的 value 即 label 值，后面的 value 是规则中的 value
return { name: name, value: value };
}
expression ?
尝试匹配表达式。如果匹配成功，返回匹配结果，否则返回null。与正则表达式不同，没有回溯。
// ----- 6. Numbers -----
// 匹配数字
// 如果有 - 号，负数情况
// 整数
// 小数点
// 指数位
// 返回匹配文本
number "number"
= minus? int frac? exp? { return parseFloat(text()); }
到这里就把 PEG.js 中才有的表达式结合 json.pegjs 过了一遍，了解完它们的基本用法。至于其他的匹配比如 [characters]、(expression)、expression *等在正则中都有接触过，这里就不展开举例说明了。
总结
先是了解完解释器和编译器的定义以及它们的区别，让我们知道了 PEG.js 是一个 JavaScript 的解析器生成器。然后学习了它生成编译器的过程及参数，经常用到的参数比如 --allow-start-rules 、--dependency 等做了详细的举例说明。最后基于 json.pegjs 去详细分析了解析表达式的用法。
总而言之，写一个编译器，无非就 3 件事：
- 基于输入字符串做解析表达式匹配（正则匹配）；
- 基于生成的结果做转换；
- 输出结果；
PEG.js 只是简化了我们去执行上述动作的流程。站在巨人的肩膀上，下篇文章我们就来实现一个自己的编译器。
腾讯云开发者
