parsing - parsec 使用 between 解析括号

Question

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

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

进入

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

我将如何使用秒差来做到这一点？使用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 ' ')

现在我们有一棵漂亮的Exprs 树，我们可以用它来收集它

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-instanceTree允许我们将它们转换为字符串。

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)"]