ruby - 非常简单的 sexp 解析器

Question

对于一项任务，我们必须实现类似非常基本的 sexp 解析器的东西，这样的输入如下:

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

它会返回:

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

因为这是一个更大的任务的一部分，解析器只得到有效的输入(匹配的括号&c)。我在 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 的做事方式感兴趣。

Answer 1

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

在 haskell 中没有有效类型(因为在 haskell 中列表的所有元素都必须是同一类型)，因此您需要为嵌套列表定义自己的数据结构，如下所示:

data NestedList = Value String | Nesting [NestedList]

现在，如果您有一个 Token 列表，其中 Token 被定义为 data Token = LPar |帕尔 | 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' [] = ([],[])