为什么解析器组合器"seq"用"bind"和"return"定义？

Question

我正在阅读这篇关于解析器组合子的文章，不理解以下内容:

他们说使用seq(见下文)会导致解析器以嵌套元组作为结果，这对于操作来说是混乱的。

 seq :: Parser a -> Parser b -> Parser (a,b)
 p ‘seq‘ q = inp -> [((v,w),inp’’) | (v,inp’) <- p inp, (w,inp’’) <- q inp’]

为了避免嵌套元组的问题，他们为解析器引入了一元 bind和return，然后将seq定义为:

 p ‘seq‘ q = p ‘bind‘ x -> q ‘bind‘ y -> result (x,y)

不幸的是，我不明白嵌套元组的问题是什么，也不明白为什么seq的第二个实现比第一个更好。你能帮我理解一下吗?

Answer 1

第一个例子扩展到类型((a,b)，(c,d,e)):

seq232 ((p,q),(r,s,t) = inp ->
     [ (((v,w),(x,y,z)),inp’’''')
     | (v, inp’) <- p inp
     , (w, inp’’) <- q inp’
     , (x, inp''') <- r inp''
     , (y, inp'''') <- s inp'''
     , (z, inp''''') <- t imp''''
     ]

第二个例子扩展为类型((a,b)，(c,d,e)):

seq232 ((p,q),(r,s,t)) =
    p ‘bind‘ v ->
    q ‘bind‘ w ->
    r `bind` x ->
    s `bind` y ->
    t `bind` z ->
    result ((v,w),(x,y,z))

虽然不是一个好很多，但我认为你可以看到第二个更干净一些。

Answer 2

我敢说，应用程序接口实际上比一元接口更老。遗憾的是，这个问题近年来才得到越来越多的关注。

这个想法是，使用seq组合子(不是一个幸运的名字)，基本解析器返回一个"简单"类型的值，然后将其组合成一个更复杂类型的最终结果。

应用程序接口的思想是有一个类型为 的顺序组合组合子。

(<*>) :: Parser (b -> a) -> Parser b -> Parser a

我们首先将一个函数(具有"复杂"类型)提升到解析器中，然后使用解析器将后续解析器返回的参数组合成结果。特殊版本是<*和*>，它们丢弃丢失的尖括号旁边的结果。您将在Control.Applicative模块中找到这个接口。

为什么要避免使用一元解析器?由于>>=组合子的右侧解析器依赖于左侧解析器的结果，因此在解析过程中会反复构造此解析器。消息是:只有在真正需要时才使用一元接口，即，如果你想构建依赖于先前运行的解析器的解析结果的解析器。

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

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

一元解析器派上用场的一个典型例子是识别A ^{n}b^{n}c^{n}。我们从识别一些a开始，然后想要看到许多b'c和c'

pAs       = length <$> many(pSym 'a')
pSyms c 0 = pure 0
pSyms c n = (+1) <$ pSym c <*> pSyms c (n-1)
pABC = do count <- pAs
          pSyms 'b' count
          pSyms 'c' count

本质上是在do-construct的下一个语句中使用前面语句的结果，而不仅仅是在最后组合它们而不执行任何解析。

参见:

@inproceedings{SwieDupo96,
Author = {Swierstra, S. D. and Duponcheel, L.},
Booktitle = {Advanced Functional Programming},
Date-Added = {2009-01-04 17:21:54 +0100},
Date-Modified = {2009-01-04 17:21:54 +0100},
Editor = {Launchbury, John and Meijer, Erik and Sheard, Tim},
Pages = {184-207},
Publisher = {Springer-Verlag},
Series = {LNCS-Tutorial},
Title = {Deterministic, Error-Correcting Combinator Parsers},
Urlpdf = {http://www.cs.uu.nl/people/doaitse/Papers/1996/DetErrCorrComPars.pdf},
Volume = {1129},
Year = {1996},
}

最后解释了为什么单子应该尽可能避免(就像当上下文无关的语法过度使用时应该使用正则表达式一样)。