非常简单的S表达式解析器

Question

作为一项任务，我们需要实现类似于非常基本的Sexp解析器，以便处理以下输入：

"((a b) ((c d) e) f)"

它将返回：

[["a", "b"], [["c", "d"], "e"], "f"]

由于这是一个更大任务的一部分，解析器只提供有效输入(匹配括号等)。我用Ruby想出了以下解决方案：

def parse s, start, stop
  tokens = s.scan(/#{Regexp.escape(start)}|#{Regexp.escape(stop)}|\w+/)

  stack = [[]]

  tokens.each do |tok|
    case tok
    when start
      stack << []
    when stop
      stack[-2] << stack.pop
    else
      stack[-1] << tok
    end
  end

  return stack[-1][-1]
end

这可能不是最好的解决方案，但它能胜任工作。

现在，我对一种习惯用语的Haskell解决方案感兴趣（即，我不关心词法分析或分隔符的选择，采用已经分析过的输入将是可以接受的），如果可能的话只使用“核心”haskell，而不使用像parsec这样的扩展或库。

请注意，这不是任务的一部分，我只是对Haskell处理事情的方式感兴趣。

- danlei

---

惯用的解决方案是使用解析器库（组合器或其他）。由于您明确排除了该选项，因此惯用的解决方案是不可能的。编程是关于重用，而不是重新发明。 - jrockway

当然，如果这是一个真实的世界问题，你绝对是正确的。但是请考虑所有教授Haskell的书籍，在学习目的下，Prelude函数被重新实现。您不认为有些解决方案比其他解决方案更符合惯用法吗？是的，编程是关于重用，但学习有时也是关于重新发明。 - danlei

Answer 1

[["a", "b"], [["c", "d"], "e"], "f"]

在Haskell中，由于列表的所有元素都需要是相同的类型，因此嵌套列表没有有效的类型。因此，您需要为这样的嵌套列表定义自己的数据结构：

data NestedList = Value String | Nesting [NestedList]

如果您有一个Token列表，其中Token被定义为data Token = LPar | RPar | Symbol String，您可以按照以下方式将其解析为NestedList：

parse = fst . parse'

parse' (LPar : tokens) =
    let (inner, rest) = parse' tokens
        (next, outer) = parse' rest
    in
      (Nesting inner : next, outer)
parse' (RPar : tokens) = ([], tokens)
parse' ((Symbol str) : tokens) =
    let (next, outer) = parse' tokens in
    (Value str : next, outer)
parse' [] = ([],[])

- sepp2k

---

谢谢，这正是我在寻找的那种示例。 - danlei

Answer 2

在Haskell中，惯用的方法是使用组合子解析器parsec。

网上有很多例子，包括：

• 这个不错的SO答案。
• 或者这里还有一个。

- Don Stewart

---

谢谢Don的快速回复，我应该补充说明我对不涉及parsec等库的解决方案感兴趣。我会相应地编辑问题，并查看链接的答案。 - danlei

Answer 3

虽然像Parsec这样的高级解析器很好，但对于这种简单情况，你并不真正需要所有这些功能。解析的经典方式是使用Prelude中的ReadS类型。这也是您为Sexp类型提供Read实例的方式。

最好至少有一点熟悉这种解析风格，因为标准库中有相当多的示例。

以下是一种简单的解决方案，采用经典风格：

import Data.Char (isSpace)

data Sexp = Atom String | List [Sexp]
  deriving (Eq, Ord)

instance Show Sexp where
  show (Atom a ) = a
  show (List es) = '(' : unwords (map show es) ++ ")"

instance Read Sexp where
  readsPrec n (c:cs) | isSpace c = readsPrec n cs
  readsPrec n ('(':cs)           = [(List es, cs') |
                                      (es, cs') <- readMany n cs]
  readsPrec _ (')':_)            = error "Sexp: unmatched parens"
  readsPrec _ cs                 = let (a, cs') = span isAtomChar cs
                                   in [(Atom a, cs')]

readMany :: Int -> ReadS [Sexp]
readMany _ (')':cs) = [([], cs)]
readMany n cs       = [(e : es, cs'') | (e, cs') <- readsPrec n cs,
                                        (es, cs'') <- readMany n cs']

isAtomChar :: Char -> Bool
isAtomChar '(' = False
isAtomChar ')' = False
isAtomChar c   = not $ isSpace c

请注意，readsPrec函数中的Int参数通常用于表示运算符优先级，在此处没有被使用。

- Yitz