Scala中的应用解析器示例 [英] Applicative parser example in Scala

问题描述

这是我以前的问题

我们可以将解析器定义为type Parser[A] = String => List[(A, String)].解析器接受输入字符串，并产生一对序列.每对都包含解析结果和输入的未使用部分. (请参见此文章中的更多内容)

We can define a parser as type Parser[A] = String => List[(A, String)]. The parser takes an input string and yields a sequence of pairs. Each pair consists of the parsing result and unconsumed part of the input. (See more in this article)

现在我们可以定义一个解析器pa，如果第一个输入字符为a，则解析器将成功，否则将失败.

Now we can define a parser pa, which succeeds if the 1st input character is a and fails otherwise.

def symbol(c: Char): Parser[Char] = {s: String => 
  s.toList match { case x :: xs if x == c => List((x, xs.mkString)); case _ => Nil } 
}

val pa = symbol('a')

我们还可以为Parser[A]定义map和flatMap，然后使用它们来构成解析器:

We can also define map and flatMap for Parser[A] and then use them to compose parsers:

val pa = symbol('a')
val pb = symbol('b')
val pab: Parser[(Char, Char)] = for (a <- pa; b <- pa) yield (a, b)

尽管结果我们也可以用<*>组成解析器.

It is turned out though that we can compose parsers with <*> too.

应用解析器的示例.假设我们要识别嵌套的括号并计算最大嵌套深度.语法S->(S)S | epsilon描述了这种结构，它直接反映在解析器中.

An example of an applicative parser. Suppose we want to recognise nested parentheses and compute the maximum nesting depth. The grammar S -> (S)S | epsilon describes this structure, which is directly reflected in the parser.

pS = (max . (+1)) <$ pSym '(' <*> pS <* pSym ')' <|> pure 0

不幸的是，我无法理解这个例子.所以我的问题是:

Unfortunately I can't get my head around this example. So my questions are:

• 如何为解析器定义<*>? (不适用于flatMap)?
• 如何将此示例转换为Scala(使用scalaz)?

• How to define <*> for parsers ? (not with flatMap) ?
• How to translate this example to Scala (with scalaz) ?

推荐答案

<*>(可怕的名字)显然具有以下签名:

<*> (terrible name) apparently has this signature:

<*>[B](f: F[(A) ⇒ B]): F[B]

因此，让我们逐一介绍类型，考虑解析器应该做什么-借助List已经实现flatMap的事实的帮助:

So let's just chase the types through, thinking about what a parser should do - helped by the fact that List already implements flatMap:

def <*>[A, B](fa: Parser[A], fab: Parser[(A) => B]) =
  new Parser[B] {
    def apply(s: String) =
      for {
        (a, rem1) ← fa(s)
        (ab, rem2) ← fab(rem1)
      } yield (ab(a), rem2)
  }

这似乎是一个明智的实现-首先解析a，然后从其余部分解析ab，然后得到结果.

That looks like a sensible implementation - parse a first, then parse ab from the remainder, and then we have our result.

该示例对我来说太象征性了，我不知道Haskell-如果您可以找到<$和<|>的文档，那么我将继续.

That example is too symbolic for me and I don't know Haskell - if you can find documentation for the <$ and <|> then I'll give it a go.

这篇关于Scala中的应用解析器示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！