编译原理与PEG.js

编译原理

这学期开始上编译原理这门课，比较纳闷的一点是老师要求用 Java。作为一个想学好编译原理的 Java 黑，自然要寻找另一门可以进行实践的语言，编译在 JavaScript 中应用非常广泛，几乎所有主流的语言都可以编译到 JavaScript，Babel 编译 ES6 到 ES5，以及 CofferScript, TypeScript, JSX 等等编译为 JavaScript。另外，JavaScript 作为一门函数第一公民的语言，我想用来做编译也是特别方便的。一开始看了 Jison，感觉还是挺简单的，不过现在貌似流行 PEG.js，老实说我并不知道他们区别，我还只是一个初学者，或者初学者也算不上，因为最近一个月根本没好好听课 =.=

解析表达式

在了解 PEG.js 之前有必要先了解下 PEG（解析表达文法），以及它与 CFG（上下文无关文法）的区别。以下摘选维基百科上面关于解析表达式的解释

解析表达文法里面的每一个非终结符本质上表示递归下降解析器里面的一个解析函数，其对应的解析表达式展示了这个函数包含的代码内容。概念上，每一个解析函数接受一个输入字符串作为参数，返回以下其中一个结果:

• 成功，函数可能向前移动或者“消耗”一个或多个输入字符串的字符
• 失败，不消耗任何字符

一个非终结符有可能成功但是不消耗任何输入字符，这也是一种不同于失败的结果。

只由一个终结符组成的原子解析表达式：成功，如果输入字符串的第一个字符就是定义中的终结符，这种情况下消耗这个输入字符；否之失败。由空字符串组成的原子解析表达式总是成功并且不消耗任何输入。只由一个非终结符A组成的原子解析表达式表示对非终结符A的解析函数的递归调用。

序列操作符 e1e2 首先调用 e1， 如果 e1成功， 接着对 e1 消耗剩下的输入字符串调用 e2， 最后返回结果。如果 e1 或者 e2 失败，那么序列表达式 e1e2 失败。

选择操作符 e1 / e2 首先调用 e1， 如果 e1成功， 立刻返回结果。否则如果 e1 失败，选择操作符回溯到输入字符串匹配 e1 的原始位置，调用 e2， 最后返回 e2 结果。

零个或多个，一个或多个，和可选操作符分别消耗零个或多个，一个或多个，或者零个或一个连续重复的子表达式e。与上下文无关文法和正则表达式不同的 是，尽管如此，在PEG里这些操作符总是执行贪婪的行为，那就是消耗尽可能多的输入，而且绝对不回溯。（正则表达式一开始执行贪婪匹配，但是如果整个正则表达式失败后，会回退并尝试短一些的匹配。）例如，解析表达式a总是尽可能多的消耗输入字符串中连续出现的a，解析表达式(a a)则必然会失败因为前半部分a*绝对不会留下一丁点a给后半部分去匹配。

最后，肯定断言和否定断言实现了句法断言。&e 表达式调用子表达式e，如果e成功，则返回成功；否则返回失败。无论结果如何都不消耗任何字符。反之，当e失败时！e 表达式成功，e成功时！e 表达式失败， 同样无论结果如何都不消耗任何字符。因为向前判断的子表达式e 可以任意的复杂，所以断言表达式提供了强大的句法向前判断和去除二义性的能力。

PEG.js

PEG.js 是一个基于 JavaScript 的简单的解析器生成器，它用来生成一个快速且具备完善错误报告的解析器。你可以用它来处理复杂的数据或计算机语言，已经轻松的构造变换器，解释器，编译器以及其他的工具。

特性

• 简单和具有表现力的语法符号
• 集成了词法分析( lexcial )和语义分析( syntactical )
• 具备优良的错误报告
• 基于解析表达式语法的形式，比传统的 LL(k) 和 LR(k) 解析器更强大
• 可以用于浏览器，命令行，或者通过 JavaScript 的 API

开始

在线版本 是生成一个解析器最简单的方式，只要输入你定义的语法，尝试解析少量的输入，下载生成的解析后的代码。

安装

Node.js

如果要使用 pegj 命令，全局安装 PEG.js

npm install -g pegjs

如果要使用 JavaScript 的 API，本地安装 PEG.js

npm install pegjs

如果你两者都需要，那么两种方式都安装即可

浏览器

下载 PEG.js 库(普通或者压缩的版本) 或者通过 Bower 安装

bower install pegjs

生成一个解析器

PEG.js 根据一个你希望解析的输入的语法以及你指定的返回结果(对匹配的进行语义分析)生成解析器。最后生成解析器本质上只是一个带有一些简单 API 的 JavaScript 对象。

命令行

想要根据你的语法生成一个解析器，使用 pegjs 命令：

pegjs arithmetics.pegjs

这将会把解析器代码写入一个以 ‘.js’ 为扩展名的相同文件名文件中， 你也可以自己指定输出：

pegjs -o arithmetics-parser.js arithmetics.pegjs

如果你省略了输入和输出文件，那么将会使用标准的输入输出

默认下，解析器的生成采用了 Node.js 的模块格式，你可以使用 --format 选项来覆盖。

你可以调整一下几个选项：

• --allowed-start-rules – 逗号相隔的会被用来解析的规则（默认为第一个规则）
• --cache – 让解析器缓存结果，避免在极端情况下出现了指数级的解析时间而降低解析器速度
• --dependency – 给解析器指定依赖（可以多次指定）
• --export-var – 指定一个全局变量名称，当没有进行模块到处时，解析器对象会以该名称命名
• --extra-options – 其他的传递给 peg.generate 的选项（JSON 格式）
• --extra-options-file – 同上，只不过选项保存在文件里面
• --format – 指定解析器的到导出格式，如 amd， commonjs，globals，umd（默认: commonjs）
• --optimize – 在优化解析速度（speed）和代码大小（size）之间进行选择（默认：speed）
• --plugin – 让 PEG.js 使用一个指定的插件（可以多次指定）
• --trace – 让解析器跟踪其运行情况

JavaScript API

在 Node.js 中，需要引入 PEG.js 这个模块

var peg = require('pegjs');

在浏览器中，通过 <script> 标签引入 PEG.js 库到你的网页中。如果 PEG.js 使用 AMD 模块化方案，它会把模块定义在一个变量上面，否则他的 API 将会挂载在全局对象 peg 中

为了生成一个解析器，调用 peg.generate 方法并把你的语法作为参数传递进去

var parser = peg.generate("start = ('a'/'b')+");

这个方法会返回解析器对象或者返回源码（取决于你的 output 参数 – 参见下文）。如果语法非法它将抛出错误，错误会包含 message 属性，它携带更详细的错误信息

你可以传入以下选项组成的对象作为 peg.generate 的第二个参数，以下选项是受支持的：

• allowedStartRules – 指定解析器从哪个规则开始解析（默认：语法中的第一个规则）
• cache – 如果为 true，解析器会缓存结果以避免指数级的解析时间影响解析器效率（默认：false）
• dependencies – 解析需要的依赖，它的值为一个变量与依赖模块映射的对象。解析器通过这些变量来使用那些模块。只有当 format 被设置为 amd，commonjs 或者 umd （默认：{}）时才有效。
• exportVar – 一个全局对象名，当没有进行模块导出时，解析器对象会以该名称命名
• format – 生成的解析器的导出格式（”amd”，”bare”，”commonjs”，”globals”，”umd”），只有当 output 设置为 source 时（默认：null）才有效
• optimize – 在优化解析速度（speed）和代码大小（size）之间进行选择（默认：speed）
• output – 如果设置为 parser，这个方法将返回解析器对象；如果设置为 source，它会以字符串的形式返回生成的解析器的源码（默认：parser）
• plugin – 让 PEG.js 使用一个指定的插件（可以多次指定）
• trace – 让解析器跟踪其运行情况

使用解析器

使用生成的解析器的方法十分简单，只要调用它的 parse 方法并把参数作为一个字符串传入即可。该方法会返回解析的结果（确切的值取决于你的生成该解析器的语法）或者抛出错误（如果你的输入非法）。抛出的错误信息带有 location，expected，found 以及包含更多错误信息的 message

parser.parse("abba");		// returns ["a", "b", "b", "a"]
parser.parse("abcd");		// throws an exception

你还可以通过传入第二个参数来调整解析行为，该参数是一个支持以下可选项的对象：

• startRule – 从这个规则开始解析
• tracer – 追踪解析行为

解析器也支持你自定义的选项

句法和语义

PEG.js 的句法不是面向行的，并且会忽略标记（token）之间的空白，这一点和 JavaScript 相似。你也可以使用 JavaScript 风格的注释（//... 和 /*...*/）

让我们看一个简单的可以识别形如 2*(3+4) 这样的表达式的语法。根据这个语法生成的解析器可以计算该表达式的值

start
  = additive

additive
  = left:multiplicative "+" right:additive { return left + right; }
  / multiplicative

multiplicative
  = left:primary "*" right:multiplicative { return left * right; }
  / primary

primary
  = integer
  / "(" additive:additive ")" { return additive; }

integer "integer"
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

在顶层，语法包含了规则（在我们的例子中，有五条规则）。每条规则都由一个名字（例如 integer）来区分它们，并且还有一个解析表达式（例如 digits:[0-9]+ { return parseInt(digits.join(""), 10); }）来定义一个对输入文本的匹配，你还可以在其中包含你的 JavaScript 代码来处理被成功匹配到的文本。规则可以包含别名以便于错误提示（例如上面的例子中，只有 integer 规则具有别名）。解析将从第一条规则，这条规则也叫作 start rule

一个规则名必须是一个 JavaScript 标识符，它后面跟着一个 = 和解析表达式。如果这个规则名有一个别名，它作为一个 JavaScript 字符串书写在规则名和 = 之间。规则之间需要用空格分割开，但在解析表达式后面跟着 ; 也是可以的。

你可以在第一个规则前初始化一些用 {} 闭合的 JavaScript 代码。这些代码会在解析器开始解析之前先执行。在初始化操作中定义的变量名和函数可以在规则操作和语义谓词中直接使用，同时他们也可以直接访问通过 options 传递进来的对象。初始化过程中括号必须严格闭合。比如我们来看一个简单的例子：

{
  function makeInteger(o) {
    return parseInt(o.join(""), 10);
  }
}

start
  = additive

additive
  = left:multiplicative "+" right:additive { return left + right; }
  / multiplicative

multiplicative
  = left:primary "*" right:multiplicative { return left * right; }
  / primary

primary
  = integer
  / "(" additive:additive ")" { return additive; }

integer "integer"
  = digits:[0-9]+ { return makeInteger(digits); }

规则的解析表达式用来匹配输入的文本。这里由好几种类型的表达式 – 匹配字符或字符类，显示可选部分和重复等等。表达式中也可以包含其他规则的引用。详细介绍见下文。

如果一个表达式成功的匹配到了一个输入流的部分文本，它会产生一个匹配结果，这是一个 JavaScript 值。例如：

• 一个匹配字符串的表达式生成一个包含被匹配串的 JavaScript 字符串
• 一个匹配包含子表达式的字符串的表达式生成一个含有全部被匹配项的 JavaScript 数组

当在表达式中使用规则名时，它将递归的解析下去并最终返回全部解析完成的结果

一个特殊的情况是解析表达式是一个解析行为 – 一段 JavaScript 代码包含在 {} 里面。它会处理匹配到的文本串并返回处理的结果，这个值是也被认为是表达式匹配的结果（换句话说，解析行为是对被匹配文本的一个变换器）

在我们的算术例子中由几个解析行为。比如这个表达式 digits:[0-9] + { return parseInt(digits.join(""), 10); }，它处理 [0-9]+ 匹配的结果，这个结果是一个包含匹配的数字字符串组成的数组，它作为参数传入到该后面的行为被拼接成为一个 JavaScript number 对象后返回

解析表达式类型

解析表达式有好几种类型，他们当中可能有些还包含子表达式从而形成一个递归结构

“literal“

‘literal‘

解析表达式会精确匹配字符串并返回，该字符串的句法和 JavaScript 一样。在字符串后面追加 i 使得匹配区分大小写

.

匹配一个字符并作为一个字符串返回

[characters]

从一个集合中匹配一个字符并作为一个字符串返回。集合中的字符可以以和 JavaScript 字符串相同的方式进行转义处理。集合中的字符也可以包含范围（例如 [a-z] 表示匹配一个小写字母）。在字符前面加上 ^ 表示取反（例如：[^a-z] 表示匹配一个非小写字母）。在右括号后面添加 i 可以让匹配区分大小写

rule

递归的匹配一个解析表达式规则并返回匹配的结果

( expression )

匹配一个子表达式并返回匹配的结果

expression *

匹配表达式零次或多次并以数组的形式返回匹配结果。这个匹配是贪婪匹配，即解析器会尽可能的进行多次匹配。不像正则表达式，解析表达式没有回溯

expression +

匹配表达式一次或多次并以数组的形式返回匹配结果。这个匹配是贪婪匹配，即解析器会尽可能的进行多次匹配。不像正则表达式，解析表达式没有回溯

expression ?

尝试匹配表达式，如果匹配成功，返回匹配的结果，否则返回 null。不像正则表达式，解析表达式没有回溯

& expression

尝试匹配表达式，如果匹配成功，只返回 undefined 并且不消耗任何输入，否则认为匹配是失败的

! expression

尝试匹配表达式，如果匹配不成功，只返回 undefined 并且不消耗任何输入，否则认为匹配是失败的

& { predicate }

predicate 是一段 JavaScript 代码，可以理解为是它是在一个函数里面等待执行。它会把前面表达式匹配得到的结果作为它的参数。它通过 return 来返回 JavaScript 值。If the returned value evaluates to true in boolean context，返回 undefined 并且不消耗任何输入，否则认为匹配是失败的

在 predicate 中的代码可以访问初始化时定义的变量和方法

在 predicate 中的代码可以通过调用 location 函数来访问当前位置信息，它会返回一个像下面这样的对象：

{
  start: { offset: 23, line: 5, column: 6 },
  end: { offset: 23, line: 5, colume: 6}
}

start 和 end 都指向当前解析的位置，offset 为一个从 0 开始的偏移值，line 和 column 为从 1 开始的行号和列号

在 pedicate 中的代码可以通过 options 变量来访问解析器被调用时传递进来的选项对象

注意括号必须严格闭合

! { predicate }

predicate 是一段 JavaScript 代码，可以理解为是它是在一个函数里面等待执行。它会把前面表达式匹配得到的结果作为它的参数。它通过 return 来返回 JavaScript 值。If the returned value evaluates to false in boolean context，返回 undefined 并且不消耗任何输入，否则认为匹配是失败的

在 predicate 中的代码可以访问初始化时定义的变量和方法

在 predicate 中的代码可以通过调用 location 函数来访问当前位置信息，它会返回一个像下面这样的对象：

{
  start: { offset: 23, line: 5, column: 6 },
  end: { offset: 23, line: 5, colume: 6}
}

start 和 end 都指向当前解析的位置，offset 为一个从 0 开始的偏移值，line 和 column 为从 1 开始的行号和列号

在 pedicate 中的代码可以通过 options 变量来访问解析器被调用时传递进来的选项对象

注意括号必须严格闭合

$ expression

尝试匹配表达式，如果匹配成功，返回匹配的文本而不是匹配的结果

label: expression

匹配表达式并使用 label 来保存匹配结果，label 必须是一个 JavaScript 符号

符号表达式通常和解析行为一起使用，表达式匹配结果保存在符号中，解析行为通过符号来访问匹配结果

expression_1 expression_2 … expression_n

匹配一连串表达式并把匹配结果作为一个数组返回

expression { action }

匹配表达式，如果匹配成功，则执行表达式，否则认为匹配是失败的

action 是一段 JavaScript 代码，可以理解为是它是在一个函数里面等待执行。它会把前面表达式匹配得到的结果作为它的参数。它通过 return 来返回 JavaScript 值。返回值是匹配的结果。

为了便于查错，action 里面可以调用 expected 函数来让解析器抛出一个错误。这个函数有两个参数，一个描述当前位置预期的结果和可选的当前位置的信息（默认为 location 函数调用返回的结果 – 见下文）。这个描述会作为抛出错误信息的一部分

action 里面也可以调用 error 函数，同样也会让编译器抛出错误。这个函数也由两个参数 – 错误信息和可选的位置信息（默认为 location 函数调用返回的结果 – 见下文）。错误信息将被抛出的错误所使用

action 里面的代码也可以访问语法初始化时的定义的变量和方法。注意必须严格括号闭合

action 里面的代码也可以通过 text 函数来访问前面表达式匹配的字符串

action 里面的代码也可以通过调用 location 函数来访问当前位置信息，它会返回一个像下面这样的对象：

{
  start: { offset: 23, line: 5, column: 6 },
  end: { offset: 25, line: 5, colume: 8}
}

start 执行表达式开始的位置，而 end 指向表达式结束的位置。offset 是从 0 开始的偏移值，line 和 column 是从 1 开始的行数和列数

action 里面的代码可以通过 options 变量来访问解析器被调用时传递进来的选项对象

注意括号必须严格闭合

expression_1 / expression_2 / … / expression_n

尝试匹配第一个表达式，如果没有匹配到，则尝试第二个，以此类推。最后返回第一个匹配成功的表达式匹配的结果。如果没有成功匹配的表达式，则认为匹配失败。

兼容性

解析器生成器和生成的解析器都可以在以下环境中运行：

• Node.js 4+
• Internet Explorer 8+
• Edge
• Firefox
• Chrome
• Safari
• Opera

Development

• Project website
• Wiki
• Source code
• Issue tracker
• Google Group
• Twitter

PEG.js is developed by David Majda (@dmajda). The Bower package is maintained by Michel Krämer (@michelkraemer).

You are welcome to contribute code. Unless your contribution is really trivial you should get in touch with me first — this can prevent wasted effort on both sides. You can send code both as a patch or a GitHub pull request.

Note that PEG.js is still very much work in progress. There are no compatibility guarantees until version 1.0.