Je cherche des interwebs pendant quelques jours, essayant de répondre à mes questions et j'admette enfin la défaite.
On m'a donné une grammaire:
Et on m'a dit d'analyser, d'évaluer et d'imprimer des expressions en utilisant cette grammaire qui prend une chaîne en tant qu'entrée et renvoie une arborescence de syntaxe abstraite lorsque l'entrée est dans le format correct (ce que je peux l'asseonner).
On me dit que je pourrais avoir besoin d'un type de données approprié et que le type de données peut avoir besoin de dériver de certaines autres classes.
suite à un exemple de sortie de Plus plus encore, je devrais envisager d'écrire une fonction Je devrais également faire une méthode PrintExpr pour imprimer le résultat de sorte que ce Je voudrais juste être dirigé dans la bonne direction de l'endroit où je pourrais commencer. J'ai peu de connaissance de Haskell et de FP en général et d'essayer de résoudre cette tâche que j'ai fabriqué une fonction de manutention à chaîne à partir de Java qui m'a fait comprendre que je suis hors de piste. J'aurais peut-être été incertain:
Je me demande comment je devrais parler d'avoir lu et goûté une chaîne d'entrée pour faire une AST. dig :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Int :: = creuser | Fouiller int
Var :: = a | b | ... z | A | B | C | ... | Z de
Expr :: = int | - Expr | + EXPR Expr | * Expr expr | Var | Laissez Var = Expr dans EXPR
où les opérateurs * + - ont leur sens normal
La tâche spécifique consiste à écrire une fonction parse :: string -> ast
data ast = feuille int | Somme Ast Ast | MIN AST | ...
Jetons :: String -> [String]
Pour diviser la chaîne d'entrée dans une liste de jetons
L'analyse doit être accomplie avec
ast :: [string] -> (ast, [string])
Lorsque l'entrée est une liste des jetons et génère une AST et pour analyser les sous-expressions, je devrais simplement utiliser la fonction AST récursivement.
printe: ast -> chaîne
print (parse "* 5 5") donne soit des rendements "5 * 5" ou "(5 * 5)"
et aussi une fonction pour évaluer l'expression
Evali :: AST -> INT
Donc, un petit pointeur dans la bonne direction, et peut-être une explication à «Comment» l'Ast devrait ressembler à ce que
Troisième jour de suite et toujours pas de code de course, j'apprécie vraiment toute tentative de m'aider à trouver une solution!
Merci d'avance!
édition
3 Réponses :
Pour commencer avec Haskell lui-même, je recommanderais Apprenez-vous un haskell pour super bien! , un très Guide bien écrit et divertissant. World Haskell réel est un autre point de départ recommandé de TTT.
Edit: une introduction plus fondamentale à l'analyse est < Un href = "http://roman-dushkin.narod.ru/files/fp__jroen_fokker_001.pdf" rel = "nofollow"> analyseurs fonctionnels . Je voulais comment remplacer une échec par une liste de succès par Philip Wadler. Malheureusement, cela ne semble pas être disponible en ligne. Pour commencer à analyser à Haskell, je pense que vous devriez d'abord lire analysant monadique à Haskell , alors peut-être Cet exemple Wikibook , mais aussi alors le Guide PERSEC . < p> Votre grammaire suggère quelques types de données abstraites: ceci est intrinsèquement un arbre de syntaxe défini de manière récursive, pas besoin de en faire un autre.
Désolé pour le clunky (personnellement, je voudrais convertir le une fois que vous avez effectué avec les basiques - Donc tout le temps, votre code HASKELL est propre et ressemble étroitement la grammaire que vous avez donnée. dig _ et INTEG _ Stuff - ils doivent commencer par une majuscule. INTEG s à int s tout droit, alors auriez effectué newtType INTEG = INTEG INT et aurait probablement effectué nouveautype var = var char mais cela pourrait ne pas vous convenir.) dig et var et Neg _ , plus _ , in _ etcI'd go avec l'interface applicative pour les construire, donc par exemple votre analyse expr pour expr serait quelque chose comme
Merci pour votre réponse, je vais vérifier et revenir à vous. Je ne pense pas que je suis censé utiliser Parsec, cependant.
OK, il semble donc que vous essayiez de construire des lots et beaucoup de choses, et vous n'êtes pas vraiment sûr où tout cela va. Je suggérerais d'obtenir la définition de Le marmmer que vous avez énuméré est intéressant .. . Vous semblez vouloir entrer Quoi qu'il en soit, faisant des hypothèses sur ce que vous vouliez dire, votre Ast va regarder quelque chose comme ceci: P> ast code> à droite, puis d'essayer d'implémenter évalui code> serait un bon début. * 5 5 code>, mais la sortie 5 * 5 code>, Whique est un choix étrange. Est-ce vraiment censé être un minimum unaire, pas binaire? Simlarly, * EXPR EXPR Var code> On dirait peut-être que vous auriez peut-être censé taper * expr expr | Var Code> ... P> evali :: AST -> Int
evali ast = evaluate Data.Map.empty ast
evaluate :: Map String Int -> AST -> Int
evaluate m ast =
case ast of
...same as before...
Let var ast1 ast2 -> evaluate (Data.Map.insert var (evaluate m ast1)) ast2
Var var -> m ! var
Merci! C'était très utile! Je pourrais avoir d'autres questions concernant l'analyse d'une chaîne dans une AST, mais pour l'instant, je suis profondément reconnaissant!
Les questions bien formées sont toujours les bienvenues. Je sais que ça peut être un peu difficile quand tu es comme "l'enfer, je ne sais même pas exactement ce que j'essaie de faire". J'espère que la tâche devient plus claire pour vous, vous serez capable de localiser exactement ce que vous avez besoin d'aide pour mieux.
Cette fonction de cartographie était brillante!
OK, prenons votre grammaire p> C'est une belle grammaire facile, car vous pouvez dire au premier jeton quoi sorte de contraction ce sera.
(S'il y avait quelque chose de plus compliqué, comme ayons une certaine échantillon d'entrée brute : p> que je comprends à partir de la grammaire représente qui convient à la grammaire, mais vous pourriez bien avoir p> qui correspond à votre échantillon avec p> J'ai nommé les bits d'un e_let code> Pour que cela soit plus clair ce qu'ils représentent. P> Vous pouvez utiliser yikes! Trop de laissez des clauses obscurcir le sens,
Et nous allons écrire le même code pour La manière standard de traiter avec ceci est d'écrire des combinaisons;
au lieu de firmer la filetage de l'entrée Nous devons d'abord définir mais vraiment ce serait mieux si je faisais p> afin que je puisse faire + code> entre les chiffres ou - code> utilisé pour la soustraction comme
ainsi que la négation, vous auriez besoin du tour de la liste de succès, expliqué dans
analgésiques fonctionnels .) P> "(- 6 (+ 45 (let x = -5 in (* xx)))" code>,
et je vais supposer que vous l'ayez hotté comme p> ast code> mieux. Je pense que c'est une bonne pratique de nommer votre ast après des morceaux de votre grammaire,
Donc, je vais aller de l'avant et remplacer p> écrire une fonction d'analyse h2>
isdigit code> en ajoutant Data.char (isdigit) code> pour aider: p> e_prod code> et très pire pour e_let code>.
Faisons ce genre! p> [string] code> S dans notre définition, définissez les moyens de
mess avec la sortie des analyseurs (carte) et combiner
Plusieurs analyses dans un (ascenseur). P> Nettoyez le code 1: Carte h2>
PMAP code>, notre propre équivalent du Carte Code> Fonction afin que nous puissions faire PMAP e_neg (EXPR1 SS) code>
au lieu de let (e, ss ') = expr1 ss in (e_neg e, ss') code> p> expr (s:ss) | s == "let" = E_Let <$> var *> equals_ <*> expr <*> in_ *> expr
C'est parfait! Merci beaucoup!!
Il semble que vous ayez besoin de lire des asts, puis de lire un didacticiel Haskell, puis de poster une question réelle si vous êtes toujours bloqué.
Merci pour votre réponse. J'ai lu sur Haskell et plusieurs tutoriels, y compris une analyse fiscale. Je ne voudrais pas demander si je n'avais pas. Ce que je ne comprends pas, c'est comment commencer à écrire une fonction qui renvoie un AST, mon livre 'Programming in Haskell' ne le mentionne pas.