解析器：在不知道顺序时强制执行唯一性

Question

使用 Attoparsec，我试图匹配恰好包含 1 'x'、1 'y' 和 1 'z' 以及任意数量的 'a'、'b'，或'c'，对每个字符的顺序没有任何限制。

例如，"abbbzacyaaaxcba" 和 "abbbzacxaaaycba" 应该匹配，但以下不应该匹配：

"abbbzacyaaacba"（原因：没有'x'）
"abbbzacyaaaxcbxa"（原因：重复'x'）

到目前为止我能做的最好的是：

import qualified Data.Attoparsec.ByteString.Char8 as A8
import qualified Data.ByteString.Char8 as B8 (pack)

p ch = do
    abcs <- A8.many' (A8.choice [A8.char 'a', A8.char 'b', A8.char 'c'])
    x    <- A8.char ch
    return $ concat [[x],abcs]

parse = do
    xyz1 <- A8.choice [p 'x', p 'y', p 'z']
    xyz2 <- A8.choice [p 'x', p 'y', p 'z']
    xyz3 <- A8.choice [p 'x', p 'y', p 'z']
    final <- A8.manyTill (A8.choice [A8.char 'a', A8.char 'b', A8.char 'c']) $ A8.char '\n'
    return (xyz1, xyz2, xyz3, final)

（随意的，我选择用'\n'停止解析，但那只是为了挑一个简单的例子）

然后在 ghci 中尝试：

Prelude> A8.parseTest parse $ B8.pack "abbbzacyaaaxcba\n"
Done "" ("zabbb","yac","xaaa", "cba")
Prelude> A8.parseTest parse $ B8.pack "abbbzacyaaacba\n"
Fail "aaacba\n" [] "Failed reading: empty"
Prelude> A8.parseTest parse $ B8.pack "abbbzacyaaaxcbxa\n"
Fail "xa\n" [] "Failed reading: empty"

但它看起来很笨重，而且它不能轻易扩展到唯一字符列表（例如，我得到一个没有重复的 givenchars :: [Char] 列表，我想匹配由所有 givenchars 组成的任何字符串以及其间的任何 'a'、'b'、'c'，顺序不限）。

是否有更好、更优雅且可扩展的方法来做到这一点？

PS：我不是在寻找正则表达式解决方案，因为它不适用于我的现实生活问题。我需要使用解析器。

Answer 1

您的代码有几个问题：

首先，它不会在字符串中强制执行 x、y 和 z。例如，它将接受 xxx\n

其次，效率很低。考虑给定字符串 aaaaaaaaaz:

时如何解析 xyz1

我们先试试p 'x'。首先解析所有 a 个字符，然后找到一个 z。由于 z 不是 x，整个 p 'x' 解析器失败。
那我们试试p 'y'。这将重新解析所有 a 字符，然后再次找到 z。由于 z 不是 y 整个 p 'y' 解析器失败。
第三次尝试我们成功了，只有在第三次重新解析所有 a 个字符之后。

最好这样写：

parse = do
   s <- A8.takeWhile (\x -> elem x "abcxyz")
   let xs = count 'x' s
       ys = count 'y' s
       zs = count 'z' s
   guard $ xs == 1 && ys == 1 && zs == 1
   return s

函数count来自Data.ByteString.Char8 and guard is from Control.Monad

解析器：在不知道顺序时强制执行唯一性

Parser: Enforcing unicity when order is not known

haskell

attoparsec