很简单SEXP解析器

对于一个任务，我们必须实现像一个非常基本的SEXP解析器，这样对于输入，如：很简单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解决方案感兴趣（即，我不在乎分隔符的选择或松散，如果可能的话只使用“核心” haskell，没有扩展名或像parsec这样的库。

请注意，这不是任务的一部分，我只是对Haskell做事感兴趣。

来源

2010-06-27 danlei

惯用的解决方案是使用解析器库（combinator或其他）。既然你明确排除了这个选项，一个惯用的解决方案是不可能的。编程是关于重用，而不是重新创建。 – jrockway 2010-06-29 04:41:37

当然，如果这是一个现实世界的问题，那么你是绝对正确的。但是考虑到所有教授haskell的书籍，为了学习的目的，Prelude功能正在被重新实现。你会不同意有一些解决方案比其他地方更习惯？是的，编程是关于重用，但学习有时可能会重塑。 – danlei 2010-06-29 10:18:07

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

不具有哈斯克尔有效的类型（因为列表中的所有元素必须在Haskell相同类型的），所以你需要定义自己的数据结构像这样嵌套列表：

data NestedList = Value String | Nesting [NestedList]

现在，如果你有其中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' [] = ([],[])

来源

2010-06-27 19:08:52 sepp2k

谢谢，这正是我所寻找的例子。 – danlei 2010-06-27 19:28:49

Haskell的惯用方法是使用parsec进行组合器解析。

有很多在线的例子，包括

This nice answer on SO。
或here's another one。

来源

2010-06-27 18:41:07

谢谢，唐，为了快速回复，我应该补充说我对一个不涉及像parsec这样的库的解决方案感兴趣。我将相应地编辑问题，并查看链接的答案。 – danlei 2010-06-27 18:45:21

虽然像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

注意，Int参数readsPrec，这通常表示运算符优先级，不这里使用。

来源

2010-06-28 17:24:39 Yitz

很简单SEXP解析器

回答

相关问题