Très simple analyseur sexp

Question

Pour une mission, nous avons dû mettre en œuvre quelque chose comme un analyseur sexp très basique, de sorte que pour l'entrée comme:

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

Il retournerait:

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

Depuis c'était partie d'une plus grande affectation, l'analyseur est seulement donné une entrée valide (parens correspondant & c). Je suis venu avec la solution suivante en 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 

Ce qui peut ne pas être la meilleure solution, mais il fait le travail. Maintenant, je suis intéressé par une solution Haskell idiomatique pour la fonctionnalité de base (ie je me fiche du lexing ou du choix des délimiteurs, en prenant déjà une entrée lexée serait bien), si possible en utilisant seulement "core" haskell, sans extensions ou libs comme parsec.

Notez que cela ne fait PAS partie de la mission, je suis simplement intéressé par la façon de faire Haskell.

Answer 1

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

N'a pas un type valable dans haskell (parce que tous les éléments d'une liste doivent être du même type dans haskell), vous aurez donc besoin de définir vos propres listes imbriquées pour structure de données comme celle-ci :

data NestedList = Value String | Nesting [NestedList] 

maintenant, si vous avez une liste de Tokens où Token est défini comme data Token = LPar | RPar | Symbol String, vous pouvez analyser cela dans un NestedList comme celui-ci:

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

Answer 2

La manière idiomatique dans Haskell serait d'utiliser parsec, pour l'analyse de combinateur.

Il y a beaucoup d'exemples en ligne, y compris,

• This nice answer on SO.
• ou here's another one.

Answer 3

Alors que les analyseurs syntaxiques comme Parsec sont agréables, vous n'avez pas vraiment besoin de toute cette puissance pour ce cas simple. La façon classique d'analyser est d'utiliser le type du Prelude. C'est aussi la façon dont vous donneriez à votre type Sexp une instance Read.

Il est bon d'être au moins un peu familier avec ce style d'analyse syntaxique , car il en existe quelques exemples dans les bibliothèques standard.

est ici une solution simple, dans le style classique:

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 

Notez que le paramètre Int-readsPrec, qui indique généralement la priorité de l'opérateur, ne utilisé ici.