Analyser dans Haskell pour un interprète simple

Question

Je suis relativement nouveau à Haskell avec l'arrière-plan principal de programmation venant des langues d'OO. J'essaie d'écrire un interpréteur avec un analyseur pour un langage de programmation simple. Jusqu'à présent, j'ai l'interprète dans un état dont je suis raisonnablement content, mais je me bats un peu avec l'analyseur.

Voici le morceau de code que je rencontre des problèmes avec

data IntExp 
= IVar Var 
| ICon Int 
| Add IntExp IntExp 
deriving (Read, Show) 

whitespace = many1 (char ' ') 

parseICon :: Parser IntExp 
parseICon = 
    do x <- many (digit) 
    return (ICon (read x :: Int)) 

parseIVar :: Parser IntExp 
parseIVar = 
    do x <- many (letter) 
    prime <- string "'" <|> string "" 
    return (IVar (x ++ prime)) 

parseIntExp :: Parser IntExp 
parseIntExp = 
    do x <- try(parseICon)<|>try(parseIVar)<|>parseAdd 
    return x 

parseAdd :: Parser IntExp 
parseAdd = 
    do x <- parseIntExp 
    whitespace 
    string "+" 
    whitespace 
    y <- parseIntExp 
    return (Add x y) 

runP :: Show a => Parser a -> String -> IO() 
runP p input 
    = case parse p "" input of 
     Left err -> 
     do putStr "parse error at " 
      print err 
     Right x -> print x 

La langue est un peu plus complexe, mais cela suffit pour montrer mon problème. Donc dans le type IntExp ICon est une constante et IVar est une variable, mais maintenant sur le problème. Cet exemple fonctionne avec succès

RUNP parseAdd "5 + 5"

qui donne (Ajouter (ICon 5) (5 ICon)), qui est le résultat attendu. Le problème se pose lors de l'utilisation Ivars plutôt que, par exemple ICÔNES

RUNP parseAdd « n + m »

Cela provoque le programme d'erreur en disant qu'il y avait un inattendu « n », où un chiffre était attendu. Cela m'amène à croire que parseIntExp ne fonctionne pas comme prévu. Mon intention était qu'elle essaye d'analyser un ICon, si cela échoue alors essayez d'analyser un IVar et ainsi de suite. Donc, soit je pense que le problème existe dans parseIntExp, ou qu'il me manque quelque chose dans parseIVar et parseICon.

J'espère avoir donné assez d'informations sur mon problème et j'ai été assez clair.

Merci pour toute aide que vous pouvez me donner!

Answer 1

Votre problème est en fait dans parseICon:

parseICon = 
    do x <- many (digit) 
    return (ICon (read x :: Int)) 

Le many Combinator correspond zéro ou plusieurs occurrences, il est donc réussir sur « m » correspondant à zéro en chiffres, puis mourir probablement quand read échoue.

---

Et pendant que je suis, puisque vous êtes nouveau à Haskell, voici quelques conseils non sollicités:

• Ne pas utiliser entre parenthèses parasites. many (digit) devrait simplement être many digit. Les parenthèses ici regroupent simplement les choses, elles ne sont pas nécessaires pour l'application des fonctions.

• Vous n'avez pas besoin de faire ICon (read x :: Int). Le constructeur de données ICon ne peut prendre qu'un Int, de sorte que le compilateur peut comprendre ce que vous vouliez dire par lui-même. Vous n'avez pas besoin de try autour des deux premières options dans parseIntExp en l'état - il n'y a pas d'entrée qui aurait pour résultat que l'un consomme une entrée avant d'échouer. Ils échoueront immédiatement (ce qui n'a pas besoin de try) ou ils réussiront après avoir fait correspondre un seul caractère.

• Il est généralement préférable de marquer d'abord avant l'analyse syntaxique. Traiter les espaces en même temps que la syntaxe est un casse-tête.

• Il est courant dans Haskell d'utiliser l'opérateur ($) pour éviter les parenthèses. C'est juste l'application de la fonction, mais avec une préséance très faible, de sorte que quelque chose comme many1 (char ' ') peut être écrit many1 $ char ' '.

En outre, faire ce genre de chose est redondant et inutile:

parseICon :: Parser IntExp 
parseICon = 
    do x <- many digit 
    return (ICon (read x)) 

Quand tout ce que vous faites est l'application d'une fonction régulière au résultat d'un analyseur, vous pouvez simplement utiliser fmap:

parseICon :: Parser IntExp 
parseICon = fmap (ICon . read) (many digit) 

Ce sont exactement la même chose. Vous pouvez rendre les choses encore plus belles si vous importez le module Control.Applicative, qui vous donne une version opérateur de fmap, appelée (<$>), ainsi qu'un autre opérateur (<*>) qui vous permet de faire la même chose avec des fonctions d'arguments multiples. Il y a aussi les opérateurs (<*) et (*>) qui rejettent respectivement les valeurs de droite ou de gauche, ce qui dans ce cas vous permet d'analyser quelque chose tout en rejetant le résultat, par exemple, les espaces et autres.

est ici une version légèrement modifiée de votre code avec quelques-unes des suggestions ci-dessus appliquées et d'autres tweaks stylistiques mineures:

whitespace = many1 $ char ' ' 

parseICon :: Parser IntExp 
parseICon = ICon . read <$> many1 digit 

parseIVar :: Parser IntExp 
parseIVar = IVar <$> parseVarName 

parseVarName :: Parser String 
parseVarName = (++) <$> many1 letter <*> parsePrime 

parsePrime :: Parser String 
parsePrime = option "" $ string "'" 

parseIntExp :: Parser IntExp 
parseIntExp = parseICon <|> parseIVar <|> parseAdd 

parsePlusWithSpaces :: Parser() 
parsePlusWithSpaces = whitespace *> string "+" *> whitespace *> pure() 

parseAdd :: Parser IntExp 
parseAdd = Add <$> parseIntExp <* parsePlusWithSpaces <*> parseIntExp 

Answer 2

Je suis aussi nouveau à Haskell, me demandais:

sera parseIntExp jamais le faire pour parser?

Il semble que ICon ou IVar seront toujours analysés avant d'atteindre 'parseAdd'.

par exemple. RUNP parseIntExp "3 + m"

tenteraient parseICon, et réussir, donnant

(ICon 3) au lieu de (Ajouter (ICon 3) (Ivar m))

Désolé si je suis stupide ici, je suis juste incertain.