Besoin d'explication sur le fonctionnement des parseurs

Le problème exposé dans ce sujet a été résolu.

Salut à tous,

j'ai commencé ce matin le tuto Write Yourself a Scheme in 48 Hours, j'en suis actuellement au chapitre 2 et je ne comprends pas le fonctionnement des parsers. Avant tout voici le code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
module Main where
import Text.ParserCombinators.Parsec hiding (spaces)
import System.Environment
import Control.Monad

data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | String String
             | Bool Bool

main :: IO ()
main = do
  (expr:_) <- getArgs
  putStrLn (readExpr expr)

readExpr :: String -> String
readExpr input = case parse parseExpr "lisp" input of
  Left err -> "No match: " ++ show err
  Right val -> "Found value"

parseExpr :: Parser LispVal
parseExpr = parseAtom <|> parseString <|> parseNumber

parseString :: Parser LispVal
parseString = do
  char '"'
  x <- many (noneOf "\"")
  char '"'
  return $ String x

parseAtom :: Parser LispVal
parseAtom = do
  first <- letter <|> symbol
  rest <- many (letter <|> digit <|> symbol)
  let atom = first:rest
  return $ case atom of
    "#t" -> Bool True
    "#f" -> Bool False
    _    -> Atom atom

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

En fait je ne comprends pas comment la fonction parse fait pour parser avec parseExpr alors que parseExpr ne prend pas d'arguments et du coup tout me parait flou et je bloque.

Merci d'avance de votre aide. :)

+1 -0

J'ai pas mal utilisé Parsec, mais ça fait un petit bout de temps que je n'ai pas touché au Haskell, donc j'espère que je ne suis pas trop à côté de la plaque.

L'idée principale, c'est que Parser est une monade. C'est-à-dire qu'à partir d'un état, Parser te donne une valeur et modifie (ou non) cet état. On peut facilement faire le parallel avec la monade IO : getLine ne prends aucun paramètre et pourtant getLine te retourne une valeur (et modifie l'état de l'entrée standard). La monade IO est un peu différente, parce que c'est le runtime Haskell qui l'exécute alors que dans le cas de Parser, c'est la fonction parse qui s'en occupe.

Si tu veux comprendre un peu plus le fonctionnement, il faut regarder un peu plus comment ce genre de monade fonctionne. La monade Parser comme la majorité (toute?) des monades peut se voir comme une fonction. Les opérateurs que tu utilises vont ensuite te permettre de combiner ces fonctions de manière à former un programme (ici, le parser, mais avec IO, c'est un "vrai" programme) qu'il te faudra ensuite exécuter et c'est le rôle de parse.

+0 -0
Banni

Pour donner un exemple similaire, on peut très bien faire une structure de donnée pour stocker des polynômes, les manipuler comme tels, et avec la possibilité de prendre la fonction d'évaluation correspondante.

edit

@Berdes : chaque monade peut se voir avec des « fonctions », oui, on peut regarder du côté des arrows et des catégories de Kleisli.

+1 -0

En fait je ne comprends pas comment la fonction parse fait pour parser avec parseExpr alors que parseExpr ne prend pas d'arguments et du coup tout me parait flou et je bloque.

Indépendamment du fait qu'on donne une interface monadique ou pas à ton parser, ce n'est pas parce que parseExpr n'est pas syntaxiquement explicitement écrit comme une fonction que ce n'en est pas une. L'opérateur <|> prend deux fonctions en paramètre et renvoie une troisième fonction.

Tu peux observer le même comportement sur un exemple plus simple :

1
2
3
4
5
6
plusUn x = x + 1
double x = 2 * x

compose f g = \x -> f (g x)

deuxXPlusUn = compose plusUn double

Syntaxiquement, la fonction deuxXPlusUn n'est pas écrite comme une fonction qui prend un paramètre x et renvoie plusUn (double x), mais on utilise compose pour composer ces deux fonctions. Dans ton cas, c'est la même chose, mais c'est <|> au lieu de compose (pour que ce soit clair : ce n'est pas la même fonction).

+0 -0

Oui j'ai assez bien compris ce principe mais du coup en y réfléchissant je pense que c'est surtout le type Parser qui me pose un problème puisque normalement même si la déclaration de la fonction est implicite la déclaration de type devrait l'expliciter puisque j'ai beau écrire deuxXPlusUn comme tu l'as fait ou ainsi deuxXPlusUn x = x*2 + 1 la déclaration de type sera toujours deuxXPlusUn :: (Num a) => a -> a

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte