无法计算解析器的最小长度 - 在Haskell中的uu-parsinglib [英] Cannot compute minimal length of a parser - uu-parsinglib in Haskell

问题描述

让我们看看代码片段：

  pSegmentBegin p i = pIndentExact i *> （（:) p $ p（（pEOL *> pSegment p i）<>纯粹的[]））
  

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

  pSegmentBegin pi = （（pEOL *> pSegmentPi）<>纯粹的[]））
< / code> 

我遇到了一个错误：



  canot计算由于moadic绑定发生的解析器的最小长度，使用addLength来覆盖
  

我认为上面的解析器应该以同样的方式行事。为什么会出现这样的错误？



编辑 上面的例子非常简单（为了简化问题），如下所述，这里没有必要使用符号，但我希望它使用的真实情况如下：



  pSegmentBegin pi = do 
j<  -  pIndentAtLast i 
（:)< $> p j * * （（pEOL *> pSegments pj）< |>纯粹[]）
  

在do语句解决问题之前添加addLength 1，但我不确定它是否是正确的解决方案：



  pSegmentBegin pi = addLength 2 $ do 
j<  -  pIndentAtLast i 
（:)< $> p j * * （（pEOL *> pSegments pj）< |>纯粹的[]）
  




解决方案

正如我多次提到的那样，应该尽可能地避免monadic接口。让我试着解释为什么应用接口是首选。



我的库的一个独特功能是通过插入或删除问题来执行纠错。当然，我们可以在这里采取一个超前的预见，但这会使这个过程非常昂贵。所以我们只需要三个步骤的有限前​​瞻。

现在假设我们必须插入一个表达式并且其中一个表达式是：



expr：=ifexprthenexprelseexpr



然后我们想排除这个选择，因为选择这个选择是必要的插入另一个表达式等等。因此，我们对这些替代方案进行抽象解释，并确保在抽签的情况下（即对于有限的前瞻，等价的成本），我们采用其中一种非递归替代方案。

不幸的是，当一个程序写入一元语法分析器时，这个方案会崩溃，因为绑定右边的长度可能取决于左边的结果。因此，我们发出错误消息，并要求程序员提供一些帮助，以指示此替代方案可能消耗的令牌数量。实际值并不重要，只要你没有为递归的东西提供有限的长度并且可能导致无限的插入。它只用于在插入的情况下选择最短的选择。

这种抽象解释有一定的代价，如果你用monadic风格编写所有解析器，这是不可避免的这个分析重复了一遍。所以：如果有适用的替代品，请勿在使用本库时书写蒙纳迪奇风格的寄存器。

Lets see the code snippet:

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

if I change this code in my parser to:

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

I've got an error:

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

I thought the above parser should behave the same way. Why this error can occur?

EDIT

The above example is very simple (to simplify the question) and as noted below it is not necessary to use do notation here, but the real case I wanted it to use is as follows:

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

I have noticed that adding "addLength 1" before the do statement solves the problem, but I'm unsure if its a correct solution:

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

解决方案

As I have mentioned many times the monadic interface should be avoided whenever possible. let me try to explain why the applicative interface is to be preferred.

One of the distinctive features of my library is that it performs error correction by inserting or deleting problems. Of course we can take an umlimited look-ahead here but that would make the process VERY expensive. So we take only a limited lookahead of three steps.

Now suppose we have to insert an expression and one of the expression alternatives is:

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

then we want to exclude this alternative since choosing this alternative would necessitate the insertion of another expression etc. So we perform an abstract interpretation of the alternatives and make sure that in case of a draw (i.e. equal costs for the limited lookahead) we take one of the non-recursive alternatives.

Unfortunately this scheme breaks down when one writes monadic parsers, since the length of the right hand side of the bind may depend on the result of the left-hand side. So we issue the error message, and ask some help from the programmer to indicate the number of tokens this alternative might consume. The actual value does not matter so much, as long as you do not provide a finite length for something which is recursive and may lead to infinite insertions. It is only used to select the shortest alternative in case of an insertion.

This abstract interpretation has some costs and if you write all your parsers in monadic style it is unavoidable that this analysis is repeated over an over again. so: DO NOT WRITE MONADIC STYLE PARSERS WHEN USING THIS LIBRARY IF THERE IS AN APPLICATIVE ALTERNATIVE.

这篇关于无法计算解析器的最小长度 - 在Haskell中的uu-parsinglib的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！