ruby – 非常简单的sexp解析器

发布时间：2020-12-17 01:44:22 所属栏目：百科来源：网络整理

导读：对于一个赋值,我们必须实现像一个非常基本的sexp解析器,这样的输入,如： "((a b) ((c d) e) f)" 它将返回： [["a","b"],[["c","d"],"e"],"f"] 由于这是较大任务的一部分,因此解析器仅被赋予有效输入(匹配的parens c).我在Ruby中提出了以下解决方案： def par

对于一个赋值,我们必须实现像一个非常基本的sexp解析器,这样的输入,如：

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

它将返回：

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

由于这是较大任务的一部分,因此解析器仅被赋予有效输入(匹配的parens& 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解决方案的核心功能感兴趣(即我不关心lexing或选择分隔符,考虑已经lexed输入会很好),如果可能只使用“核心”haskell,没有扩展或者像parsec这样的库.

请注意,这不是赋值的一部分,我只是对Haskell的处理方式感兴趣.

解决方法

[["a","f"]

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

data NestedList = Value String | Nesting [NestedList]

现在,如果你有令牌列表,其中Token被定义为数据Token = LPar | RPar |符号字符串,您可以将其解析为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' [] = ([],[])

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!