很簡單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解析器

回答

相關問題