1

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

例如，“abbb z ac y aaa x cba”和“abbb z ac x aaa y cba”应该匹配，但以下不应该：

  • “abbb z ac y aaacba”（原因：没有“x”）
  • “abbb z ac y aaa x cb x a”（原因：重复的“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：我不是在寻找正则表达式解决方案，因为它不适用于我的现实问题。我需要使用解析器。

4

1 回答 1

2

您的代码有几个问题：

首先，它并不完全强制执行 one x，y并且z在字符串中。例如，它将接受xxx\n

其次，效率非常低。考虑xyz1在给定字符串时如何解析aaaaaaaaaz：

  1. 我们先试试p 'x'。这首先解析所有a字符，然后找到一个z. 因为zis not x，所以整个p 'x'解析器失败。

  2. 那我们试试p 'y'。这会重新解析所有a字符，然后z再次找到。因为z不是y整个p 'y'解析器都失败了。

  3. 第三次尝试我们成功了，只是在第三次重新解析所有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和guard是从Control.Monad

于 2016-09-14T16:11:52.007 回答