代码之家 › 专栏 › 技术社区 › danlei

非常简单的sexp解析器

haskell parsing ruby

danlei · 技术社区 · 14 年前

对于赋值,我们必须实现一些类似于非常基本的sexp解析器的东西,例如对于输入:

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

它将返回:

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

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解决方案感兴趣(即,我不关心词法转换或分隔符的选择,使用已经词法转换的输入就可以了),如果可能的话,只使用“core”Haskell,而不使用像parsec这样的扩展或lib。

请注意,这不是作业的一部分,我只是对哈斯克尔做事的方式感兴趣。

3 回复 | 直到 14 年前

sepp2k 14 年前

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

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

data NestedList = Value String | Nesting [NestedList]

现在,如果您有一个标记列表,其中标记定义为 data Token = LPar | RPar | Symbol String ,您可以将其解析为嵌套列表,如下所示:

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' [] = ([],[])

Community Michael Schmitz 7 年前

Haskell的惯用方法是 parsec ,用于组合分析。

网上有很多例子,包括,

This nice answer on SO .
或者 here's another one

Yitz 14 年前

虽然像Parsec这样的高级解析器很不错,但您并不需要所有这些功能对于这个简单的例子。经典的解析方法是使用 ReadS 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

Int 参数到 readsPrec , 它通常表示运算符优先级,而不是在这里使用。