0

我正在尝试用 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，解析就应该停止。

4

1 回答 1

2

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

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

大量的分配可能是由于attoparsec建立延续来管理回溯。作为一般规则，您输入的任何解析器many都不应该能够轻易成功（即不消耗任何输入流）。因此，您将需要重写inline或以其他方式重组解析器以避免这种情况。

于 2014-05-17T05:13:36.867 回答