内存不足使用Attoparsec

Question

我想用attoparsec做一个简单的解析器。生成规则如下:

block:  ?token> [inline]
inline: <?token>foo<?> | anyText

所以，我想要得到的是，一个块以文字?开头，后面跟着一个记号，然后是一个>，然后是一个内联序列。

内联可以是foo形式的序列，也可以是任何纯文本。

我有爆炸性的内存使用，但我不确定如何使解析器避免它。我正在编写的解析器的重点是提取那些"标记"的东西。下面是我的实现:

import Control.Applicative
import Control.Monad
import Data.Attoparsec.Text as Text
import Data.Text
blockLine :: Parser [Text]
blockLine = do
  block   <- hiddenBlock                       -- the block token
  inlines <- many (hiddenInline <|> inline)    -- followed by inlines, which might have tokens
  return $ block : inlines
inline = manyTill anyChar (hiddenInline <|> (endOfInput >> return Text.empty)) 
hiddenInline = Text.pack <$> do
  char '<'   -- opening "tag"
  char '?'   -- opening "tag" still
  token <- manyTill anyChar (char '>')  -- the token
  manyTill anyChar (string "<?>") -- close the "tag"
  return token
hiddenBlock = Text.pack <$> do
  char '?'
  manyTill anyChar (char '>')

在我看来，这是将生成规则非常直接地翻译成LL解析器。我想困难在于我不确定如何表示内联的结果。它应该是"任意"文本，但解析应该在发现hiddenInline后立即停止。

Answer 1

问题是在使用的内部嵌套了对manyTill的调用many。由于inline的终止条件为endOfFile, manyTill anyChar会愉快地消耗你所有的投入，然后成功。inline的后续使用也将成功，因为manyTill可以运行它的第一个解析器零次或多次。因此，在inline解析器上使用many只会导致many成功永远循环，同时产生一个空字符串的无限列表。这个行为在

这个例子中更加明显

 parseOnly (many (manyTill anyChar endOfInput)) $ Text.pack ""

大量的分配可能是由于attoparsec的积累管理回溯的延续。作为一般规则，您提供给many的任何解析器都不应该能够这样做平凡地成功(即不消耗任何输入流)。因此，您将需要重写inline或以其他方式重组您的