解析器组合器中有什么?(2016)

2020-05-29 10:51:54

作为我在Haskell取得进展的持续努力的一部分(这是我2016年的目标之一!),我在edX上关注Erik Meijer的函数式编程MOOC。

第一堂课是非常基础的东西,我很快就学完了。第7课是关于函数解析器和M*(可怕的)。这就是我第一次遇到困难的地方,我想这会是一篇有趣的文章。我以前已经在Haskell中使用过解析器组合器(主要是Parsec和Attoparsec),但从未真正理解它们是如何工作的,或者至少不足以自己实现一个解析器组合器。下面是我对这个问题的看法。不要期待真正先进的东西!这只是对基本概念的介绍,我们可以在此基础上构建更复杂、更有用的工具。特别是,我不会谈论:

编写您自己的解析器组合器库的一个有趣的事实是,您将在这个过程中学习(或巩固)其他知识,比如:函数器、应用程序,当然还有Monad,更一般的是,如何在Haskell中设计DSL。我已经知道这个概念了(至少,我是这么想的,…)。,但是从高级抽象中知道某件事是什么,与知道如何在具体类型(如解析器)上实现它不是一回事!

我们可以将解析器视为消耗某些输入的东西,并输出所消耗内容的结构化表示形式。为简单起见,我们将只使用字符串(Haskell类型字符串)。所以这大概是这样的:

这里,a表示从字符流(字符串)构建的内容的类型。这可以是语法树、数字列表或其他任何内容。例如,能够识别像";[1,2,3,4]";这样的字符串的解析器的类型可以是:parser[Int](扩展为string->;[Int]),这意味着它接受一个字符串并输出一个整数列表。

考虑到第一点,我们可以返回a而不是a(在失败的情况下不会产生任何结果)。请注意,我们还可以使用更丰富的类型,如任一种类型来处理解析错误。对于第二点,我们可以返回一个由a和字符串组成的元组,它表示未被解析器使用的字符串部分。然后,该类型将变为:

举一个失败的解析器的例子,如果您使用我们前面的能够处理整数列表的解析器,如果您给它字符串";[1,2";;,它将失败,并且不返回任何内容。

类似地,如果我们向解析器提供";[1,2,3,4]toto";,它将消耗字符串中表示整数列表的部分,而留下";toto";作为剩余的输入。因此,结果将是:Just([1,2,3,4],";toto";)。

--此解析器始终成功并返回作为输入给定的值--(保持输入字符串不变)::a->;Parser a a=Parser$\s->;Just(a,s)。

--此解析器返回输入字符串的第一个字符,--空输入时失败::parser Char=Parser$\s->;case s of[]->;Nothing(c:xs)->;Just(c,xs)。

基本解析器的行为似乎与预期一致。我们在失败的情况下什么也得不到,并且他们能够部分使用输入。所以一切都很好,但是更复杂的解析器呢?我们希望解析字符串或更复杂的模式。让我们使用基本的解析器尝试从输入中识别字符串:

::string->;Parser String";";=return";";(c1:xs1)=Parser$\s->;case runParser oneChar of Nothing->;Nothing Just(c2,REST)->;if c1==c2则case runParser(String Xs1)Nothing of Nothing->;Nothing Just(Match,rest 2)->;Just(c2:Match,REST 2。

这不是很方便(但很有效)…。因为我们必须一遍又一遍地编写样板来编写解析器。希望我们知道一个著名的结构,它允许在Haskell中进行组合,它叫做Monad(我不会再做关于Monad的教程,所以我假设您已经熟悉了这个概念)。这意味着我们可以通过使我们的解析器类型成为Monad的实例来避免所有的样板。这将允许我们使用DO语法干净地编写我们的解析器!甜!。

要做到这一点,我们必须使我们的解析器成为:Functor、Applicative和Monad的实例。

首先,我们的解析器是函数器的一个实例,这意味着我们可以将函数映射到我们的解析结果上:

Instance functor Parser其中--FMAP::(a->;b)->;Parser a->;Parser b--1.对输入字符串运行Parser。--2.对解析结果应用函数。FMAP f p=Parser$\s->;case runParser p s of Nothing->;Nothing Just(a,rest)->;Just(f a,rest)

--解析`String`";42";然后使用`read`::parser Int=(FMAP Read$String";42";)parse42";42将其转换为`Int`!";

其次,我们可以使我们的解析器成为Applicative的实例。这部分对我来说并不明显。我找到的所有示例都是关于简单类型的实例,比如可能,但我发现解析器非常不同。但是多亏了类型和一些用例(您可以在下面找到),我想到了下面的实现(希望它是正确的…)。:

实例应用解析器,其中--PURE::A->;Parser a--在解析器内包装一个值,保持输入不变。Pure a=Parser$\s->;Just(a,s)--(<;*>;)::Parser(a->;b)->;Parser a->;Parser b--1.在输入上运行第一个解析器(生成函数(a->;b)。--2.对第一个解析器留下的剩余输入运行第二个解析器。--3.对第二个解析器的结果应用函数(a->;b)。p1<;*>;p2=解析器$\s->;case runParser p1 s of Nothing->;Nothing Just(f,rest)->;case runParser p2 Rest of Nothing->;Nothing Just(a,rest 2)->;Just(f a,rest 2)。

前一个实例的用处可能并不明显,但它允许我们在解析器领域内提升一些功能。例如,如果我们想要获取几个解析器的结果,然后将它们的结果分组到一个元组中,我们可以使用Applicative来实现:

这是我们将用来将原始解析结构转换为我们自己的类型(例如:AST)的构造。

数据AST=Foo String|Bar String|Pair Char Char派生(显示),parseBar,parsePair::parser AST=Foo<;$>;String";foo";=Bar<;$>;String";bar";=Pair<;$>;oneChar<;*>;oneChar。

最后但并非最不重要的一点是,我们的解析器是Monad。这意味着它必须实现:>;>;=,>;>;>;,返回和失败:

实例单项解析器WHERE--(>;>;=)::Parser a->;(a->;Parser b)->;Parser b--1.在输入时运行第一个解析器。--2.将解析结果反馈给`f`。--3.在剩余部分运行第二个解析器(`f`的结果)--input(由第一个解析器留下)p>;=f=Parser$\s->;case runParser p s of Nothing->;Nothing Just(a,rest)->;runParser(F A)rest--(>;>;):parser a-->;Parser b->;Parser b--1.运行。--2.对剩余输入(第一个解析器留下)运行第二个解析器--我们忽略第一个解析器的结果。p1>;>;p2=解析器$\s->;case runParser p1s of Nothing->;Nothing Just(_,REST)->;runParser p2 rest--return::A->;Parser a return=纯--FAIL::String->;Parser a Fail_=Parser(Const Nothing)

多亏了这个定义,我们可以使用DO语法糖,这将简化更复杂的解析器的实现。让我们看看我们能做些什么。

--从输入解析特定的`Char`::Char->;Parser Char c=do C1<;-oneChar如果c==C1,则返回C1否则失败。

--从输入解析特定模式::string->;Parser string[]=return[](c:xs)=do c1<;-char c rest<;-string';xs return(c1:rest)。

do表示法使组合解析器变得非常容易!我们现在有了一些基本的构建块,我们可以使用它们来实现更多的解析组合符:选项、许多、选项等等。但是我将把它留作练习。

此外,实现错误报告机制以及位置跟踪(定位输入中的错误)会很有趣,但我将把它留给另一个博客帖子(或者作为读者的练习!)。

实现(非常)基本的解析组合器使我更好地理解了Parsec或Attoparsec等库的基础,并实现了Applicative和Monad等类型类的不那么微不足道的实例。虽然很基本,但我认为这是更熟悉Haskell的类似DSL的功能,并感受该语言在特定领域建模方面提供的强大功能的好方法。