p>> = f在解析器实例中如何工作? [英] How does p >>= f works in Parser instance?

问题描述

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

instance Monad Parser where
    return a = Parser (\cs -> [(a,cs)])
    p >>= f = Parser (\cs -> concat [parse (f a) cs’ | (a,cs’) <- parse p cs])

纸

(>> =)运算符是解析器的排序运算符.用一个 由parse(Parser p)= p定义的解析器的解构函数 解析器p >> = f首先将解析器p应用于参数字符串 cs给出形式(a，cs’)的结果列表，其中a是一个值 而cs是一个字符串.对于每个这样的对，f a是一个解析器，它是 应用于字符串cs'.结果是一个列表列表，即 然后连接起来以给出最终结果列表.

The (>>=) operator is a sequencing operator for parsers. Using a deconstructor function for parsers defined by parse (Parser p) = p, the parser p >>= f first applies the parser p to the argument string cs to give a list of results of the form (a,cs’), where a is a value and cs’ is a string. For each such pair, f a is a parser which is applied to the string cs’. The result is a list of lists, which is then concatenated to give the final list of results.

但这还不清楚.有人可以用一些例子解释吗?非常感谢.

But this is still not clear. Can anyone explain it with some examples? Thanks a lot.

推荐答案

在Haskell中，解析器是Monad的示例. Monad实际上是一个比解析器更广泛的话题，但实际上它们对这个概念进行了很好的介绍.这是这里的工作方式.

In Haskell a parser is an example of a Monad. Monads are actually a much broader topic than just parsers, but they actually make a good introduction to the concept. Here is how it works here.

在解析器中，您希望能够识别类似(在BNF中)的规则

In a parser you want to be able to recognise rules like (in BNF)

assignment ::= identifier "=" expression

在Haskell中，您应该这样写:

In Haskell you would write it like this:

data Statement = 
    Assignment Identifier Expression
    | Block [Statement]  -- A block is a list of statements.
    | Conditional Expression Statement Statement
    | -- etc. 

identifier :: Parser Identifier  -- Implementation omitted.

literal :: String -> Parser ()   -- Implementation omitted.

expression :: Parser Expression   -- Implementation omitted.

assignment :: Parser Statement
assignment = do          -- Note the "do" here.
   ident <- identifier   
   literal "="          
   expr <- expression
   return (Assignment ident expr)   -- "return" doesn't mean what you think.

这捕获了将解析器分配为子解析器序列的想法:首先解析标识符，然后识别"="，然后解析右侧的表达式.希望您能看到BNF如何映射到Haskell代码中.

This captures the idea of a parser for assignments being a sequence of sub-parsers: first you parse the identifier, then you recognise the "=", then you parse the expression on the right hand side. Hopefully you can see how the BNF maps into the Haskell code.

Haskell中的"do"语法是使用>>=运算符(称为"bind")的表达式的语法糖.上面的assignment示例将糖分解为以下内容(大约:这里有一些关于模式匹配失败的信息)

The "do" syntax in Haskell is syntactic sugar for expressions that use the >>= operator (which is called "bind"). The assignment example above de-sugars into the following (approximately: there is stuff about pattern match failures that I am skipping over here)

assignment = 
    identifier >>= (\ident ->
        operator "=" >>= (\dummy ->
           expression >>= (\expression -> return (Assignment ident expr))))

每个\(称为"lambda")都引入了一个匿名函数. >>=运算符采用两个参数.左侧是包裹在Parser monad中的一些值.右侧是一个函数，该函数接受此值并返回新的包装值.绑定运算符的作用是解开左侧的值(这可能涉及做一些魔术上的副作用)，并将其传递给右侧的函数.在这种情况下，魔术的副作用包括消耗输入文本.

Each \ (called "lambda") introduces an anonymous function. The >>= operator takes two arguments. On the left hand side is some value wrapped up in the Parser monad. On the right hand side is a function that takes this value and returns a new wrapped value. The job of the bind operator is to unwrap the value on the left (which may involve doing some magic side effects) and pass it to the function on the right. In this case the magic side effects include consuming the input text.

请注意绑定和匿名函数如何嵌套在已删除版本中. "do"语法中的每一行都将转换为上一行中的一个新函数.这意味着到目前为止，最后一个函数可以访问所有函数中的所有变量.它是一种使用Haskell这样的纯函数式语言对一组作业进行建模的方法.

Note how the binds and anonymous functions are nested in the de-sugared version. Each successive line in the "do" syntax translates into a new function inside the one for the previous line. That means that the last function has access to all the variables in all of the functions so far. Its a way of modelling a block of assignments in a pure functional language like Haskell.

我在评论中说，返回"并不意味着您认为的含义.在Haskell中，它与控制流无关，它只是将一个值包装在monad中(在本例中为Parser)，而不会引起任何副作用.

I said in the comments that "return" doesn't mean what you think it means. In Haskell it is nothing to do with flow of control, it just wraps up a value in a monad (in this case Parser) without causing any side effects itself.

此特定的解析器生成结果列表.也就是说，当遇到任何模棱两可的东西时，它会生成一个结果列表，而不是在每个步骤上都决定一个真实解析.绑定运算符将每个结果取至今，并将其传递给右侧的函数，这又可能再次生成多个结果.否则解析器可能不会产生任何结果，在这种情况下该分支将被放弃.因此，每个步骤都从结果列表开始，然后下一步给出结果列表的列表，然后通过"concat"功能将其折叠成平坦的结果列表.

This particular parser generates lists of results. That is, rather than deciding on the One True Parse at every step, when it encounters something ambiguous it generates a list of results. The bind operator takes each of the results so far and passes it to the function on its right, which in turn may generate multiple results again. Or a parser may generate no results in which case that branch is abandoned. Hence each step starts with a list of results, and the next step gives a list of lists of results, which is then folded back into a flat list of results by the "concat" function.

您的问题中给出的Monad类是标准库的一部分.碰巧有许多有用的功能适用于所有monad，因此为它们提供一个通用接口非常有效.对于Parser，绑定运算符的类型为

The Monad class given in your question is part of the standard library. It happens that there are lots of useful functions that apply to all monads, so giving them a common interface works well. In the case of Parser the bind operator has the type

(>>=) :: Parser a -> (a -> Parser b) -> Parser b

和return具有类型

return :: a -> Parser a

沉思这些类型以及我对绑定和返回所做的描述，您可能会获得一元启示.

Meditate on these types and the description I gave of what bind and return do, and you may achieve monadic enlightenment.

这篇关于p>> = f在解析器实例中如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！