文档结构  
翻译进度:已翻译     翻译赏金:15 元 (?)    ¥ 我要打赏

使用 Phunkie 进行函数式编程

作者的更多文章

Phunkie 是一个具有函数式结构的 PHP 库。在这两篇文章中,Phunkie 的创建者 Marcello Duarte, Inviqa 的培训主管,解释了如何用函数式库来创建解析选择符。本篇文章首次出现在他的博客中, 得到他的允许发布在这里。为了解释 PHP 中的“非奇异”特性,也提供了更好的付费教程

第 1 段(可获 1.2 积分)

在这个系列的第一部分中,说到了解析器和选择符,你能从 PHP 的函数式编程中获取结果。用例子概况了基础知识,现在我们来学习更多的序列和策略。

让我们继续上一部分留下的内容!

Phunkie logo

序列选择符

好了,让我们现在试一下有用的解析器。这个解析器,提供一种操作,如果满足条件,保持字符内容,否则另外处理。从该条件开始,我们把这个解析器叫做 sat.

        describe("sat", function() {


            it("parses one character when it satisfies the predicate", function(){
                expect(sat("is_numeric")->run("4L"))->toEqual(ImmList(Pair('4', 'L')));
            });


            it("returns Nil when the character does not satisfy the predicate", function(){
                expect(sat("is_numeric")->run("L4"))->toEqual(Nil());
            });

        });
第 2 段(可获 1.04 积分)

这个使用 itemresult 和 zero这些原始解析器的实现,看起来像这样:

function sat(callable $predicate): Parser
{
    return item()->flatMap(function($x) use ($predicate) {
        return $predicate($x) ? result($x) : zero();
    });
}

你可以看到这些构造块现在是如何派上了用场。我们根据其结果将item解析器称为flatMap,并应用谓词。如果该谓词被应用成功,我们便返回到result 解析器,而该解析器基本上将$ x提升到了解析器语境。另外, zero只会做同样的事情,但是它会和Nil一起做而不是和任何结果一起做。

第 3 段(可获 0.76 积分)

我们可以快速对 sat 进行首字符大写转换,是需要创建一些排序组合即可。

    context("Sequencing combinators", function() {
        describe("char", function() {
            it("parses a character", function() {
                expect(char('h')->run("hello"))->toEqual(ImmList(Pair('h', "ello")));
            });
        });

        describe("digit", function() {
            it("parses a digit", function() {
                expect(digit()->run("42"))->toEqual(ImmList(Pair('4', '2')));
            });
        });

        describe("lower", function() {
            it("parses a lowercase character", function() {
                expect(lower()->run("hello"))->toEqual(ImmList(Pair('h', "ello")));
            });
        });

        describe("upper", function() {
            it("parses an upper case character", function() {
                expect(upper()->run("Hello"))->toEqual(ImmList(Pair('H', "ello")));
            });
        });
    });
第 4 段(可获 0.15 积分)

实现的方法简单到会让你笑出来!

function char($c): Parser
{
    return sat(function($input) use ($c) { return $input === $c; });
}

function digit(): Parser
{
    return sat('is_numeric');
}

function lower(): Parser
{
    return sat(function($c) { return ctype_lower($c); });
}

function upper(): Parser
{
    return sat(function($c) { return ctype_upper($c); });
}

选择符

在现实世界的语法中,如果我必须在第一个解析器运行失败的第一时间退回一份空白名单,那么我们就没办法生存了。解析器需要对语法选择进行构造。一个很常见的情况就是匹配一种 模式或者另一种模式。我们通过将plus选择符添加到我们的解析器库来实现它。

第 5 段(可获 0.85 积分)
use function concat;

function plus(Parser $p, Parser $q)): Parser
{
    return new Parser(function(string $s) use ($p, $q) {
        return concat($p->run($s), $q->run($s));
    });
}

我喜欢将一些组合实现转移到解析器类本身。例如,plus组合子成为该类的or方法,并为各种解析器创建一些语法糖。

function plus(Parser $p, Parser $q)): Parser
{
    return $p->or($q);
}

选择各种解析器的一个例子既可以是接受小写字符也可以是大写字符。我们可以将那个解析器命名为letter。我们还可以创建另一个能接受数字或字母的解析器,我们可以将其命名为alphanum。

第 6 段(可获 0.78 积分)

而且实现的简洁说明了一切:

function letter(): Parser
{
    return plus(lower(), upper());
}

function alphanum(): Parser
{
    return plus(letter(), digit());
}

递归组合子

我们可以使用的一个很好的技巧就是将result 分析器传递给 plus来创建非确定性解析器。为了说明这一点,让我们构建一个word解析器吧,该解析器能从一串字符中识别整个单词。该结果可能令你吃惊:

   context("Recursive combinators", function() {
        describe("word", function() {
            it("recognises entire words out of a string", function() {
                expect(word()->run("Yes!"))
                    ->toEqual(ImmList(
                        Pair("Yes", '!'),
                        Pair("Ye", "s!"),
                        Pair('Y', "es!"),
                        Pair("", "Yes!")
                    ));
            });
        });

    //...
    });
第 7 段(可获 0.59 积分)

在深入探讨为什么有这么多对结果之前,让我们来看一下它的内部实现:

function word(): Parser
{
    $nonEmptyWord = letter()->flatMap(function($x) {
        return word()->map(function($xs) use ($x) {
            return $x . $xs;
        });
    });

    return plus($nonEmptyWord, result(''));
}

正如我们所看到的,当解析到字母时意味着我们会消耗一个可用的字母,然而我们可能消耗了一个字母后还未到解析结束的时候。 这时候的选择符是不确定的。 我们能得到某种结果;我们已经得到了一个字母. 现在让我们看看更多时候的情况. 直到我们找到的东西不是一个字母时我们再停止解析.

第 8 段(可获 1.1 积分)

另外,请注意我们在该实现里使用递归去继续解析,将各种结果连接在一起。顺便说一下,这就是为什么我没有在这里使用for notation 了。PHP并不是一个懒惰的语言,因此它用该符号实现递归性会导致堆栈溢出。

一个非常有用的解析器可以识别在另一串字符中的整个字符串(或令牌)。我们将它称为 string并递归地实现它。

        describe("string", function() {

            it("parses a string", function() {
                expect(string("hello")->run("hello world"))
                    ->toEqual(ImmList(Pair("hello", " world")));
            });


               expect(string("helicopter")->run("hello world"))
                   ->toEqual(Nil());


        });
第 9 段(可获 0.88 积分)

这就是实现:

function string($s): Parser
{
    return strlen($s) ?

        for_(
            __($c)->_(char($s[0])),
            __($cs)->_(string(substr($s, 1)))
        )->call(concat, $c, $cs) :

        result ('');
}

简单的重复

您可以想象在单词和字符串中使用的重复模式是解析器经常遇到的一种模式。我们或许也可以将其概括一下。用这种方式创建各种解析器的好处就在于它们可以很容易地被组合起来去创建各种新的解析器。

现在我们将这种简单的重复解析器定义为 many。我们将做出许多非确定性的选择,这就意味着它从来都不会失败,而是会返回到一个空字符串。

第 10 段(可获 0.96 积分)

这个实现看起来非常类似于word实现,只是我们找一个解析器而不是使用letter,因此我们可以对任何类型的重复提出异议。

function many(Parser $p): Parser
{
    return plus($p->flatMap(function($x) use ($p) {
        return many($p)->map(function($xs) use ($x) {
            return $x . $xs;
        });
    }), result(''));
}

我们现在可以将word 简单地定义为 many(letter())。同样,我们可以尝试并实现一个带有many(digit())的数字解析器,但由于many是不确定性的,我们需要一个many版本,该版本至少匹配一个字符. 我们将其称为many1.

第 11 段(可获 0.78 积分)
       describe("many1", function() {
            it("does not have the empty result of many", function() {
                expect(many1(char('t'))->run("ttthat's all folks"))->toEqual(ImmList(
                    Pair("ttt", "hat's all folks"),
                    Pair("tt", "that's all folks"),
                    Pair('t', "tthat's all folks")
                ));
            });
            it("may produce an error", function() {
                expect(many1(char('x'))->run("ttthat's all folks"))->toEqual(Nil());
            });
        });

使用 for 语句实现:

第 12 段(可获 0.04 积分)
function many1(Parser $p): Parser
{
    return for_(
        __($x)->_($p),
        __($xs)->_(many($p))
    )->call(concat, $x, $xs);
}

我们接着可以使用该实现来实现自己的自然数字解析器,nat。这次我们将更上一层楼并通过将其转换成一个整数来评估结果。我们可以通过列表的head得到结果,该列表是一对,然后使用_1评估去得到结果。例子如下:

       describe("nat", function() {
            it("can be defined with repetition", function() {
                expect(nat()->run("34578748fff"))->toEqual(ImmList(
                    Pair(34578748, "fff"),
                    Pair(3457874, "8fff"),
                    Pair(345787, "48fff"),
                    Pair(34578, "748fff"),
                    Pair(3457, "8748fff"),
                    Pair(345, "78748fff"),
                    Pair(34, "578748fff"),
                    Pair(3, "4578748fff")
                ));
                expect(nat()->run("34578748fff")->head->_1)->toEqual(34578748);
            });
        });
第 13 段(可获 0.7 积分)

下面是映射后的实现代码:

function nat(): Parser
{
    return many1(digit())->map(function($xs) {
        return (int) $xs;
    });
}

如果我们要负数,我们可以使用 nat 来编译整数解析器:

       describe("int", function() {
            it("can be defined from char('-') and nat", function() {
                expect(int()->run("-251")->head->_1)->toEqual(-251);
                expect(int()->run("251")->head->_1)->toEqual(251);
            });
        });

实现起来很简单:

function int()
{
    return plus(for_(
        __($_)->_(char('-')),
        __($n)->_(nat())
    )->call(negate, $n), nat());
}
第 14 段(可获 0.34 积分)

任何传进 $_ gets 的,都会被忽略,除了匹配的。然后 Phunkie 中的负函数会把数字转换成一个负整数。nat() 确保也我们接受负数。

使用分隔符进行重复

此时,我们已经可以创建非常有趣的解析器了。例如,我们可以分析一组用 PHP 数组标记的整数:[1,-42,500]。我们已经可以这样写:

for_(
    __($open) ->_ (char('[')),
    __($n   ) ->_ (int()    ),
    __($ns  ) ->_ (many(
        for_(
            __($comma ) ->_ (char(',')),
            __($m )     ->_ (int()    )
        ) -> call (concat, $comma, $m))),
    __($close) ->_ (char(']'))
) -> call (concat, $open , $n , $ns , $close);

事实上,我们可以通过推广分隔符的用法来简化这一点——在这种情况下,使用字符逗号(,)。下一步我们将实现sepby1,它是一款已被应用很多次的解析器,并被另一个解析器的应用所分隔。下面是一个例子:

       describe("sepby1", function() {
            it("applies a parser several times separated by another parser", function() {
                expect(sepby1(letter(), digit())->run("a1b2c3d4"))
                    ->toEqual(ImmList(
                        Pair("abcd", '4'),
                        Pair("abc", "3d4"),
                        Pair("ab", "2c3d4"),
                        Pair('a', "1b2c3d4"))
                );
            });
        });
第 16 段(可获 0.51 积分)

实现起来很简单:

function sepBy1(Parser $p, Parser $sep)
{
    return for_(
        __($x)->_($p),
        __($xs)->_(many(for_(
            __($_)->_($sep),
            __($y)->_($p)
        )->yields($y)))
    )->call(concat, $x, $xs);
}

sepBy1 的实现移到 Parser 类中,针对整数列表,通过 sepBy1 一个分隔符,可以再次实现我们的解析器,代码就更加容易阅读了:

function ints()
{
   return for_(                                 __
        ($_) ->_ (char('[') )                  ,__
        ($ns  ) ->_ (int()->sepBy1(char(','))) ,__
        ($_) ->_ (char(']'))
    ) -> yields ($ns);
}
第 17 段(可获 0.44 积分)

我们应用一个通用的解析模式来作为一般情况下的写法。

function surrounded(Parser $open, Parser $p, Parser $close)
{
    return for_(
        __($_)->_($open),
        __($ns)->_($p),
        __($_)->_($close)
    )->yields($ns);
}

然后我们可以这样重写ints函数:

function ints()
{
    return surrounded(
        char('['),
        int()->sepBy1(char(',')),
        char(']')
    );
}

JSON解析器

使用我们现在所拥有的处理方法, 我们来构建一个JSON解析器. 我们应该不需要再一步一步的介绍说明了, 在这篇文章里(文章最后)我会给出Github 的仓库链接. 在这里,我也会和你谈一些不太被直接察觉到的方面。

第 18 段(可获 0.89 积分)

解析器应该基于规范创建一个基本的JsonObject对象。这几乎是一个完整实现。为了简单,我将会忽略空格、数字与字符串的问题处理。

如下面的示例所示:

    context("Json parser", function() {
        describe("json_object", function() {

            it("parses json objects with no space or fancy digits", function() {
                expect((string)json_object()->run(

                    '{a:1,b:null,c:true,d:{x:"a",b:[1,2,3]}}'
                )->head->_1)->toEqual((string)

                new JsonObject(
                    ImmMap([
                        "a" => new JsonNumber(1),
                        "b" => new JsonNull(),
                        "c" => new JsonBoolean(true),
                        "d" => new JsonObject(
                            ImmMap([
                                "x" => new JsonString("a"),
                                "b" => new JsonArray([
                                    new JsonNumber(1),
                                    new JsonNumber(2),
                                    new JsonNumber(3)
                                ])
                            ])
                        )
                    ])
                ));
            });
        });
    });
第 19 段(可获 0.46 积分)

json_value 是一个位于顶部的选择解析器。其实现非常直接:

function json_value(): Parser
{
    return json_string()
        ->or(json_boolean())
        ->or(json_null())
        ->or(json_number())
        ->or(json_array())
        ->or(json_object());
}

值得注意的方面是由已解析的值到JSON对换的转换。这通常是通过解析器组合器尾部的 map 来实现的。例如下面的json_null 解析器:

function json_null(): Parser
{
    return string("null")->map(function($_) {
        return new JsonNull();
    });
}
第 20 段(可获 0.6 积分)

我创建了一个 sepby1array 选择符,而不是返回的连接值最后返回一个数组的值解析。这是非常方便的json_array 解析器。(译者注:https://github.com/MarcelloDuarte/ParserCombinators/blob/master/src/Md/ParserCombinators/Functions/parsers.php

function json_array(): Parser
{
    return char('[')->flatMap(function($_) {
        return sepBy1array(json_value(), char(','))->flatMap(function($elements) {
            return char(']')->map(function($_) use ($elements) {
                return new JsonArray(
                    array_filter($elements, function($a){ return $a != ''; })
                );
            });
        });
    });
}
第 21 段(可获 0.35 积分)

使用 Phunkie 的不可变对象 Maps 可以实现相同的安排。

function json_object(): Parser
{
    return char('{')->flatMap(function($_) {
        return sepBy1Map(word()->flatMap(function($key) {
            return char(':')->flatMap(function($colon) use ($key) {
                return json_value()->map(function($value) use ($key) {
                    return ImmMap($key , $value);
                });
            });
        }), char(','))->flatMap(function($pairs) {
            return char('}')->map(function() use ($pairs) {
                return new JsonObject($pairs);
            });
        });
    });
}
第 22 段(可获 0.18 积分)

现在就这样! 希望这能向您展示函数编程的功能有多么强大,以及可组合解析器是如何组合的.我希望你喜欢本教程,并受到启发,为自己尝试一些Phunkie!

问题?评论?在Twitter上找到我@ _md,或者在下面发表评论!

有用的链接

[1] – Phunkie repository https://github.com/phunkie/phunkie
[2] – Marcello Duarte’s parsers combinators repository https://github.com/MarcelloDuarte/ParserCombinators

第 23 段(可获 0.95 积分)

文章评论