无法计算解析器的最小长度 - 在Haskell中使用uu-parsinglib

Question

让我们看看代码片段:

pSegmentBegin p i   = pIndentExact i *> ((:) <$> p i <*> ((pEOL *> pSegment p i) <|> pure []))

如果我在我的解析器中将此代码更改为:

pSegmentBegin p i   = do
    pIndentExact i
    ((:) <$> p i <*> ((pEOL *> pSegment p i) <|> pure []))

我有一个错误:

canot compute minmal length of a parser due to occurrence of a moadic bind, use addLength to override

我认为上面的解析器应该以相同的方式运行.为什么会出现此错误？

编辑

上面的例子很简单(为了简化问题),如下所述,这里没有必要使用do notation,但我希望它使用的实际情况如下:

pSegmentBegin p i   = do
    j <- pIndentAtLast i
    (:) <$> p j <*> ((pEOL *> pSegments p j) <|> pure [])

我注意到在do语句之前添加"addLength 1"解决了问题,但我不确定它是否是正确的解决方案:

pSegmentBegin p i   = addLength 2 $ do
    j <- pIndentAtLast i
    (:) <$> p j <*> ((pEOL *> pSegments p j) <|> pure [])

Answer 1

正如我多次提到的那样,应尽可能避免使用monadic接口.让我试着解释为什么首选应用程序界面.

我的库的一个显着特点是它通过插入或删除问题来执行错误纠正.当然,我们可以在这里采取毫无根据的预测,但这会使这个过程非常昂贵.所以我们只采取三个步骤的有限前瞻.

现在假设我们必须插入一个表达式,其中一个表达式替代方案是:

expr:="if"expr"then"expr"else"expr

那么我们想要排除这个选择,因为选择这个替代方案将需要插入另一个表达式等.所以我们对替代方案进行抽象解释并确保在抽签的情况下(即有限前瞻的相同成本)我们采取一个非递归替代方案.

不幸的是,当编写monadic解析器时,这种方案会崩溃,因为绑定右侧的长度可能取决于左侧的结果.因此,我们发出错误消息,并向程序员请求一些帮助,以指示此替代方案可能消耗的令牌数.实际值并不重要,只要你没有为递归的东西提供有限长度并且可能导致无限插入.它仅用于在插入时选择最短的替代方案.

这种抽象的解释有一些成本,如果你用monadic风格编写所有的解析器,这个分析不可避免地重复进行.所以:如果有适用的替代方案,请不要在使用本图书馆时写下MONADIC STARLE PARSERS.

Answer 2

它试图静态分析需要读取多少输入以优化性能，但这种优化需要静态已知的解析器结构——可以由Applicatives构建的类型，因为解析器效果不能依赖于解析器值，例如(>>=)做。

所以这就是问题所在——当你使用do符号时，它会转化为一个打破Applicative预测器的 Monadic 绑定。如果库只公开两个接口中的一个，这样就不会发生这种错误，那就太好了，但是如果您在同一个解析器中同时使用这两个接口，则会出现一些不一致。

由于这种使用do是完全没有必要的——你没有使用 monadic 接口给你的额外功能——最好避免它。