使用Haskell/Parsec，如何解析编码自己长度的字符串

Question

我正在尝试用Haskell和Parsec解析一个二进制数字字符串。二进制字符串被划分为可变长度的数据包。一个数据包可以编码一个整数值，也可以再次编码一堆子数据包。假设第一个比特告诉我们它是什么类型的数据包。1表示值；CCD_ 2表示子分组。下面的10位告诉我们数据包的剩余长度。因此，每个数据包都有一个固定长度的报头(11位(和一个可变长度的主体。

对我来说，棘手的部分是，如何根据其他解析器定义Parser，但将消耗的字符量固定为我在解析过程中动态获得的数字(正文长度(。

我想出了一个解决方案，但我觉得这不是最佳实践：

data Packet = Value Int | SubPackets [Packet]
binaryDigit :: Parser Char
binaryDigit = char '0' <|> char '1'
packet :: Parser Packet
packet = do
isValue <- binaryDigit
packetBody isValue
packetBody :: Char -> Parser Packet
-- body encodes value
packetBody '1' = do
bodyLength <- binToInt <$> count 10 binaryDigit
body <- count bodyLength binaryDigit
return $ Value (binToInt body)
-- body encodes sub packages
packetBody '0' = do
bodyLength <- binToInt <$> count 10 binaryDigit
body <- count bodyLength binaryDigit
-- is this best practice? :
case parse (many packet <* eof) "" body of
Right packets -> return $ SubPackets packets
Left parseError -> unexpected (show parseError)    
binToInt :: [Char] -> Int
binToInt [] = 0
binToInt (x:xs) = (digitToInt x) * 2 ^ length xs + binToDec xs

在parseBody的第二种情况中，我没有为子数据包定义Parser，而是直接使用parse。尤其是错误处理让我觉得有点难看。

Answer 1

正如Carl提到的，这是解析二进制格式时常见的megaparsec。我不太确定要为它定义一个合适的组合子需要做多少工作。

然而，至少在这种情况下，一种解决方案是在每个子包之前和/或之后轮询当前偏移量。

packetBody '0' = do
bodyLength <- binToInt <$> count 10 binaryDigit
start <- getOffset
let checkOffset = do
new <- getOffset
if new < start + bodyLength then pure () else empty
SubPackets <$> many (checkOffset *> packet)

这只会检查在读取下一个数据包之前是否还有空间，因此您可能会读取超过预期长度的数据包。为了避免这种情况，您可以在每个数据包之后进行检查，或者您可以在checkOffset中添加一个额外的分支，如果是new > start + bodyLength，则会出现不可恢复的故障(这涉及到不在Identity上使用ParsecT，而是在有自己故障的monad上使用(。