parsec使用它来解析parens

Question

例如,如果我想将具有多个带括号的组的字符串解析为包含每个组的字符串列表

"((a b c) a b c)"

成

["((a b c) a b c)","( a b c)"]

我怎么用parsec做到这一点？使用between看起来不错,但似乎不可能用开始和结束值分开.

Answer 1

我使用递归解析器:

data Expr = List [Expr] | Term String

expr :: Parsec String () Expr
expr = recurse <|> terminal

terminal你的原语在哪里,在这种情况下,这些似乎是字符串

 where terminal = Term <$> many1 letter

并且recurse是

       recurse  = List <$>
                  (between `on` char) '(' ')' (expr `sepBy1` char ' ')

现在我们有一个很好的树Expr,我们可以收集

collect r@(List ts) = r : concatMap collect ts
collect _           = []

Answer 2

虽然jozefg的解决方案几乎与我提出的解决方案相同(并且我完全同意他的所有建议),但是有一些小的差异使我认为我应该发布第二个答案:

1. 由于初始示例的预期结果,没有必要将空格分离的部分视为单独的子树.
2. 此外,看到实际计算预期结果的部分(即字符串列表)可能会很有趣.

所以这是我的版本.正如jozefg已经建议的那样,将任务分成几个子任务.那些是:

1. 将字符串解析为代表某种树的代数数据类型.
2. 收集此树的(所需)子树.
3. 把树变成字符串.

关于1,我们首先需要树数据类型

import Text.Parsec
import Text.Parsec.String
import Control.Applicative ((<$>))

data Tree = Leaf String | Node [Tree]

然后是一个可以将字符串解析为此类型值的函数.

parseTree :: Parser Tree
parseTree = node <|> leaf
  where
    node = Node <$> between (char '(') (char ')') (many parseTree)
    leaf = Leaf <$> many1 (noneOf "()")

在我的版本中,我确实将括号之间的孔字符串视为一个Leaf节点(即,我不在白色空格处分割).

现在我们需要收集我们感兴趣的树的子树:

nodes :: Tree -> [Tree]
nodes (Leaf _) = []
nodes t@(Node ts) = t : concatMap nodes ts

最后,s 的Show-instance Tree允许我们将它们变成字符串.

instance Show Tree where
  showsPrec d (Leaf x) = showString x
  showsPrec d (Node xs) = showString "(" . showList xs . showString ")"
    where
      showList [] = id
      showList (x:xs) = shows x . showList xs

然后可以解决原始任务,例如:

parseGroups :: Parser [String]
parseGroups = map show . nodes <$> parseTree

> parseTest parseGroups "((a b c) a b c)"
["((a b c) a b c)","(a b c)"]