用两百行_JavaScript_创造你自己的编程语言

解析器是一种超级有用的软件库。从概念上简单的说,它们的实现很有挑战性,并且在计算机科学中经常被认为是黑魔法。在这个系列的博文中,我会向你们展示为什么你不需要成为哈利波特就能够精通解析器这种魔法。但是为了以防万一带上你的魔杖吧!

我们将探索一种叫做 Ohm 的新的开源库,它使得搭建解析器很简单并且易于重用。在这个系列里,我们使用 Ohm 去识别数字,构建一个计算器等等。在这个系列的最后你将已经用不到 200 行的代码发明了一种完整的编程语言。这个强大的工具将让你能够做到一些你可能过去认为不可能的事情。

为什么解析器很困难?

解析器非常有用。在很多时候你可能需要一个解析器。或许有一种你需要处理的新的文件格式,但还没有人为它写了一个库;又或许你发现了一种古老格式的文件,但是已有的解析器不能在你的平台上构建。我已经看到这样的事发生无数次。 Code 在或者不在, Data 就在那里,不增不减。

从根本上来说,解析器很简单:只是把一个数据结构转化成另一个。所以你会不会觉得你要是邓布利多校长就好了?

解析器历来是出奇地难写,所面临的挑战是绝大多数现有的工具都很老,并且需要一定的晦涩难懂的计算机科学知识。如果你在大学里上过编译器课程,那么课本里也许还有从上世纪七十年传下来的技术。幸运的是,解析器技术从那时候起已经提高了很多。

典型的,解析器是通过使用一种叫作形式语法formal grammar的特殊语法来定义你想要解析的东西来创造的,然后你需要把它放入像 Bison 和 Yacc 的工具中,这些工具能够产生一堆 C 代码,这些代码你需要修改或者链接到你实际写入的编程语言中。另外的选择是用你更喜欢的语言亲自动手写一个解析器,这很慢且很容易出错,在你能够真正使用它之前还有许多额外的工作。

想像一下,是否你关于你想要解析的东西的语法描述也是解析器?如果你能够只是直接运行这些语法,然后仅在你需要的地方增加一些挂钩hook呢?那就是 Ohm 所可以做到的事。

Ohm 简介

Ohm 是一种新的解析系统。它类似于你可能已经在课本里面看到过的语法,但是它更强大,使用起来更简单。通过 Ohm, 你能够使用一种灵活的语法在一个 .ohm 文件中来写你自己的格式定义,然后使用你的宿主语言把语义加入到里面。在这篇博文里,我们将用 JavaScript 作为宿主语言。

Ohm 建立于一个为创造更简单、更灵活的解析器的多年研究基础之上。VPRI 的 STEPS program (pdf) 使用 Ohm 的前身 Ometa 为许多特殊的任务创造了专门的语言(比如一个有 400 行代码的平行制图描绘器)。

Ohm 有许多有趣的特点和符号,但是相比于全部解释它们,我认为我们只需要深入其中并构建一些东西就行了。

解析整数

让我们来解析一些数字。这看起来会很简单,只需在一个文本串中寻找毗邻的数字,但是让我们尝试去处理所有形式的数字:整数和浮点数、十六进制数和八进制数、科学计数、负数。解析数字很简单,正确解析却很难。

亲自构建这个代码将会很困难,会有很多问题,会伴随有许多特殊的情况,比如有时会相互矛盾。正则表达式或许可以做的这一点,但是它会非常丑陋而难以维护。让我们用 Ohm 来试试。

用 Ohm 构建的解析器涉及三个部分:语法grammar、语义semantics和测试tests。我通常挑选问题的一部分为它写测试,然后构建足够的语法和语义来使测试通过。然后我再挑选问题的另一部分,增加更多的测试、更新语法和语义,从而确保所有的测试能够继续通过。即使我们有了新的强大的工具,写解析器从概念上来说依旧很复杂。测试是用一种合理的方式来构建解析器的唯一方法。现在,让我们开始工作。

我们将从整数开始。一个整数由一系列相互毗邻的数字组成。让我们把下面的内容放入一个叫做 grammar.ohm 的文件中:

  1. CoolNums   {
  2. // just a basic integer
  3. Number   =  digit +
  4. }

这创造了一条匹配一个或多个数字(digit)叫作 Number 的单一规则。+ 意味着一个或更多,就在正则表达式中一样。当有一个或更多的数字时,这个规则将会匹配它们,如果没有数字或者有一些不是数字的东西将不会匹配。“数字(digit)”的定义是从 0 到 9 其中的一个字符。digit 也是像 Number 一样的规则,但是它是 Ohm 的其中一条构建规则因此我们不需要去定义它。如果我们想的话可以推翻它,但在这时候这没有任何意义,毕竟我们不打算去发明一种新的数。

现在,我们可以读入这个语法并用 Ohm 库来运行它。

把它放入 test1.js:

  1. var  ohm  =   require ( 'ohm-js' );
  2. var  fs  =   require ( 'fs' );
  3. var   assert   =   require ( 'assert' );
  4. var  grammar  =  ohm . grammar ( fs . readFileSync ( 'src/blog_numbers/syntax1.ohm' ). toString ());

Ohm.grammar 调用将读入该文件并解析成一个语法对象。现在我们可以增加一些语义。把下面内容增加到你的 JavaScript 文件中:

  1. var  sem  =  grammar . createSemantics (). addOperation ( 'toJS' ,   {
  2. Number :   function ( a )   {
  3. return  parseInt ( this . sourceString , 10 );
  4. }
  5. });

这通过 toJS 操作创造了一个叫作 sem 的语法集。这些语义本质上是一些对应到语法中每个规则的函数。每个函数当与之相匹配的语法规则被解析时将会被调用。上面的 Number 函数将会在语法中的 Number 规则被解析时被调用。语法grammar定义了在语言中这些代码是什么,语义semantics定义了当这些代码被解析时应该做什么。

语义函数能够做我们想做的任何事,比如打印出故障信息、创建对象,或者在任何子节点上递归调用 toJS。此时我们仅仅想把匹配的文本转换成真正的 JavaScript 整数。

所有的语义函数有一个内含的 this 对象,带有一些有用的属性。其 source 属性代表了输入文本中和这个节点相匹配的部分。this.sourceString 是一个匹配输入的串,调用内置在 JavaScript 中的 parseInt 函数会把这个串转换成一个数。传给 parseInt 的 10 这个参数告诉 JavaScript 我们输入的是一个以 10 为基底(10 进制)的数。如果少了这个参数, JavaScript 也会假定以 10 为基底,但是我们把它包含在里面因为后面我们将支持以 16 为基底的数,所以使之明确比较好。

#Java工程师##运维工程师##前端工程师##算法工程师#
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务