有了这个神器，每个人都可以轻松地发明新语言

95 views
Skip to first unread message

Simeon Chaos

unread,
Jan 10, 2014, 7:25:26 AM1/10/14
to cno...@googlegroups.com
一直以来，设计程序语言是一项复杂的工作。因为传统上这项任务需要我们理解深奥的编译理论和技术，而其中最关键，也很困难的部分则是定义新语言的规则及其解析。为了解决这个难题，出现了很多的理论、技术和工具。这些工具大致可以分为两大类：一类是编译器产生器，一类是为方便手动编写解析程序而提供一个程序库。

编译器产生器一般基于某种类型的形式语言，根据给定的词法分析器和解析器规则产生目标编译程序。这类工具强的方面是它们能够为自己所支持的形式语言类型产生最高效的编译程序，依据形式语言的特点，一般可以确保线性时间复杂度。常见的分为三种类型：LR技术，LL系列，PEG系列。LR系列语言具有移近归约、自底向上，最右派生等技术特征，它们只能支持LR语言，更准确的说主要是LAIR变种，再加上某些针对运算符优先级做出的特殊处理。其中最知名的当属lex/yacc以及众多的后续变种（比如bison，jison（javascript语言），ply（python lex/yacc）等等）。LL系列形式语言具有自顶向下，递归下降，最左派生等技术特征，虽然概念上比LR语言更容易理解，但是因为所覆盖的语言相对更少，因此并不如lex/yacc应用普遍。代表性产品是antlr。PEG系列指的是基于解析表达式文法设计的编译器产生器。peg是近年来随着解析器技术研究深入而新出现的一类特别适合解析的文法，目前也已经有很多工具出现。最常见的算法是基于论文packrat parsing paper的实现。如rats, ometa(有很多版本，如ometa/squeak, ometa-js, pyMeta等）, python下的pyPEG, javascript下的peg.js, ruby下的treetop和citrus等等。

不管是哪一类型的编译器产生器，其使用方法都是我们为这些工具设计规则，然后它们再生成编译程序。这带来几个方面的困难。第一、它们产生的目标程序是基于状态转移、涉及到栈的处理，难以理解、调试和修改。第二、我们必须理解这些工具所基于的编译理论和技术中涉及到的诸多抽象概念。第二，这些工具所用的规则实际上是一种领域特定语言，本身表达能力有限，而同时我们又必须先理解和熟悉这种新语言才能设计规则。第三、我们必须将某些处理（抽象语法树的构造，语义，错误报告与处理等等）用产生器的目标语言（目标编译程序本身所用的语言）嵌入其中。这几个方面的困难使大多数程序员无法方便地使用这一类工具。
    
与此同时，技术界也一直在追求能够更轻松而灵活地编写规则和解析器的方法。这类方法产生的工具大多数可以归类为组合式解析程序库，也有一部分基于peg文法的程序库。利用这类程序库，程序员可以用自己日常所用的通用语言来设计新的语言，解析文本，因此用途更加广阔。这方面的代表作品以haskell语言下的parsec最为成熟和强大。但是因为haskell过于学院派的关系，并没有普遍流行开来。c++语言下有boost phoenix库，大概因为依赖于c++模板这一高级语言技术的原因，也没有被广泛使用。python语言下产生了众多的工具，代表性的比如pyparsing，用户非常多。针对具体问题，也有很多的应用并没有使用任何工具或程序库，而是手动编写了整个解析程序，比如cpython的实现，javascript下的esprima等等。 然而，遗憾的是，文法和解析中两个明显的难点在上述这些工具中一直没有得到很好的解决：首先是左递归文法，因为左递归将导致函数的无条件无限递归。第二是解析的效率。为了得到线性的时间复杂度，我们在任何位置应该只对同样的语法成分只做一次解析。为了实现后者，对解析结果进行是必要的。同时，解析器还需要考虑结合进行抽象语法树的产生、语义处理、错误处理等工作，而这些库或者回避了某些问题（左递归在组合式程序库中被普遍回避了），或者为了解决这些问题而使得程序非常复杂、难以理解、使用、修改和扩展。

从上面的介绍可以看到，解析是一项非常普遍的编程需求，同时又具有非常高的技术难度，因此产生了众多的理论、技术和工具，从文后的列表可以看到，这方面的各种技术论文、代码和工具简直可以用汗牛充栋来形容，但是依然没有达到理想的效果。

peasy的出现，第一次完整而优雅地解决了上述所有问题。可以说peasy一方面最为简单而优雅，同时又具有最强大的能力和适应性，并且也不需要牺牲速度和效率。其特征如下：
第一：peasy首次在递归下降手动编写解析器方法下简单而完整地解决了左递归问题，包括直接左递归和间接左递归。全部用于处理左递归的代码只有一个函数（在coffeescript下只有20行代码）。
第二：peasy允许程序员直接使用通用的编程语言编写解析器，同时解析程序又和输入给解析器产生器的语法规则相类似，既简洁又可读，容易修改和扩展。
第三：peasy简单灵活的缓存机制可以提高解析效率，对于线性时间复杂度的文法，我们可以通过缓存保持解析程序的线性时间复杂度。对于复杂的文法和数据，我们也可以通过缓存机制提高时间效率，可以避免象某些解析算法一样，虽然通用，但是却保持着指数、立方或者平方时间复杂度。peasy的缓存实现也非常简单，只有一个函数（coffeescript下只有十行代码）。
第四：整个peasy的实现非常简单。cofeescript下只有两百多行代码。概念上也很简单。只有两种部件: 直接操作数据和指针的匹配器和产生匹配器的组合器。而匹配器和组合器实质上只不过是普通函数。同时，peasy自身的实现除了左递归和缓存处理函数之外，其它所谓匹配器和组合器都很简单，一般只有几行代码，实际上只不过演示了一种方法，是程序员编写其它解析函数的范例，是可以根据具体需求删除、修改和替换的。

实际上，可以不把peasy看作一个程序库或者一个工具，而是将其看作一种亲自编写解析器的方法和范例。这样将能够更大程度地发挥peasy方法的威力。

peasy提供了具体的实例支持上述论断。最明显的实例是，常见的编程语言都为了适应编译器工具而修改它们的文法以避免左递归。比如python的文法(http://docs.python.org/2/reference/grammar.html)，javascript的文法（http://www-archive.mozilla.org/js/language/grammar14.html）,而通过用peasy，所有的二元运算表达式都可以浓缩为一条简单的左递归规则，不必进行左递归消除。对表达式解析，为了进一步提高时间效率，peasy另外还提供了一个范例，对具有很多不同优先级的运算，该范例可以跳过调用栈，直接将优先级最高的常数直接解析为最终的表达式，而不是象目前常见的做法一样，书写象如下的规则：or -> (or || and) | and; ...; add -> add + mul | mul; mul -> mul * atom | atom。难得的是，peasy在实现这些表达能力的增强的同时还可以保证线性时间复杂的的解析过程。至于peasy是如何实现上述结果的，大家可以到我在github的peasy项目一睹究竟(https://github.com/chaosim/peasy)。

以下两个链接是我最开始获得灵感开始编写peasy的时候发布的帖子。因为有其它项目的影响，中间中断了一些时间。前不久根据项目的需要我将peasy运用到了自己的项目当中，同时进一步优化了peasy的api，现在已经非常简单优雅了，朕很满意:) 至于最关键的左递归和缓存算法，经受住了后续实例的考验，暂时没有任何改变。同时，这些实例也继续证明了peasy的优点。

最后，我需要提一下语言对思维的影响：如果不是在使用coffeescript语言，估计我很难有peasy相关的这些创意。coffeescript的函数记法，以及它从javascript继承来的“赋值是表达式”的语法特点，使得文法特别简洁可读。在python中也可以先实现类似的结果，需要经过一些曲折，而非自然而然产生。其它动态语言应该也没有太大的障碍，但是都比不上coffeescript的优雅。对比一下peasy中coffeescript的代码和编译产生的javascript代码，体现得很明显。

中文


lr文法

LL文法


左递归


peg和packrat

phoenix 

ometa：
Alessandro Warth 在他的博士论文中首次提出了一种针对peg文法的支持左递归规则解析的方法。
我在有了我的算法思路之后，我搜索到了他的论文，仔细研究之后，我发现我的算法和他的算法实际上非常类似。
Memoization in Top-Down Parsing：缓存机制在自顶向下解析中的应用，实现了左递归和间接左递归。


python下的解析器

解析javascript的解析器

Zoom.Quiet

unread,
Jan 10, 2014, 7:51:15 AM1/10/14
to cno...@googlegroups.com
这个可是以后各种内置 DSL 的快速构建神器!
值得收!
> --
> 您收到此邮件是因为您订阅了 Google 网上论坛的“cnodejs”论坛。
> 要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 cnodejs+u...@googlegroups.com。
> 要查看更多选项，请访问 https://groups.google.com/groups/opt_out。



--
人生苦短, Pythonic! 冗余不做,日子甭过!备份不做,十恶不赦!
KM keep growing environment culture which promoting organization be learnning!
俺: http://zoomquiet.io
许: http://creativecommons.org/licenses/by-sa/2.5/cn/
Reply all
Reply to author
Forward
0 new messages